## 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[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, [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. [J92] Joseph JáJá, Introduction to Parallel Algorithms. Addison Wesley, 1992. ISBN: 9780201548563. [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. |