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

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]

Homework

Takehome exam

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