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)
Dynamic Programming.
- 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
- Find the LONGEST, NODE-weighted path in this graph with an OPEN start and OPEN end point
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
Dynamic Programming
- 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] - Find LONGEST, EDGE-weighted path from an OPEN start to an OPEN end
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)
Dynamic Programming
- 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
What is the algorithm to find the shortest path in a DAG with a FIXED start?
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
What is the algorithm to find the shortest path in a DAG with an OPEN start?
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}
How do you modify a DAG path algorithm to return the sequence/subproblems?
- 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
