Key Dates

It's likely that the topics will change, but very UNlikely that the dates of recitations, APPs, homeworks, or exams will. Please note the dates you're expected to be present in lecture (otherwise, our CS3000 Attendance Policy Applies.

Follow the schedule below (also on the CS3000 Canvas) for recitation schedules. Tuesday recitations are "official" and we work through practice problems related to course material. Thursday recitations (1:30pm only) are "fun-algo recitations" that run on vibes; we'll solve some problems together, we'll have fun and help prepare you for a potential future interview, but the propblems are not necessarily related to an upcoming homework.

Date Topics/Reading Class Materials APP/Recitation HW
May 5 (M)
  • Overview of CS3000
  • Structure and setup
  • Communicating algorithms
Handouts Lecture Notes & Pseudocode Short-Take Videos
May 6 (T) Ch. 1.3, A.1
  • Linear search
  • Run-time introduction
  • Asymptotic notation
Lecture Notes & Pseudocode Short-Take Videos Recitation 1 (PDF, .tex)
Rec 1 Solns
May 7 (W) Ch. 1.2
  • Algorithm steps vs. asymptotic run-time
  • Sorting
  • Insertion sort
  • Proving correctness: loop invariant
Lecture Notes & Pseudocode Short-Take Videos APP1 (PDF, .tex) due 5/8 @11:30am
APP1 Solns
May 8 (R) Ch. 4
  • Summation Math
  • Best-case, worst-case run-time
  • Recursive sequences
Lecture Notes & Pseudocode Short-Take Videos Fun-algo recitation HW1 (PDF, .tex) due 5/15 @9pm
May 12 (M) Ch. 1.4
  • Recursive algorithms
  • Recusive run-times
  • Solving recurrences: Master method, iteration method
Lecture Notes & Pseudocode Short-Take Videos APP2 (PDF, .tex) due 5/13 @ 11:30am
APP2 Solns
May 13 (T) Ch. 1.4
  • Divide & Conquer
  • Mergesort
Lecture Notes & Pseudocode Short-Take Videos Recitation 2 (PDF, .tex)
Rec 2 Solns
May 14 (W) Ch. 7
  • Divide & Conquer
  • Quicksort
Lecture Notes & Pseudocode Short-Take Videos APP3 (PDF, .tex) due 5/15 @ 11:30am
APP3 Solns
May 15 (R) Ch. 6
  • Data structure: Heap
  • Heaps as arrays
  • Heapsort
Handouts Lecture Notes & Pseudocode Short-Take Videos Fun-algo recitation HW2 (PDF, .tex due 5/22 @ 9pm
May 19 (M) Ch. 10
  • Data Structures
  • Operations: insert/find/remove
  • Arrays
  • Stacks
  • Queues
Lecture Notes & Pseudocode Short-Take Videos APP4 (PDF, .tex) due 5/20 @ 11:30am
APP4 Solns
May 20 (T) Ch. 12
  • Data Structures
  • Trees vs. Binary Trees
  • Binary Search Trees
  • Tree traversal, insert, find
Lecture Notes & Pseudocode Short-Take Videos Recitation - Exam Prep
May 21 (W) Ch. 13
  • Data structures
  • Linked Lists
  • Hash tables
  • Exam prep
Lecture Notes & Pseudocode Short-Take Videos

May 22 (R)

EXAM ONE (in class)

 HW3 (PDF, .tex) due 5/30 @ 9pm <== extra day!
May 26 (M)

No class (Memorial Day)
May 27 (T) Ch. 14
  • Dynamic Programming
  • The rod-cutting problems
  • Elements of dynamic programming
Lecture Notes & Pseudocode Short-Take Videos Recitation 3 (PDF, .tex)
Rec 3 Solns
May 28 (W) Dynamic Programming
  • Longest Common Subsequence
Lecture Notes & Pseudocode Short-Take Videos APP5 (PDF, .tex) due 5/29 @ 11:30am
APP5 Solns
May 29 (R) Ch. 15
  • Greedy Algorithms
  • Scheduling problem
  • Correctness of a greedy strategy
Lecture Notes & Pseudocode Short-Take Videos Fun-algo recitation HW4 (PDF, .tex) due 6/5 @ 9pm
June 2 (M) Ch. 15
  • Greedy & DP
  • Tradeoffs in strategy
  • Huffman Coding
Lecture Notes & Pseudocode Short-Take Videos APP6 (PDF, .tex) due 6/3 @ 11:30am
APP6 Solns
June 3 (T) Ch. 20
  • Graphs
  • Graph definitions
  • Breadth-first Search
  • Connected components
Lecture Notes & Pseudocode Short-Take Videos Recitation 4 (PDF, .tex)
Rec 4 Solns
June 4 (W) Ch. 20
  • Graphs
  • Depth-first Search
  • Topological sort
  • Cycles and Edge Classification
Lecture Notes & Pseudocode Short-Take Videos APP7 (PDF, .tex) due 6/5 @ 11:30am
APP7 Solns
June 5 (R) Ch. 21
  • Graphs
  • Minimum Spanning Trees
  • Kruskal & Prim
Handouts Lecture Notes & Pseudocode Short-Take Videos Fun-algo recitation HW5 (PDF, .tex) due 6/12 @ 9pm
June 9 (M) Ch. 22
  • Graphs
  • Single-Source Shortest Paths
  • Dijkstra's Algorithm
Lecture Notes & Pseudocode Short-Take Videos APP8 (PDF, .tex) due 6/11 @ 11:30am
June 10 (T) Ch. 23
  • Graphs
  • All-Pairs Shortest Paths
  • Floyd-Warshall Algorithm
Lecture Notes & Pseudocode Short-Take Videos Recitation - exam prep
June 11 (W) Ch. 24
  • Wrapping up Graphs!
  • Max Flow
  • Ford-Fulkerson Method
  • Exam prep
Lecture Notes & Pseudocode Short-Take Videos
June 12 (R)

EXAM TWO (in class)
June 16 (M) Ch. 5
  • Randomized Algorithms
  • Randomized Quicksort
  • Impact on run-time analysis
Lecture Notes & Pseudocode
June 17 (T) Ch. 34
  • P vs. NP
Lecture Notes & Pseudocode (No recitation)
June 18 (W) (OPTIONAL) Exam XC Question RESUBMISSION DEADLINE (submit ONE of HW1-5)