| layout | title | nav |
|---|---|---|
default |
Lectures |
lectures |
##Lectures
It is recommended that students take careful notes in class, which might be based on the course notes.
Chapter numbers under "Topic" refer to the textbook, while the chapter numbers under "Notes" refer to the posted lecture notes.| Lec | Topic | Notes | Slides | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | Course Overview – Motivation for DS, Review of Memory Allocation (Ch. 1-2, C++ Interlude 2) | Chapters 1-3, 4.1-4.2 | Overview PDF Memory & Scope PDF |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 2 | Recursion & Linked Lists (C++ Interlude 2) | Chapter 5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 3 | Abstract Data Types: Set, List, Dictionary/Map and Classes (Chapters 1, 8, 18, Interlude 1) Array Lists, Stacks, Queues (Chapters 9, 6, 7, 13.1, 13.2, 14.1) |
Chapters 6, 7, 13, 14 | ADT PDF Classes PDF Queues & Stacks PDF |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 4 | Runtime Analysis (Chapter 10), Amortized Runtime and Operator Overloading (C++ Interlude 5) | Chapter 10 | Runtime PDF Op. Overloading & Copy Semantics PDF |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 5 | Copy Constructors (C++ Interlude 5) and STL Maps (C++ Interlude 7, Appendix I) | Chapters 11 and 15 | Copy Semantics PDF STL PDF | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 6 | Inheritance & Polymorphism(C++ Interludes 1, 2, 4) | Chapters 12 | Make PDF
Inheritance PDF Polymorphism PDF |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 7 | Sorting Algorithms (Chapter 19) | Chapter 19 | Sorting PDF | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 8 | Searching (Chapters 17), Templates & (C++ Interlude 1) | Chapter 17, 8 | Search PDF Templates PDF |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 9 | Qt and Event-Based Programming Midterm Review |
Chapter 18 | PDF Sample Midterm (no solutions) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 10 | Exceptions (C++ Interlude 3) | Chapter 9 | Exceptions PDF | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Midterm -- Tuesday, June 23rd | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 11 | Intro to Graphs (Chapters 20.1, 20.2), Trees and their Implementations (Chapter 15) and Tree Traversals and Search (Chapter 16) Priority Queues and Heaps (Chapters 13.3, 14.2, 17) |
Chapter 20-22 | Graphs PDF Heaps PDF |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 12 | Graph Algorithms (Chapters 20.3.1, 20.3.2) Backtracking Search (Chapter 5) |
Chapter 20 | Graph Algs. PDF Backtracking PDF |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 13-14 | Balanced Search Trees (Chapter 19) | Chapters 23-24 | 2-3 Tree PDF 2-3-4 & RB-Tree PDF |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 15 | Iterators (C++ Interlude 6) | 16 | Iterators PDF | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 16 | Hash Tables (C++ Interlude 3) | Chapters 9, 25-26 | Hashing PDF | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 17 | Bloom Filters and Tries(Chapter 18, lecture notes), Skip Lists, and Splay Trees | Chapter 26 | Other Maps/Sets PDF SkipLists PDF Splay TreesPDF |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 18 | More C++ Topics & Design Patterns Final Review |
TBA | PDF Sample Final (no solutions) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Final -- Tuesday, July 21st 5:00 p.m. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||