Classes are in Webster 101. 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 08/24 - #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;
- Wed 08/26 - #2 & #3 - Examples of Analysis with Insertion Sort, Growth of Functions and Asymptotic Concepts:
CLRS Chapters 2.1-2.2 & 3;
Topic 02 Notes;
Topic 03 Notes ;
screencasts 2A-C, 03*;
MIT Lecture 01
(17:00-1:03:30).
MIT Lecture 02
(beginning-16:50).
- Fri 08/28 - Problem Set #1
(Topics 1-4) due 22:00 (10:00 pm)
Week 2: Divide & Conquer, Recurrences and Binary Search Trees
- Mon 08/31 - #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).
- Wed 09/02 - #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).
- Fri 09/04 - Problem Set #2
(Topics 7 & 8) due 22:00 (10:00 pm)
Week 3: Balanced Binary Search Trees
- Mon 09/07 - Holiday
- Wed 09/09 - #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!).
- Fri 09/11 - Problem Set #3
(Topic 11) due 22:00 (10:00 pm)
Week 4: Heaps, Priority Queues and Randomized Algorithms
- Mon 09/14 - #9 - Heap, Heapsort and Priority Queues:
CLRS Chapter 6 (all); Topic 09 Notes; screencasts 09*
- Wed 09/16 - #5A - Probabilistic Analysis:
CLRS Chapter 5.1-5.3; Topic 05A Notes; screencasts 5A-B
- Fri 9/18 - Problem Set #4
(Topics 9 & 5A) due 22:00 (10:00 pm)
Week 5: Applications of Randomized Algorithms
Week 6: Selection, Sorting Lower Bound, Linear Sorting
- Mon 09/28 - #10a - Selection and Order Statistics:
CLRS Chapter 9 (all);
MIT Lecture 06; no lecture notes.
- Wed 09/30 - #10b - Theoretical Limits, and O(n) Sorts:
CLRS Chapter 8; Topic 10 Notes; screencasts 10C;
MIT Lecture 05.
- Fri 10/02 - Problem Set #6
(Topics 10a & 10b) due 22:00 (10:00 pm)
Week 7: Review and Midterm
- Mon 10/05 - Pre-Midterm Review
- Wed 10/07 - Midterm 1: Topics 1-11
Week 8: Dynamic Programming
- Mon 10/12 - #12A - Dynamic Programming:
CLRS Chapter 15.1-15.3
Topic 12A Notes;
screencasts 12A, 12B (minutes 0:00-5:00), 12D (minutes 0:00-6:16);
- Wed 10/14 - #12B - Dynamic Programming (cont.):
CLRS Chapter 15.4-15.5
Topic 12B Notes;
screencasts 12B (from minute 5:00), 12C, 12D (from minute 6:17);
MIT Lecture 15
- Fri 10/16 - Problem Set #7
(Topics 12A & 12B) due 22:00 (10:00 pm)
Week 9: Greedy Algorithms and Basic Graph Algorithms
- Mon 10/19 - #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)
- Wed 10/21 - #14A - Graph Representations, Breadth-First Search, Depth-First Search:
CLRS Sections 22.1-22.3; Goodrich & Tamassia section on Graph Representations in Laulima;
Optionally Newman (2010) chapter 9 in Laulima;
Topic 14A Notes;
screencasts 14A-E;
MIT Lecture 16 (till minute 23:26, the rest focuses on MST — next week's topic).
- Fri 10/23 - Last day for withdrawal with W
- Fri 10/23 - Problem Set #8
(Topics 13 & 14A) due 22:00 (10:00 pm)
Week 10: Topological Sort, SCC, Sets and Union-Find
- Wed 10/26 - #14B - Topological Sort, and Strongly Connected Components:
CLRS Sections 22.4-22.5;
Topic 14B Notes;
screencasts 14F;
not covered in MIT video lectures.
- Tue 10/28 - #16 - Sets and Union-Find:
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.
- Fri 10/30 - Problem Set #9
(Topics 14B & 16) due 22:00 (10:00 pm)
Week 11: Minimum Spanning Trees, Finding Shortest Paths in Graphs
Week 12: All-Pairs Shortest Paths on Dense Graphs
- Mon 11/09 - #19 - All-Pairs Shortest Paths:
CLRS Chapter 25;
Topic 19 Notes;
screencasts 19*;
MIT Lecture 19 (00:00-9:00 and 53:00-end)
- Wed 11/11 - Holiday:
- Fri 11/13 - Problem Set #11
(Topic 19) due 22:00 (10:00 pm)
Week 13: Midterm and Midterm Review
- Mon 11/16 - Midterm 2: Topics 12-14, 16-19
- Wed 11/18 - Review of Midterm Results
Week 14: Maximum Flow in Graphs
- Mon 11/23 - #20 - Maximum Flow:
CLRS Sections 26.1-26.3;
Topic 20 Notes;
screencasts 20*.
- Wed 11/25 - #20 - Maximum Flow (continued):
CLRS Sections 26.1-26.3;
Topic 20 Notes;
screencasts 20*.
- Fri 11/27 - Problem Set #12
(Topic 20) due 22:00 (10:00 pm)
Week 15: NP-Completeness and Approximation Algorithms
- Mon 11/30 - #24 - Complexity Theory & NP-Completeness :
CLRS Chapter 35;
Topic 24 Notes;
screencasts 24*;
not covered in MIT video lectures.
- Wed 12/02 - #25 - Approximation Algorithms:
CLRS Chapter 34;
Topic 25 Notes;
screencasts 25*;
not covered in MIT video lectures.
- Fri 12/04 - Problem Set #13
(Topics 24 & 25) due 22:00 (10:00 pm)
Week 16: Multithreading
- Mon 12/07 - #22 - Multithreading:
CLRS Chapter 27;
Topic 22 Notes;
no screencasts.
- Wed 12/16 - Course Review
Finals Week:
- Final Exam: Cumulative on all topics (1-14, 16-20, 22, 24, & 25), in Webster 101
- Section 1 (MW 1:30-3:10pm): Friday 2:15-4:15pm
- Section 2 (MW 4:00-5:40pm): Wednesday 4:30-6:30pm
