CSC265 (Fall 2016): Enriched Data Structures and Analysis

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