ICS 311 Fall 2015 Index
This is an index of web pages for ICS 311 Algorithms, taught Fall 2015 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/f15/, and on YouTube. However, course participants
will need to log into Laulima regularly to watch screencasts, submit assignments, and
to use other facilities such as discussions and the mail tool as needed. Classes are in Webster 101
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
- 08/24 - #1 & #4 - Introduction to Course, Examples of Analysis with Insertion Sort, Review of Basic Data Structures:
CLRS Chapters 1 & 10;
Topic 01 Notes;
Topic 04 Notes
- 08/26 - #2 & #3 - Growth of Functions and Asymptotic Concepts:
CLRS Chapters 2.1-2.2 & 3;
Topic 02 Notes;
Topic 03 Notes
- Week 2
- 08/31 - #7 - Divide & Conquer and Analysis of Recurrences:
CLRS Chapter 2.3, 4 (4.1 & 4.3-4.5); Topic 07 Notes
- 08/31 - Drop date (without W)
- 09/02 - #8 - Binary Search Trees: CLRS Sections 12.1-12.3 (skim 12.4);
Topic 08 Notes
- Week 3
- 09/07 - HOLIDAY
- 09/09 - #11 - Balanced Trees (2-3-4 and Red-Black):
Sedgewick Chapter 15 & CLRS Chapter 13;
Topic 11 Notes
- Week 4
- 09/14 - #9 - Heaps, Heapsort and Priority Queues: CLRS Chapter 6 (all);
Topic 09 Notes
- 09/16 - #5a - Probabilistic Analysis :
CLRS Chapter 7 ;
Topic 05A Notes
- Week 5
- 09/21 - #5b - Randomized Algorithms, Quicksort :
CLRS Chapter 7 (all);
Topic 05B Notes
- 09/23 - #6 - Hash Tables: CLRS Sections 11.1-11.4;
Topic 06 Notes
- Week 6
- 09/28 - #10a - Selection and Order Statistics: CLRS Chapters 9; MIT Video Lecture 06; no lecture notes for this topic.
- 09/30 - #10b - Theoretical Limits, and O(n) Sorts: CLRS Chapters 8;
Topic 10 Notes
- Week 7
- 10/05 - Pre-Midterm 1 Review
- 10/07 - Midterm 1
- Week 8
- 10/12 - #12a - Dynamic Programming:
CLRS Chapters 15.1-15.3
Topic 12A Notes
- 10/14 - #12b - Dynamic Programming (cont.):
CLRS Chapter 15.4-15.5
Topic 12B Notes
- Week 9
- 10/19 - #13 - Greedy Algorithms & Huffman Codes:
CLRS Sections 16.1-16.3;
Topic 13 Notes
- 10/21 - #14A - Graph Representations, BFS, DFS:
CLRS Chapter 22.1-22.3; Goodrich & Tamassia excerpt on Representations;
Optionally Newman (2010) chapter 9 in Laulima;
Topic 14A Notes
- 10/23 - Drop date (with W)
- Week 10
- 10/26 - #14B - Topological Sort, Strongly Connected Components:
CLRS Chapter 22.4-22.5;
Topic 14B Notes
- 10/28 - #16 - Disjoint Sets and Union-Find:
CLRS Sections 21.1-21.3;
Topic 16 Notes (leave out the linked representation)
- Week 11
- 11/02 - #17 - Minimum Spanning Trees :
CLRS Chapter 23;
Topic 17 Notes
- 11/04 - #18 - Single-Source Shortest Paths:
CLRS Sections 24.1-24.3;
Topic 18 Notes
- Week 12
- 11/09 - #19 - All-Pairs Shortest Paths
CLRS Chapter 25;
Topic 19 Notes
- 11/11 - HOLIDAY
- Week 13
- 11/16 - Midterm 2
- 11/18 - Midterm 2 Review
- Week 14
- 11/23 - #20 - Maximum Flow:
CLRS Sections 26.1-26.3;
Topic 20 Notes
- 11/25 - #20 - Maximum Flow (continued):
CLRS Sections 26.1-26.3;
Topic 20 Notes
- Week 15
- 11/30 - #24 - Complexity Theory & NP-Completeness: CLRS Chapter 34; Topic 24 Notes
- 12/02 - #25 - Approximation Algorithms:
CLRS Chapter 35;
Topic 25 Notes
- Week 16
- 12/07 - #22 - Multithreading CLRS Chapter 27 (emphasis on sections 27.1 and 27.3); Topic 22 Notes
- 12/09 - Special Topic (TBD) and/or Course Review
The problems sets are being revised for Fall 2015, and will be released here and in Laulima when ready.
- Problem Set #1
(Topics 1-4) due 22:00 (10:00 pm) Friday August 28th
- Problem Set #2
(Topics 7 & 8) due 22:00 (10:00 pm) Friday September 4th
- Problem Set #3
(Topic 11) due 22:00 (10:00 pm) Friday September 11th
- Problem Set #4
(Topics 9 & 5a) due 22:00 (10:00 pm) Friday September 18th
- Problem Set #5
(Topic 5b & 6) due 22:00 (10:00 pm) Friday September 25th
- Problem Set #6
(Topics 10a & 10b) due 22:00 (10:00 pm) Friday October 2nd
- Problem Set #7
(Topics 12a & 12b) due 22:00 (10:00 pm) Friday October 16th
- Problem Set #8
(Topics 13 & 14a) due 22:00 (10:00 pm) Friday October 23rd
- Problem Set #9
(Topic 14b & 16) due 22:00 (10:00 pm) Friday October 30th
- Problem Set #10
(Topics 17 & 18) due 22:00 (10:00 pm) Friday November 6th
- Problem Set #11
(Topic 19) due 22:00 (10:00 pm) Friday November 13th
- Problem Set #12
(Topic 20) due 22:00 (10:00 pm) Friday November 27th
- Problem Set #13
(Topics 24 & 25) due 22:00 (10:00 pm) Friday December 4th
- 10/07: Midterm 1 - Topics 1-11, in Webster 101
- 11/16: Midterm 2 - Topics 10, 12-14, 16-19, in Webster 101
- Final Exam: Cumulative on all topics (1-20, 22, 24, & 25), in Webster 101
- Section 1 (MW1:30-3:10): Friday 2:15-4:15pm
- Section 2 (MW4:00-5:40): Wednesday 4:30-6:30pm
Nodari Sitchinava (based on material by Dan Suthers)
