ICS621 Analysis of Algorithms (CRN 79344)

Mon & Wed 9:00AM - 10:15AM HOLM 247


ICS621 is an advanced algorithms course focusing on analysis of algorithms. For more information, please consult the syllabus.

Instructor: Lipyeow Lim. POST 303E. Wed 10:30AM-12:30PM or by appointment. 808-956-3495. lipyeow at hawaii dot edu.

Examinations: There is no written final exam, but there will be a course project.

Textbooks: “CLRS” – Introduction to Algorithms (3rd Ed.) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, ISBN-13 978-0-262-03384-8.

Communications: We will be using Slack for communications (falling back on email when necessary). Please post questions there so that the whole class can participate & benefit.

Remote Students: Participate via skype (id: Lipyeow).

Late policy: work submitted past due date and time will receive zero credits.

Student Conduct: All students are expected to conduct themselves above and beyond the standard set forth in UH Systemwide Student Conduct Code.

Disability: Any student who feels s/he may need an accommodation based on the impact of a disability is invited to contact the instructor privately. The instructor would be happy to work with you, and the KOKUA Program (Office for Students with Disabilities) to ensure reasonable accommodations in the course. KOKUA can be reached at (808) 956-7511 or (808) 956-7612 (voice/text) in room 013 of the Queen Liliuokalani Center for Student Services.

Schedule

Week Date Topic Before Class In Class After Class
1 Mon Aug 21 Introduction - organization Syllabus
1 Wed Aug 23 Introduction - model Ch.1 | Asymptotics CLRS 2-3
2 Mon Aug 28 Sorting Ch 2-4 | SelectionSort | InsertionSort | MergeSort | Reccurences CLRS 2-2 | CLRS 2-4 Homework 1
2 Wed Aug 30 Sorting - heaps Ch 6 | Heaps | Heapsort CLRS 6-3 video
3 Mon Sep 4 Labor Day Holiday
3 Wed Sep 6 CLUSTER Conference. No Class.
4 Mon Sep 11 Sorting - quicksort Ch 7 | Quicksort | Worst Case Analysis | Average Case Analysis CLRS 7-5 | CLRS 7-6 HW1 due.
4 Wed Sep 13 Sorting - lower bounds Ch 8 | Lower Bounds | Counting Sort | Radix Sort | Bucket Sort CLRS 8-3
5 Mon Sep 18 Sorting - Order Statistics Ch 9 | Order Stats 1 Min Max | Order Stats 2 Median of Medians | Order Stats 3 Quicksort | Ch 12 | Binary Search Trees CLRS 9-1 | CLRS 12-3 Homework 2
5 Wed Sep 20 Trees Ch 14 | Red Black Trees | Order Statistics Red Black Trees | Interval Trees CLRS 14-2
6 Mon Sep 25 Heaps - Amortized Analysis Ch 17 | Amortized A. - Agg. Mtd | Amortized A. - Binary Cnt. Eg. | Amortized A. - Acc. Mtd | Amortized A. - Pot. Mtd | Amortized A. - Dyn. Tables CLRS 17-1
6 Wed Sep 27 Heaps - Amortized Analysis Ch 17 CLRS 17-2
7 Mon Oct 2 Heaps - Binomial Heaps Ch 19 (2nd Ed.) | Binomial Heaps 1 | Binomial Heaps 2 | Binomial Heaps 3 CLRS 2e-19-1 HW2 due.
7 Wed Oct 4 FutureFocus Conference. No f2f class. Prepare for exam.
8 Mon Oct 9 Mid-term Exam due at 12PM.
8 Wed Oct 11 Post Midterm Review & Project Project
9 Mon Oct 16 Heaps - Fibonacci Heaps Ch 19 | Fibonacci Heaps 1 | Fibonacci Heaps 2 | Fibonacci Heaps 3 | Fibonacci Heaps 4 | Fibonacci Heaps 5 CLRS 19-1 | CLRS 19-3
9 Wed Oct 18 Algorithm Design Methods - Dynamic Programming Ch 15 | Dynamic Programming 1 | Dynamic Programming 2 | Dynamic Programming 3 CLRS 15-2 Homework 3
10 Mon Oct 23 Trees - B+ Trees Ch 18 CLRS 18-1 | CLRS 18-2 Project proposal due.
10 Wed Oct 25 Project - Proposals
11 Mon Oct 30 Algorithm Design Methods - Greedy Algo Ch 16 | Greedy Algo 1 | Greedy Algo 2 | Greedy Algo 3 CLRS 16-1 | CLRS 16-5
11 Wed Nov 1 Algorithm Design Methods - Greedy Algo Ch 16 CLRS 16-5 video
12 Mon Nov 6 Hashing Ch 11 | Hashing 1 | Hashing 2 | Hashing 3 | Hashing 4 | Hashing 5 CLRS 11-1 HW3 due.
12 Wed Nov 8 Graph Algorithms Ch 22-23 | BFS | DFS | SCC | MST CLRS 22-2
13 Mon Nov 13 Graph Algorithms Ch 24-25 | Bellman Ford | Dijkstra | Constraints | All Pairs Shortest Path | Floyd Warshall Johnson CLRS 24-3 video
13 Wed Nov 15 Graph Algorithms Ch 26 | Max Flow Problem | Augmenting Paths | Ford Fulkerson Edmonds Karp | Matching CLRS 26-2 video | video
14 Mon Nov 20 NP-Completeness Ch 34 | Decision Problems | Encoding | Languages | NP | NPC | DTM | NTM
14 Wed Nov 22 NP-Completeness - Cook Levin Thm SAT to 3SAT | SAT to 3SAT proof | 3SAT to VC | 3SAT to VC Proof Garey & Johnson Ch 2
15 Mon Nov 27 NP-Completeness - NPC proofs CLRS 34-2
15 Wed Nov 29 NP-Completeness - approximation algo Ch 35 | Approx Algo VC | Approx Algo 3SAT CLRS 35-1
16 Mon Dec 4 Project Anson | Sayera | Suraj | Ryan
16 Wed Dec 6 Project Elliot | Jared | Selim | Gavin | David

About this site: Modules lists the topics covered. Learning outcomes collect all the desired student learning outcomes of all the modules. Readings list the “passive” learning opportunities like reviewing of textbook sections, web pages, screencasts, etc. Experiences list the “active” learning opportunities where you must actually demonstrate a capability.