Exam will be comprehensive so you MUST study earlier material again (in particular review previous study guides). However, the exam will focus most heavily on material covered since Test 2. Not sure right now the exact percentage split, but assume 60-70% of questions will be on reading and materials covered since Test 2. This handout documents only that material! As always, if I wrote it on the board you are likely to see it again.

Review resources
• Handouts / class notes: binary files, direct access C++ code.
• Assigned Readings since Test 2:hashing techniques, heaps and binary files, graphs
• Programming assignments
• Terminology, discussion points, advantages/disadvantages, average/best/worst cases, and practical applications.

Terms to be definedor explain/discuss/give examples of: Greedy algorithm (like Kruskal'sor Prim's for finding Minimum Spanning Tree or Stable Marriage Algorithm), divide and conquer algorithms (like quick sort and merge sort that use recursion), text files versus binary files (pros and cons of each), sequential access, direct (random) access,hash table packing factor, hash function, collisions, mid-square hashing function, hashing function based on folding, secondary hashing, priority queue (and operations on it), complete tree, heap, heap operations[be able to pseudo code add/remove an item to/from a max/min heap], possible implementations of a priority queue, possible implementations of a heap (one via an array based tree technique with children/parent addresses computable), collision resolution mechanisms [linear probing, quadratic probing], tombstones, chaining with separate lists, complexity classes associated with various search/add/delete operations on a wide variety of data structures, b-trees in particular: contents? How to add/remove an item for a b-tree?, graphs, vertices (nodes), edges, directed graphs, acyclic graphs, DAGs, weighted graphs, possible representations for a graph (adjacency matrix and adjacency lists) - how would operations of various kinds on graphs be "achieved" on each of the two main representations? - for example, for each possible representation how would we find all of the nodes adjacent to a particular node?Depth first and breadth first traversal/searches from a given starting node (definition and algorithm). How would these differ depending on which representation of a graph you were using?

Specific algorithms to know: heap sort, breadth and depth first traversal/search algorithms, shortest path algorithm from source to destination (unweighted graphs - based on using a breadth first traversal), Dijkstra's shortest path algorithm (weighted graphs - this uses a priority queue), Prim's and Kruskal'sminimum spanning tree algorithms[greedy algorithms]. And of course algorithms to add/delete from linked lists and BSTs - algorithms to traverse both of those and do/count/observe something at each node in the structure - use of recursion to process BSTs.Merge Sort vs Quick Sort vs Heap sort.

C++: templates, char arrays and their null terminated representation, sizeof operator, seekp, seekg, read and write operations for binary file operations, eof() function, proper opening and closing of files with different arguments, code to process a linked list or a BST.

General Data Structures: given a set of conditions, tell which DS to use, and state why using Big O Notation.