Here is our first worksheet on NP-completeness, focusing on Boolean satisfiability.
Be sure you’re keeping up with the reading! There’s a lot to NP-completeness that we won’t get a chance to discuss in class!
Readings for 2018/03/24
Before Sunday’s pre-class quiz: Read sections 6.6 and 8.1 in your textbook. Note that as you read Chapter 8, you will want to visit and revisit 8.10 to get a high-level sense of how NP-complete problems fit into the set of problems you’re learning!
Making Change worksheet sample solutions
Here are sample solutions to the two parts of our making change worksheet:
DP in 2-D worksheet
Attached is our worksheet on a dynamic programming problem where our recurrence has more than one parameter (that’s critical to the recurrence).
Making change worksheets (parts 1 and 2)
Catching up with the pre-class quizzes in readings
We’ve been letting the pre-class quizzes list the readings. In case you’re looking for them here:
- Read by 11 Feb: Section 4.5 and 4.7
- Read by 25 Feb: Section 5.1 and 5.2 plus this Master Theorem entry on Wikipedia.
- Read by 4 Mar: Sections 5.3 and 5.4
- Read by 11 Mar: Sections 6.1 and 6.2
- Read by 18 Mar: Section 6.3 and 6.4
Assignment #4
Here is the full assignment version of Assignment #4 (and latex source with a txt file extension).
The assignment is due Thursday 22 March (later than usual!). (However, if you submit A#4 and your last submission is no later than Tuesday 20 March, we’ll give you one course bonus point.)
MEANWHILE here are the collected quizzes and the collected quizzes with sample solutions.
Deterministic Select, Sample Solution
Here are sample solutions to our live-coding exercise on Deterministic Select in various formats:
Divide and Conquer (quick select) worksheet sample solution
Deterministic Select, Live!
We don’t code a lot in CPSC 320, and that’s intentional. You have lots of coding classes in CPSC. Reasoning about problems, writing about them on paper or whiteboards, designing and analyzing solutions: these are all incredibly important skills to be a successful Computer Scientist, no matter what work you take on.
However, now and then, it’s fun to code. Especially when an algorithm is so completely bizarre that it’s hard to believe it works without trying it.
Enter Deterministic Select.
We’ll do our best to code this rather intricate algorithm live, after working through the ideas that lead up to it. It could even work!
If you’d like to follow along, try opening https://ubc.syzygy.ca. You can then download our blank DSelect Jupyter Notebook to your computer, start your Syzygy server, and use the “Upload” button to upload the notebook onto syzygy. Use the “play”, “up”, and “down” buttons on syzygy to run code and navigate among the cells.
You can also see blank copies in plain python, PDF, or HTML.