Classes are in Webster 101 and in POST 319. See the index page
for categorical listings of all assignments and topics.
Week 1: Introduction and Basic Concepts (Mostly review of ICS 211, 141 and 241)
- Mon 01/08 - #1 & #4 - Introduction to Algorithms, Review of Basic Data Structures:
Study resources include CLRS Chapter 1 & 10;
Topic 01 Notes;
Topic 04 Notes; and
screencasts 01A-C (or 01* for all of them), 4A-B henceforth available in Laulima and YouTube.
- Tue 01/16 - Review of proof techniques :
Study resources posted in Laulima (see the Wiki for the class).
- Wed 01/10 - #2 - Proving Correctness; Analyzing Algorithms:
CLRS Sections 2.1-2.2;
Topic 02 Notes;
screencasts 2A-C;
MIT Lecture 01
(17:00-1:03:30).
Week 2: Growth of Functions
- Mon 01/15 - Holiday
- Tue 01/16 - Problem Set #1
(Topics 1, 2 & 4) due at the start of the class
- Wed 01/17 - #3 Growth of Functions and Asymptotic Concepts
CLRS Chapter 3;
Topic 03 Notes ;
screencasts 2A-C, 03*;
MIT Lecture 02
(beginning-16:50).
Week 3: Divide & Conquer, Recurrences and Binary Search Trees
- Mon 01/22 - #7 - Divide & Conquer and Analysis of Recurrences:
CLRS Sections 2.3, 4.1 & 4.3-4.5;
Topic 07 Notes; screencasts
02D, 02E, 07*;
MIT Lecture 02
(16:51-end) and
MIT Lecture 03
(through about 13:07: we don't cover Strassen or Fibonacci numbers).
- Tue 01/23 - Problem Set #2
(Topic 3) due at the start of class
- Wed 01/24 - #8 - Binary Search Trees:
CLRS Sections 12.1-12.3 (12.4 requires probabilistic analysis, covered later);
Topic 08 Notes; screencasts 08*;
(No corresponding MIT lecture identified).
Week 4: Balanced Binary Search Trees, Heap, Heapsort and Priority Queues
- Mon 01/29 - #11 - 2-3-4 Trees and Red-Black Trees:
Sedgewick Chapter 15 & CLRS Chapter 13;
Topic 11 Notes;
screencasts 11*;
MIT Lecture 10. (Read
Sedgewick first to understand the 2-4 tree and how a RBT is a representation of a 2-4
tree. Allow extra time for this material!).
- Tue 01/30 - Problem Set #3
(Topics 7 & 8) due at the start of class
- Wed 01/31 - #9 - Heap, Heapsort and Priority Queues:
CLRS Chapter 6 (all); Topic 09 Notes; screencasts 09*
Week 5: Probabilistic Analysis and Randomized Algorithms
- Mon 02/05 - #5a - Probabilistic Analysis:
CLRS Chapter 5.1-5.3; Topic 05A Notes; screencasts 5A-B
- Tue 02/06 - Problem Set #4
(Topics 9 & 11) due at the start of class
- Wed 02/07 - #5b - Randomized Algorithms, Quicksort:
CLRS Chapter 7 (all) Topic 05B Notes; screencasts 10A-B
Week 6: HashTables and Selection
- Mon 02/12 - #6 - Hash Tables:
CLRS Sections 11.1-11.4;
Topic 06 Notes; screencasts 06*;
MIT Lecture 07 and
MIT Lecture 08 (through 11:02).
- Tue 02/13 - Problem Set #5
(Topics 5a & 5b) due at the start of class
- Wed 02/14 - #10a - Selection and Order Statistics:
CLRS Chapter 9 (all);
MIT Lecture 06; no lecture notes.
Week 7: Sorting Lower Bound and Linear Sorting
- Mon 02/19 - Holiday
- Tue 02/20 - Problem Set #6
(Topics 6 & 10a) due at the start of class
- Wed 02/21 - #10b - Theoretical Limits, and O(n) Sorts:
CLRS Chapter 8; Topic 10 Notes; screencasts 10C;
MIT Lecture 05.
Week 8: Midterm 1
- Mon 02/26 - Midterm 1: Topics 1-10a & 11
- Tue 02/27 - Midterm 1 review
- Wed 02/28 - Recursive Algorithms Review:
Chapter 1 of Jeff Erickson's lecture notes. No videos.
Week 9: Dynamic Programming
- Mon 03/05 - #12A - Dynamic Programming:
CLRS Chapter 15.1-15.3
and Chapter 5 of Jeff Erickson's lecture notes (through Section 5.4);
Topic 12A Notes;
screencasts 12A, 12B (minutes 0:00-5:00), 12D (minutes 0:00-6:16 and 9:23-end);
- Tue 03/06 - Problem Set #7
(Topics 10b) due at the start of class
- Wed 03/07 - #12B - Dynamic Programming (cont.):
CLRS Chapter 15.4-15.5;
additional examples in the rest of Chapter 5 of Jeff Erickson's lecture notes (sections 5.5-5.9);
Topic 12B Notes;
screencasts 12B (from minute 5:00), 12C, 12D (from minute 6:17);
MIT Lecture 15
- Fri 03/09 - Last day for withdrawal with W
Week 10: Greedy Algorithms and Basic Graph Algorithms
- Mon 03/12 - #13 - Greedy Algorithms & Huffman Codes:
CLRS Sections 16.1-16.3;
Topic 13 Notes;
screencasts 13*;
(MIT Lecture 16: only briefly mentioned at 48:16)
- Tue 03/13 - Problem Set #8
(Topics 12A & 12B) due at the start of class
- Wed 03/14 - #14A - Graph Representations, Breadth-First Search, Depth-First Search:
CLRS Sections 22.1-22.3; Chapter 18 of Jeff Erickson's lecture notes; Goodrich & Tamassia section on Graph Representations in Laulima;
Topic 14A Notes;
screencasts 14A-E;
MIT Lecture 16 (till minute 23:26, the rest focuses on MST — next week's topic).
Week 11: Topological Sort, SCC, Union-Find, MST
- Mon 03/19 - #14B - Topological Sort, and Strongly Connected Components:
CLRS Sections 22.4-22.5; CLRS Chapter 23;
Topic 14B Notes;
screencasts 14F;
not covered in MIT video lectures.
- Tue 03/20 - Problem Set #9
(Topics 13 & 14A) due at the start of class
- Wed 03/21 - #16 & #17 - Disjoint Sets, Union-Find & Minimum Spanning Trees:
CLRS Sections 21.1-21.3; Also see Lemma 21.11, 21.12, 21.13 and Theorem 21.14;
Topic 16 Notes (skip Linked List representation: Forest is
much better) - not covered in MIT video lectures;
Topic 17 Notes;
screencasts 17*;
MIT Lecture 16 (from minute 23:26).
Week 12: Finding Shortest Paths in Graphs
- Mon 04/02 - #18 - Single-Source Shortest Paths:
CLRS Sections 24.1-24.3;
Topic 18 Notes;
screencasts 18*;
MIT Lecture 17,
MIT Lecture 18
(until minute 36:20)
- Tue 04/03 - Problem Set #10
(Topics 14B, 16 & 17) due at the start of class
- Wed 04/04 - #19 - All-Pairs Shortest Paths:
CLRS Chapter 25;
Topic 19 Notes;
screencasts 19*;
MIT Lecture 19 (00:00-9:00 and 53:00-end)
Week 13: Midterm 2
- Mon 04/09 - Dynamic Programming revisited :
Problem Set #11
(Topic 18 & 19) due at the start of class
- Tue 04/10 - Midterm 2 Preview
- Wed 04/11 - Midterm 2: Topics 10b, 12-14, 16-19
Week 14: Maximum Flow in Graphs
- Mon 04/16 - #20 - Maximum Flow:
CLRS Sections 26.1-26.3;
Topic 20 Notes;
screencasts 20*.
- Tue 04/17 - Midterm 2 review
- Wed 04/18 - #20 - Maximum Flow (continued):
CLRS Sections 26.1-26.3;
Topic 20 Notes;
screencasts 20*.
Week 15: NP-Completeness and Approximation Algorithms
- Mon 04/23 - #24 - Complexity Theory & NP-Completeness :
CLRS Chapter 35;
Topic 24 Notes;
screencasts 24*;
not covered in MIT video lectures.
- Tue 04/17 - Problem Set #12
(Topic 20) due at the start of class
- Wed 04/25 - #25 - Approximation Algorithms:
CLRS Chapter 34;
Topic 25 Notes;
screencasts 25*;
not covered in MIT video lectures.
Week 16: Multithreading
- Mon 04/30 - #22 - Multithreading:
CLRS Chapter 27;
Topic 22 Notes;
no screencasts.
- Tue 05/01 - Problem Set #13
(Topics 24 & 25) due at the start of class
- Wed 05/02 - Course Review
Finals Week:
- Final Exam: Cumulative on all topics (1-14, 16-20, 22, 24, & 25) in Webster 101
- Section 1 (MW 2:15-3:30pm): Monday 2:15-4:15pm
- Section 2 (MW 4:30-5:45pm): Monday 4:30-6:30pm