Qualifier Practice Exam: Foundations

Question 7 (5 Points): A complete ternary tree is defined as a tree in which every non-leaf

node has exactly 3 children and every leaf is the same distance from the root. The height of

a complete ternary tree is defined as the distance (number of links) from the root to a leaf.

A ternary tree with just one node has height 0.

Prove the following by mathematical induction: “a complete ternary tree of height h has

a total of (3^(h+1)−1)/2 nodes.”

i. Base Case: Let h=0. (3 ^ (0+1) - 1)/2 = 1. Just one node, h=0.

ii. Let h be an arbitrary value such that h > 1. Assume P(h) holds.

iii. Profit?

I know this section should somehow involve (3 ^ ((h+1)+1)-1)/2, but there really isn't a "left side" to this equation to work with.

Using our induction hypothesis, P(h) = (3^(h+1)-1)/2

Spending too long on this problem, moving on. This is not boding well. ._.

Part II: Data Structures and Algorithms (52 pts)

Question 1 (8 Points): Which of the following problems is known to be solvable in

running time O (n3)? (Give a list of the problem numbers.)

1. Finding the longest simple path from a given start vertex to a given end vertex in a

directed acyclic graph on n vertices with nonnegative integer weights.

2. Finding the shortest path from a given start vertex to a given end vertex in a directed

graph on n vertices with arbitrary integer weights.

3. Finding the longest simple path from a given start vertex to a given end vertex in a

directed graph on n vertices with nonnegative integer weights.

This is referring to Floyd-Warshall algorithm. Definitely 1, 3. It mentions an ability to identify (2), but since the cycles produce arbitrary weights when negative, I'm going to stick with 1, 3.

Question 2 (5 Points): True or False: Circle your final answers.

T [F] If an algorithm runs in O(n) time on the worst case input then it runs in O(n) time on every input.

[T] F Running BFS on a directed unweighted graph with cycles will produce shortest paths from the source vertex to all other reachable vertices (where path length is simply the number of edges).

T [F] log(n!) = o(n2)

[T] F Running DFS on an undirected graph may produce cross edges.

[T] F The lowest weight edge in a graph with all unique edge-weights is always included in any minimum spanning tree

Question 3 (6 Points): Code for the Floyd-Warshall all-pairs shortest paths algorithm (the dynamic programming based O(V 3) algorithm) appears below. Write a loop invariant for the end of the outer loop (on variable k) – i.e., at the point in the code indicated, what can be claimed about adj[i][j] with respect to k. Hint: this loop invariant essentially why the algorithm works!

// adj[][] is initially the weight matrix.

// If there is no edge (i,j) then adj[i][j] = Infinity

// where Infinity is a sufficiently large number (e.g.,

// n*MAX_EDGE_WEIGHT).

for (k = 1 to n){

for (i = 1 to n){

for (j = 1 to n){

adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

}

}

// adj[i][j] is the minimum path as far nodes 1...k are concerned.

}

Question 4 (6 Points):

Part (A) Give example functions f(n) and g(n) where f(n) = o(g(n)).

f(n) = n

g(n) = n^2

o(g(n)) = n

(Because lim(n->inf) (n/(n^2))=0)

Part (B) Is the following statement TRUE or FALSE (if it is true, give a clear argument;

if it is false, give a counter-example):

“If f(n) = o(g(n)) then log(f(n)) = o(log(g(n))).”

False.

Let's use the previous f(n)-(g(n) pair here. log(f(n))= log(n), while log(g(n))= log(n^2) = 2log(n)

lim(n->inf) logn/2logn = .5 =/= 0.