Information on the Second Test

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 formulasunderstand 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)