ICS 621 Fall 2021 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	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] Slides	Notes 02	Homework 1
4	Sep 17	Fibonacci Heaps	[CLRS09,Ch 19] Slides	Notes 03	Homework 2
5	Sep 24	Dynamic Programming	[CLRS09, Ch 15] [E19, Ch 3] Slides	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]] Slides		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.

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