ICS 621 Fall 2021 Analysis of Algorithms


This is a graduate-level course in the design and analysis of algorithms. It picks up where an undergraduate algorithms course (e.g. ICS 311) leaves off, covering topics such as amortized analysis, data structure persistency, computational geometry, cache-efficient algorithms, and parallel algorithms.

Topics and Schedule

The following is a  tentative  schedule of the topics that will be covered in this class and is subject to change. Those topics that have an overlap with the topics covered in ICS 311, will be covered at greater depth and detail. Therefore, students are expected to know the material from ICS 311 and are encouraged to review it prior to the start of the semester.

Week Date Topic Lecture Notes/Reading Scribe Notes Due
1 Aug 27 Introduction
Review of ICS 311
ICS 311
2 Sep 3 Amortized analysis [CLRS09, Ch 17] Notes 01
3 Sep 10 Binomial Heaps [CLRS01,Ch 19]
Notes 02 Homework 1
4 Sep 17 Fibonacci Heaps [CLRS09,Ch 19]
Notes 03 Homework 2
5 Sep 24 Dynamic Programming [CLRS09, Ch 15]
[E19, Ch 3]
Notes 04
6 Oct 1 Self-adjusting
Data Structures
[ST85, FSST86] Notes 05
7 Oct 8 LECTURE CANCELLED Homework 3
8 Oct 15 Randomized Search Trees [E19, Directors cut 3 ] Notes 06
9 Oct 22 Tail bounds [E19, Director's cut 4 ] Notes 07
10 Oct 29 Applications of Tail bounds [E19, Director's cut 4 ] Homework 4
Project Proposal
11 Nov 5 Computational Geometry I [BKOS00 Chapter 1] Homework 5
12 Nov 12 Computational Geometry II [BKOS00, Chapters 2.1-2.2, 7]
13 Nov 19 External Memory Algorithms [AV88]
[CLRS09, Chapter 18]
[V06, Chapters 2, 5.2, 6.1, 7.2, 11.1]
[D02, Section 4.1]
Homework 6

Submission Server

Project progress report
14 Nov 26 HOLIDAY: Thanksgiving
15 Dec 3 Parallel Algorithms [J92]]
Final Project

Reading Material

[AV88] Alok Aggarwal, Jeffrey S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9), pages 1116-1127, 1988. (Link through UH Libraries – requires UH account)

[BKOS00] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2000. ISBN: 3540656200. Availability at UH Library.

[CLRS01] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 2nd Edition. The MIT Press, 2001. ISBN: 0-262-03293-7. Availability at UH Library.

[CLRS09] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 3rd Edition. The MIT Press, 2009. ISBN: 9780262033848. Available online at UH Library.

[D02] Erik Demaine, Cache-oblivious Algorithms and Data Structures, 2002.

[DSST89] J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan: Making Data Structures Persistent, Journal of Computer and System Sciences 38(1): 86-124, 1989.

[E19] Jeff Erickson, Algorithms, 1st Edition. Available free online, 2019.

[FSST86] Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, Robert E. Tarjan. The pairing heap: a new form of self-adjusting heap. Algorithmica, 1(1): 111–129, 1986.

[FLPR12] Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. Cache-Oblivious Algorithms. ACM Transactions on Algorithms 8(1), pages 4:1-4:22. 2012 (Link through UH Libraries – requires UH account)

[J92] Joseph JáJá, Introduction to Parallel Algorithms. Addison Wesley, 1992. ISBN: 9780201548563. Availability at UH Library.

[KSB06] Juha Karkkainen, Peter Sanders, and Stefan Burkhardt. Linear work suffix array construction. Journal of the ACM, 53(6):918–936, 2006.

[MM17] Michael Mitzenmacher and Eli Upfal. Probability and Computing. Cambridge University Press, 2017. ISBN: 9781107154889. Availability at UH Library.

[ST85] Daniel D. Sleator, Robert E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652-686, 1985.

[V06] Jeffrey S. Vitter. Algorithms and Data Structures for External Memory Foundations and Trends in Theoretical Computer Science, 2(4), pages 305-474, 2006.