ICS 311 Spring 2018 Index
This is an index of web pages for ICS 311 Algorithms, taught in Spring 2018 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/s18/, and on YouTube. However, course participants
will need to log into Laulima regularly to watch screencasts and
to use other facilities such as discussions and the mail tool as needed. Classes are in Webster 101 and POST 319.
Contents
 Schedule: A weekly listing of events (includes lecture notes,
problem sets, projects, and exams).
 Syllabus: Overview of course and plan.
 Topics: Summary of weekly topics.
 Problem Sets: List of active and planned problem sets.
 Exams: Planned exam dates
This is not a complete schedule: see the Schedule for that. CLRS is the Cormen Leiserson Rivest and Stein textbook. Topic numbers are not in sequence due to changes to the curriculum since 2014.
 Week 1
 01/08  #1 & #4  Introduction to Course, Review of Basic Data Structures:
CLRS Chapters 1 & 10;
Topic 01 Notes;
Topic 04 Notes
 01/09  Recitation: Review of proof techniques.
 01/10  #2  Proving Correctness; Analyzing Algorithms:
CLRS Chapters 2.12.2 ;
Topic 02 Notes;
 Week 2
 01/15  HOLIDAY
 01/16  Recitation: Problem Set #1 due. Drop date (without W)
 01/17  #3  Growth of Functions and Asymptotic Concepts:
CLRS Chapter 3; Topic 03 Notes
 Week 3
 01/22  #7  Divide & Conquer; Analysis of Recurrences:
CLRS Chapter 2.3, 4 (4.1 & 4.34.5); Topic 07 Notes
 01/23  Recitation: Problem Set #2 due.
 01/24  #8  Binary Search Trees: CLRS Sections 12.112.3 (skim 12.4);
Topic 08 Notes
 Week 4
 01/29  #11  Balanced Trees (234 and RedBlack):
Sedgewick Chapter 15 & CLRS Chapter 13;
Topic 11 Notes
 01/30  Recitation: Problem Set #3 due.
 01/31  #9  Heaps, Heapsort and Priority Queues: CLRS Chapter 6 (all);
Topic 09 Notes
 Week 5
 02/05  #5a  Probabilistic Analysis :
CLRS Chapter 7 ;
Topic 05A Notes
 02/06  Recitation: Problem Set #4 due.
 02/07  #5b  Randomized Algorithms, Quicksort :
CLRS Chapter 7 (all);
Topic 05B Notes
 Week 6
 02/12  #6  Hash Tables: CLRS Sections 11.111.4;
Topic 06 Notes
 02/13  Recitation: Problem Set #5 due.
 02/14  #10a  Selection and Order Statistics: CLRS Chapters 9; MIT Video Lecture 06; no lecture notes for this topic.
 Week 7
 02/19  HOLIDAY
 02/20  Recitation: Problem Set #6 due.
 02/21  #10b  Theoretical Limits, and O(n) Sorts: CLRS Chapters 8;
Topic 10 Notes
 Week 8
 02/26  Midterm 1
 02/27  Recitation: Midterm 1 review.
 02/28  Recursive algorithms review:
Chapter 1 of Jeff Erickson's lecture notes
 Week 9
 03/05  #12a  Dynamic Programming:
CLRS Chapters 15.115.3
and Chapter 5 of Jeff Erickson's lecture notes (through Section 5.4);
Topic 12A Notes
 03/06  Recitation: Problem Set #7 due.
 03/07  #12b  Dynamic Programming (cont.):
CLRS Chapter 15.415.5;
additional examples in the rest of Chapter 5 of Jeff Erickson's lecture notes (sections 5.55.9);
Topic 12B Notes
 03/09  Drop date (with W)
 Week 10
 03/12  #13  Greedy Algorithms & Huffman Codes:
CLRS Sections 16.116.3;
Topic 13 Notes
 03/13  Recitation: Problem Set #8 due.
 03/14  #14a  Graph Representations, BFS, DFS:
