5 Questions about Dynamic algorithm and sequence

1. Suppose your class is on a field trip to an island with n towns on it, connected by m townto-town buses (which run in both directions), run by c companies. Each company’s buses are a different colour, and there can be buses from two or more companies running between two towns. You have a map showing which companies run buses between which towns. The drivers have a relaxed attitude to schedules and the buses run often, so there’s no telling which buses will be arriving and leaving next. Your classmate Ryan has wandered off and got lost and you’re (somewhat reluctantly) trying to find him. You’d told him which buses the class was supposed to take during the day, and given him tickets from the appropriate companies, the same colours as the buses and stapled together in the right order. Ryan didn’t remember which towns the class was going to visit, however, so he always took the first bus he saw of the colour of the next ticket, tearing off that ticket and giving it to the driver. Design a polynomial-time dynamic-programming algorithm that, given the map of the bus routes, Ryan’s starting point and the colours of the buses he took, calculates the probability Ryan is in each of the n towns. For example, if the map is as shown below and Ryan started in town A and took a red bus, a green bus, a blue bus and another green bus, then he could have gone A-B-C-D-B, A-B-D-A-C, A-B-D-C-A, A-B-D-C-B, A-C-A-B-C, A-C-A-B-D, A-C-A-D-B, A-C-B-A-C . The probability Ryan went first from A to B is 0.5, and the probability he went first from A to C is 0.5. Therefore, after one trip, the probability he was in B is 0.5 and the probability he was in C is 0.5. The probability Ryan’s second trip took him from B to C is 0.5 times the probability he was in B, or 0.25. The probability it took him from B to D is also 0.5 times the probability he was in B, or 0.25. The probability it took him from C to A is 0.5 times the probability he was in C, or 0.25. The probability it took him from C to B is 0.5 times the probability he 1was in C, or 0.25. Therefore, after two trips, the probability is 0.25 he was in any particular town. The probability Ryan’s third trip took him from A to B is 0.5 times the probability he was in A, or 0.125. The probability it took him from A to D is 0.5 times the probability he was in A, or 0.125. The probability it took him from B to A is the probability he was in A, or 0.25. The probability it took him from C to D is the probability he was in C, or 0.25. The probability it took him from D to A is 0.5 times the probability he was in D, or 0.125. The probability it took him from D to C is 0.5 times the probability he was in D, or 0.125. Therefore, after three trips, the probabilities Ryan was in A, B, C, D are, respectively, 0.25 + 0.125 = 0.375 (the probability his third trip took him from B to A plus the probability it took him from D to A), 0.125, 0.125 and 0.125 + 0.25 = 0.375 (the probability his third trip took him from A to D plus the probability it took him from C to D). You can compute the probability of Ryan being in a particular town after four trips and five trips similarly. Isn’t it lucky you’re on an island, so you can’t accidentally lose Ryan forever? (Hint: first design an algorithm that computes the number of ways Ryan could have ended up in a town, and then modify it to compute the probability.) A B C D 2. Your professor Travis told your TA Sarah that he was going to ask you to modify the code in the lecture notes for computing edit distance, to compute an optimal alignment using only one pass through the matrix.* (The question on Assignment 5 allows filling in the matrix and then walking back from the bottom right corner to the top left corner to compute the alignment.) Travis claimed it was possible by keeping two more arrays, B[0..m, 0..n] and C[0..m, 0..n], where B[i, j] is a pointer to a string of length O(m + n) containing the top line in an optimal alignment of S[1..i] to T[1..j], and C[i, j] is a pointer to a string of length O(m+n) containing the bottom line in that alignment. To compute B[i, j], we sprintf into an empty string either B[i − 1, j] or B[i − 1, j − 1] or B[i, j − 1], followed by either S[i] or ‘-’. To compute C[i, j], we sprintf into an empty string either C[i − 1, j] or C[i − 1, j − 1] or C[i, j − 1], followed by either T[j] or ‘-’. Sarah correctly pointed out that sprintfing a string of length O(m + n) takes O(m + n) time, so Travis’s solution takes cubic time. Help Travis by figuring out how to modify his solution to use quadratic time again. *Yes, this question is based on a true story. 2(Hint: pointers are your friends!) Bonus (worth 10% of the midterm): Can you reduce the space usage to O((m + n)k), assuming you’re given the edit distance k between S and T? (Hint: banded dynamic programming and garbage collections are your friends!) 3. For the problem Longest Kind-Of Increasing Subsequence (LKOIS), we’re given a sequence S[1..n] of integers and asked to find the longest subsequence S 0 of S such that S 0 [i − 1] − 3 ≤ S 0 [i] for 1 < i ≤ |S 0 |. Give an O(n log n) algorithm for LKOIS. 4. For the problem Partition, we’re given a set S of positive integers that sum to 2t and asked if there is a subset of S that sums to exactly t. Prove Partition is NP-complete by ˆ showing Partition is in NP, ˆ reducing one of the NP-complete problems we’ve seen in class to Partition. 5. Write a program that, given a list of the edges in a connected graph G on the vertices 1, . . . , n, in polynomial time outputs a Boolean formula F that is satisfiable if and only if G has a Hamiltonian path. You can assume the list of edges looks something like (1, 2) (1, 3) (4, 2) (6, 5) (5, 3) with one pair per line, and your output should consist of a single line containing copies of space, (, ), AND, OR, NOT and variables that look something like x1, x2, etc. Requirements: in word doc