Week 13 Day 1 - Hash Tables
1Today we went over two types of hash tables:
1) Linear Probing
2) Chaining (with BSTs)
I went through the theory on how they worked, and talked a bit about the code you'll write in class. The next class will go over a better way of doing it than the basic way shown here.
After that we talked about benchmarking code. Benchmarking is really important in computer science (it's the science in computer science) and is ultimately the only way to answer the question of if your code will run faster one way versus another. For a lot of complicated questions about performance in computer science, an experienced person will answer, "Benchmark the code and find out." We did a lot of this in grad school, exploring which techniques in computer science yielded faster run times.
While you could run the hundreds of test cases by hand, a much much better way is to use a shell script to feed a set of input files into your program, so I went over how timing_script.sh (an example timing script using shell scripting) worked, and also how to make input files to begin with using the generator.cc file which you can modify to your heart's content.
As with all things, the more UNIX knowledge you have the better off your life will be.