22C:30, 22C:115 Review for Final Exam

The final exam is scheduled for Wednesday, Decenmber 17th, from 9:45 to 11:45 in Room 321, CB

Given below is a detailed list of topics that you should study for the final Exam. The problems on the exam will involve (i) answering questions about small code fragments that are given and (ii) writing small code fragments to perform a specific task. You will not be asked to write large functions or entire classes.

To prepare for the exam read (i) lecture notes and notes from discussion sections, (ii) code posted on the course webpages (including the solutions to Project 2 and Homework 3, Homework 3 extra credit, etc.) and (iii) the following material from the textbook: Chapter 3 (on running time analysis), Sections 2.5 and 4.1 (on recursion), Chapter 6 (on trees and tree traversals), Sections 7.1, 7.2, and 7.3 (on priority queues and heaps), Sections 9.1 and 9.2 (on binary search trees and AVL trees), Sections 10.1 amd 10.3 (on Quick sort and Merge sort), and Sections 12.2 and 12.3 (graph representation and DFS, BFS). In general, focus on material that relates to what was discussed in class and in the discussion sections.

As should be clear from the above list of topics, the primary focus of the exam will be material covered after the second mid-term. However, you should also review a few topics from prior to the second mid-term; these are recursion, graphs, BFS, DFS, and sorting algorithms,

• Recursion: How recursion is used to implement divide-and-conquer algorithms; how recursion is used in algorithms that use search with backtracking; how recursion is implemented in most high level langauges using stacks of activation records. Interesting examples of recursive functions such as: merge sort, quick sort, depth-first search, tree traversals, etc.

• Running Time Analysis: The "Big Oh" notation; worst case vs best case vs average case running time; useful sums (arithmetic series and geometric series); examples of analysis involving nested loops, recursive functions, etc.

• Binary Trees: Representing trees; the three tree traversal algorithms (pre-order, in-order, and post-order); height and depth of trees.

• Binary Search Trees: Definition; implementing search, insert, and delete on binary search trees; worst case running time of these algorithms.

• AVL Trees: Definition; implementing search, insert, and delete on AVL trees; the single rotation and the double rotation operation.

• Priority Queues and Binary Heaps: What is the priority queue ADT? How is this ADT implemented using a binary heap? on the operations min, insert, and delete on heaps; analysis of the worst case running time of these operations.

• Graph traversals: How graph traversals such as depth-first-search and breadth-first-search work; what the difference between the two traversals is.