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
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 4
01/28  #8  Binary Search Trees
01/29  Recitation: Problem Set #3 due
01/30  #11  Balanced Trees (234 and RedBlack)
Week 5
02/04  #5a  Probabilistic Analysis
02/05  Recitation: Problem Set #4 due
02/06  #5b  Randomized Algorithms, Quicksort
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
Week 11
03/25  #14b  Topological Sort, Strongly Connected Components
03/26  HOLIDAY
03/27  #16 & #17  Disjoint Sets, UnionFind, Minimum Spanning Trees
Week 12
04/01  #18  SingleSource Shortest Paths
04/02  Recitation: Problem Set #10 due
04/03  #19  AllPairs Shortest Paths
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 & NPCompleteness
04/23  Recitation: Problem Set #12 due
04/24  #25  Approximation Algorithms
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 110a, 11 in Webster 101
04/10: Midterm 2  Topics 10b, 1214, 1619, in Webster 101
Final Exam: Cumulative on all topics (114, 1620, 22, 24, & 25) in Webster 101
