Description

Instructions:
1. This is a 2-hr exam. Closed book and notes
2. If a description to an algorithm or a proof is required please limit your description or proof to within 150 words, preferably not exceeding the space allotted for that question.
3. No space other than the pages in the exam booklet will be scanned for grading.
4. If you require an additional page for a question, you can use the extra page provided within this booklet. However please indicate clearly that you are continuing the solution on the additional page.
5. Do not detach any sheets from the booklet. Detached sheets will not be scanned.
6. If using a pencil to write the answers, make sure you apply enough pressure, so your answers are readable in the scanned copy of your exam.
7. Do not write your answers in cursive scripts.

1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any justification.

[ TRUE/FALSE ]
In any graph we have that |E| = Θ(|V|2)

[ TRUE/FALSE ]
If Path P is the shortest path from u to v and w is a node on the path, then the part of the path from u to w is also the shortest path from u to w.

[ TRUE/FALSE ]
Dijkstra algorithm is able to find the Shortest Path in directed and undirected graphs with positive edge weights.

[ TRUE/FALSE ]
Kruskal’s algorithm can fail in the presence of negative cost edges.

[ TRUE/FALSE ]
Given a graph G. If the edge e is not part of any MST of G, then it must be the maximum weight edge on some cycle in G.

[ TRUE/FALSE ]
In a binary max heap containing n numbers, the smallest element can be found in time O(logn).

[ TRUE/FALSE ]
Nodes in a binomial heap can have more than 2 children.

[ TRUE/FALSE ]
An array with following sequence of terms [16, 14, 10, 10, 12, 9, 3, 2, 4, 1] is a binary max-heap.

[ TRUE/FALSE ]
In the stable matching problem involving n men and n women, for any given set of preference lists, there will be at most two stable matchings.

2) 12 pts
Indicate if the expression of each row is Θ, O or Ω of the expressions in each column, as the example.
If an expression is both O and Ω you should write Θ.
Note 1: the solutions for the first function ( ) are given to you as an example. Note 2: If you need to make an assumption about the base of log use base 2.

Θ Ω O

100

3) 16 pts
Given a directed graph with m edges and n nodes where every edge has weight as either 1 or 2, find the shortest path from a given source vertex ‘s’ to a given destination vertex ‘t’. Expected time complexity is O(m+n).

4) 18 pts
Suppose you are the registrar for USC and you need to schedule classrooms to be used for various classes. There are n available classrooms and n classes that need rooms at a given time. Each classroom i has a maximum capacity ci , and each class j has sj students. A classroom can’t take a class that is over its maximum capacity.
Assume that there exists a perfect matching of classrooms and classes.
a) Design a greedy algorithm which returns a perfect matching of classes to appropriate classrooms (10 pts)
b) Give the asymptotic worst-case complexity (2 pts)
c) Prove that your algorithm produces correct results (6 pts)

5) 16 pts

a) Execute Prim’s algorithm on the above graph starting at vertex A. If there are any ties, the vertex with the lower letter comes first. List the nodes in the order in which they are connected to the MST. (8 pts)

b) Execute Dijkstra’s algorithm on the above graph starting at vertex A. If there are any ties, the vertex with the lower letter comes first. List the nodes in the order in which they are found. (8 pts)