Implement and test (in your favorite programming language) one of the following graph algorithms (your choice):
Write (in pseudocode) and analyze (i.e. tell me its run-time in big-O notation) a dynamic-programming solution to the "longest common subsequence" problem. Hand-trace its execution on the example
LCS("abcb", "bacbbc")Design, implement (in real code), and analyze a solution to the "making change" problem: given a list of coin denominations, and an amount of money, give a list of coins whose values add up to that amount, minimizing the number of coins. For example, given the US coin denominations {1,5,10,25,50,100} and the amount 47, an optimal solution would be {1,1,10,10,25}, i.e. two pennies, two dimes, and a quarter.
You may assume that all denominations and the amount are positive integers, that one of the denominations is 1, and that the denominations are given to you in sorted order. Be sure to test your program on different, weird sets of denominations!
Write (in pseudocode) and analyze an algorithm for "Eulerian paths": given an undirected graph without edge weights, tell whether there is a path that travels each edge of the graph exactly once. Extra credit: if so, produce such a path.
Note: I haven't told you how to do this; it'll take some original thinking, but it's not difficult.
Write (in pseudocode) and analyze an algorithm for "Hamiltonian paths": given an undirected graph without edge weights, tell whether there is a path that visits each vertex of the graph exactly once. Extra credit: if so, produce such a path.
Note: I haven't told you how to do this; it'll take some original thinking. If you find an efficient algorithm -- say, O(n2) or O(n3) -- you get an automatic A for the semester, but an algorithm that's merely correct shouldn't be too difficult.
Extra credit: Write (in pseudocode) and analyze an algorithm for "strong connectivity": given a directed graph without edge weights, tell whether every vertex is reachable from every other vertex. Note that the "connectedness" algorithm we did in class isn't enough for this, because that applied to an undirected graph; in a directed graph, it's quite possible that u is reachable from v but not vice versa.
Note: I haven't told you how to do this; it'll take some original thinking.
Extra credit: Write (in pseudocode) and analyze an algorithm for the "traffic capacity" problem (number 3 on my handout of "Some Graph Theory Problems").
The input will be an edge-weighted, directed graph, with each edge weight representing traffic capacity, and specified start and finish vertices. Note that there may be one-way streets, or roads that can carry more traffic in one direction than the other due to construction; that is, the graph is directed.
The output will be an assignment of numbers ("flows") to the edges, each number less than or equal to the capacity of that edge, such that the total flow into each vertex (except start and finish) is equal to the total flow out of that vertex, and the total flow out of start (which will of course be equal to the total flow into finish) is maximized.
Note: I haven't told you how to do this; it'll take some original thinking.
This problem turns out to be widely applicable to other problems that don't immediately look like traffic-flow problems, e.g. number 4 and 6 on my handout.