CLRS Chapter 22.122.3; Chapter 18 of Jeff Erickson's lecture notes; Goodrich & Tamassia excerpt on Representations;
Topic 14a Notes
 Week 11
 03/19  #14b  Topological Sort, Strongly Connected Components:
CLRS Chapter 22.422.5;
Topic 14B Notes
 03/20  Recitation: Problem Set #9 due.
 03/21  #16 & #17  Disjoint Sets, UnionFind, Minimum Spanning Trees:
CLRS Sections 21.121.3 & Chapter 23;
Topic 16 Notes (leave out the linked representation);
Topic 17 Notes

SPRING RECESS: 03/26 — 03/30
 Week 12
 04/02  #18  SingleSource Shortest Paths:
CLRS Sections 24.124.3;
Topic 18 Notes
 04/03  Recitation: Problem Set #10 due.
 04/04  #19  AllPairs Shortest Paths
CLRS Chapter 25;
Topic 19 Notes
 Week 13
 04/09  Dynamic Programming revisited Problem Set #11 due.
 04/10  Recitation: Midterm preview.
 04/11  Midterm 2
 Week 14
 04/16  #20  Maximum Flow:
CLRS Sections 26.126.3;
Topic 20 Notes
 04/17  Recitation: Midterm 2 review.
 04/18  #20  Maximum Flow (continued):
CLRS Sections 26.126.3;
Topic 20 Notes
 Week 15
 04/23  #24  Complexity Theory & NPCompleteness: CLRS Chapter 34; Topic 24 Notes
 04/24  Recitation: Problem Set #12 due.
 04/25  #25  Approximation Algorithms:
CLRS Chapter 35;
Topic 25 Notes
 Week 16
 04/30  #22  Multithreading CLRS Chapter 27 (emphasis on sections 27.1 and 27.3); Topic 22 Notes
 05/01  Recitation: Problem Set #13 due.
 05/02  Course Review
The problems sets will be released here and in Laulima when ready. They are due in person at the start of the class on the corresponding day. No late submissions will be accepted.
 Problem Set #1 (PDF)
(Topics 1, 2, & 4) due Tuesday January 16th at the beginning of class
 Problem Set #2 (PDF)
(Topic 3) due Tuesday January 23rd at the beginning of class
 Problem Set #3 (PDF)
(Topics 7 & 8) due Tuesday January 30th at the beginning of class
 Problem Set #4 (PDF)
(Topics 9 & 11) due Tuesday February 6rd at the beginning of class
 Problem Set #5 (PDF)
(Topic 5a & 5b) due Tuesday February 13th at the beginning of class
 Problem Set #6 (PDF)
(Topics 6 & 10a) due Tuesday February 20th at the beginning of class
 Problem Set #7 (PDF)
(Topic 10b) due Tuesday March 6th at the beginning of class
 Problem Set #8 (PDF)
(Topics 12a & 12b) due Tuesday March 13th at the beginning of class
 Problem Set #9 (PDF)
(Topic 13 & 14a) due Tuesday March 20th at the beginning of class
 Problem Set #10 (PDF)
(Topics 14b, 16 & 17) due Tuesday April 3rd at the beginning of class
 Problem Set #11 (PDF)
(Topics 18 & 19) due Monday April 9th at the beginning of class
 Problem Set #12 (PDF)
(Topic 20) due Tuesday April 24st
 Problem Set #13 (PDF)
(Topics 24 & 25) due Tuesday May 1st at the beginning of class
 02/26: Midterm 1  Topics 110a, 11 in Webster 101
 04/11: Midterm 2  Topics 10b, 1214, 1619, in Webster 101
 Final Exam: Cumulative on all topics (114, 1620, 22, 24, & 25) in Webster 101
 Section 1 (MW 2:153:30): Monday 2:154:15pm
 Section 2 (MW 4:305:45): Monday 4:306:30pm
Nodari Sitchinava (based on material by Dan Suthers)