ICS 311 Spring 2018 Schedule

Click here to go to this week.

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