Today we’ll continue to talk about NP-completeness and reductions.
- For next class, please read section 8.3 and complete the pre-class quiz on 8.2 and 8.3.
- Here’s a sample solution to our current notes on reductions and NP-completeness.
- Here is code implementing memoized and DP versions of Longest Common Subsequence. Here’s a Jupyter Notebook version and plain Python version. (I use the CPSC 103 test library, but it should be pretty easy to remove that dependency!)
- Start in on the assignment, due next week and posted at the end of the day Friday!