Home
Syllabus
Classwork
printable version
Section F11:
[1]
Section F16:
[1]
Section F18:
[1]
[2]
[3]
Section F20:
[1]
Section F23:
[1]
[2]
[3]
Section F25:
[1]
[2]
Section F27:
[1]
In the knapsack problem, we imagine we're given some capacity c and a list of n weights w0, w1, … wn − 1. We saw in class that we can solve it using dynamic programming in O(c ⋅ n) time based on the following recurrence.
Suppose our knapsack also has a limit that restricts it from holding more than k items? How can we modify our recurrence to lead to a dynamic programming solution that takes O(c ⋅ n ⋅ k) time?
Recall that we could find a dynamic programming solution to the edit distance problem using the following recurrence.
Suppose we decide that adding an extra apostrophe is not a serious error, and so we want to count it as just a half-point in the distance formula. Thus, the distance from wits to it's is 1.5 steps rather than 2 as by the above recurrence. How could we modify the recurrence to address this?
Consider the following recursive algorithm.
public static int f(int n, int r) {
if(r == 0 || r >= n) return 1;
else return f(n - 1, r - 1) + f(n - 1, r);
}
Using dynamic programming, convert this into a method that takes O(n ⋅ r) time.
public static int f(int n, int r) {
int[][] sub = new int[n + 1][r + 1];
for(int ni = 0; ni <= n; ni++) {
for(int ri = 0; ri <= r; ri++) {
if(ri == 0 || ri >= ni) sub[ni][ri] = 1;
else sub[ni][ri] = sub[ni - 1][ri - 1] + sub[ni - 1][ri];
}
}
return sub[n][r];
}
Suppose we are playing a series of games against an opponent for which we have a probability p of winning, and we want to know the probability that we'll win k of the next n games against our opponent. Write a recurrence for the problem leading to a dynamic programming algorithm taking O(n ⋅ k) time.
A roadside advertising company hires you to find an algorithm for selecting billboard sites. They have rights to n locations along a road, each identified by its mile marker mi. They know the revenue ri that will be earned from each potential location. However, they are not allowed to erect billboards within 10 miles of each other.
Construct an algorithm that determines the maximum revenue that can be obtained by building at most k billboards.
Define R(i, j) as the best revenue that can be earned by erecting a billboard at location i and j − 1 billboards at location previous to i. This can be computed using the below recurrence.
Once we have this, we return the largest value of R(i, k) over all i.
What distinguishes an abstract data type from a data structure? Give an example of each.
An abstract data type is simply a list of operations that will typically be performed on a set of data, without any implementation of those operations. A data structure is a particular way of structuring data in memory.
An example of an abstract data type is a set, into which one can add new elements, remove an element, or query whether an element lies within the set. An example of a data structure is a hash table, which can be used to implement the set operations.
Another example of an abstract data type is a priority queue, while an example data structure is a heap, which happens to be very suitable for implementing the operations associated with a priority queue.
Why use the Bellman-Ford algorithm for finding the shortest path between two vertices in a graph, when Dijkstra's algorithm does the same thing and is faster?
If the graph contains any edges with negative weights, then Dijkstra's algorithm does not find the correct answer. But Bellman-Ford does (assuming there are no cycles whose total weight is negative).
We can model a data network as a directed graph, with each vertex corresponding to a router and each edge corresponding to a connection between routers. In routing data through a network, there is a time delay associated with going through a connection — but there is also a time delay associated with passing through the router from one connection to the next. How can we use Dijkstra's algorithm so that it still finds the fastest route between two points in the network?
We can add each router's delay to all its outgoing edges, and then we can run Dijkstra's algorithm on that.
Suppose we have a network of roads, where each road connects two vertices and has an associated length. However, some of the roads are known to be very rough, and we never want to take a route that takes more than a single rough road. How can we efficiently find the shortest route between two points s and t that doesn't traverse more than a single rough road?
For each vertex v, we create two copies of the vertex, v0 and v1, which will be connected with a directed edge of zero length from v0 to v1. For each smooth road from u to v, we include an edge from u0 to v0 and from u1 to v1. For each rough road from u to v, we include a directed edge from u0 to v1 (and from v0 to u1 if it is a two-way road).
We then use Dijkstra's algorithm on this new graph to find the shortest path from s0 to t1. This path can only use a single rough road, since taking a rough road takes it from the v0's to v1's, and after that there is no way to go back. If the shortest acceptable path takes no rough roads, then it will take one of the zero-length directed edges from some v0 to the corresponding v1.
Recall the breadh-first search algorithm.
def bfs(vertices, source):
for v in vertices: v.dist = INFINITY
source.dist = 0
q = new queue()
q.add(source)
while not q.isEmpty():
u = q.remove()
for v in u.neighbors:
if v.dist == INFINITY:
v.dist = u.dist + 1
q.add(v)
A graph is said to be bipartite if the vertices can be divided into two groups, and every edge connects one group to another. Assuming we're given a graph where all vertices are reachable from each other, how can we modify our breath-first search code in order to determine whether our graph is bipartite?
def isBipartite(vertices):
for v in vertices: v.dist = INFINITY
vertices[0].dist = 0
q = new queue()
q.add(vertices[0])
while not q.isEmpty():
u = q.remove()
for v in u.neighbors:
if v.dist == INFINITY:
v.dist = u.dist + 1
q.add(v)
elif v.dist % 2 == u.dist % 2:
return False
return True
(Actually, the elif condition can be just
, since when BFS
discovers a previously-discovered vertex, the vertex's distance
will either be at the same distance from the source, or it will
be one link farther from the source.)v.dist == u.dist
Suppose we know of a way to reduce a problem A to a problem B. If I then learn of an efficient algorithm to solve A, can I also solve B efficiently? Vice versa?
No, an efficient algorithm for A does not imply an efficient algorithm for B. But an efficient algorithm for B does mean we can solve A efficiently.
In the GRAPH COLORING problem, we are given an undirected, unweighted graph and some number of colors; we want to determine whether there is way to assign one color to each vertex so that no two adjacent vertices have the same color.
Argue that GRAPH COLORING is a problem that is within NP.
Here's our algorithm: We assign a random color to each vertex, and then we verify that no edge has two vertices that have been given the same color. If so, we say the graph is colorable with the given colors; and if not, we say the graph is not.
This algorithm's time complexity is O(n + m), so it has the required polynomial-time efficiency. It works correctly if the graph has a valid coloring, because in that case there is a chance (though quite small) that the algorithm happens upon such a valid coloring and identifies it as such, saying yes. And it works correctly if the graph does not have valid coloring, because in that case the algorithm is guaranteed to say no regardless of the random choices made. Thus, this algorithm satisfies all the conditions that NP requires.