Category: Readings

Before Sunday’s pre-class quiz: Read section 8.3; theorems 8.12, 8.14 and the subsection called “General Strategy for Proving New Problems NP-Complete” from section 8.4; one of sections 8.5, 8.7, and 8.8; and again read through 8.10 to tie these together.

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!

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

Before Sunday’s pre-class quiz: Read sections 4.2 or 4.3 (your choice, though many of you may have already read 4.2!) and section 4.4. If you decide to read section 4.3, you may want to also look at this document that provides examples illustrating the five cases in the proof of Theorem 4.12.

Before Sunday’s pre-class quiz: Read sections 3.5, 3.6, 4.1, and 4.2. This will start you in on greedy algorithms. Note that we’ll start working (in the week after this pre-class quiz) on greedy algorithms via a graph example, bridging the graphs and greedy algorithms sections.

Before Sunday’s pre-class quiz (pquiz): Our upcoming readings for the week of Jan 15 to Jan 21 are: Sections 3.1, 3.2, 3.3, and 3.4. Sections 3.1-3.3 should be largely review, with section 3.4 providing a (hopefully!) new application area to explore.

(Readings will slow down after this week, as we exit “review territory” in the textbook.)

Before Sunday’s pre-class quiz (pquiz): Read Chapter 2 of the textbook. Most of this should be review! Sections 2.3 and 2.4 are especially valuable for applied review of asymptotic analysis. This is what you should be good at to be awesome computer scientists. Work through the asymptotic analysis worked example. Here’s the blank worksheet and the screencast solution.

Please finish Chapter 1 and watch and work through the Unequal Stable Marriage Problem video playlist.  Here is a blank copy of the problem. (Suggestion: print the blank problem and try it, but after each major section or if you’re stuck even briefly, let the screencast help! This is not the way to study for an exam, but it will prepare you for class.)

This week and always, the pre-reading quiz also lists the readings it assesses in its description. So, if you’re ever in doubt, just check the quiz! (If we mess up and post different readings, just tell us on Piazza! 🙂