## ICS 621 Fall 2019 Analysis of Algorithms## Topics(A subset) of the following topics will be covered in class during the semester. Those topics that have an overlap with the topics covered in ICS 311, will be covered at greater depth and detail. Therefore, students are encouraged to review the material from ICS 311 on their own. The topics will be filled into the schedule as they are covered. Algorithm Design and Analysis Techniques Amortized analysis Probabilistic analysis Divide & Conquer/Backtracking Dynamic Programming Greedy Algorithms/Matroid Theory (Partial) Persistency Fractional Cascading
Data Structures Search trees Priority Queues Dictionaries and Hash Tables Geometric Data Structures
Tree/Graph Algorithms Computational Geometry String Algorithms Word-level parallelism Complexity Theory and Lower bounds Parallel Algorithms External Memory (cache-efficient) algorithms
## ScheduleSpecific topics will be filled in the schedule below as they are covered during 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. [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. [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. [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. [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. |