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
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, Director's 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] Notes 10
11 Fri Nov 8 Range Queries [BKOS00, Chapters 5, 10.2] Notes 11
12 Fri Nov 15 Interval Trees, Segment Trees [BKOS00, Chapter 10] Notes 12 Homework 5 due
Submission Server
13 Fri Nov 22 External Memory Algorithms [AV88]
[CLRS09, Chapter 18]
[V06, Chapters 2, 5.2, 6.1, 7.2, 11.1]
[D02, Section 4.1]
14 Fri Nov 29 HOLIDAY: Thanksgiving
15 Fri Dec 6 String Algorithms [CLRS09, Chapter 32]
[E19, Director's Cut 7 ]
[KSB06]
Project due
Fri Dec 13 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.

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

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