ICS 311 Spring 2017 Schedule

Click here to go to this week.

Classes are in Webster 101 and in Holmes 247. 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/09 - #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 01/11 - #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).
• Fri 01/13 - Problem Set #1 (Topics 1, 2 & 4) due 22:00 (10:00 pm)

Week 2: Growth of Functions

• Mon 01/16 - Holiday
• Wed 01/18 - #3 Growth of Functions and Asymptotic Concepts CLRS Chapter 3; Topic 03 Notes ; screencasts 2A-C, 03*; MIT Lecture 02 (beginning-16:50).
• Fri 01/20 - Problem Set #2 (pdf) (Topic 3) due 22:00 (10:00 pm)

Week 3: Divide & Conquer, Recurrences and Binary Search Trees

• Mon 01/23 - #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 01/25 - #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 01/27 - Problem Set #3 (pdf) (Topics 7 & 8) due 22:00 (10:00 pm)

Week 4: Balanced Binary Search Trees, Heap, Heapsort and Priority Queues

• Mon 01/30 - #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!).
• Wed 02/01 - #9 - Heap, Heapsort and Priority Queues:
  CLRS Chapter 6 (all); Topic 09 Notes; screencasts 09*
• Fri 02/03 - Problem Set #4 (pdf) (Topics 9 & 11) due 22:00 (10:00 pm)

Week 5: Probabilistic Analysis and Randomized Algorithms

• Mon 02/06 - #5a - Probabilistic Analysis:
  CLRS Chapter 5.1-5.3; Topic 05A Notes; screencasts 5A-B
• Wed 02/08 - #5b - Randomized Algorithms, Quicksort:
  CLRS Chapter 7 (all) Topic 05B Notes; screencasts 10A-B
• Fri 02/10 - Problem Set #5 (pdf) (Topics 5a & 5b) due 22:00 (10:00 pm)

Week 6: HashTables and Selection

• Mon 02/13 - #6 - Hash Tables:
  CLRS Sections 11.1-11.4; Topic 06 Notes; screencasts 06*; MIT Lecture 07 and MIT Lecture 08 (through 11:02).
• Wed 02/15 - #10a - Selection and Order Statistics:
  CLRS Chapter 9 (all); MIT Lecture 06; no lecture notes.
• Fri 02/17 - Problem Set #6 (pdf) (Topics 6 & 10a) due 22:00 (10:00 pm)

Week 7: Sorting Lower Bound and Linear Sorting

• Mon 02/20 - Holiday
• Wed 02/22 - #10b - Theoretical Limits, and O(n) Sorts:
  CLRS Chapter 8; Topic 10 Notes; screencasts 10C; MIT Lecture 05.
• Fri 02/24 - Problem Set #7 (pdf) (Topics 10b) due 22:00 (10:00 pm)

Week 8: Midterm 1

• Mon 02/27 - Midterm 1: Topics 1-11
• Wed 03/01 - Midterm 1 Review

Week 9: Dynamic Programming

• Mon 03/06 - #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 and 9:23-end);
• Wed 03/08 - #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 03/10 - Last day for withdrawal with W
• Fri 03/10 - Problem Set #8 (Topics 12A & 12B) due 22:00 (10:00 pm)

Week 10: Greedy Algorithms and Basic Graph Algorithms

• Mon 03/13 - #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 03/15 - #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 03/17 - Problem Set #9 (Topics 13 & 14A) due 22:00 (10:00 pm)

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

• Mon 03/20 - #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.
• Wed 03/22 - #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).
• Fri 03/24 - Problem Set #10 (pdf) (Topics 14B, 16 & 17) due 22:00 (10:00 pm)

Week 12: Finding Shortest Paths in Graphs

• Mon 04/03 - #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)
• Wed 04/05 - #19 - All-Pairs Shortest Paths:
  CLRS Chapter 25; Topic 19 Notes; screencasts 19*; MIT Lecture 19 (00:00-9:00 and 53:00-end)
• Fri 04/07 - Problem Set #11 (Topic 18 & 19) due 22:00 (10:00 pm)

Week 13: Midterm 2

• Mon 04/10 - Midterm 2: Topics 12-14, 16-19
• Wed 04/12 - Midterm 2 Review

Week 14: Maximum Flow in Graphs

• Mon 04/17 - #20 - Maximum Flow:
  CLRS Sections 26.1-26.3; Topic 20 Notes; screencasts 20*.
• Wed 04/19 - #20 - Maximum Flow (continued):
  CLRS Sections 26.1-26.3; Topic 20 Notes; screencasts 20*.
• Fri 04/21 - Problem Set #12 (Topic 20) due 22:00 (10:00 pm)

Week 15: NP-Completeness and Approximation Algorithms

• Mon 04/24 - #24 - Complexity Theory & NP-Completeness :
  CLRS Chapter 35; Topic 24 Notes; screencasts 24*; not covered in MIT video lectures.
• Wed 04/26 - #25 - Approximation Algorithms:
  CLRS Chapter 34; Topic 25 Notes; screencasts 25*; not covered in MIT video lectures.
• Fri 04/28 - Problem Set #13 (Topics 24 & 25) due 22:00 (10:00 pm)

Week 16: Multithreading

• Mon 05/01 - #22 - Multithreading: CLRS Chapter 27; Topic 22 Notes; no screencasts.
• Wed 05/03 - Course Review

Finals Week:

• Final Exam: Cumulative on all topics (1-14, 16-20, 22, 24, & 25), in TBD
  • Section 1 (MW 8:30-10:10pm): Monday 7:30-9:30am
  • Section 2 (MW 10:30-10:10pm): Monday 9:45-11:45am