Dynamic Programming

Question 1

Decide where to build a Chain of Restaurants along a linear highway.

• at each integer location, i, you’ll make p(i) profit if you build a restaurant there
• you canNOT put two restaurants within ‘k’ miles of eachother

Where should you place the restaurants to maximize profit? (Algorithm)

Answer 1

Dynamic Programming.

1. Draw a DAG where:
   * nodes correspond to integer locations from 0 to N (where N is highway length), and represent the question: what is the sequence of restaurants we can build ending with a restaurant at integer i, to get max profit?
   * edges: draw an edge from i to j if i < j - k

Add node-weights = p(i) for every node i

2. Find the LONGEST, NODE-weighted path in this graph with an OPEN start and OPEN end point

Question 2

Given a sequence of numbers, find the Longest Increasing Subsequence

• Sequence = from left to right (can skip over, but no backtracking)
• increasing = elements in sequence is in ascending order

Answer 2

Dynamic Programming

1. Create a DAG such that:
   * nodes correspond to elements in given sequence and represent the question: “what is the length of the Longest Increasing Subsequence ending at index i”
   * edges: Draw an edge from node i to j if i < j, and A[i] < A[j]
2. Find LONGEST, EDGE-weighted path from an OPEN start to an OPEN end

Question 3

Given a sequence of numbers that can be negative,

Find the Maximum Contiguous Subsequence

• contiguous = canNOT skip elements in between
• find subsequence with greatest Sum (add all elements together)

Answer 3

Dynamic Programming

1. Draw a DAG
   * nodes correspond to indices in given array and represent the question: “what is the Max Contig Subsequence ending at & including index i”?
   * edges: Draw an edge from node i to j if i = j - 1

Make it so the node weight = number value at index i
2. Find the LONGEST NODE-weighted path with an OPEN start and an OPEN end

Question 4

What is the algorithm to find the shortest path in a DAG with a FIXED start?

Answer 4

Initialize all dist(u) = infinity
dist(s) = 0
for each v in V \ {s} (all nodes in set except for start) in LINEARIZED ORDER
dist(v) = min((u,v) in E) {dist(u) + l(u,v)}
Or dist(v) = 0 if there’s no incoming edges

Question 5

What is the algorithm to find the shortest path in a DAG with an OPEN start?

Answer 5

Initialize all dist(u) = infinity
dist(s) = 0
for each v in V \ {s} (all nodes in set except for start) in LINEARIZED ORDER
dist(v) = min {min((u,v) in E) {dist(u) + l(u,v)},
OR 0}

Question 6

How do you modify a DAG path algorithm to return the sequence/subproblems?

Answer 6

1. Initialize a “prev(i) = null” variable for all nodes

2. Inside the for loop, do “prev(i)= j” for the j value that was chosen in the condition