CS 601: Algorithms and Complexity October, 2025

Dynamic Programming Assignment (Graded)

Instructor: Akash Kumar TAs: Siddhi Pevekar
Manish Kumar Saini

Problem 1: Word Segmentation with Maximum Likeli-

hood (20 Points)
In several languages, words in a sentence may not be explicitly separated by spaces. For
example, in languages like Japanese or Thai, multiple words often appear as one continuous
sequence. Similarly, in German, long compound words such as “Lebensversicherungsge-
sellschaft” (life insurance company) are formed by joining several smaller words.
Assume you are provided with a function score(s) that, for any substring s, returns a
numerical value representing how likely it is that s is a valid indivisible word. For instance,
score(“leben”) or score(“versicherung”) would be high, whereas score(“ensvers”)
would be low.
Given a continuous string
S = s1 s2 . . . sn ,
design a dynamic programming algorithm to segment S into a sequence of words
w1 , w2 , . . . , wk
(where k is not specified in advance) such that the total score
score(wi )
X

is maximized and provide a short argument or induction sketch showing correctness..

Problem2: Minimum Time to Collect All Coins in a

Grid (20 points)
You are given an n × n grid where each cell contains:
• 0 → Empty cell
• 1 → A coin
• −1 → An obstacle
You start at position (0, 0) and can move in all four directions: up, down, left, and
right. Moving from one cell to an adjacent cell takes 1 time unit.
Your task is to collect all coins in the grid and then return to (0, 0) while minimizing
the total time [Link] is guaranteed that1 all coins in the grid can be collected. Every
coin cell should be visited exactly once.
Requirements:
1. Dynamic Programming Formulation: Define a suitable structure for DP to
solve this problem.
Hint: You can form a graph of the grid cells and compute shortest paths between coins.

2. Recurrence relation: Derive the recurrence relation for updating your DP state.

3. Complexity Analysis: Determine the time and space complexity of your approach
in terms of n (grid size) and c (number of coins).

4. Proof of Correctness: Argue why your DP formulation guarantees the minimum

total time.

Problem 3: Expected Longest Streak in a Markov Chain

(20 Points)
Manish is an avid sports bettor who specializes in long-term futures wagers. His latest
obsession is predicting the longest consecutive winning streak (L) a team will achieve over a
full season of N games. The value of L determines the payoff of his bet.
While casual bettors assume every game is independent, Manish has observed that mo-
mentum is a critical factor: a team is statistically more likely to win if they just won the
previous game, and conversely, a team that just lost has a lower probability of winning the
next one. To make an informed bet, Manish needs an accurate calculation of the Expected
Length of the Longest Streak, E[L].

N
E[L] = k · Pr(L = k)
X

k=0

To reflect Manish’s observation, we model the sequence of game outcomes as a two-state

Markov chain, where the win probability for any game depends exclusively on the result
of the immediately preceding game.
Problem Statement:
Compute the Expected Length of the Longest Consecutive Winning Streak,
E[L], for a season of N games, based on the following probability model:

• The probability of winning the first game is a fixed constant P0 .

• If the previous game was a Win, the probability of winning the next game is PW .

• If the previous game was a Loss, the probability of winning the next game is PL .

The loss probabilities are QW = 1 − PW and QL = 1 − PL . All games follow this Markov
dependence structure.

2
Your task is to design and analyze a Dynamic Programming (DP) formulation to com-
pute E[L] given N , P0 , PW , and PL .

1. Recurrence Relation: Formulate the recurrence relation to compute the expected

value of the longest winning streak. Clearly define your DP state variables and explain
the meaning of each term in the recurrence.
Hint: Let your DP state capture:

• The number of games played so far.

• The longest winning streak observed so far.
• The current ongoing streak length.
• Whether the last game was a Win or Loss.

2. Algorithm Design: Write clear pseudocode implementing your recurrence using

dynamic programming. Your pseudocode should:

• Initialize appropriate base cases (e.g., for the first game),

• Iteratively update states for each subsequent game, and
• Compute and return the final expected value E[L] after N games.

3. Complexity Analysis: Provide the time and space complexity of your dynamic
programming approach in terms of N . Discuss whether any optimization (e.g., space
reduction) is possible without affecting correctness.

4. Proof of Correctness: Provide a brief theoretical justification or inductive proof

sketch to argue that your recurrence and algorithm correctly compute the expected
length of the longest winning streak.

Example (for Illustration Only)

Consider a season of N = 3 games, with parameters:

P0 = 0.4, PW = 0.6, PL = 0.3.

Enumerate or outline how your DP recurrence would handle this example to compute E[L].
(You do not need to perform full numerical computation; focus on explaining how the states
and transitions evolve.)

