The reading this week is 6.5, 6.6, 6.8 and 8.1 in the Kleinberg and Tardos textbook.
(We’re finishing up Dynamic Programming and diving into NP-completeness in the readings. The readings are a bit behind class at this point. So, you may want to do 8.1 first to get in sync with class and then jump back to Chapter 6 to strengthen your understanding of dynamic programming.)
Posted in Readings
We’re going back to reductions again! Here is a worksheet on a new way to think about and use reductions.
Posted in Handouts
For sample solutions to the live-coding of LCS in various formats, check out:
Posted in Handouts
The reading for this week is section 6.4 in the textbook.
Posted in Readings
Here is a sample solution to our Longest Common Subsequence worksheet.
Posted in Handouts
Live, in concert, Cinda and Steve and the CPSC 320 band coding Longest Common Subsequence!
Here are starter copies of the Longest Common Subsequence Jupyter Notebook in several formats:
You can run Jupyter Notebooks on UBC Syzygy (among other places, including on your own computer).
Posted in Handouts
Here is Assignment #4, composed of the collected tutorial quizzes, solutions to those quizzes, and some extra questions building on the quizzes for the assignment. (Here is LaTeX source, with a .txt extension so the blog lets us post it!)
The assignment is due on Fri 17 Nov at 10PM. HOWEVER, we expect to base some of the midterm problems on these quizzes/assignment. So, we strongly recommend that you create a solid draft solution before the exam (which may not yet be in clean enough form to submit).
Please submit it on GradeScope.
Posted in Assignments
Here is the longest common subsequence worksheet.
Posted in Handouts