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.
   

   ---