CSCI 570 – Summer 2020 – HW 4
Note:
• This homework assignment mainly covers Dynamic Programming.
• The deadline for this homework is Wednesday July 29th by 11:30 PM on
DEN.
Graded Problems
1. Suppose you have a DAG with costs ce > 0 on each edge and a distin-
guished vertex s. Give a dynamic programming algorithm to find the
most expensive path in the graph that begins at s. Prove your algorithms
runtime and correctness. For full credit, your algorithms runtime should
be linear.
2. A palindrome is a string that reads the same forwards and backwards.
Suppose we are given a string S = s1s2s3…sn, and we want to find the
longest palindrome that can be formed by deleting some characters from
the string. Give an efficient dynamic programming algorithm to solve this
problem. Prove its running time and correctness. For full credit, your
algorithm should output which character(s) to delete to form the longest
palindrome.
3. Given a rod of length n inches and an array of prices that contains prices of
all pieces of size smaller than n. Determine the maximum value obtainable
by cutting up the rod and selling the pieces.
4. Given a sequence a1, a2, …, an of n numbers, describe an O(n
2) algorithm
to find the longest monotonically increasing sub-sequence.
5. Solve Kleinberg and Tardos, Chapter 6, Exercise 5.
6. Solve Kleinberg and Tardos, Chapter 6, Exercise 12.
7. Solve Kleinberg and Tardos, Chapter 6, Exercise 20.
1