Here’s the full assignment, with LaTeX source (extension .txt for posting), and the figure with the boxes.
The assignment is due Thursday 24 Nov at 10PM. For more details, see the assignment itself. Have fun!
Month: November 2016
Assignment #5, Tue 1PM Edition
Here’s the assignment version of the Tue 1PM quiz.
Lecture 2016/11/14
Today we continue to talk about reductions and NP-completeness.
- Please read section 8.3 by Wednesday and complete the pre-class quiz on 8.2 and 8.3 due at noon on Wed.
- Here’s a sample solution to our current notes on reductions and NP-completeness.
- Don’t forget this week’s quiz, and start in on the assignment.
Assignment #5, Mon 3PM Edition
Here’s the assignment version of the Mon 3PM quiz.
Assignment #5, Mon 9AM Edition
Here’s the assignment version of the Mon 9AM quiz.
Protected: Sample Solution to Assignment #4
Implementations of LCS
This should be considered “just for fun” handouts, as long as you are confident you are capable of implementing something like LCS in whatever your favorite language is, given sufficient time.
With that caveat, here’s a PDF of our LCS implementation, with some extra embellishments toward the end, including patching the code we didn’t quite finish.
Lecture 2016/11/09
Today we’ll start talking about NP-completeness with special guest host and TA Raunak Kumar! Thanks, Raunak!
- Here are our notes on NP-completeness.
- Don’t forget that there’s an assignment due Thursday!
- Please read Section 8.2 and skim Section 8.10 for this coming Monday. Keep skimming 8.10 as we read each section. It will help to keep the problems straight in your head! (Note that we won’t discuss every type of problem categorized in 8.10, however.)
- No reading quiz for Monday. (It’s a long weekend; have fun, remember those who have served the country, but do think for at least a while about algorithms!)
Lecture 2016/11/07
Today we’ll do some live-coding. Fun! Adventure! Steve making ridiculous mistakes and writing strange-looking code! 🙂
- For Wednesday, please read Section 8.1 (and the very important intro to Chapter 8) and complete the reading quiz due at noon on Wednesday.
(Note: I know this is a long-ish section. I hope you’ll find that, since we’ve already discussed reductions many times, this will be a new twist on how to use them but not brand new material. Take time over the next week or so to consolidate your understanding of this very important section!)
- No new handouts for today.
- Come to class Wednesday, but don’t forget that Friday is a holiday: no class and no office hours.
Sample solution to DP in 2-D notes
Here is a sample solution to the DP in 2-D notes.