ICS 621 Fall 2022 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	Lecture Notes/Reading	Due
1	Aug 26	Introduction Review of ICS 311	ICS 311
2	Sep 2	Amortized analysis	[CLRS09, Ch 17]
3	Sep 9	Binomial Heaps	[CLRS01,Ch 19] Slides	Homework 1
4	Sep 16	Fibonacci Heaps	[CLRS09,Ch 19] Slides	Homework 2
5	Sep 23	Dynamic Programming	[CLRS09, Ch 15] [E19, Ch 3] Slides
6	Sep 30	Self-adjusting Data Structures	[ST85, FSST86]	Homework 3 Submission Server
7	Oct 7	Randomized Search Trees	[E19, Directors cut 3 ]
8	Oct 14	Tail bounds	[E19, Director's cut 4 ]	Homework 4
9	Oct 21	Applications of Tail Bounds	[E19, Director's cut 4 ]
10	Oct 28	Computational Geometry I	[BKOS00 Chapter 1] Slides	Homework 5 Project Proposal
11	Nov 4	Computational Geometry II	[BKOS00, Chapters 2.1-2.2, 7]
12	Nov 11	HOLIDAY: Veterans’ Day
13	Nov 18	Parallel Algorithms	[J92] Slides	Homework 6 Submission Server Project progress report
14	Nov 25	HOLIDAY: Thanksgiving
15	Dec 2	External Memory Algorithms	[AV88] [CLRS09, Chapter 18] [V06, Chapters 2, 5.2, 6.1, 7.2, 11.1] [D02, Section 4.1]	Final Project
16	Dec 9	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.

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