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

Schedule

Specific topics will be filled in the schedule below as they are covered during the semester.

Week Day Date Topic Lecture Notes/Reading Scribe notes Comments
1 Fri Aug 30 Introduction
Amortized analysis
[CLRS09, Ch 17] Notes 01
2 Fri Sep 6 Binomial Heaps [CLRS01,Ch 19]
Slides
Notes 02 Homework 1 due
3 Fri Sep 13 Review of Induction [E19, Appendix I]
4 Fri Sep 20 Fibonacci Heaps [CLRS09, Ch 19]
Slides
Notes 04 Homework 2 due
5 Fri Sep 27 Dynamic Programming [CLRS09, Ch 15]
[E19, Ch 3]
Fall'18 DP II Slides
Fall'18 DP III Slides
Notes 05
6 Fri Oct 4 Self-adjusting Data Structures [ST85, FSST86] Notes 06
7 Fri Oct 11 Randomized search trees [E19, Directors cut 3 ] Notes 07 Homework 3 due
Submission Server
8 Fri Oct 18 Tail Bounds [E19, Directors cut 4 ] Notes 08 Project Proposal due
9 Fri Oct 25 Computational Geometry: Convex Hulls [BKOS00 Chapter 1] Notes 09 Homework 4 due due
10 Fri Nov 1 Computational Geometry: Plane sweep [BKOS00, Chapters 2.1-2.2, 7]
11 Fri Nov 8 Range Queries [BKOS00, Chapters 5, 10.2]
12 Fri Nov 15 Homework 5 due
Submission Server
13 Fri Nov 22
14 Fri Nov 29 HOLIDAY: Thanksgiving
15 Fri Dec 6 Project due
Fri Dec 13 NO FINAL EXAM

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

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