ICS 311 Spring 2015 Schedule

Click here to go to this week.

Classes are in Webster 101. See the index page for categorical listings of all assignments and topics.

Week 1: Introduction and Basic Concepts

• Tue 01/13 - #1 - Introduction to Algorithms:
  Study resources include CLRS Chapter 1; Topic 01 Notes; and screencasts 01A-C (or 01* for all of them) in Laulima. After class, try the "Practice Quiz on Topic 01" (graded automatically but not included in course grade: it's for practice).
• Thu 01/15 - #2 - Examples of Analysis with Insertion:
  Study resources include CLRS Chapter 2 sections 2.1 and 2.2; Topic 02 Notes up through "Worst Case Rate of Growth"; screencasts 02A-C in Laulima (up through "Detailed Analysis of Insertion Sort"); MIT Lecture 01; Quiz on Topic 02a due at 11:20 today (and on future days for every numbered topic).

Week 2: Continuing Basic Concepts

• Mo 01/19 - HOLIDAY
• Tue 01/20 - #2 - Examples of Analysis with Merge Sort:
  Rest of CLRS Chapter 2; rest of Topic 02 Notes; screencasts 02D and 02E in Laulima. Don't forget Quiz on Topic 02b due 11:20.
• Tue 01/20 - Last day to withdraw without "W"
• Tue 01/20 - Problem Set #0 (practice homework, Topic 1) due 23:55 (11:55 pm) in Laulima (not graded)
• Thu 01/22 - #2.5 - Review of proof techniques
  The study material is posted in Laulima (in Wiki, under "Topic 02.5"). There is no quiz on topic 2.5, but you should still study the materials to be able to do in-class exercises.

Week 3: Analysis of Basic Data Structures

• Tue 01/27 - #3 - Growth of Functions and Asymptotic Concepts:
  CLRS Chapter 3; Topic 03 Notes ; screencasts 03*, henceforth available in Laulima, iTunesU and YouTube; MIT Lecture 02 (beginning-16:50).
• Tue 01/27 - Problem Set #1 (Topics 2 & 2.5) due 23:55 (11:55 pm) in Laulima
• Thu 01/29 - #4 - Basic ADTs (Stacks, Queues, Lists and Trees):
  CLRS Chapter 10; Topic 04 Notes; screencasts 04* in Laulima, iTunesU and YouTube; (not covered in MIT video lectures).

Week 4: Divide and Conquer and Binary Search Trees

• Tue 02/03 - #7 - Divide & Conquer and Analysis of Recurrences:
  CLRS Sections 4.1 & 4.3-4.5; Topic 07 Notes; screencasts 07*; MIT Lecture 02 (16:51-end) and MIT Lecture 03 (through about 13:07: we don't cover Strassen or Fibonacci numbers).
• Tue 02/04 - Problem Set #2 (Topics 3 & 4) due 23:55 (11:55 pm)
• Thu 02/04 - #8 - Binary Search Trees:
  CLRS Sections 12.-12.3 (12.4 requires probabilistic analysis, covered later); Topic 08 Notes; screencasts 08*; (No corresponding MIT lecture identified).

Week 5: Heapsort, Priority Queues, Quicksort, Probabilistic Analysis, Randomized Algorithms

• Tue 02/10 - #9 - Heap, Heapsort and Priority Queues:
  CLRS Chapter 6 (all); Topic 09 Notes; screencasts 09*
• Tue 02/10 - Problem Set #3 (Topics 7 & 8) due 23:55 (11:55 pm)
• Thu 02/12 - 5 - Quicksort, Probabilistic Analysis, Randomized Algorithms:
  CLRS Sections 5.1-5.3, CLRS Chapter 7 (all); Topic 05 Notes; screencasts 10A, 5A, 10B, 5B

Week 6: Selection, Sorting Lower Bound, Linear Sorting

• Mon 02/16 - HOLIDAY
• Tue 02/17 - #10a - Selection and Order Statistics:
  CLRS Chapter 9 (all); MIT Lecture 06.
• Tue 02/17 - Problem Set #4 (Topics 9 & 5) due 23:55 (11:55 pm)
• Thu 02/19 - #10b - Theoretical Limits, and O(n) Sorts:
  CLRS Chapter 8; Topic 10 Notes; screencasts 10C; MIT Lecture 05.

Week 7: Hash Tables and Balanced Trees

• Tue 02/24 - #6 - Hash Tables:
  CLRS Sections 11.1-11.4; Topic 06 Notes; screencasts 06*; MIT Lecture 07 and MIT Lecture 08 (see my notes for guide to what parts to attend to).
• Tue 02/24 - Problem Set #5 (Topics 10a and 10b) due 23:55 (11:55 pm)
• Thu 02/26 - #11 - Balanced Trees (2-3-4 and Red-Black):
  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!).

Week 8: Midterm and Review

• Tue 03/03 - Midterm 1: Topics 1-10, Excluding 6
• Thu 03/05 - Review of Midterm Results

Week 9: Dynamic Programming and Greedy Algorithms

• Tue 03/10 - #12 - Dynamic Programming:
  CLRS Chapter 15 (and optionally Sedgewick Chapter 37); Topic 12 Notes; screencasts 12*; MIT Lecture 15
• Tue 03/10 - Problem Set #6 (Topics 6 & 11) due 23:55 (11:55 pm)
• Thu 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)
• Fr 03/13 - Last day for withdrawal with W

