58053-7 Design and Analysis of Algorithms (5 cu)
In Spring 2004 the class was given in Finnish. For foreign students, and also those Finnish students who prefer a printed textbook to lecture notes, it is possible to get credit for the course by taking an exam based on the textbook
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Second Edition, MIT Press 2001. [Notice that there are significant changes from the first edition.]
If you want to use this option, please contact the lecturer well in advance of your planned exam.
For the exam you should read Chapters 1-5, 9, 15-17, 19-27, and 35. This also includes the sections marked with a star. The additional material introduced in the problem sections at the end of each chapter is not included, except for the method of generating functions (see below).
There are no formal pre-requisites, but in practice the students should be familiar with the material covered by the courses Data Structures and Theory of Computation offered by the departement. This course will introduce more advanced ideas building on top of those courses and will be sufficiently challenging even for students who do know the basics. (However the part covering decidability in Theory of Computation is not directly relevant here.)
Notice that the textbook does not exactly match what is taught in the lectures. Some comments on the chapters of the text book in relation to the course:
- 1. The Role of Algorithms in Computing
- 2. Getting Started
- 3. Growth of Functions
- The first three chapters are mainly general background that you presumably know from earlier courses. At lectures we covered this material very briefly to refresh people's memories. There will be no exam questions specifically about this material, but it is necessary for understanding what follows.
- 4. Recurrences
- The lecture course covers the whole material of this chapter, including the method of generating functions, introduced in Problem 4-5 (Fibonacci numbers) and further developed in Problem 12-4 (Number of different binary trees). This whole topic is an essential part of the course.
- 5. Probabilistic Analysis and Randomized Algorithms
- On this topic there is actually a rather large difference between what is in the book and what is covered in the lectures. However for the purposes of the exam, just read this chapter.
- 9. Median and Order Statistics
- It is assumed that you are already familiar with the basics of sorting (Ch. 6-8). This chapter expands a little on a related topic, applying the analysis tools we have learned earlier.
- 15. Dynamic Programming
- 16. Greedy Algorithms
- 17. Amortized Analysis
- These three chapters are a central part of the course. Study them well.
- 19. Binomial Heaps
- 20. Fibonacci Heaps
- 21. Data Structures for Disjoint Sets
- It is assumed that the basic heap data structure and at least some variant of balanced binary search trees are familiar from earlier courses. Here we develop on these themes, again applying analysis tools from the earlier chapters.
- 22. Elementary Graph Algorithms
- 23. Minimum Spanning Trees
- 24. Single-Source Shortest Paths
- 25. All-Pairs Shortest Paths
- 26. Maximum Flow
- Graph algorithms are another central part of the course. Some material in the earlier chapters is probably already familiar to you, but we will develop it a little more deeply now.
- 27. Sorting Networks
- This is one of the "selected topics" that is not really a core topic for the course but has been selected as an example of some more specialized research directions. In particular, this is the only example of (a very limited model of) parallel computation on this course. [The first edition of the book also included a chapter on the Parallel RAM model which has now been dropped.]
- 35. Approximation Algorithms
- Another "selected topic" but much more mainstream. I assume that NP-completeness (Chapter 34) is familiar from an earlier course. Approximation algorithms is a natural way to continue from there.
Jyrki Kivinen