Topics Covered Through Exam 2
Note: This exam is not cumulative. However, topics covered on this exam may require knowledge of concepts learned earlier in the course. For example, you can't get away from recursion!
C++:
constructors [11.3, C++ book]
destructors [p. 499, C++ book]
Anything from Project 1
UNIX:
Required Reading: Automatic Compilation with make (class handout)
makefiles (class handout)
changing permissions (class notes)
Open Source controversy
Data Structures and Algorithms:
Required Reading: 5.6 (Extendible Hashing), 6.4 (Applications of Priority Queues)
Optional Reading: Ch. 5, 6, 8
Anything from Project 1
BST implementation
Hashing: [Ch. 5]
motivation, terminology [5.1]
examples of hash functions (you don't need to memorize those in the book) [5.2]
separate chaining [5.3]
open addressing (linear and quadratic probing, how to remove() ) [5.4]
tradeoffs between separate chaining and open addressing [class notes]
rehashing [5.5]
extendible hashing [5.6]
examples of when you use hashing [class notes]
tradeoffs between hash tables and other data structures [your brain]
Heaps: [Ch. 6]
motivation, terminology, operations [6.1]
implementations [6.2]
binary heaps (structure and heap-order property) [6.3]
implementing heap operations (percolate up and percolate down) [6.3.3]
other heap operations [6.3.4]
applications of priority queues [6.4]
Disjoint Sets: [Ch. 8]
equivalence relations, terminology, definitions [8.1]
The Dynamic Equivalence Problem [8.2]
Various Implementation [8.2 - 8.3]