CPSC 035: Schedule
Schedule
This page contains the schedule and lectures for CS35. Each week includes a summary, lecture videos, and a link to your lab assignment. You can learn more about how the course will work in the introductory video or on the course policies page.
The discussion question icon (
) indicates the video containing the discussion question each week. Make sure you have watched at least as far as this video before your discussion group section. Videos will be posted at least three days in advance of when you need to watch them and often before.
[+]Week 1 - Introduction to C++
Lecture Videos - Week 1 Playlist - Materials
- Course Introduction (8:37)
- Hello World in C++ (11:01)
- Compilation (4:53)
- Input, Local Variables, and Conditions (11:13)
- Value Types (8:54)
- While Loops (4:49)
- For Loops (6:31)
- Functions (7:13)
- Recursive Functions and Stack Diagrams (13:42)
- Statically-Allocated Arrays (8:04)
- Dynamically-Allocated Arrays (18:56)
- Compiler Errors and Uninitialized Variables (12:00)
- Files (7:29)
- Goldwasser and Letscher: Ch 1-6
- Schaffer: Ch 1
- Syllabus Quiz (Due on Thursday, September 10th @ 11:59pm EDT)
- Lab 1 Assigned: Gitting Started (Due on Wednesday, September 16th @ 11:59pm EDT)
[+]Week 2 - Arrays, Objects, and Memory
Lecture Videos - Week 2 Playlist - Materials
- Separate Compilation (11:11)
- Classes and Objects (13:29)
- Methods (12:42)
- Constructors and Permissions (16:58)
- Subclassing and Polymorphism (18:26)
- Dynamically-Allocated Arrays of Dynamically-Allocated Objects (9:04)
- Command-Line Arguments (6:50)
- GDB Tutorial (6:09)
- Goldwasser and Letscher: Ch 7, 8, 12
- Quiz (Due on Thursday, September 17th @ 11:59pm EDT)
- Lab 1 Due: Gitting Started (Due on Wednesday, September 16th @ 11:59pm EDT)
- Lab Reflection
- Lab 2 Assigned: PicFilter (Due on Wednesday, September 23rd @ 11:59pm EDT)
[+]Week 3 - Big-O; Merge Sort
Lecture Videos - Week 3 Playlist - Materials
- Basic Functions and Big-O (8:01)
- Big-O Proofs (4:51)
- Definition of Runtime (3:59)
- Computational Problems, Algorithms, and Runtime (7:02)
- Discussion Prompt about Computational Resources (2:49)
- Basics of Sorting, Selection Sort, and Insertion Sort (19:50)
- Merge Sort (9:34)
- Valgrind Tutorial (9:12)
- Schaffer: Ch 3, Ch 7 Secs 1,2,4,5
- Quiz (Due on Thursday, September 24th @ 11:59pm EDT)
- Lab 2 Due: PicFilter (Due on Wednesday, September 23rd @ 11:59pm EDT)
- Lab Reflection
- Lab 3 Assigned: Shapes (Due on Wednesday, September 30th @ 11:59pm EDT)
[+]Week 4 - Quick Sort; Linked Lists
Lecture Videos - Week 4 Playlist - Materials
- Quick Sort (12:12)
- Quick Sort Implementation (2:59)
- Review of Sorting Algorithms (3:08)
- Abstract Data Types (12:45)
- ADTs and Templatization in C++ (8:45)
- Implementing Linked Lists (17:11)
- Size of Linked Lists (9:22)
- Schaffer: Ch 4 Sec 1
- Quiz (Due on Thursday, October 1st @ 11:59pm EDT)
- Lab 3 Due: Shapes (Due on Wednesday, September 30th @ 11:59pm EDT)
- Lab Reflection
- Lab 4 Assigned: MergeSort and Big-O (Due on Wednesday, October 7th @ 11:59pm EDT)
[+]Week 5 - Array Lists; Stacks
Lecture Videos - Week 5 Playlist - Materials
- Introducing ArrayList (10:36)
- Implementing ArrayList: Fields and Invariants (11:56)
- Implementing ArrayList: Methods (13:52)
- Time Complexity of List Algorithms (14:11)
- Stacks (4:59)
- Stack Applications and Implementation (8:46)
- Unit Testing (12:17)
- Schaffer: Ch 4 Secs 2-3
- Quiz (Due on Thursday, October 8th @ 11:59pm EDT)
- Lab 4 Due: MergeSort and Big-O (Due on Wednesday, October 7th @ 11:59pm EDT)
- Lab Reflection
- Lab 5 Assigned: ASCIImation (Due on Wednesday, October 14th @ 11:59pm EDT)
[+]Week 6 - Queues; Induction and Recursive Invariants
Lecture Videos - Week 6 Playlist
- Queues (4:10)
- Queue Applications and Implementation (6:14)
- Push and Pop Game (4:30)
- Mathematical Induction (11:52)
- More Examples of Mathematical Induction (10:23)
- Search Problems and Ordered Collections (11:29)
- Schaffer: Ch 3
- Quiz (Due on Thursday, October 15th @ 11:59pm EDT)
- Lab 5 Due: ASCIImation (Due on Wednesday, October 14th @ 11:59pm EDT)
- Lab Reflection
- Lab 6 Assigned: Labyrinth (Due on Wednesday, October 28th @ 11:59pm EDT)
[+]Week 7 - Binary Trees
Lecture Videos - Week 7 Playlist - Materials
- Dictionaries (11:35)
- Sorted Array Dictionary (6:32)
- Binary Search Trees: Introduction (7:23)
- Some Kinds of Trees (16:07)
- A Binary Search Tree Data Structure (15:01)
- BST Algorithm: Get (8:12)
- BST Algorithm: Insert (11:57)
- BST Algorithm: Remove (15:13)
- Complexity of BST Algorithms (5:37)
- Tree Traversals (8:09)
- Schaffer: Ch 5 Secs 1-4
- Quiz (Due on Thursday, October 22nd @ 11:59pm EDT)
- Lab 6 Work: Labyrinth (Due on Wednesday, October 28th @ 11:59pm EDT)
[+]Week 8 - Balanced Binary Trees
Lecture Videos - Week 8 Playlist
- Balanced Binary Search Trees and Rotations (9:43)
- Examples of Unbalanced BST's (2:51)
- AVL Tree Insert Operation (12:46)
- AVL Tree Remove Operation (4:11)
- BST Animations
- AVL Tree Animations (Note: they label each node with height + 1.)
- Schaffer: Ch 13 Sec 2
- Quiz (Due on Thursday, October 29th @ 11:59pm EDT)
- Lab 6 Due: Labyrinth (Due on Wednesday, October 28th @ 11:59pm EDT)
- Lab Reflection
- Lab 7 Assigned: Binary Search Trees (Due on Wednesday, November 11th @ 11:59pm EST)
[+]Week 9 - Priority Queues
Lecture Videos - Week 9 Playlist - Materials
- Priority Queues (12:21)
- Heaps (10:07)
- CompleteArrayListTree (13:36)
- Heap Operations (18:38)
- Heapification (18:12)
- Schaffer: Ch 5 Sec 5, Ch 7 Sec 6
- Quiz (Due on Friday, November 6th @ 11:59pm EST)
- Lab 7 Work: Binary Search Trees (Due on Wednesday, November 11th @ 11:59pm EST)
[+]Week 10 - Hash Tables
Lecture Videos - Week 10 Playlist
- Runtime of Dictionary Operations (5:14)
- HashTables and a Simple Example (3:21)
- Hash Functions (1:24)
- More About Hash Functions and Examples (4:56)
- HashTables with Linear Probing (10:47)
- HashTables with Chaining (8:15)
- Schaffer: Ch 9 Sec 4
- Quiz (Due on Thursday, November 12th @ 11:59pm EST)
- Lab 7 Due: Binary Search Trees (Due on Wednesday, November 11th @ 11:59pm EST)
- Lab Reflection
- Lab 8 Assigned: Hash Tables (Due on Wednesday, November 18th @ 11:59pm EST)
[+]Week 11 - Graphs and Graph Algorithms (Part 1)
Lecture Videos - Week 11 Playlist - Materials
- Graphs (9:10)
- Graph Terminology By Example (17:34)
- Trees as Graphs (8:21)
- Graph Implementations (19:47)
- Depth-First Search (15:30)
- Breadth-First Search (16:27)
- Schaffer: Ch 11
- Quiz (Due on Thursday, November 19th @ 11:59pm EST)
- Lab 8 Due: Hash Tables (Due on Wednesday, November 18th @ 11:59pm EST)
- Lab Reflection
- Lab 9 Assigned: Graphs (Due on Friday, December 4th @ 11:59pm EST)
[+]Week 12 - Graphs and Graph Algorithms (Part 2)
Lecture Videos - Week 12 Playlist
- All-Lengths BFS (14:29)
- Dijkstra's Algorithm (19:19)
- More Graph Problems (3:17)
- Topological Sorting (10:18)
- Runtime Analysis of Graph Algorithms (8:34)
- Schaffer: Ch 11
- Lab 9 Due: Graphs (Due on Friday, December 4th @ 11:59pm EST)
- Lab Reflection