The final exam is scheduled for **Monday, December 16, from 2:15 to 4:15 in
Room 321, CB**

Note that this is an open notes/book exam.

Since this is a 2 hour long exam, it will be more in-depth as compared to Exams 1 and 2. The problems on the exam will involve (i) answering questions about small code fragments that are given or (ii) writing small code fragments to perform a specific task. You will not be asked to write large functions or entire classes.

The exam is *comprehensive*, but it will focus more on material
covered after Exam 2.
This material includes:

- Recursion (Chapter 9)
- Running Time Analysis (Section 1.2)
- Heaps and Priority Queues (Section 11.1)
- Representation of Binary Trees (Section 10.1-10.2)
- Tree traversals (Section 10.4)
- Binary Search Trees (Section 10.5)
- AVL trees (See links to notes on course page)
- Biconnectivity (Project 3 handout and class lectures)
- Hamiltonian Cycles (Project 3 handout and class lectures)
- Search with backtracking and pruning (Project 3 handout and class lectures).

Here are some specific questions that might help you study for the exam. Please do NOT expect the exam to test you just on these problems, these are merely questions to get you started thinking.

**Recursion:**(a) Write a recursive function that takes the root of a binary and determines if it is a binary search tree or not. (b) Write a recursive function that takes the root of a binary tree and determines the height of the tree.

**Running Time Analysis:**(a) Review the Big-Oh notation, arithmetic series, and geometric series. (b) Review examples of nested loops and their analysis.

**Heaps and Priority Queues:**(a) We can define a ternary heap as one in which each node has at most three children. Extend the array representation of binary heaps to ternary heaps. In particular, if a node is stored in slot i, where might its children be stored. Where might its parent be stored? (b) Implement the insertion and deletion operations for ternary heaps.

**Tree traversals:**(a) Suppose we want to represent trees in which each node can have an arbitrarily many children. For such a tree we could use the following representation: each node has two pointers: (i) a firstChild pointer and (ii) a sibling pointer. Given a tree in which nodes have lots of children, show how this representation works. (b) Show how a tree represented in this manner can be traversed.

**Binary Search Trees:**(a) Show how deletion from a binary search tree works. The three cases to pay attention to are: Case 1: node to be deleted has no children Case 2: node to be deleted has exactly on child Case 3: node to be deleted has two children Cases 1 and 2 are very simple. In Case 3, we replace the node to be deleted by the largest node in the left subtree.

**AVL trees:**(a) Show binary search trees that are AVL and those that are not. (b) Show examples of insertion operations that leads to each of the following rotations: (i) single left rotation (ii) single right rotation (iii) double left rotation and (iv) double right rotation.

**Biconectivity and Hamiltonian Cycles:**(a) Given an example of a graph that is biconnected, but not Hamiltonian (b) Show an example of the working of the dfs-based algorithm that computed low numbers and uses these to detect cutpoints.

**Search with backtracking and Pruning:**(a) The Eight Queens Problem is the following: place eight queens on a chessboard so that no queen is threatened by any other queen. A solution that is similar to your solution to Project 3 (using search with backtracking and possibly pruning) will work for this problem.