|
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
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 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)
Week 5
02/10 - #5A - Probabilistic Analysis
02/11 - Recitation: Problem Set #4 due
02/12 - #5B - Randomized Algorithms, Quicksort
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 9
03/09 - #12A - Dynamic Programming
03/10 - Recitation: Midterm 1 review
03/11 - #12B - Dynamic Programming (cont.)
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 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
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)
|