Week 10: Graph Represenations and Basic Algorithms

• Tue 03/17 - #14 - Graph Representations and Breadth-First Search:
  CLRS 22.1-22.2; Goodrich & Tamassia section on Graph Representations in Laulima; Optionally Newman (2010) chapter 9 in Laulima; Topic 14 Notes; screencasts 14A-C; MIT Lecture 16 (just the first few minutes for graph representations; the rest focuses on MST).
  
• Tue 03/17 - Problem Set #7 (Topics 12 & 13) due 23:55 (11:55 pm)
• Thu 03/19 - #14 - Depth-First Search, Topological Sort, and Strongly Connected Components:
  CLRS 22.3-22.5; screencasts 14D-F.

Spring Break 03/23-27

Week 11: Amortized Analysis, Union-Find, and Minimum Spanning Trees

• Tue 03/31 - #15 - Amortized Analysis & #16 - Sets and Union-Find:
  CLRS 17.1-17.2, 21.1, & 21.3; Also see Lemma 21.11, 21.12, 21.13 and Theorem 21.14; Topic 15 Notes (skip Potential Method) & Topic 16 Notes (skip Linked List representation: Forest is much better); MIT Lecture 13
• Tue 03/31 - Problem Set #8 (Topic 14)
• Thu 04/02 - #17 - Minimum Spanning Trees:
  CLRS Chapter 23; Topic 17 Notes; screencasts 17*; MIT Lecture 16 (second part).

Week 12: Finding Shortest Paths in Graphs

• Tue 04/07 - #18 - Single-Source Shortest Paths:
  CLRS Sections 24.1-24.3; Topic 18 Notes; screencasts 18*; MIT Lecture 17, MIT Lecture 18 (first half)
• Tue 04/07 - Problem Set #9 (Topic 15, 16 & 17) due 23:55 (11:55 pm)
• Thu 04/09 - #19 - All-Pairs Shortest Paths:
  CLRS Chapter 25; Topic 19 Notes; screencasts 19*; MIT Lecture 19

Week 13: Maximum Flow in Graphs and Multithreading

• Tue 04/14 - #20 - Maximum Flow:
  CLRS Sections 26.1-26.3; Topic 20 Notes; screencasts 20*.
• Tue 04/14 - Problem Set #10 (Topics 18 & 19) due 23:55 (11:55 pm)
• Thu 04/16 - #22 - Multithreading: CLRS Chapter 27 (emphasis on sections 27.1 and 27.3); Topic 22 Notes; no screencasts.

Week 14: Midterm and Midterm Review

• Tue 04/21 - Midterm 2: Topics 6, 12-19
• Thu 04/23 - Review of Midterm Results

Week 15: NP-Completeness and Approximation Algorithms

• Tue 04/28 - #24 - Complexity Theory & NP-Completeness :
  CLRS Chapter 35; Topic 24 Notes; screencasts 24*; not covered in MIT video lectures.
• Tue 04/28 - Problem Set #11 An extra credit problem set on Topics 20 & 22 due 23:55 (11:55 pm)
• Thu 04/30 - #25 - Approximation Algorithms:
  CLRS Chapter 34; Topic 25 Notes; screencasts 25*; not covered in MIT video lectures.

Week 16: Special Topics

• Tue 05/05 - Special Topics (brief introductions, no homework) potentially including the following and to presented by guest speakers where possible
  • #21 - Linear Programming:
    Sedgewick (1983) Chapters 5 and 38 (read these first); CLRS Sections 29.0-29.3 (half way); Topic 21 Notes
  #23 String Matching: CLRS Chapter 32 (emphasis on sections 32.1 and 32.3); Topic 23 Notes
  • Public Key Encryption: CLRS Chapter 31 (emphasis on 31.7)

Finals Week:

• TBA Final Exam: Cumulative on all topics (1-20, 22, 24, & 25), excluding Special Topics.