All answers must be proved: it is not sufficient to simply state the answer. If you consult outside sources (such as Wikipedia), cite
your source. All answers must be written in your own words. Treat single arithmetic operations (addition, subtraction, multiplication,
and division) as constant time operations.
1. It is possible for a graph to have multiple shortest paths between two nodes. In class, we saw how to find the length of the
shortest path from a node s to all other nodes. Suppose that in addition to finding the length of these shortest paths, we also want to
know how many shortest paths there are. Describe an algorithm to do this.
2. A binary tree is full if all vertices have either 0 or two children. Let Bn denote the number of full binary trees with n
vertices.
1. What are the values of B3, B5, and B7?
2. Is it possible to have a full binary tree with an even number of vertices? Why or why not?
3. For general n, derive a recurrence relation for Bn. Include base cases. Hint: Think about the left and right sub-trees of a full
binary tree of size n. What are the possible sizes for these sub-trees?
4. Show that Bn is Ω(2(n−1)/2 ). Hint: If you do an internet search for this problem, you will come across the concept of Catalan
numbers. Try proving this using induction, without using Catalan numbers (though if you can’t figure it out and need to use the Catalan
numbers, you can do so.)
3. In an undirected graph G with vertex set V and edge set E, the degree d(u) of a node u is the number of neighbors that u has
(i.e., the number of nodes that u is linked to). In a directed graph, a node u has an indegree, which counts the number of incoming
edges, and an outdegree, which counts the number of outgoing edges.
1. Show that in an undirected graph, P u∈V d(u) = 2|E|. Here, |E| represents the size of the edge set E: in other words, the number of
edges.
2. Show that in an undirected graph, there must be an even number of vertices with odd degree.
3. Does a similar statement hold for the number of vertices with odd indegree in a directed graph? Why or why not?
4. Let G be a directed graph. Let s be a ‘start vertex’. An infinite path of G is an infinite sequence v0, v1, v2, … of vertices
such that v0 = s and for all i> 0, there is an edge from vi to vi+1. In other words, this is a path of infinite length. Because G has a
finite number of vertices, some vertices in an infinite path are visited infinitely often.
1. If p is an infinite path, let Inf(p) be the set of vertices that occur infinitely many times in p. Prove that Inf(p) is a subset of
a single strongly connected component of G.
2. Describe an algorithm to determine if G has an infinite path. Prove that it is correct.
5. Suppose that you are given a directed graph and a target node t. You want to find the shortest path to target node t from every
other node. (Notice that this is different from what we covered in class: in class, we considered the problem of finding the shortest
path from the specified node to every other node.) Describe an algorithm to calculate these values.
6. Both QuickSort and MergeSort require splitting the input array into two smaller arrays, recursively sorting the subarrays, and
then joining the sorted subarrays to obtain a sorted version of the initial input array. One way to handle the recursive calls is to
allocate new memory for the subarrays, copy 1 the elements from the input array to the newly allocated memory, and pass these new
subarrays in the recursive call. However, this requires a lot of extra memory.
1. In MergeSort, each sub-array is approximately half the size of the input array. Suppose the original input array originally used n
units of memory. Suppose we allocate new memory for the subarrays every time the array is split. Then over the entire set of recursive
calls, how much total memory is required?
2. Describe how QuickSort can be implemented in place (that is, without allocating new memory for the subarrays). If you need a small
amount of memory for temporary storage, that’s fine.
TAKE ADVANTAGE OF OUR PROMOTIONAL DISCOUNT DISPLAYED ON THE WEBSITE AND GET A DISCOUNT FOR YOUR PAPER NOW!