• Section 6.5

Sorry for the late post, but I did at least manage to mention this in both sections 🙂

Subsequent readings will include 6.6 and much of Chapter 8, but there will be no new reading for Friday.

• Section 6.4

• Section 6.3

• Section 6.2

• Section 6.1 (and the introduction to Chapter 6)

Note that this starts as a divide-and-conquer problem and solution. So, it’s great to read right away (up to page 256’s “memoizing” section).

During Reading Break, I thought we should have some reading 🙂

Please read:

• Section 5.3
• Section 5.4

We’ll likely finish Chapter 5 at that point.

Next, we’ll either continue discussing Divide and Conquer for a while with limited new readings (perhaps one or both of the remaining sections) or we’ll move on to Chapter 6.

Since we’re definitely moving on to Chapter 6 eventually, if you want to read ahead, I recommend starting with 6.1 to 6.4 on the completely awesome topic of Memoization and Dynamic Programming.

• Section 5.2
• Wikipedia’s page on the Master Theorem

As you’re reading, think about how Sections 5.1 and 5.2 relate to the cases of the Master Theorem. (The same sorts of tree analyses that we and the textbook will do can also build up a proof of correctness for the Master Theorem.)

• Chapter 5 intro
• Section 5.1

Yes, you have a midterm on the evening of the 10th. So, just skim the reading and come back to it later.

It should be largely review; pay particular attention to the section entitled “Unrolling the Mergesort Recurrence” (~1 page of reading spanning pages 212-213).

• Review all readings so for (Chapters 1, 2, and 3; Sections 4.1-4.7)
• At minimum read through midterm 1 practice problems (better to actually work through them!)

I will also ask you to read Section 5.1 before the Wednesday 11 Feb class (just after the midterm); so, I recommend doing that reading now.

That said, the reading should be largely review; so, skim quickly, paying particular attention to the section entitled “Unrolling the Mergesort Recurrence” (~1 page of reading spanning pages 212-213).

• Section 4.7

Note that this section discusses the running problem we used in class for greedy algorithms, although with a very small twist. (Essentially, they consider edge weights to be “dissimilarities” rather than “similarities”.)

Next up, we’ll be reading Chapter 5. We’ll work through 5.1-5.4. We’ll also discuss the Master Theorem.

(Without mentioning it specifically, Section 5.2 of the textbook describes many pieces needed to derive the Master Theorem.)