Problem 4: Balancing Work and Leisure Before Exams

(20 Points)
Riya is planning her schedule for the next n days leading up to exams. Each day, the weather
forecast predicts an integer temperature value ti , which can be positive or negative.

3
 If Riya spends the day outdoors, her mood increases by ti — higher temperatures
make her happier, while negative temperatures decrease her mood. If she chooses to study
indoors, her mood remains unchanged that day.
However, to maintain focus, Riya has decided never to spend more than two con-
secutive days outdoors.
Design an O(n)-time dynamic programming algorithm to determine which days
Riya should study so that her total mood improvement over n days is maximized.

Requirements:
1. Recurrence Relation: Derive the recurrence relation to compute the optimal total
mood.

2. Algorithm Design: Write the pseudocode for your algorithm and explain how it
achieves O(n) time.

3. Complexity Analysis: Provide the time and space complexity of your solution.

4. Proof of Correctness: Justify why your DP solution always finds the optimal set of
study days.

Example
Input:

• n=5

• temperatures = [3, -1, 2, 4, -2]

Expected Output: An optimal plan of study and outdoor days that maximizes total mood
while satisfying the “no more than two consecutive outdoor days” rule.

Problem 5: The Mentor Allocation Challenge (20 Points)

In course CS601: Algorithms and Complexity, a mentoring event is being organized
to help students prepare for the upcoming midterm. There are three mentoring sessions —
focused on topics Graphs, Dynamic Programming (DP), and Greedy Algorithms —
each conducted in a separate virtual room.
There are a total of 3n students, and each student must be assigned to exactly one of the
three sessions. Each student i has a known nonnegative integer learning gain represented by
three values:
gi , di , and ri ,
corresponding to the benefit they would receive from attending the sessions on Graphs,
DP, and Greedy, respectively.
The organizers aim to:

4
 • Assign exactly n students to each of the three sessions, and

• Ensure that every student gains a strictly positive benefit (i.e., no student is as-
signed to a session where their benefit value is 0).

Your task is to determine:

(i) Whether it is possible to assign the 3n students equally across the three sessions such
that every student’s benefit is positive.

(ii) If such an assignment exists, compute the maximum total learning gain achievable
among all valid assignments.

Design and describe an O(n3 )-time dynamic programming algorithm to solve this
problem.

Requirements
1. Recurrence Relation: Derive and explain the recurrence relation capturing feasible
allocations and benefit updates.

2. Base Cases: Specify appropriate initial conditions for your DP table.

3. Algorithm Design: Provide pseudocode or structured steps implementing your DP

approach.

4. Complexity Analysis: Prove that your algorithm runs in O(n3 ) time and discuss
any possible space optimizations.

5. Proof of Correctness: Briefly justify that your recurrence and algorithm correctly
compute the optimal total learning gain when a feasible assignment exists.

Example
Input:

n = 2, (g, d, r) = [(4, 0, 2), (3, 5, 0), (2, 4, 1), (1, 3, 5), (0, 6, 2), (5, 2, 4)]

Output: Either:

• A statement that no valid assignment exists (due to zero-benefit constraints), or

• The maximum total learning gain achievable under the given conditions.

5
Problem6: Analyzing Connectivity in a Restricted So-
cial Network [Bonus Problem]
You are given a social network with n individuals, labeled from 0 to n−1. A set of restrictions
is provided as a 2D array, restrictions, where each element [xi , yi ] signifies that person xi
and person yi are prohibited from becoming friends, either directly or through a chain of
mutual friends.
Initially, all individuals are in their own disjoint sets (no friendships exist). You are also
given a sequence of friend requests, represented by a 2D array, requests. Each element
[uj , vj ] in this array represents a request for person uj and person vj to become friends.
A friend request between uj and vj is considered successful if and only if making them
friends does not violate any of the given restrictions. A violation occurs if, after forming the
friendship, any two individuals xi and yi from the restrictions list end up in the same
connected component (i.e., they become indirect friends).
If a friend request is successful, the friendship is permanently formed, and this new
connection must be considered for all subsequent requests. If uj and vj are already friends,
the request is still considered successful.
Your task is to return a boolean array, result, where result[j] is true if the j-th
friend request is successful, and false otherwise.

Requirements
1. Design and Implement an Algorithm: Provide the pseudocode and working code
for a solution using dynamic programming.

2. Analyze Time Complexity: Calculate and justify the time complexity of your al-
gorithm in terms of the number of people, restrictions, and requests.

3. Prove Correctness: Write a formal proof (e.g., using induction or loop invariants)
to demonstrate that your algorithm works correctly.

Example
Input:

• n=3

• restrictions = [[0, 1]]

• requests = [[0, 2], [2, 1]]

Expected Output:
[ true, false ]