# 22C:30, 22C:115 Review Questions for the Final Exam

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.

1. 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.
```
2. Running Time Analysis:
```	(a) Review the Big-Oh notation, arithmetic series, and geometric series.

(b) Review examples of nested loops and their analysis.
```
3. 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.
```
4. 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.
```
5. 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.
```
6. 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.
```
7. 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.
```
8. 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.
```