CSC 226

Reading Guide

When I give several options for readings (separated by 'or'), the first reading I list is the one I most highly recommend.

For any Roughgarden (R) readings, do try the quizzes. The quizzes are there to make sure you are thinking while reading.

These two chapters (Chapters 1 and 2) do not introduce the RAM model, but I'll mention the RAM model in class.
For Chapter 1, students wanting a deeper understanding should read Chapter 1 closely. Other students may decide to skim over the coverage of Karatsuba multiplication. For all students, even though you saw MergeSort in CSC 225, it is still good to see Roughgarden's coverage of MergeSort to become more familiar with the author's style of thinking.

I equally recommend the reading from KT or the reading from Roughgarden. Non-native English speakers may have an easier time with the reading from KT. The reading from Roughgarden uses a correctness proof strategy based on the "minimum bottleneck property", whereas the reading from KT uses a proof strategy based on the "cut property". In class, I will use the "cut property". Students wanting a deeper understanding are recommended to do the Roughgarden reading and then to use the KT reading to reinforce understanding of my lecture.

I believe the reading from Roughgarden should be easier to follow (explanations are more detailed) than the reading from KT. Even if you did the KT reading for MSTs, it should be fine to switch to the Roughgarden reading for Union-Find.

The Roughgarden reading doesn't explain the runtime analysis for Dijkstra's algorithm until Chapter 10. It is fine if you don't look at Chapter 10. In class, we will see how the runtime analysis of Dijkstra's algorithm is essentially the same as the runtime analysis of Prim's algorithm.

The Roughgarden reading is recommended because I think it will give you more intuition about how to think of Bellman-Ford in a dynamic programming way. Also, CLRS 4th covers Bellman-Ford already in Chapter 22 (or Chapter 24 for CLRS 3rd). Roughgarden's order better matches the course.

Either reading option is great. The Roughgarden reading covers the Weighted Independent Set problem, which is is quite related to the Weighted Interval Scheduling problem that we covered in class. The Kleinberg and Tardos reading covers the Weighted Interval Scheduling problem, so for for reviewing what we did in class, I suggest reviewing the Kleinberg and Tardos reading .

I suggest the Avrim Blum reading because it is short and yet comprehensive enough; my lecture will follow this reading. That said, if you find the reading difficult (not enoguh is explained for you), then I suggest the reading from CLRS or the reading from Roughgarden. The Roughgarden reading will be longer (which is why I listed it as the last option), but the plus side is that the explanations might be better for your understanding.

My absolute minimum expectation is that all students read and understand Chapter 19. This won't give you everything you need to know about complexity for this course (because Chapter 19 is a bit high-level), but it will give you a great overview and great intuition about the major ideas from complexity that we will cover.
In Chapter 22, you'll note that each of Sections 22.5 through 22.8 prove that a particular problem is NP-Hard, but I only included Section 22.5 (Independent Set is NP-Hard) in the reading. I feel that this proof is not too difficult to follow and gives you a clear example of a not-super-easy reduction. While the reduction might be on the easier side to understand, it is doubtful that it will seem easy for someone to invent this reduction from scratch. By seeing examples of reductions, you should be able to get better at being able to come up with reductions in the future.
Chapter 23 formally defines the complexity class of NP and formally defines both NP-hardness and NP-completeness. Yet, it is not that technically difficult. One exception is Section 23.3.5. This section might not be easy to follow. Don't worry if you can't follow Section 23.3.5; it's not essential for this course.