UNIVERSITY OF AARHUS
BRICS INTERNATIONAL PHD SCHOOL

Algorithms, Fall 1999
Lecturers · Time and place · Course description · Schedule · Literature · Handouts · Homework · Takehome exam · Evalutation

Lecturers

Gerth Stølting Brodal and Rolf Fagerberg.

Time and place

Tuesdays 10.15-12.00 in Colloquium B4 and Wednesdays 9.15-11.00 in Auditorium D4.

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 25 Graph representations, BFS, DFS, Topological Sorting [Cormen et al., Chap. 23.1-23.4]
  October 27 Strongly connected components [Dijkstra, Chap. 25]
45 November 2 Shortest path [Kozen, Lecture 5], Amortized analysis
  November 3 Binomial queues [Kozen, Lecture 8], Fibonacci heaps [Kozen, Lecture 9]
46 November 9 Maximum flow [Goldberg; Kozen, Lecture 16]
  November 10 Maximum flow [Kozen, Lectures 17 and 18]
47 November 16 Convex hull [Cormen et al., Chap. 35.1 and 35.3; Chan, Sections 1-2 and 4-5]
  November 17 Segment intersection [Cormen et al., Chap. 35.2], Suffix tree construction [Ukkonen]
48 November 23 Suffix tree construction [Ukkonen]; String matching [Cormen et al., Chap. 34.1, 34.3-4]
  November 24 FKS hashing [Motwani and Raghavan, Chap. 8.5]
49 November 30 Lower bounds, Decision trees, Algebraic decision trees [Baase, Chap. 2.4; Skyum]
  December 1 Algegraic decision trees [Skyum]; Dynamic programming [Cormen et al., Chap. 16]
50 December 7 Quick sort, Randomized convex hull, Treaps [Motwani and Randomized, Chap. 9.1-9.2; Seidel and Aragon]
  December 8 Treaps, Paging algorithms [Seidel and Aragon; Albers, Chap. 1-2]

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. [Ukkonen]
  9. [Cormen et al., Chap. 34]
  10. [Motwani and Raghavan, Chap. 8-9.2]
  11. [Baase, Chap. 2.4]
  12. [Skyum]
  13. [Cormen et al., Chap. 16]
  14. [Seidel and Aragon]
  15. [Cherkassky et al.]
  16. [Albers]
  17. Literature Notes on Homeworks and the Takehome Exam (references.tex)

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