The in-class part of the second test for this class will take place on Friday, April 12. The take-home part of the test will be handed out at that time.
The test will concentrate on material that we have covered since the first test. This includes topics from Chapters 4, 5, 6, 7, and 8, but we certainly didn't cover those chapters in their entirety. See the list of topics below. From the first part of the course, you still need to remember run-time and space efficiencies including how to work with Big-Theta, Big-Oh, and Big-Omega. Aside from that, material from the first part of the course will only be covered to the extent that newer material builds on it.
Here is a list of some of the things that you should know about:
be able to explain general principles/ideas of algorithmic patterns we have covered:
decrease-and-conquer
divide-and-conquer
transform-and-conquer
dynamic programming
be able to apply certain algorithms by hand to specific instances of the problem:
topological sort of a directed acyclic graph
Lomuto and Hoare partitioning
inserting items into and searching a 2-3 tree
insertion and deletion in a heap, represented as a binary tree
insertion, deletion, and search in an open hash table
insertion, deletion, and search in a closed hash table using linear probing
find a solution by dynamic programming, given the algorithm's code and formulas
understand certain algorithms and data structures well enough to explain them:
the source-removal algorithm for topological sort
generating all the subsets of a given set
quickselect, for finding the k-th order statistic of an array
quicksort, for sorting an array
big-integer multiplication
the efficient algorithm for finding the closest pair of points
using presorting to efficiently test for element uniqueness in an array
using presorting to efficiently find the intersection of two sets
2-3 trees
heaps, represented as binary tree and represented as array
priority queues, implemented using heaps
heapsort, for sorting an array
hash tables
B-Trees
Floyd's all-pairs shortest path algorithm
NOTE: You should know the run-time and/or space efficiency of many of these
NOTE: For the simpler algorithms, you might be asked to write code or pseudocode
some other terms and ideas:
using recursion for divide-and-conquer algorithms
databases, relational databases
indexing in databases
hash functions
load factor of a hash table
clustering in a closed hash table
how dynamic programming relates to divide-and-conquer
the role of "subproblems" in dynamic programs
the edit distance problem (from dynamic programming)
the longest common subsequence problem (from dynamic programming)