282 Design & Analysis of Efficient Algorithms - Fall 2013 Instructor: Henry Kautz Assignment 4 Due: Friday Nov 15 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/. Remember that you *are allowed* to collaborate and use outside sources, as long as you name your collaborators and cite the outside sources used. (If you collaborate or copy and do not cite your sources of help, you risk failing the course or worse.) I recommend, however, that you try hard to solve the problems without help first. The exams as designed to check that you do understand the details of each problem and its solution. Goals for this assignment: - Practice solving original dynamic programming problems. - Understand the idea of reducing problems to linear programming. Become familiar with specific techniques for representing problems involving flows in networks and the notion of duality. The optional extra-credit problems for this assignment are in total worth as much as an entire assignment. The extra-extra credit problems are worth in total another 50% of an assignment. 1. [dynamic programming] DVP 6.7. Palindromic subsequences, like many other string problems, have applications in genetics. A mutation where a piece of DNA is "flipped over" and copied can create a palindromic subsequence. Solve this problem using two different definitions of a palindromic subsequence: (a) Where the elements of the palindrome need not be contiguous (the problem as stated in the book). This was the extra-credit problem on the last exam, so if you solved it then, just reconstruct your solution. (b) Where the elements of the palindrome must be contiguous. 2. [dynamic programming] DVP 6.6. This is an example of using dynamic programming to solve a problem in mathematical group theory. 3. [dynamic programming] DVP 6.12. Here is a dynamic programming problem in computational geometry. Triangularizing polygons is key operation in computer graphics. 4. [linear programming] DVP 7.4. The phrase "solving geometrically" means drawing a plot of the feasible region and the direction of the objective function, and visually identifying the solution vertex. 5. [linear programming] DVP 7.11. Practice with the concept of duality. 6. [linear programming] DVP 7.17. Practice with the concept of max flow. EXTRA CREDIT PROBLEMS: Extra 1-2: Implement the dynamic programs for any two of the three dynamic programming problems above. Your implementation should return the solution itself as well as the value of the solution. Make up at least three test inputs for each. Hand in a print out of your code and the results on your test inputs. Be sure to check that the answers your program returns are sensible! You may use any programming language you like. I'd use Python or Ruby myself for small programs like this, but use whatever language you can program in most easily and quickly. Extra 3. DVP 6.4. Word splitting. Extra 4. DVP 6.20. Optimal binary search trees. Extra 5. DVP 6.21. Vertex cover. EXTRA-EXTRA CREDIT PROBLEMS: Extra-Extra 1-2: Implement solutions to any two of the extra credit problems (DVP 6.4, 6.20, 6.21). As before, make up at least three test instances for each.