# 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

## Topics

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.1-2.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.3-4.5); Topic 07 Notes
• 01/23 - Recitation: Problem Set #2 due.
• 01/24 - #8 - Binary Search Trees: CLRS Sections 12.1-12.3 (skim 12.4); Topic 08 Notes
• Week 4
• 01/29 - #11 - Balanced Trees (2-3-4 and Red-Black): 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
• Week 6
• 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.1-15.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.4-15.5; additional examples in the rest of Chapter 5 of Jeff Erickson's lecture notes (sections 5.5-5.9); Topic 12B Notes
• 03/09 - Drop date (with W)
• Week 10
• 03/12 - #13 - Greedy Algorithms & Huffman Codes: CLRS Sections 16.1-16.3; Topic 13 Notes
• 03/13 - Recitation: Problem Set #8 due.
• 03/14 - #14a - Graph Representations, BFS, DFS: CLRS Chapter 22.1-22.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.4-22.5; Topic 14B Notes
• 03/20 - Recitation: Problem Set #9 due.
• 03/21 - #16 & #17 - Disjoint Sets, Union-Find, Minimum Spanning Trees: CLRS Sections 21.1-21.3 & Chapter 23; Topic 16 Notes (leave out the linked representation); Topic 17 Notes

• SPRING RECESS: 03/26 — 03/30

• Week 12
• 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.1-26.3; Topic 20 Notes
• 04/17 - Recitation: Midterm 2 review.
• 04/18 - #20 - Maximum Flow (continued): CLRS Sections 26.1-26.3; Topic 20 Notes
• Week 15
• 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 - Special Topic (TBD) and/or Course Review

## Problem Sets

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.

## Exam Dates

• 02/26: Midterm 1 - Topics 1-10a, 11 in Webster 101
• 04/11: 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:15-3:30): Monday 2:15-4:15pm
• Section 2 (MW 4:30-5:45): Monday 4:30-6:30pm

Nodari Sitchinava (based on material by Dan Suthers)