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
10 Inheritance (C++ Interlude 2) Chapter 14
11 Polymorphism, (C++ Interlude 2) Chapters 14, 15
12 STL Maps and Exceptions (C++ Interlude 3, 8, Appendix H) Chapters 15, 18
13 Searching, and Sorting Algorithms (Ch. 11, 12) Chapters 16, 17.1-17.3
14 Sorting Algorithms (Ch. 11) Chapter 17.3-17.6
15 QuickSort, and Templates (Ch. 11, C++ Interlude 5) Chapter 19
16 Midterm Review
Midterm -- Friday, October 13th
Location: TBA
17 Intro to Graphs and Graph Algorithms (Ch. 20) Chapters 20, 21
18 Graph Algorithms (Ch. 20) Chapters 21, 22
19 Backtracking Search and Intro to Trees (Ch. 5, 15) Chapters 20, 23
20 Tree Traversals, Priority Queues, and Heaps (Ch. 13.3, 14.2, 15, 17) Chapters 20, 23
21 Balanced Search Trees: 2-3 Trees (Ch. 19) Chapter 21
22 2-3-4 Trees, B-Trees (Ch. 19) Chapters 24, 25, 26
23 AVL Trees (Ch. 19) Chapters 27, 28
24 Tries and Suffix Trees Chapter 28
25 Hash Tables and Hash Functions Chapter 28
26 Hash Tables and Bloom Filters Chapters 29, 30
27 Bloom Filters and Log-Structured Merge Trees Chapters 31, 32.1
28 Merge Trees and Splay Trees Chapter 32
29 Final Review
Final -- Monday, December 11th 4:30 p.m. Location TBA