CSci 4041, Final exam
Name:
Student ID number:
Instructions: The time limit is 120 minutes. Please write your answers in the space below. If you need more space, write on the back of the paper. The exam is open book and notes. You may use electronic devices to ONLY look at either an e-book version or electronic notes. You may not use the internet, program/run code or any other outside resources. (If you are typing on your keyboard/input device for anything other than ctrl-F to find words in the e-book or notes, this is probably not acceptable.) For all questions you must show work.
Problem 1. (20 points)
Use the Floyd-Warshall algorithm to find all-pairs shortest-paths for the following graph represented as an adjacency matrix. (Floyd-Warshall is the one that uses dynamic programming on the vertexes involved in the path.) (Note: your answer should be a 3×3 matrix.) You must show work for full credit.
Problem 2. (20 points)
Suppose there is a directed graph where all the edges have the same weight (and the weight is larger than zero). What is the runtime of Dijkstra’s algorithm (using the book/lectures implementation) when run on this graph? Is there a more efficient way to find the same solution as Dijkstra’s algorithm for this specific type of graph? Justify you answer for the runtime. Give a few sentences describing your reasoning for the second part.
Problem 3. (20 points)
What is the runtime of Prim’s algorithm if a normal array was used instead of a heap? (Prim’s algorithm is the one that uses vertexes to find the minimum spanning tree.)
Problem 4. (20 points)
Prove (i.e. give a formal detailed argument) that every ¡°back edge¡± (as labeled from a depth-first search) is part of some cycle.
Problem 5. (10 points)
What is the worst case runtime of the following pseudo-code? Justify your answers.
FindK(A, k, start, end) // A is some array
mid = (start+end)/2
if A[mid] == k or mid == start or mid == end
return mid
else if A[mid] > k
return FindK(A, k, start, mid)
else
return FindK(A, k, mid, end)
FindB(A, B, end) // B is some array
for i from 1 to B.length
if B[i] == FindK(A, B[i], 1, A.length)
return true
return false
Problem 6. (10 points)
You and your co-workers regularly go out and get drinks together. Sometimes someone forgets their money and other co-workers buy drinks for them. These ¡°drink IOUs¡± form a graph denoting who owes whom how many drinks. Specifically, in this directed graph, an edge from U to V means person U owes person V a number of drinks equal to the edge weight.
Over time, this graph has become too complex. Describe an algorithm (using either pseudo-code or a precise description) to simplify this IOU system so that everyone still owes and receives the same IOUs but no one in the graph is both owing and receiving at the same time. The runtime of this algorithm must be O(n2), where n is the number of co-workers. An example of the initial graph and solution graph for n=3 is below: