General Info
The lectures allow us to explain new material, how it relates to the rest of the course (and what you've learned in other courses), and to show examples of applying the material. From a technical point of view, lectures will not cover anything that is not already in the textbook (or that can be found in other texts or online resources). The values of the lectures is that your instructor provides context and motivation for the material, focuses your attention on the key and more subtle points, and answers questions that arise while you're learning something new.
We will not publish lecture notes. You are expected to read the assigned material, and make your own notes during lectures and tutorials. While making notes, you should not aim to record everything that is said and written during the lecture, but instead write down the main points that will help you to understand the reading material, and to study for exams.
Students often learn a lot from working with one another. You are encouraged to meet with other students from class for this purpose. For example, you might work through exercises in the course text together or discuss any material you found confusing in lecture or in the text.
Tentative Schedule of Lectures
Unless otherwise specified, all readings are from CLRS.
Week and Topic | Readings |
Week 1: Sept 12 –18 ADTs, Priority queues, Heaps |
Review: Appendices A, C; Chapters 2, 3 Chapter 6 |
Week 2: Sept 19–25 Priority queues: mergeable heaps Dictionaries |
Review: Chapter 12; Notes on binomial heaps (from CLRS ed 2). |
Week 3: Sept 26–Oct 2 Balanced Search Trees |
Notes on AVL trees by V. Hadzilacos. Chapter 18 |
Week 4: Oct 3–9 Augmenting Data Structures |
Chapter 14 |
Week 5: Oct 10–16 Lower Bounds |
Section 8.1.; Notes on decision trees;
Notes on adversarial method. Watch video lectures! (See Announcements for links) |
Week 6: Oct 17–23 Probabilistic and randomized analysis Hashing |
Sections 5.1-5.3; Chapter 11; Sections 31.1-31.4; Review of Modular Arithmetic Review of Probability Theory (also take a look at Appendix C) |
Week 7: Oct 24–30 Quicksort |
Chapter 7. |
Week 8: Oct 31–Nov 6 Amortization; Dynamic Arrays |
Chapter 17. |
Nov 7–13 NO CLASS |
|
Week 9: Nov 14–20 Disjoint Sets |
Chapter 21. Log-star analysis. (from CLR 1st ed.) |
Week 10: Nov 21–27 Data structures for Graphs; BFS |
Sections 21.1-21.2 |
Week 11: Nov 28–Dec 4 DFS |
Sections 22.3-22.5 |
Week 12: Dec 5–11 Minimum spanning trees |
Chapter 23 |