430.

329: Introduction to Algorithm Spring 2025

Homework 3
(Due on May 26, 2025 11:59PM KST)

Instructor: Jonghyun Choi ([email protected])

TAs: Byeonghwi Kim and Taeheon Kim

Problem 1. Dynamic Programming (30 Points)

An automotive plant has two assembly lines, Line A (Top line) and Line B (Bottom line), each with n stations.
Every product must pass through the stations in order from 1 to n. However, you may process the product at either
station i of Line A or station i of Line B, for each i = 1, 2, . . . n. The overall time cost to produce one item depends
on :
1. Processing Time
— ai : the time needed to process station i on Line A.
— bi : the time needed to process station i on Line B.
— ea , eb : the time needed to enter the Line A or Line B.
— xa , xb : the time needed to exit the Line A or Line B.
2. Transition Time
— tai : the time needed to transfer from station i on Line A to station i + 1 on Line B.
— tbi : the time needed to transfer from station i on Line B to station i + 1 on Line A.
If you stay on the same line for stations i and i + 1, there is no additional transfer cost beyond the normal station
processing times.
You must use exactly one station from each ‘column’ (i.e., ith time slot)—either from Line A or Line B. You proceed
through stations in increasing order of i. You may switch from one line to the other between consecutive stations, but
you pay the corresponding transfer cost.

1. Let fa [j] and fb [j] be the fastest time to get from the starting point through station aj and bj , and let f ∗ be
the fastest time at exit (going through the entire factory). What is the recursive formula of the problem using
fa [j], fb [j], and f ∗ ? (7 points)

2. Show the optimal substructure property using contradiction. (7 points)

3. Write down a pseudocode for the bottom-up approach. (10 points)

4. What are the time and space complexities of your algorithm ? (3 points)

5. What is the fastest time f ∗ of this assembly line (in the figure) ? Please write all fa [j] and fb [j] for j = 1, 2, 3, 4.
(3 points)

1
Homework 3 2

Problem 2. Elementary Graph Algorithm (20 Points)

1. In a multi-agent system, improved performance can often be achieved compared to a single-agent system through
communication between agents. Such a system can be represented as an undirected graph G = (V, E), where
each agent corresponds to a node and each communication channel between agents corresponds to an edge.
In general, multi-agent systems are fully connected, meaning that each agent communicates with all other agents.
However, in practice, there are many cases where the communication network is sparse and only a subset of agent
pairs are connected.

Suppose we model two types of communication graphs, as described in (a) and (b) below :
Analyze which graph representation—adjacency matrix or adjacency list—is more suitable in terms of space
complexity. In addition, consider the efficiency of interaction lookup, i.e., checking whether a given pair of
agents can directly communicate.
(a) A fully connected graph with n agents. (5 points)
(b) A sparse graph with n agents, where each agent communicates with exactly 2 other agents. (5 points)
2. A multi-agent system can be represented by a Directed Acyclic Graph (DAG), where information flows
from a single source agent (src) to multiple sink agents. Each directed edge represents a one-way communication
channel between agents. Each agent i has a processing delay di , which is the time required for that agent to
process incoming information before forwarding it. The communication structure is described by the following
adjacency matrix C, where Cij = 1 indicates that agent i can send information directly to agent j :
 
0 1 1 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
 
0 0 0 0 1 1 0 0 0 0
 
0 0 0 0 0 0 1 0 0 0
 
0 0 0 0 0 0 1 1 0 0
C=
0

 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
 
0 0 0 0 0 0 0 0 0 1
 
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
The processing delays for each agent are :

d = [0, 2, 1, 3, 2, 3, 0, 1, 2, 0]
Assume agent 0 is the source, and agents 6 and 9 are the sink agents (with delay 0).
(a) Draw the DAG based on the adjacency matrix C. Label the agents from 0 to 9, and include a directed edge
from agent i to agent j if Cij = 1. (5 points)
(b) For each sink agent t ∈ {6, 9}, compute the critical path length, defined as the maximum total time among
all possible paths from the source agent 0 to agent t, where the total time is the sum of the processing
delays of all agents along the path. (5 points)
Homework 3 3

