ICS 311 Schedule Fall 2022

This schedule subject to change.

Week 1: Introduction and Basic Concepts

• Mon 08/22 - #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.
• Wed 08/24 - #2 - Examples of Analysis with Insertion Sort:
  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 above Topic 02 material in class today (and on future days for every numbered topic).

Week 2: Continuing Basic Concepts

• Mon 08/29 - #2 - Examples of Analysis with Merge Sort:
  Rest of CLRS Chapter 2; rest of Topic 02 Notes; screencasts 02D and 02E. Don’t forget Quiz on remainder of Topic 02.
• Tue 08/30 - Problem Set #00 (Topic 1) due 23:55 (11:55 pm) in Laulima
• Wed 08/31- #3 - Characterizing Run Times:
  CLRS Chapter 3; Topic 03 Notes ; screencasts 03*, available in Laulima and YouTube; MIT Lecture 02 (beginning-16:50).

Week 3: Analysis of Basic Data Structures

• Mon 09/05 - Holiday (Labor Day)
• Tue 09/06 - Problem Set #01 (Topic 2) due 23:55 (11:55 pm) in Laulima
• Wed 09/07 - #4 - Review of Basic ADTs (Stacks, Queues, Lists and Trees):
  CLRS Chapter 10; Topic 04 Notes; screencasts 04* in Laulima and YouTube; (not covered in MIT video lectures).

Week 4: Probabilistic Analysis, Randomization, and Hash Tables

• Mon 09/12 - #5 - Probabilistic Analysis and Randomized Algorithms; Skip Lists:
  CLRS Sections 5.1-5.3 and 5.1.4; Goodrich & Tamassia Skip Lists; Topic 05 Notes; screencasts in Laulima and YouTube; MIT Lecture on Skip Lists
• Tue 09/13 - Problem Set #2 (Topics 3 & 4) due 23:55 (11:55 pm)
• Wed 09/14 - #6 - Hash Tables:
  CLRS Sections 11.1-11.4; Topic 06 Notes; screencasts in Laulima, iTunesU and YouTube; MIT Lecture 07 and MIT Lecture 08 (see my notes for guide to what parts to attend to)

Week 5: Divide and Conquer and Binary Search Trees

• Mon 09/19 - #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 09/20 - Problem Set #3 (Topics 5 & 6) due 23:55 (11:55 pm)
• Wed 09/21 - #8 - Binary Search Trees:
  CLRS Sections 12.1-12.3 (see also Theorem 12.4); Topic 08 Notes; screencasts 08*; (No corresponding MIT lecture identified).

Week 6: Advanced Sorts and Queues (Heaps, Priority Queues, Heapsort, Quicksort)

• Mon 09/26 - #9 - Heap, Heapsort and Priority Queues:
  CLRS Chapter 6 (all); Topic 09 Notes; screencasts in Laulima and YouTube; (no corresponding MIT lecture identified)
• Tue 09/27 - Problem Set #4 (Topics 7 & 8) due 23:55 (11:55 pm)
• Wed 09/28 - #10A - Quicksort:
  CLRS Chapter 7 (Chapter 8 is in notes but will be continued on Monday); Topic 10 Notes; screencasts in Laulima and YouTube; MIT Lecture 04

Week 7: O(n) Sorts and Midterm

• Mon 10/03 - #10B - Theoretical Limits, and O(n) Sorts; Midterm Review:
  CLRS Chapter 8; Topic 10 Notes; screencasts in Laulima and YouTube; MIT Lecture 05 (but we don’t go into as much detail)
• Tue 10/04 - No problem set!
• Wed 10/05 - Midterm 1, Topics 1-8

Week 8: Midterm Results Review; Intro to Dynamic Programming

• Mo 10/10 - #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.).
• Tue 10/11 - Problem Set #5 (Topics 9 & 10a, quicksort) due 23:59 Deadline extended to 10/17 11:59pm.
• Wed 10/12 - Intro to Dynamic Programming (no quiz)

Week 9: Problem Solving with Dynamic Programming and Greedy Algorithms

• Mon 10/17 - #12 - Dynamic Programming:
  CLRS Chapter 14 (and optionally Sedgewick Chapter 37); Topic 12 Notes; screencasts 12*; MIT Lecture 15
• Tue 10/18 - Problem Set #6 (Topics 10b linear sorts & 11) due 23:55 (11:55 pm)
• Wed 10/19- #13 - Greedy Algorithms (and how they compare to DP):
  CLRS Sections 15.1-15.3; Topic 13 Notes; screencasts 13*; (MIT Lecture 16: only briefly mentioned at 48:16)

Week 10: Graph Representations and Basic Algorithms

• Mon 10/24 - #14A - Graph Representations and Breadth-First Search:
  CLRS 20.1-20.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 10/25 - Problem Set #7 (Topics 12 & 13) due 23:55 (11:55 pm)
• Wed 10/26 - #14B - Depth-First Search, Topological Sort, and Strongly Connected Components: CLRS 20.3-20.5; screencasts 14D-F.

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

• Mo 10/31 - #15 - Amortized Analysis & #16 - Sets and Union-Find:
  CLRS 16.1-16.2, 19.1, & 19.3. Topic 15 Notes (skip Potential Method) & Topic 16 Notes (skip Linked List representation: Forest is much better); MIT Lecture 13
• Tue 11/01 - Problem Set #8 (Topic 14) due 23:55 (11:55 pm)
• Wed 11/02 - #17 - Minimum Spanning Trees:
  CLRS Chapter 21; Topic 17 Notes; screencasts 17*; MIT Lecture 16 (second part).

Week 12: Finding Shortest Paths in Graphs

• Mon 11/08 - #18 - Single-Source Shortest Paths:
  CLRS Sections 22.1-22.3; Topic 18 Notes; screencasts 18*; MIT Lecture 17, MIT Lecture 18 (first half)
• Tue 11/09 Problem Set #9 (Topic 15, 16 & 17) due 23:55 (11:55 pm)
• Wed 11/10 - #19 - All-Pairs Shortest Paths: CLRS Chapter 23; Topic 19 Notes; screencasts 19*; MIT Lecture 19

Week 13: Shortest Paths Continued; Midterm

• Mon 11/14 - Midterm 2 Review: (Bring questions)
• Wed 11/16 - Midterm 2: Topics 9-17

Week 14: Midterm Results Review; Maximum Flow in Graphs

• Mon 11/21 - Review of Midterm Results
• Wed 11/23 - #20 - Maximum Flow:
  CLRS Sections 24.1-24.3; Topic 20 Notes; screencasts 20*.

Week 15: Complexity Theory; NP-Completeness

• Mon 11/28 - #24 - Complexity Theory & NP-Completeness:
  CLRS Chapter 34; Topic 24 Notes; screencasts 24*; not covered in MIT video lectures.
• Wed 11/30 - Complexity Theory & NP-Completeness (continued)

Week 16: Multithreading; Review

• Mon 12/05 - #22 - Parallel Algorithms:
  CLRS Chapter 26 (emphasis on sections 26.1 and 26.3); Topic 22 Notes; no screencasts.
• Wed 12/07 - Review (LAST DAY CLASS). Review for final exam.

---

Finals Week:

• **Final Exam ** - Cumulative on all topics. Section 1: F 12:00 – 2:00 pm, Section 2: F 2:15 - 4:15

---