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:

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
  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
  7. Biconectivity and Hamiltonian Cycles:
    	(a) Given an example of a graph that is biconnected, but not 
    	(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