282 Design & Analysis of Efficient Algorithms - Fall 2013 Instructor: Henry Kautz Assignment 2 Due: Friday Oct 4 by 2:00pm, turn-in box in CSB 708 Be sure to follow Homework Rules at http://www.cs.rochester.edu/u/www/courses/282/fall2013/ 1. DPV 2.14. You may describe the algorithm in English rather than pseudocode. 2. DPV 2.23. You may describe the algorithm in English rather than pseudocode. 3. In class we described an algorithm for topological sort of a DAG that used the precount[v] and postcount[v] arrays. The textbook mentions that there is an alternate algorithm that works by repeatedly deleting a source node. Turn this algorithm into pseudocode. Be sure that your algorithm efficiently finds source nodes as they arise, without having to repeatedly scan through the set of vertices. It will be useful to define an array incount[v], which keeps track of the number of edges that go into vertex v. It should be clear how each step is implemented where the graph is implemented using adjacency lists. It is okay to include iteration over the outgoing edges of a vertex v, such as: for all (v, u) in E because it is clear how this can be efficiently implemented, for example using an array Out[v] that points to the list of edges leading out of v. However, a step such as "delete v from G" would need to be broken down into more basic steps. If you are unsure, err on the side of providing more detail. Explain why your algorithm runs in linear time O(|E|+|V|). 4. DVP 3.28. 5-6. Solve DVP 4.19 in two ways: For (5), modify Dijkstra's algorithm to take into account cost[v]. For (6), describe in English how to transform any generalized shortest path problem (one with costs on both vertices and edges) into an ordinary shortest path problem (costs only on edges), such that a solution to the latter can be turned into a solution for the former. (If you are confused about what it means to "transform a problem", think about transforming a path finding problem in an undirected graph into a path finding problem in a directed graph. The transformation is turn the undirected graph G into a directed graph G', where for every edge (a,b) in G there are a pair of directed edges, (a,b) and (b,a).) 7. Shortest path algorithms are used in speech and handwriting recognition systems. Consider a recognition system that starts by breaking the input into words, and then tries to recognize each word. (This is a simplification, because state of the art systems start at the level of phonemes, not words, but the principles are the same.) The sounds are in general ambiguous, so for each position i, the system determines a set of possible words, and assigns a probability to each, according to how closely the sound it hears matches its internal model of the word. For example, suppose the system hears 4 words. Let p(i x) represent the probability that system assigns to word number i being the word x. Further suppose that the system comes up with three word hypotheses for each position, and computes probabilities as follows: p(1 see) = .5 p(1 sea) = .3 p(1 she) = .2 p(2 sells) = .5 p(2 cells) = .3 p(2 shells) = .2 p(3 see) = .5 p(3 sea) = .3 p(3 she) = .2 p(4 sells) = .4 p(4 shells) = .3 p(4 selves) = .3 Using only this information, the probability of a possible sentence (all 4 words) is simply the product of the probabilities of each hypothesis. For example, most probable interpretation of the entire sentence is "see sells see sells", because p(1 see) x p(2 sells) x p(3 see) x p(4 sells) = .5 x .5 x .5 x .4 = 0.05 is the biggest product of one hypothesis for each word. (7A) What is the least probable interpretation, and what is its probability? (7B) What is the probability of "she sells sea shells"? The next stage of the speech recognizer takes into account the probabilities that pairs of words are adjacent. These probabilities are estimated by determining the frequencies of all adjacent pairs of words, or "word bigrams", in an large collection of English texts. Let p(x y) = probability that word x is followed by word y. The symbol "^" means "beginning of sentence" and "$" means "end of sentence", and we treat these as special words. Bigram probabilities are all very small, because of the very large number of bigrams. Following is a table of bigram probabilities, where the value in each row should be multiplied by 10^-3 (that is, 0.001). x 10^-3 p(^ sea) .01 p(^ see) .1 p(^ she) .2 p(cells sea) .007 p(cells see) .04 p(cells she) .01 p(sea cells) .004 p(sea sells) .0001 p(see sea) .001 p(sea selves) .02 p(sea shells) .4 p(see cells) .03 p(see sells) .0001 p(see selves) .05 p(see shells) .2 p(sells sea) .001 p(sells see) .0001 p(sells she) .02 p(sells $) .1 p(she cells) .0001 p(she sells) .1 p(she she) .0001 p(she shells) .01 p(she selves) .0001 p(shells $) .1 p(selves $) .2 p(shells sea) .008 p(shells see) .02 p(shells she) .1 p(the cells) .4 p(the sells) .0001 p(the shells) .4 Taking this information into account, the algorithms determines the probability of a sentence as product of all of its words and all of its bigrams. Thus, the probability of ""see sells see sells" is: p(^ see) x p(1 see) x p(see sells) x p(2 sells) x p(sells see) x p(3 see) x p(see sells) x p(4 sells) x p(sells $) = (.01 x 10^-3) x .5 x (.0001 x 10^-3) x .5 x (.05 x 10^-3) x .5 x (.0001 x 10^-3) x .4 x (.1 x 10^-3) = .01 x .5 x .0001 x .5 x .05 x .5 x .0001 x .4 x .1 x 10^-15 (7C) Evaluate this expression, and compare it to the probability of "she sells sea shells". Finding the most likely interpretation of the sentence can be turned into the problem of finding the shortest path in a generalized DAG (one with costs on both nodes and edges). (7D) Draw a DAG as follows: - There is a source node "^". - There is sink node "$". - There is a node for each word position hypothesis. In this example problem, there are 12 such nodes. - There are edges from "^" to each position 1 hypothesis. - There are edges from each position 4 hypothesis to "$". - There are edges from each position i hypothesis to each position i+1 hypothesis. - The word nodes are labeled with the word hypothesis probabilities. - The edges are labeled with the appropriate bigram probabilities. The product of the probabilities on any path from ^ to $ give the probability of that interpretation of the sentence. However, we have learned about finding shortest paths where costs are additive, not about finding longest paths where costs are multiplicative. So, we have just a little more work to do. Note that a * b > c * d if and only (-log a) + (-log b) < (-log c) + (-log d). Further note the fact that for any number a where 0 <= a <= 1, that (log a) is negative, so (-log a) is positive. (7E) Use these facts to relabel the DAG you created in (7D) so that the costs are positive numbers, and that a shortest path in the generalized DAG gives the most likely interpretation of the sentence. Finally, redraw the graph as a regular DAG, with costs only on edges, not nodes, using the method you created for question (6). EXTRA CREDIT: Do any, all, or none of the following: (7F) EXTRA CREDIT. Sec. 4.7 of the textbook describes a algorithm for finding shortest paths in DAGs only that is simpler than Dijkstra's algorithm. Run this algorithm by hand on the example and show how it finds the most likely interpretation of the sentence. (7G) EXTRA CREDIT. Use an implementation of Dijkstra's algorithm to solve the example problem. You do not have to write your own, you can download one from the web or get the code from another student, as long as you run it yourself. Include a print out the program and the solution it finds. Indicate how you obtained the program. (7E) EXTRA CREDIT. Suppose the set of word hypotheses was extremely large. Describe in English how to modify Dijkstra's algorithm so as to reduce the amount of the work required, at the cost of sometimes not finding the optimal solution.