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
May 6 (T) Ch. 1.3, A.1
  • Linear search
  • Run-time introduction
  • Asymptotic notation
Recitation 1
May 7 (W) Ch. 1.2
  • Algorithm steps vs. asymptotic run-time
  • Sorting
  • Insertion sort
  • Proving correctness: loop invariant
APP1 due 5/8 @11:30am
May 8 (R) Ch. 4
  • Summation Math
  • Best-case, worst-case run-time
  • Recursive sequences
Fun-algo recitation HW1 due 5/15 @9pm
May 12 (M) Ch. 1.4
  • Recursive algorithms
  • Recusive run-times
  • Solving recurrences: Master method, iteration method
APP2 due 5/13 @ 11:30am
May 13 (T) Ch. 1.4
  • Divide & Conquer
  • Mergesort
Recitation 2
May 14 (W) Ch. 7
  • Divide & Conquer
  • Quicksort
APP3 due 5/15 @ 11:30am
May 15 (R) Ch. 6
  • Data structure: Heap
  • Heaps as arrays
  • Heapsort
Fun-algo recitation HW2 due 5/22 @ 9pm
May 19 (M) Ch. 10
  • Data Structures
  • Operations: insert/find/remove
  • Arrays
  • Stacks
  • Queues
APP4 due 5/20 @ 11:30am
May 20 (T) Ch. 12
  • Data Structures
  • Trees vs. Binary Trees
  • Binary Search Trees
  • Tree traversal, insert, find
Recitation - Exam Prep
May 21 (W) Ch. 13
  • Data structures
  • Balanced binary search trees
  • Exam prep

May 22 (R)

EXAM ONE (in class)

 HW3 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
Recitation 3
May 28 (W) Dynamic Programming
  • Longest Common Subsequence
APP5 due 5/29 @ 11:30am
May 29 (R) Ch. 15
  • Greedy Algorithms
  • Scheduling problem
  • Correctness of a greedy strategy
Fun-algo recitation HW4 due 6/5 @ 9pm
June 2 (M) Ch. 15
  • Greedy & DP
  • Tradeoffs in strategy
  • Huffman Coding
APP6 due 6/3 @ 11:30am
June 3 (T) Ch. 20
  • Graphs
  • Graph definitions
  • Breadth-first Search
  • Connected components
Recitation 4
June 4 (W) Ch. 20
  • Graphs
  • Depth-first Search
  • Topological sort
  • Cycles and Edge Classification
APP7 due 6/5 @ 11:30am
June 5 (R) Ch. 21
  • Graphs
  • Minimum Spanning Trees
  • Krusal & Prim
Fun-algo recitation HW5 due 6/12 @ 9pm
June 9 (M) Ch. 22
  • Graphs
  • Single-Source Shortest Paths
  • Dijkstra's Algorithm
APP8 due 6/10 @ 11:30am
June 10 (T) Ch. 23
  • Graphs
  • All-Pairs Shortest Paths
  • Floyd-Warshall Algorithm
Recitation - exam prep
June 11 (W) Ch. 24
  • Wrapping up Graphs!
  • Max Flow
  • Ford-Fulkerson Method
  • Exam prep
June 12 (R)

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