Problem 3. Single-Source Shortest Paths (20 Points)

The Bellman-Ford algorithm solves the single-source shortest-path problem when the graph has edge weights that
may be negative. Given a weighted directed graph G = (V, E) with source vertex s and weight function w : E → − R,
as an extended version of the lecture’s version (but is the textbook version), this Bellman-Ford algorithm returns a
boolean value indicating whether there is a negative-weight cycle that is reachable from the source. This Bellman-Ford
algorithm is described in the following algorithm box. The input graph is illustrated in Figure 1.

Algorithm Bellman-Ford(G, w, s) 3
v1 v2
1: Initialize-Single-Source(G,s)
2: for i = 1 to |G.V | − 1
3: for each edge (u, v) ∈ G.E 4
4: Relax(u, v, w) 7
5: for each edge (u, v) ∈ G.E 8
6: if v.d > u.d + w(u, v) 4 v5 s
7: return false 1 6 5
8: return true
1
Algorithm Relax(u, v, w) v3 v4
9
1: if v.d > u.d + w(u, v)
2: v.d = u.d + w(u, v)
3: v.π = u
Figure 1 – A sample graph.

Show the followings.

1. the step-by-step change of v.d and v.π, ∀v ∈ V (10 points)
2. the decision of Bellman-Ford (i.e., true or false) (5 points).

Hints.
1. Show the step changes only if the condition in line 1 of Relax holds (i.e., only when v.d gets updated).
2. Use the graph layout in Figure 1 to show each step-by-step change.
3. Assume that the edges in line 3 of Bellman-Ford(G, w, s) always come in the order below :

(v2, v1) →
− (v3, v1) →
− (v4, v2) →
− (v4, v3) →
− (v4, v5) →
− (v5, v1) →
− (v5, v3) →
− (s, v2) →
− (s, v4) →
− (s, v5)
Homework 3 4

Problem 4. All-Pairs Shortest Paths (30 Points)

We consider the problem of finding shortest paths between all pairs of vertices in a graph. Formally, we wish to
find a shortest (least-weight) path from u to v, for every pair of vertices u, v ∈ V , where the weight of a path is the
sum of the weights of its constituent edges. For this, we can use a dynamic-programming algorithm based on matrix
multiplication as illustrated by Slow-All-Pairs-Shortest-Paths and Fast-All-Pairs-Shortest-Paths.

Algorithm Extend-Shortest-Paths(L, W )
Algorithm Slow-All-Pairs-Shortest-Paths(W ) 1: n = L.rows
1: n = W.rows 2: let L′ = (lij′
) be a new n × n matrix
2: L(1) = W 3: for i = 1 to n
3: for m = 2 to n − 1 4: for j = 1 to n
4: let L(m) be a new n × n matrix 5: ′
lij =∞
5: L(m) = Extended-Shortest-Paths(L(m−1) , W ) 6: for k = 1 to n
6: return L(n−1) 7: L′ij = min(L′ij , Lik + Wkj )
′
8: return L

3 3
Algorithm Fast-All-Pairs-Shortest-Paths(W ) 1 2 3
1: n = W.rows
2: L(1) = W
3: m = 1 -2
5 6 -4 5
4: while m < n − 1 2 -1
5: let L(2m) be a new n × n matrix
6: L(2m) = Extended-Shortest-Paths(L(m) , L(m) )
4 5 6
7: m = 2m 1 3
8: return L(n−1)
Figure 2 – A sample graph.

For the input graph of Figure 2, answer the following questions.

1. Show all L(m) ’s generated by Slow-All-Pairs-Shortest-Paths. (15 points)
2. Show all L(m) ’s generated by Fast-All-Pairs-Shortest-Paths. (15 points)