ICS 621 Fall 2024 Analysis of Algorithms

About

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	Reading	Lecture Slides	Due
1	Aug 30	Introduction (Brief) review of ICS 311	ICS 311
2	Sep 6	Amortized analysis Binomial Heaps	[CLRS22, Ch 16] [E19, Director's Cut 9 ] [CLRS01,Ch 19]	Lecture 1 Lecture 2	Homework 0
3	Sep 13	Binomial Heaps (cont.) Fibonacci Heaps	[CLRS01,Ch 19] [CLRS09,Ch 19]	Lecture 2 Lecture 3	Homework 1
4	Sep 20	Dynamic Programming	[CLRS22, Ch 14] [E19, Ch 3]
5	Sep 27	Dynamic Programming	[CLRS22, Ch 14] [E19, Ch 3]	Lecture 4
6	Oct 4	Self-adjusting Data Structures	[ST85, FSST86] [E19, Director's Cut 10.6 ]	Notes 5
7	Oct 11	Randomized Search Trees	[E19, Directors cut 3 ]	Notes 6	Homework 2 Submission Server
8	Oct 18	Tail bounds	[E19, Director's cut 4 ]	Notes 7
9	Oct 25	Applications of Tail bounds	[E19, Director's cut 4 ]	Notes 8
10	Nov 1	Computational Geometry I	[BKOS00 Chapter 1]	Notes 9	Homework 3
11	Nov 8	Computational Geometry II	[BKOS00, Chapters 2.1-2.2, 7.1-7.2]	Notes 10 Scribe Notes	Project Proposal
12	Nov 15	External Memory Algorithms	[AV88] [CLRS22, Chapter 18] [V06, Chapters 2, 5.2, 6.1, 7.2, 11.1] [D02, Section 4.1]	Notes 11	Homework 4 Submission Server
13	Nov 22	Parallel Algorithms	[J92]	Lecture 12
14	Nov 29	HOLIDAY: Thanksgiving
15	Dec 6	String algorithms	[CLRS22, Chapter 32] [E19, Director's Cut 7 ] [KSB06]	Lecture 13a Lecture 13b	Final Project
16	Dec 10	NO FINAL EXAM

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.

[CLRS22] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 4rd Edition. The MIT Press, 2022. ISBN: 9780262046305.

[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.