16f-4800: Algorithms L9
Here are the Lecture 9 annotated slides which include discussing the Matrix chain problem, the Typesetting problem, and the Gerrymandering problem.
In class, we discussed a typesetting algorithm. You can find the java code for that example in
- typeset.java
- and a sample input in charly.txt.
To run the program, first compile it using javac typeset.java and then run it using java typeset charly 42 where 42 represents the margin width. The program displays a lot of the intermediate data such as the S table, the best[] scores, etc.
Video on Matrix Chains
Video on Typesetting
Video on Gerrymandering
- To help with the Tug of War problem on the homework, I am posting slides about a similar problem called the “Gerrymander” problem. The slides begin at page 39 and explain how to define the DP problem. The video below also describes that solution. It begins at 14:24.