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]
2	Fri	Sep 6	Binomial Heaps	[CLRS01,Ch 19]		Homework 1 due
3	Fri	Sep 13	Review of Induction	[E19, Appendix I]
4	Fri	Sep 20	Fibonacci Heaps	[CLRS09, Ch 19]		Homework 2 due
5	Fri	Sep 27	Dynamic Programming	[CLRS09, Ch 15] [E19, Ch 3]
6	Fri	Oct 4	Self-adjusting Data Structures	[ST85, FSST86]
7	Fri	Oct 11	Randomized search trees	[E19, Directors cut 3 ]		Homework 3 due
8	Fri	Oct 18	Tail Bounds	[E19, Director's cut 4 ]		Project Proposal due
9	Fri	Oct 25	Computational Geometry: Convex Hulls	[BKOS00 Chapter 1]		Homework 4 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	Interval Trees, Segment Trees	[BKOS00, Chapter 10]		Homework 5 due
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.