Question 0 (worth 2^0 points): What is the best case run time for Shell Sort with a gapSize sequence from n/2 to 1, stepping by a factor of 2.2? Why?

Answer 0: nlog_2.2(n) = O(nlog(n)). See part B of problems 8.4, 8.5, and 8.6 from Homework 4 for an explanation.



Question 1 (worth 2^1 points): What is required to get Quick Sort to run in nlog(n) (and not n^2) time on an array of all the same numbers?

Answer 1: You must stop (and swap) when the current element at either of the pointers equals the pivot. Otherwise, all of the numbers will fall into just one of the partitions (likely the one that is "less than" the pivot) with each iteration.



Question 2 (worth 2^2 points): How do you perform Heap Sort without using any substantial amount of extra memory (double the memory would certainly not be acceptable)?

Answer 2: With a simple implementation of the normal array based version of Heap Sort, each element is removed from the original array, using removeMin, and inserted in order into a new array. In this version, we instead insert each element to the space opened up at the end of the portion of the array currently occupied by the heap, as a result of the associated removeMin. For example:

1 4 2 9 5 3 8 - Initial Heap
2 4 3 9 5 8|1 - After a removeMin
3 4 8 9 5|2 1 - Another removeMin
...
9 8 5 4 3 2 1 - After all removeMin's

This array is sorted in descending order. If necessary, we can transition it to ascending order either using a linear time swap or using a max heap and doing removeMax operations.

Question 0 (worth 2^0 points): Describe the four access modifiers.

Answer 0:
1. Public is visible everywhere.
2. Protected is visible in the package and child classes.
3. Default is visible only in the package.
4. Private isn't visible outside the class (or package).



Question 1 (worth 2^1 points): What's wrong with this code?

public class Parent
{
      int p;
      
      public Parent(int i)
      {
         p = i;
      } 
      
      public int getP()
      {
         return p;
      }
}

public class Child extends Parent
{
      int c;
      
      public Child()
      {
         c = 5;
      }
      
      public int getC()
      {
         return c;
      }
}

Answer 1: Because Child doesn't explicitlly call any constructor in Parent, Java will insert an implicit call to the no-argument constructor of Parent. However, because Parent defines its own constructor (with arguments), the default (no-argument) constructor will not be automatically created by Java. A compile error will result.



Question 2 (worth 2^2 points): You have a class representing a game board piece. It has the following fields: row, column, height, width. How must you modify the class so you can sort an array of insances of that class using Arrays.sort() based on area? It is not particularly important where the fields are visible or what other methods exist in the class definition.

Answer 2: The class must implement the Comparable interface and the compareTo() method.

Question 0 (worth 2^0 points): Is every Directed Acyclic Graph (DAG) a tree?

Answer 0: No; It is possible for a node in a DAG to have two parents (two incoming edges), which violates the tree invariant. However, every tree is a DAG (as a tree is defined to be directed and not have any cycles).



Question 1 (worth 2^1 points): How many edges are there in a tree with |V| vertices/nodes?

Answer 1: A tree is defined as having exactly one incoming edge associated with each node, except the root. Therefore, no matter what kind of tree it is (binary, n-ary), there will be (|V| - 1) edges.



Question 2 (worth 2^2 points): How many edges are there in a complete (fully connected), undirected graph with no self edges and n nodes/vertices?

Answer 2: There are n(n-1)/2 edges. There are two ways to come to this conclusion:

1. Begin with just the nodes and then fill in the edges. It will require (n-1) edges to connect the first node to all other nodes. It will require (n-2) edges to connect the second node to the others (except the first, to which it is already connected), and so on. In all, it will require (n-1) + (n-2) + ... + 2 + 1 edges. We can pairwise sum these to get (n-1)/2 pairs, each with sum n. Therefore, the total cost is n(n-1)/2

Start    3 edges + 2 edges + 1 edge  = 6 edges 
O   O     O   O     O---O     O   O ?= 4(4-1)/2
          |  /       \            | ?= 4(3)/2  
          | /         \           |  = 6 edges 
          |/           \          |            
O   O     O---O     O   O     O   O            

2. Alternatively, for each of n nodes, we could draw an edge to each of the (n-1) other nodes in the graph (even if we are already connected to a node). This will result in n(n-1) edges. But, each node is now connected twice to each other node. Eliminating one of these two edges for each pair of nodes will result in a well formed, complete graph with n(n-1)/2 edges.



Question 3 (worth 2^3 points): What is the minimum size (in terms of the number of nodes/vertices) of an AVL tree of height/depth h?

Answer 3: S_h = 1 + S_(h-1) + S_(h-2).
For a given height h, the size of the smallest AVL tree of that height (S_h) will be composed of a root node (1), a left subtree of size S_(h-1) (the smallest subtree of height (h-1)), and a right subtree of size S_(h-2) (the smallest subtree of height (h-2)). We cannot decrease the size of any of the subtrees while maintaining a valid AVL tree of height h. The book provides further details and shows that this recursive definition actually decomposes into the Fibonacci numbers.

Question 0 (worth 1 point):
1. What sort of traversal does a stack correspond to?
2. What sort of traversal does a queue correspond to?

Answer 0:
1. Depth first search (including preOrder, inOrder, and postOrder).
2. Breadth first.



Question 1 (worth 1 point): What are the search tree, AVL tree, and heap properties?

Answer 1:
1. Search - For each node, all values in the left subtree must be less than the nodes value and all values in the right subtree must be greater.
2. AVL - For each node, the heights of the left and right subtrees may differ by at most one.
3. Heap - For each node, its value must be less than all values in its left and right subtrees. Also, the heap must be a complete binary tree.



Question 2 (worth 1 point): Can you use Bellman-Ford on an unweighted, acyclic graph?

Answer 2: Bellman-Ford is the most general of the graph traversal / shortest path discovery algorithms. Therefore, it can handle unweighted, acyclic graphs as just a subset of its functionality.