Help with Homework question 2 on the attached document. Due midnight CST
Algorithms
Homework 7, due Wednesday, Nov 17, at 11:59 p.m.
Reading: CLRS 24.3, 24.5, 23.1, 23.2.
“HOMEWORK” exercises: submit on Gradescope by
1. Suppose that, in the single-source shortest path problem in weighted graphs, we wish to find not just
any shortest (min-weight) path between a source vertex s and a vertex v, but among those, the shortest
(min-weight) path that has the fewest edges. Given a directed, edge-weighted graph G = (V, E) with
integer edge weights w(e) > 0 and a source vertex s ∈ V , give an O((V + E) lg V ) time algorithm to
find the shortest (min-weight) path from s to v with the fewest number of edges, for all v ∈ V . Assume
that G is in adjacency list format.
(a) (2 points) Briefly describe the basic idea of your algorithm.
(b) (5 points) Describe your algorithm in pseudocode. Comment your code.
(c) (2 points) Argue why your algorithm returns the correct answer.
(d) (1 point) Analyze the running time of your algorithm with reference to your pseudocode.
2. Given a directed graph G = (V, E) with non-negative edge weights w(e) ≥ 0 and two vertices s and t,
find the shortest path from s to t that has an even number of edges. Such a path need not be a simple
path, i.e. it may repeat vertices or edges.
(a) (5 points) Modify Dijkstra’s algorithm to solve the problem. Give the complete pseudocode for
your modified algorithm. Analyze the time taken by your algorithm. Argue why your algorithm is
correct.
(b) (5 points) Modify G = (V, E) into G0 = (V
0
, E0
), such that executing the original Dijkstra’s algorithm on G0
solves the problem. Explain clearly, using an example, how you would create G, and
how you would obtain the required distances. Analyze the time taken by your solution. Argue why
your algorithm is correct.
3. The following statements may or may not be correct. In each case, either prove it (if it is correct) or
give a counterexample (if it isnt correct). Always assume that the graph G = (V, E) is undirected and
connected. Do not assume that edge weights are distinct unless this is specifically stated.
(a) (1 point) If graph G has more than |V | − 1 edges, and there is a unique heaviest edge, then this
edge cannot be part of a minimum spanning tree.
(b) (2 points) If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.
(c) (1 point) Let e be any edge of minimum weight in G . Then e must be part of some MST.
(d) (2 points) If the lightest edge in a graph is unique, then it must be part of every MST.
(e) (2 points) If e is part of some MST of G , then it must be a lightest edge across some cut of G .
(f) (2 points) Prim’s algorithm works correctly when there are negative edges.
4. CLRS 23-1, page 638 as:
◦ Part (a): Prove that the MST (in this case) is unique, and give a counter example to show that the
second-best MST need not be unique. (2 points)
◦ Part (b) (2 points)
◦ Part (c) Give pseudocode for the algorithm. (3 points)
◦ Part (d). Give pseudocode for the algorithm. (3 points)
Page 2
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
| Sun | Mon | Tue | Wed | Thu | Fri | Sat |
|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 1 | 2 | 3 | 4 | 5 |
