CSC 226

Reading Guide

General guide on readings

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.

• Reading for 5/11 (Intro, Big-O, RAM model)
• Notes on the Roughgarden (R) 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.
• Reading for 5/14 (MSTs)
• 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.
• Reading for 5/25 (Union-Find)
• 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.
• Reading for 5/28 (Single-source shortest paths, Dijkstra's algorithm)
• 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.
• Reading for 6/4 (Bellman-Ford algorithm, Floyd-Warshall 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.