UNIVERSITY OF AARHUS
BRICS INTERNATIONAL PHD SCHOOL

# Algorithms, Fall 1998

Lecturer · Time and place · Course description · Schedule · Literature · Handouts · Homework · Takehome exam · Evalutation

## Lecturer

Gerth Stølting Brodal.

## Time and place

Wednesdays,13.15-15.00, and Fridays, 11.15-13.00, in Coll. B2, starting October 28 and continuing for 7 weeks.

## Course description

The course is a graduate-level introduction to the design and analysis of algorithms. The aim of the course will be to explain basic methodological aspects such as amortized analysis of data structures, probabilistic analysis of algorithms or competitive analysis. To illustrate these, specific examples from important application areas - e.g. graph algorithms, string matching, or algebraic algorithms - will be discussed.
• Graph algorithms:
• Strongly connected componenets
• Max flow
• String matching: Knuth-Morris-Pratt algorithm
• Computational geometry: convex hulls, Voronoi diagrams
• Data structures:
• Hashing a' la Carter-Wegman
• Amortized analysis: binomial heaps, Fibonacci heaps
• Numerical algorithms:
• Finding best way to multiply matrices (dynamic programming)
• Solving systems of linear eq's
• FFT (and integeger multiplication via FFT)
• Randomization:
• Miller's primality test
• Computing maximal independent sets in parallel
• Skip lists, treaps
• Competitive analysis of paging heuristics
• Lower bounds:
• Sorting
Note: The syllabus given above is a bit ambitious; chances are that only a subset will be covered. The order given is not the one which will be followed. Furthermore, the content is subject to change according to contingencies.

## Schedule

 Week Date Topics 44 October 28 [Cormen et al., Chap. 23], [Dijkstra, Chap. 25]: BFS, DFS, Topological Sorting, Strongly Connected Components October 30 [Kozen, Lectures 5.1, 8-9]: Dijkstra's Single-Source Shortest Paths Algorithm, Binomial Heaps, Amortized analysis 45 November 4 [Kozen, Lectures 9, 16]: Fibonacci Heaps, Max Flow November 6 [Kozen, Lectures 17-18]: Max Flow 46 November 11 [Cormen et al., Chap. 35] Computational Geometry: Segment-Intersection, Convex Hull November 13 [Chan] Convex Hull 47 November 18 [Cheng and Janardan] Dynamic Planar Point Location November  20 [Cormen et al., Chap. 34.1,3-4] String Matching 48 November 25 [Motwani and Raghavan, Chap. 9.2, 8.2.] Randomized Convex Hull, Backwards Analysis, Random Treaps November 27 [Motwani and Raghavan, Chap. 8.3, 8.4.1-2] Skip Lists, Hash Tables 49 December 2 [Motwani and Raghavan, Chap. 8.4.3] Hash Tables, [Kozen, Lecture 36] Randomized Maximal Independent Sets in Parallel December 4 [Kozen, Lectures 37,38] Randomized Maximal Independent Sets in Parallel, Miller's Primality Test 50 December 9 [Kozen, Lectures 39] Miller's Primality Test December 11 [Albers, Chapter 1] Paging Algorithms

## Literature

• Susanne Albers, Competitive Online Algorithms, BRICS LS-96-2, 1996.
• Timothy M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete and Computational Geometry, 16, pages 361-368, 1996 .
• Siu Wing Cheng and Ravi Janardan, New Results on Dynamic Planar Point Location, SIAM Journal of Computing 21(5):972-999, 1992.
• Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, MIT Press, 1990.
• Edsger D. Dijkstra: A Discipline of Programming, Prentice-Hall, 1976.
• Andrew V. Goldberg, Recent Developments in Maximum Flow Algorithms, 6th Skandinavian Workshop on Algorithm Theory (SWAT '98), LNCS 1432, pages 1-10, 1998.
• Dexter C. Kozen, The Design and Analysis of Algorithms, Springer-Verlag, 1992.
• Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

## Handouts

1. [Cormen et al., Chap. 23]
2. [Dijkstra, Chap. 25]
3. [Kozen, Lectures 5, 8-9]
4. [Kozen, Lectures 16-18]
5. [Goldberg]
6. [Cormen et al., Chap. 35]
7. [Chan]
8. [Cheng and Janardan]
9. [Cormen et al., Chap. 34]
10. [Motwani and Raghavan, Chap. 8-9.2]
11. [Kozen, Lectures 36-37]
12. [Kozen, Lectures 38-39]
13. [Albers]

## Evaluation

Homeworks (2/3 of grade) and Take-home exam (1/3 of grade). A grade will be given on the A-F scale.

Page maintained by
Gerth Stølting Brodal <gerth@cs.au.dk>.