CSCI 104 - Summer 2016 Data Structures and Object Oriented Design

Lecture Videos

Videos for the lecture topics are available.

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 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 PDF
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 Templates (C++ Interlude 1) & Exceptions (C++ Interlude 3) Chapter 8, 9 Templates PDF
Exceptions PDF
8 Sorting Algorithms (Chapter 19), Searching (Chapters 17) Chapter 17, 8 Sorting PDF
Search PDF
9 Qt and Event-Based Programming Chapter 18 PDF
10 Midterm Review Chapter 9 Sample Midterm (no solutions)
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
Midterm -- Thursday, June 23rd in Quiz Section
12 Graph Algorithms (Chapters 20.3.1, 20.3.2)
Backtracking Search (Chapter 5)
Chapter 20 Graph Algs. PDF
Backtracking PDF
13 Balanced Search Trees (Chapter 19) Chapters 23-24 2-3 Tree PDF
2-3-4 & RB-Tree PDF
14 More Red-Black Trees (Chapter 19)
Iterators (C++ Interlude 6)
Hash Tables (C++ Interlude 3)
Chapters 25, 26 Iterators PDF
Hashing PDF
15 Hash Tables + Functions (C++ Interlude 3) Chapters 27 Hashing PDF
16 Bloom Filters and Splay Trees and Skip Lists Chapter 29, 30 SkipLists PDF
Splay TreesPDF
17 Tries and List of Arrays
C++11 Topics & Design Patterns
Final Review
Chapter 28, 31, 32 Merge Trees PDF
Other Maps/Sets PDF
C++11 PDF
Sample Final (no solutions)
Final -- Tuesday, July 19th 9:30 a.m.