ICS 311
Main
Schedule
Course Evaluations
Syllabus
Course Info
Format
Assessment/Grading
Policies

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/13: #1 & #4 - Introduction to Course, Review of Basic Data Structures

  • Tue 01/14: Review of proof techniques

    • Reading: Appendix I of Jeff Erickson's online textbook

    • Notes: proof_techniques.pdf (In Laulima)

  • Wed 01/15: #3 Growth of Functions and Asymptotic Concepts

Week 2: Algorithm Correctness and Analysis

  • Mon 01/20: HOLIDAY

  • Tue 01/21:

    • Due: Problem Set #1 (Topics 1, 3 & 4) at the start of class

  • Wed 01/22: #2 - Proving Correctness, Analyzing Algorithms

Week 3: Divide & Conquer and Analysis of Recurrences, Heaps and Priority Queues

  • Mon 01/27:#7 - Divide & Conquer and Analysis of Recurrences:

    • Reading: CLRS Sections 2.3, 4.1 & 4.3-4.5

    • Lecture Notes: Topic 07

    • Screencasts: 02D (in Laulima), 02E (in Laulima), 07A, 07B, 07C, 07D

    • (Additional Screencasts): MIT Lecture 02 (16:51-end), MIT Lecture 03 (through about 13:07  —  we don't cover Strassen or Fibonacci numbers).

  • Tue 01/28:

    • Due: Problem Set #2 (Topics 2) at the start of class

  • Wed 01/29: #9 - Heap, Heapsort and Priority Queues:

Week 4: Binary Search Trees

  • Mon 02/03: #8 - Binary Search Trees:

    • Reading: CLRS Sections 12.1-12.3 (12.4 requires probabilistic analysis, covered later)

    • Lecture Notes: Topic 08

    • Screencasts: 08A, 08B, 08C, 08D

  • Tue 02/04:

    • Due: Problem Set #3 (Topic 7 & 9) at the start of class

  • Wed 02/05: #11 - 2-3-4 Trees and Red-Black Trees:

    • Reading: Sedgewick Chapter 15 (in Laulima) & CLRS Chapter 13

    • Lecture Notes: Topic 11

    • Screencasts: 11A, 11B, 11C, 11D

    • (Additional Screencasts): 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!

Week 5: Probabilistic Analysis and Randomized Algorithms

  • Mon 02/10: #5a - Probabilistic Analysis:

    • Reading: CLRS Chapter 5.1-5.3

    • Lecture Notes: Topic 05A

    • Screencasts: 05A, 05B

  • Tue 02/11:

    • Due: Problem Set #4 (Topics 8 & 11) at the start of class

  • Wed 02/12: #5b - Randomized Algorithms, Quicksort:

    • Reading: CLRS Chapter 7 (all)

    • Lecture Notes: Topic 05B

    • Screencasts: 10A, 10B

Week 6: HashTables

  • Mon 02/17: HOLIDAY

  • Tue 02/18:

    • Due: Problem Set #5 (Topics 5A & 5B) at the start of class

  • Wed 02/19: #6 - Hash Tables:

Week 7: Selection, Sorting Lower Bound and Linear Sorting

  • Mon 02/24: #10a - Selection and Order Statistics:

    • Reading: CLRS Chapter 9 (all)

    • Lecture Notes: None

    • Screencast: MIT Lecture 06

  • Tue 02/25:

    • Due: Problem Set #6 (Topic 6) at the start of class

  • Wed 02/26: #10b - Theoretical Limits, and O(n) Sorts:

Week 8: Midterm 1

  • Mon 03/02: Backtracking (Recursive algorithms review):

    • Reading: Chapter 2 (sections 2.1, 2.3-2.4, 2.6, 2.8) of Jeff Erickson's online textbook (the remaining sections provide additional examples, that you may read if you want to see more examples). If you are shaky on recursive algorithms, review Chapter 1 of Jeff Erickson's online textbook.

    • Lecture Notes: None

    • Screencasts: None

    • Due: Problem Set #7 (Topics 10A & 10B) at the start of class

  • Tue 03/03: Recitation: Midterm 1 review

  • Wed 03/04: Midterm 1:

    • Topics 1-11

Week 9: Dynamic Programming

  • Mon 03/09: #12A - Dynamic Programming:

    • Reading: CLRS Chapter 15.1-15.3 and Chapter 3 of Jeff Erickson's online textbook (through Section 5.4)

    • Lecture Notes: Topic 12A

    • Screencasts: 12A, 12B (minutes 0:00-5:00), 12D (minutes 0:00-6:16 and 9:23-end)

  • Tue 03/10:

    • Midterm 1 Review

  • Wed 03/11: #12B - Dynamic Programming (cont.):

    • Reading: CLRS Chapter 15.4-15.5; additional examples in the rest of Chapter 3 of Jeff Erickson's online textbook (sections 5.5-5.9)

    • Lecture Notes: Topic 12B

    • Screencasts: 12B (from minute 5:00), 12C, 12D (from minute 6:17)

    • (Additional Screencasts): MIT Lecture 15

Week 10: Greedy Algorithms and Basic Graph Algorithms

  • Mon 03/23: #13 - Greedy Algorithms & Huffman Codes:

    • Reading: CLRS Sections 16.1-16.3

    • Lecture Notes: Topic 13

    • Screencasts: 13A, 13B, 13C

    • (Additional Screencasts): MIT Lecture 16: only briefly mentioned at 48:16

  • Tue 03/24:

    • Due: Problem Set #8 (Topics 12A & 12B) at the start of class

  • Wed 03/25: #14A - Graph Representations, Breadth-First Search, Depth-First Search:

    • Reading: CLRS Sections 22.1-22.3; Chapter 5 of Jeff Erickson's lecture notes; Goodrich & Tamassia section on Graph Representations (in Laulima)

    • Lecture Notes: Topic 14A

    • Screencasts: 14A, 14B, 14C, 14D, 14E

    • (Additional Screencasts): MIT Lecture 16 (till minute 23:26, the rest focuses on MST  —  next week's topic).

  • Thur 03/26: HOLIDAY

Week 11: Topological Sort, SCC, Union-Find, MST

  • Mon 03/30: #14B - Topological Sort, and Strongly Connected Components:

    • Reading: CLRS Sections 22.4-22.5, CLRS Chapter 23

    • Lecture Notes: Topic 14B

    • Screencasts: 14F

  • Tue 03/31:

    • Due: Problem Set #9 (Topics 13 & 14A) at 3pm

  • Wed 04/01: #16 & #17 - Disjoint Sets, Union-Find & Minimum Spanning Trees:

    • Reading: CLRS Sections 21.1-21.3. Also see Lemma 21.11, 21.12, 21.13 and Theorem 21.14

    • Lecture Notes: Topic 16 (skip Linked List representation: Forest is much better), Topic 17 Notes

    • Screencasts: 17A, 17B, 17C

    • (Additional Screencasts): MIT Lecture 16 (from minute 23:26).

Week 12: Finding Shortest Paths in Graphs

  • Mon 04/06: #18 - Single-Source Shortest Paths:

  • Tue 04/07:

    • Due: Problem Set #10 (Topics 14B, 16 & 17) at 3pm

  • Wed 04/08: #19 - All-Pairs Shortest Paths:

  • Fri 04/10: HOLIDAY - No office hours

Week 13: Midterm 2

  • Mon 04/13: Additional practice with Dynamic Programming

  • Tue 04/14: Problem Set #11 (Topic 18 & 19) at 3pm

  • Wed 04/15: Midterm 2:

    • Topics 10B, 12-14, 16-19

Week 14: Maximum Flow in Graphs

  • Mon 04/20: #20 - Maximum Flow:

    • Reading: CLRS Sections 26.1-26.3

    • Lecture Notes: Topic 20

    • Screencasts: 20A, 20B, 20C

  • Tue 04/21: Midterm 2 review

  • Wed 04/22: #20 - Maximum Flow (continued):

    • Reading: CLRS Sections 26.1-26.3

    • Lecture Notes: Topic 20

    • Screencasts: 20A, 20B, 20C

Week 15: NP-Completeness and Approximation Algorithms

  • Mon 04/27: #24 - Complexity Theory & NP-Completeness:

  • Tue 04/28:

    • Due: Problem Set #12 (Topic 20) at 3pm

  • Wed 04/29: #25 - Approximation Algorithms:

    • Reading: CLRS Chapter 35

    • Lecture Notes: Topic 25

    • Screencasts: 25A, 25B

Week 16: Multithreading

  • Mon 05/04: #22 - Multithreading:

    • Reading: CLRS Chapter 27

    • Lecture Notes: Topic 22

    • Screencasts: None

  • Tue 05/05:

    • Due: Problem Set #13 (Topics 24 & 25) at 3pm

  • Wed 05/06: Course Review

Finals Week:

  • Final Exam: Cumulative on all topics (1-14, 16-20, 22, 24, & 25)

    • Section 1 (MW 2:15-3:45pm): (Take-home due to move to online teaching)

    • Section 2 (MW 4:30-5:45pm): (Take-home due to move to online teaching)