ICS 311 Spring 2020

This is an index of web pages for ICS 311 Algorithms, taught in Spring 2020 by Nodari Sitchinava. Generally the course is run within Laulima. Notes and other material are posted on this site, http://www2.hawaii.edu/~nodari/teaching/s20/, and on YouTube. There are two sections of the class. Section 1 classes are held in Holmes 243 and POST 318A. Section 2 classes are held in Webster 101 and POST 126.

Contents

  • Topics: Summary of weekly topics.

  • Problem Sets: List of active and planned problem sets.

  • Exams: Planned exam dates

Topics

For a detailed schedule, including reading assignments see the Schedule page. Topic numbers are not in sequence due to changes to the curriculum since 2014.

  • Week 1

    • 01/13 - #1 & #4 - Introduction to Course; Review of Basic Data Structures

    • 01/14 - Recitation: Review of proof techniques

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

  • Week 2

    • 01/20 - HOLIDAY

    • 01/21 - Recitation: Problem Set #1 due

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

  • Week 3

    • 01/27 - #7 - Divide & Conquer, Analysis of Recurrences

    • 01/28 - Recitation: Problem Set #2 due

    • 01/29 - #9 - Heaps, Heapsort and Priority Queues

  • Week 4

    • 02/03 - #8 - Binary Search Trees

    • 02/04 - Recitation: Problem Set #3 due

    • 02/05 - #11 - Balanced Trees (2-3-4 and Red-Black)

      • Drop date (without W)

  • Week 5

    • 02/10 - #5A - Probabilistic Analysis

    • 02/11 - Recitation: Problem Set #4 due

    • 02/12 - #5B - Randomized Algorithms, Quicksort

  • Week 6

    • 02/17 - HOLIDAY

    • 02/18 - Recitation: Problem Set #5 due

    • 02/19 - #6 - Hash Tables

  • Week 7

    • 02/24 - #10A - Selection and Order Statistics

    • 02/25 - Recitation: Problem Set #6 due

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

  • Week 8

    • 03/02 - Backtracking (Recursive algorithms review)

      • Problem Set #7 due

    • 03/03 - Recitation: Midterm 1 preview

    • 03/04 - Midterm 1

  • Week 9

    • 03/09 - #12A - Dynamic Programming

    • 03/10 - Recitation: Midterm 1 review

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

  • SPRING RECESS: 03/16 — 03/20

  • Week 10

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

    • 03/24 - Recitation: Problem Set #8 due

    • 03/25 - #14A - Graph Representations, BFS, DFS

    • 03/26 - HOLIDAY - No office hours

    • 03/27 - Drop date (with W)

  • Week 11

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

    • 03/31 - Recitation: Problem Set #9 due

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

  • Week 12

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

    • 04/07 - Recitation: Problem Set #10 due

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

    • 04/10 - HOLIDAY - No office hours

  • Week 13

    • 04/13 - Additional practice with Dynamic Programming

    • 04/14 - Recitation: Problem Set #11 due

    • 04/15 - Midterm 2

  • Week 14

    • 04/20 - #20 - Maximum Flow

    • 04/21 - Recitation: Midterm 2 review

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

  • Week 15

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

    • 04/28 - Recitation: Problem Set #12 due

    • 04/29 - #25 - Approximation Algorithms

  • Week 16

    • 05/04 - #22 - Multithreading

    • 05/05 - Recitation: Problem Set #13 due

    • 05/06 - Course Review

Problem Sets

The problems sets will be released here at least a week before they are due. They are due in person at the start of the class on the corresponding day. No late submissions will be accepted.

  • Problem Set #1 (Topics 1, 3, & 4) due Tuesday January 21st at the beginning of class

  • Problem Set #2 (Topic 2) due Tuesday January 28th at the beginning of class

  • Problem Set #3 (Topics 7 & 9) due Tuesday February 4th at the beginning of class

  • Problem Set #4 (Topics 8 & 11) due Tuesday February 11th at the beginning of class

  • Problem Set #5 (Topic 5A & 5B) due Tuesday February 18 at the beginning of class

  • Problem Set #6 (Topics 6) due Tuesday February 25 at the beginning of class

  • Problem Set #7 (Topic 10A & 10B) due Monday March 2nd at the beginning of class

  • Problem Set #8 (Topics 12A & 12B) due Tuesday March 24th at the beginning of class

  • Problem Set #9 (Topic 13 & 14A) due Tuesday March 31st at the beginning of class

  • Problem Set #10 (Topics 14B, 16 & 17) due Tuesday April 7th at the beginning of class

  • Problem Set #11 (Topics 18 & 19) due Tuesday April 14th at the beginning of class

  • Problem Set #12 (Topic 20) due Tuesday April 28th at the beginning of class

  • Problem Set #13 (Topics 24 & 25) due Tuesday May 5th at the beginning of class

Exam Dates

  • 03/04: Midterm 1 - Topics 1-11 in class

  • 04/15: Midterm 2 - Topics 12-14, 16-19 Take-home due to move to online teaching

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

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

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