## ICS 621 Fall 2021 Analysis of Algorithms## AboutThis 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 ScheduleThe 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.
## 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, [CLRS09] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, [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. |