## Lectures

It is recommended that students take careful notes in class, which might be based on the course notes.

### Lecture Schedule (may be updated as needed)

Chapter numbers under "Topic" refer to the textbook, while the chapter numbers under "Notes" refer to the posted lecture notes.

Lec | Topic | Notes | Handouts | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 |
Course Overview & Motivation for DS, Review of Memory Allocation | Chapters 1, 2 | handout1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

2 |
Review: Streams & Recursion | Chapters 3, 4 | handout2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

3 |
Recursion | Chapters 4 | handout3 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

4 |
Linked Lists | Chapters 5 | handout4 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

5 |
Linked Lists, ADTs, Classes, Objects | Chapter 5, 6, 7 | handout5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

6 |
Runtime Analysis | Chapters 8 | handout6 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

7 |
Runtime and Array Lists | Chapters 8, 9 | handout7 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

8 |
Amortized Runtime, Stacks, Queues | Chapters 10, 11 | handout8 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

9 |
Operator Overloading | Chapters 12 | handout9 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

10 |
Operator Overloading and Copy Constructors | Chapter 12 | handout10 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

11 |
Inheritance | Chapters 14 | handout11 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

12 |
Polymorphism | Chapters 14 | handout12 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

13 |
STL, Exceptions, Searching | Chapters 13, 15, 16 | handout13 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

14 |
Sorting Algorithms | Chapter 17 | handout14 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

15 |
Midterm Review | handout15 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

16 |
Sorting Algorithms | Chapter 17 | handout16 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Midterm -- Thursday, March 1stLocation: TBA |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

17 |
Templates, Intro to Graphs | Chapters 18, 20 | handout17 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

18 |
Graph Search Algorithms | Chapters 20 | handout18 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

19 |
Backtracking Search and Intro to Trees | Chapters 4, 21 | handout19 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

20 |
Tree Traversals, Priority Queues, and Heaps | Chapters 21, 22 | handout20 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

21 |
Heaps, Dijkstra | Chapter 22, 23 | handout21 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

22 |
A*, Balanced Binary Search Trees | Chapters 23, 24 | handout22 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

23 |
AVL Trees | Chapters 24 | handout23 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

24 |
AVL Trees, Log-structured Merge Trees | Chapter 24, 29 | handout24 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

25 |
Splay Trees | Chapter 30 | handout25 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

26 |
Hash Tables | Chapters 28 | handout26 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

27 |
Hash Functions | Chapters 28 | handout27 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

28 |
Bloom Filters and Tries | Chapter 28, 32 | handout28 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

29 |
Tries and Suffix Trees | Chapter 32 | handout29 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

30 |
Final Review | handout30 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Final -- Wednesday, May 9th 11am Location: TBD |