COM S 311 Exam 2
1 (Solving Recurrences)
2 (Graph Algorithms)
3 (Graph: Shortest Paths) 4 (Divide and Conquer) 5 (Greedy)
Copyright By PowCoder代写 加微信 powcoder
6 (Extra Credit: MST) Total
Max Points 20
Recitation Time
• When asked to design an algorithm, write pseudo code, not code of any specific programming language and not library operations of any specific programming language library.
• Proof of correctness ⇒ justifiable and unambiguous arguments. No need for formalism. • Level of points for solutions related to design and analysis algorithm
if designed algorithm is correct and efficient as expected then
if proof of correctness is unambiguous and justifiable then
if run-time analysis shows derivation steps and is correct then
points = 100%
points = 75%
else if run-time analysis shows derivation steps and is correct then
points = 75%
points = 50%
else if designed algorithm is correct and brute force then
points = 30%
else if designed algorithm is incorrect then
points = 0–20% (at the discretion of grader)
else if answer is “DO NOT GRADE” (YOU NEED TO EXPLICITLY WRITE DO NOT GRADE)
points = 15%
points = 0%
You may use following algorithms, runtimes and their correctness proofs as blackbox
1. Basic Data Structures: BST, Hash Tables, Priority Queue
2. BFS, DFS, Reversing a Graph, SCC, Topological Sorting, MST, Dijkstra’s Shortest Path Algorithm that returns Distance Array as well as Shortest Path Tree.
3. Sorting Algorithms.
Your application/use of these algorithms must match input/output behaviors.
1. Solve the recurrences (assume T (2) or T (3) is constant). Do not use Master Theorem. (a) T(n) = 3T(n/2) + n
(b) T(n) = T(n/3) + T(2n/3) + c
2. Given a directed graph G = (V,E), we say that a vertex v ∈ V is a bottom vertex if there exists a path from all vertices to v. Write an algorithm to find all bottom vertices in a directed graph. Justify the correctness of your algorithm. Derive the runtime of your algorithm.
3. Let G = (V, E) be a weighted undirected graph and let s ∈ V be a vertex. Let d[u] denote the length of the shortest path from s to u. We say that an edge ⟨x,y⟩ is purple edge if the following condition holds:
d[y] = d[x] + c(⟨x, y⟩), where c(⟨x, y⟩) is the cost of the edge ⟨x, y⟩.
Give an algorithm that gets G and s as input and outputs all purple edges. State the run-time of your algorithm.
4. Given a sorted array A of integers and an integer k, write an algorithm that outputs the number of times k appears in A. Justify the correctness of your algorithm. Derive the runtime of your algorithm.
5. You own a car repair business, and each morning you have a set of customers whose cars need to be fixed. You can fix only one car at a time. Customer i’s car needs ti time to be fixed. Given a schedule (i.e., an ordering of the jobs), let Ci denote the finishing time of fixing customer i’s car. For example, ifjobjisthefirsttobedone,wewouldhaveCj =tj;andifjobiisdonerightafterjobj,wewould have Ci = Cj + ti. Each customer i also has a given weight wi that represents his or her importance to the business. The happiness of customer i is expected to be dependent on the finishing time of i’s job. So the company decides that they want to schedule the jobs to minimize the weighted sum of the completion times, Σni=1wiCi.
The company is scheduling the jobs in decreasing order of wi/ti. Prove that this strategy gives an optimal solution, i.e., minimizes Σni=1wiCi. Use an exchange argument to prove correctness.
6. Extra Credit. There are n towns in a mountainous county. They are connected by m roadways. The objective of the local government officials is to ensure that some subset of roadways are kept clear through the winter and to maintain accessibility to all towns.
You can view the network of roadways as an undirected graph G = (V, E), |V | = n and |E| = m. Each edge e in this graph is annotated with a number ae, that gives the altitude of the highest point on the road. We’ll assume that no two edges have exactly the same altitude value ae. The height of a path P in the graph is then the maximum of ae over all edges e on P. Finally, a path between towns i and j is declared to be winter-optimal if it achieves the minimum possible height over all paths from i to j. The local government wants to find a subset E′ ⊆ E of roadways such that the subgraph (V, E′) is connected and for every pair of towns i and j, the height of the winter-optimal path in (V,E′) should be no greater than it is in the full graph G = (V,E). We’ll say that (V,E′) is a minimum-altitude connected subgraph if it has this property.
Prove or disprove that a MST is a minimum-altitude connected subgraph.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com