EE360C: Algorithms
University of Texas at Austin Homework #9
Dr. Christine Julien, Dr. Vallath Nandakumar Due Date: April 12, 2018
Homework #9
You should try to solve these problems by yourself. I recommend that you start early and get help
in office hours if needed. If you find it helpful to discuss problems with other students, go for it.
You do not need to turn in these problems. The goal is to be ready for the in class
quiz that will cover the same or similar problems.
Instructions: For all the following problems, give the recurrence relation, prove your
optimal substructure is correct and calculate the runtime.
Problem 1: Longest Paths
Given an undirected graph G = (V, E) with positive edge weights we for each edge e ∈ E, give
a dynamic programming algorithm to compute the longest path in G from a given source s that
contains at most n edges.
(Hint: Let A[v, k] denote the weight of the longest path from s to node v of at most k edges).
Solution
Initialize A[v, 1] = wsv if (s, v) ∈ E, A[v, 1] = 0 otherwise.
A[v, k] = max{A[v, k − 1], maxu:(u,v)∈E {wuv + A[u, k − 1]}}
Correctness: The problem has optimal substructure. Take a maximum weight path from s
to t in atmost k steps. If this path is {s, u1 , u2 , · · · , uj , t}, then the maximum weight path
from u1 to t in atmost k − 1 steps must be {u1 , u2 , · · · , uj , t}.
Perform induction on k. The base case k = 1 is trivial. Assume it is optimal for k. To
prove optimality for k + 1 using contradiction, assume that the algorithm is not optimal.
This implies that there exists a u ∈ V such that the maximum weight path to u in k steps is
greater than A[u, k]. But since the algorithm is optimal for k, this is impossible. Therefore
the algorithm is optimal for k + 1.
Running time: Any path can have atmost |V | steps. For any k, the cost is O(|V | + |E|)
since for each node v the cost of computing A[v, k] is proportional to 1 + degree(v). Thus
the total runtime is O(|V |(|E| + |V |)).
Problem 2: Moving in a Grid
Imagine that you are placed on a grid with n spaces in every row and n spaces in every column.
You can start anywhere along the bottom row of the grid, and you must move to the top row of
the grid. Each time you move, you can either move directly up (staying in the same column, but
moving up a row), up and to the left (moving over one column and up one row), or up and to the
right (moving over one column and up one row). You cannot move up and to the left if you are in
the leftmost row, and you cannot move up and to the right if you are in the right most row.
Each time you move, you are either paid or pay; that is, every legal move from square x to
square y is assigned a real value p(x, y). Sure, p(x, y) can also be 0.
Give a dynamic programming algorithm to compute your sequence of moves to receive the
maximum payoff to move from the bottom of the grid to the top of the grid. (Your maximum
payoff may be negative.) You must calculate the value of the optimal solution (i.e., the payoff) and
, Homework #9: April 12, 2018 2
the solution itself (i.e., the sequence of moves). Again, you can start at any square in the bottom
row and end in any square in the top row.
University of Texas at Austin Homework #9
Dr. Christine Julien, Dr. Vallath Nandakumar Due Date: April 12, 2018
Homework #9
You should try to solve these problems by yourself. I recommend that you start early and get help
in office hours if needed. If you find it helpful to discuss problems with other students, go for it.
You do not need to turn in these problems. The goal is to be ready for the in class
quiz that will cover the same or similar problems.
Instructions: For all the following problems, give the recurrence relation, prove your
optimal substructure is correct and calculate the runtime.
Problem 1: Longest Paths
Given an undirected graph G = (V, E) with positive edge weights we for each edge e ∈ E, give
a dynamic programming algorithm to compute the longest path in G from a given source s that
contains at most n edges.
(Hint: Let A[v, k] denote the weight of the longest path from s to node v of at most k edges).
Solution
Initialize A[v, 1] = wsv if (s, v) ∈ E, A[v, 1] = 0 otherwise.
A[v, k] = max{A[v, k − 1], maxu:(u,v)∈E {wuv + A[u, k − 1]}}
Correctness: The problem has optimal substructure. Take a maximum weight path from s
to t in atmost k steps. If this path is {s, u1 , u2 , · · · , uj , t}, then the maximum weight path
from u1 to t in atmost k − 1 steps must be {u1 , u2 , · · · , uj , t}.
Perform induction on k. The base case k = 1 is trivial. Assume it is optimal for k. To
prove optimality for k + 1 using contradiction, assume that the algorithm is not optimal.
This implies that there exists a u ∈ V such that the maximum weight path to u in k steps is
greater than A[u, k]. But since the algorithm is optimal for k, this is impossible. Therefore
the algorithm is optimal for k + 1.
Running time: Any path can have atmost |V | steps. For any k, the cost is O(|V | + |E|)
since for each node v the cost of computing A[v, k] is proportional to 1 + degree(v). Thus
the total runtime is O(|V |(|E| + |V |)).
Problem 2: Moving in a Grid
Imagine that you are placed on a grid with n spaces in every row and n spaces in every column.
You can start anywhere along the bottom row of the grid, and you must move to the top row of
the grid. Each time you move, you can either move directly up (staying in the same column, but
moving up a row), up and to the left (moving over one column and up one row), or up and to the
right (moving over one column and up one row). You cannot move up and to the left if you are in
the leftmost row, and you cannot move up and to the right if you are in the right most row.
Each time you move, you are either paid or pay; that is, every legal move from square x to
square y is assigned a real value p(x, y). Sure, p(x, y) can also be 0.
Give a dynamic programming algorithm to compute your sequence of moves to receive the
maximum payoff to move from the bottom of the grid to the top of the grid. (Your maximum
payoff may be negative.) You must calculate the value of the optimal solution (i.e., the payoff) and
, Homework #9: April 12, 2018 2
the solution itself (i.e., the sequence of moves). Again, you can start at any square in the bottom
row and end in any square in the top row.
