CSE101: Design and Analysis of Algorithms
• The instructions are the same as in Homework-00 except the note on Piazza regarding group
submissions & typed homework requirement.
There are 5 questions for a total of 100 points.
1. (15 points) Suppose Dijkstra’s algorithm is run on the following graph, starting at node A
A : B(4), H(8)
B : A(4), C(8), H(11)
C : B(8), D(7), F(4), I(2)
D : C(7), E(9), F(14)
E : D(9), F(10)
F : C(4), D(14), E(10), G(2)
G : F(2), H(1), I(6)
H : A(8), B(11), G(1), I(7)
I : C(2), G(6), H(7)
Note that the numbers in brackets indicate the weight of the edge.
Answer the following questions.
(a) Draw a table showing the intermediate distance values and previous values of all the nodes at each
iteration of the algorithm.
(b) Draw the final shortest path tree.
2. (20 points) Given a strongly connected directed graph, G = (V, E) with positive edge weights along
with a particular node v0 ∈ V . You wish to pre-process the graph so that queries of the form ”what is
the length of the shortest path from s to t that goes through v0” can be answered in constant time for
any pair of distinct vertices s and t. The pre-processing should take the same asymptotic run-time as
3. (20 points) In cases where there are several different shortest paths between two nodes (and edges have
varying lengths), the most convenient of these paths is often the one with fewest edges. For instance,
if nodes represent cities and edge lengths represent costs of flying between cities, there might be many
ways to get from city s to city t which all have the same cost. The most convenient of these alternatives
is the one which involves the fewest stopovers. Accordingly, for a specific starting node s, define
best[u] = Minimum number of edges in a shortest path from s to u
In the example below, the best values for nodes S, A, B, C, D, E, F are 0, 1, 1, 1, 2, 2, 3, respectively.
1 of 2
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Spring-2020) Homework-03
Give an efficient algorithm for the following problem.
Input: Graph G = (V, E); positive edge lengths le; starting node s ∈ V .
Output: The values of best[u] should be set for all nodes u ∈ V .
4. (20 points) You are driving down a very long highway, with gas stations at mile-posts m1, m2, . . . , mn,
where m1 = 0 is your starting point and mn is your final destination. You want to make as few gas
stops as possible, but your car can only hold enough gas to cover M miles. Give an algorithm to find
the minimum number of stops you need to make. Argue the correctness of the algorithm, and analyze
its running time.
5. (25 points) Alice wants to throw a party and is deciding whom to call. She has n people to choose from,
and she has made up a list of which pairs of these people know each other. She wants to pick as many
people as possible, subject to a constraint: at the party, each person should have at least five other
people whom they know.
(a) Give a high-level description of an efficient algorithm that takes as input the list of n people and
the list of pairs who know each other and outputs the best choice of party invitees. Argue that this
scheme is correct.
(b) Give an efficient implementation (psuedocode) of the scheme from part (a), and analyze its running
time in terms of n.
2 of 2
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: firstname.lastname@example.org 微信号:vipnxx