MPCS 55001 Sample Timed Assessment 2020 December 1
• You have 50 minutes to complete this examination.
• Show all your work.
• Do not use books, notes, internet, or any electronic devices.
• You are explicitly prohibited from collaborating or communicat- ing with any other person on this examination.
• If you are not sure of the meaning of a problem, send a private chat to instructors on Zoom.
• This examination contributes 0% to your course grade.
NAME :
• This examination is not representative of the difficulty of the final examination problems.
• This examination is representative of the format of the final examination.
1
Name: 2 Problem 1. (6 points)
You are given a directed graph G = (V, E) on n vertices and m edges, and two two vertices s, t ∈ V . Two paths from s and t are said to be vertex disjoint if they do not share any vertices except s and t. Give an efficient algorithm to find the maximum number of vertex disjoint paths from s to t in G.
1(a). [5 points]
Describe your algorithm in pseudocode.
1(b). [1 points]
Analyze the running time of your algorithm in terms of |V | and |E|.
Name: 3 Problem 2. (6 points)
You are given a flow network with unit capacity edges: It consists of a directed graph G = (V, E), a source s ∈ V , and a sink t ∈ V ; c(e) = 1 for every e ∈ E. You are also given an integer k. The goal is to delete k edges so as to reduce the maximum flow in G by as much as possible. In other words, you should find a set of edges F ⊆ E so that |F| = k and the maximum s-to-t flow in G′ = (V,E−F) is as small as possible subject to this. Give an efficient algorithm to solve this problem.
2(a). [5 points]
Describe your algorithm in pseudocode.
2(b). [1 points]
Analyze the running time of your algorithm in terms of |V | and |E|.