CSCI 104 - Fall 2017 Data Structures and Object Oriented Design

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 (Ch. 1, C++ Interlude 2) Chapters 1, 2 handout1
2 Review: Streams & Recursion (Ch. 2) Chapters 3, 4 handout2
3 Recursion and Linked Lists (Ch. 2, 4) Chapters 5, 6 handout3
4 Linked Lists and Abstract Data Types: Set, List, Dictionary/Map (Ch. 1, 4, 8) Chapters 7, 8 handout4
5 Classes, Objects, and Runtime Analysis (Ch. 10, C++ Interlude 1) Chapter 8 handout5
6 Runtime Analysis (Ch. 10) Chapters 9, 10 handout6
7 Array Lists and Amortized Runtime (Ch. 3, 9) Chapters 11, 12.1-12.4 handout7
8 Stacks, Queues, and Operator Overloading (Ch. 6, 7, 13.1, 13.2, 14.1, C++ Interlude 6) Chapters 12.1-12.4 handout8
9 Operator Overloading and Copy Constructors (C++ Interlude 6) Chapters 12.5, 13 No Handout
10 Inheritance (C++ Interlude 2) Chapter 14 handout10
11 Polymorphism, (C++ Interlude 2) Chapters 14, 15 handout11
12 STL Maps and Exceptions (C++ Interlude 3, 8, Appendix H) Chapters 15, 18 handout12
13 Searching, and Sorting Algorithms (Ch. 11, 12) Chapters 16, 17.1-17.3 handout13
14 Sorting Algorithms (Ch. 11) Chapter 17.3-17.6 handout14
15 QuickSort, and Templates (Ch. 11, C++ Interlude 5) Chapter 19 handout15
16 Midterm Review handout16
Midterm -- Friday, October 13th
Location: TBA
17 Intro to Graphs and Graph Algorithms (Ch. 20) Chapters 20, 21 handout17
18 Graph Algorithms (Ch. 20) Chapters 21, 22 handout18
19 Backtracking Search and Intro to Trees (Ch. 5, 15) Chapters 20, 23 handout19
20 Tree Traversals, Priority Queues, and Heaps (Ch. 13.3, 14.2, 15, 17) Chapters 20, 23 handout20
21 Balanced Search Trees: 2-3 Trees (Ch. 19) Chapter 21 handout21
22 2-3-4 Trees, B-Trees (Ch. 19) Chapters 24, 25, 26 handout22
23 AVL Trees (Ch. 19) Chapters 27, 28 handout23
24 Tries and Suffix Trees Chapter 28 handout24
25 Hash Tables and Hash Functions Chapter 28 handout25
26 Hash Tables and Bloom Filters Chapters 29, 30 handout26
27 Bloom Filters and Log-Structured Merge Trees Chapters 31, 32.1 handout27
28 Merge Trees and Splay Trees Chapter 32
29 Final Review
Final -- Monday, December 11th 4:30 p.m. THH 102/121/202