ICS 311
Main
Schedule
Course Evaluations
Syllabus
Course Info
Format
Assessment/Grading
Policies

ICS 311 Spring 2019

This is an index of web pages for ICS 311 Algorithms, taught in Spring 2019 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/s19/, and on YouTube. Classes are in Webster 101 and POST 319.

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/07 - #1 & #4 - Introduction to Course; Review of Basic Data Structures

    • 01/08 - Recitation: Review of proof techniques

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

  • Week 2

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

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

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

  • Week 3

    • 01/21 - HOLIDAY

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

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

  • Week 4

    • 01/28 - #8 - Binary Search Trees

    • 01/29 - Recitation: Problem Set #3 due

    • 01/30 - #11 - Balanced Trees (2-3-4 and Red-Black)

      • Drop date (without W)

  • Week 5

    • 02/04 - #5a - Probabilistic Analysis

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

    • 02/06 - #5b - Randomized Algorithms, Quicksort

  • Week 6

    • 02/11 - #6 - Hash Tables

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

    • 02/13 - #10a - Selection and Order Statistics

  • Week 7

    • 02/18 - HOLIDAY

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

    • 02/20 - #10b - Theoretical Limits, and O(n) Sorts

  • Week 8

    • 02/25 - Midterm 1

    • 02/26 - Recitation: Midterm 1 review

    • 02/27 - Backtracking (Recursive algorithms review)

  • Week 9

    • 03/04 - #12a - Dynamic Programming

    • 03/05 - Recitation: Problem Set #7 due

    • 03/06 - #12b - Dynamic Programming (cont.)

  • Week 10

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

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

    • 03/13 - #14a - Graph Representations, BFS, DFS

  • SPRING RECESS: 03/18 — 03/22

  • Week 11

    • 03/25 - #14b - Topological Sort, Strongly Connected Components

    • 03/26 - HOLIDAY

    • 03/27 - #16 & #17 - Disjoint Sets, Union-Find, Minimum Spanning Trees

  • Week 12

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

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

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

  • Week 13

    • 04/08 - Dynamic Programming revisited

    • 04/09 - Recitation: Midterm preview

    • 04/10 - Midterm 2

  • Week 14

    • 04/15 - #20 - Maximum Flow

    • 04/16 - Recitation: Midterm 2 review

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

  • Week 15

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

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

    • 04/24 - #25 - Approximation Algorithms

  • Week 16

    • 04/29 - #22 - Multithreading

    • 04/30 - Recitation: Problem Set #13 due

    • 05/01 - 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, 2, & 4) due Tuesday January 15th at the beginning of class

  • Problem Set #2 (Topic 3 & 7) due Tuesday January 22nd at the beginning of class

  • Problem Set #3 (Topics 9) due Tuesday January 29th at the beginning of class

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

  • Problem Set #5 (Topic 5a & 5b) due Tuesday February 12th at the beginning of class

  • Problem Set #6 (Topics 6 & 10a) due Tuesday February 19th at the beginning of class

  • Problem Set #7 (Topic 10b) due Tuesday March 6th at the beginning of class

  • Problem Set #8 (Topics 12a & 12b) due Tuesday March 12th at the beginning of class

  • Problem Set #9 (Topic 13 & 14a) due Monday March 25th at the beginning of class

  • Problem Set #10 (Topics 14b, 16 & 17) due Tuesday April 2nd at the beginning of class

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

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

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

Exam Dates

  • 02/25: Midterm 1 - Topics 1-10a, 11 in Webster 101

  • 04/10: Midterm 2 - Topics 10b, 12-14, 16-19, in Webster 101

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

    • Section 1 (MW 2:30-3:45pm): Monday 2:15-4:15pm

    • Section 2 (MW 4:30-5:45pm): Monday 4:30-6:30pm