Advanced algorithms, avalg14
The course evaluation is now complete. Here are the
It is now possible to book at time for discussions of project
2 at the following [ location].
The third homework is now published. The deadline is
The second project is now published. The deadline is
For the students interested in more advanced material
we recommend the theory group
[ reading seminars],
These seminars present current research to give a taste what
is happening around the world in the computational complexity area.
People involved in the course
- Lecturer: Johan Håstad
- Assistents: Sangxia Huang, Mladen Mikša och Marc Vinyals
Exactly how much time that will be spent on each topic is not
clear and adjustments are made as the course progresses.
You find the current plan [ here
which might be compared to the original
- 24/9,13-15, D2 [ Notes1],
- 25/9,10-12, K1 [ Notes]
- 29/9,8-10, D2 [ Notes]
- 7/10,13-15, D2[ Notes]
- 10/10,13-15, F2[ Notes]
- 17/10,13.00 Deadline homework 1 (no lecture).
- 3/11,8-10, K1 [ Notes]
- 5/11,13-15, K1 Guest lecture by Torbjörn Granlund on GMP.
- 12/11,13-15, F1, [ Notes]
- 19/11,13-15, E1, Deadline project 1. [ Notes]
- 21/11,10-12, D2 [ Notes]
- 24/11,8-10, F2 [ Notes]
Deadline homework 2.
- 1/12,8-10, F1 [ Notes]
- 3/12,13-15, D1 [ Notes]
- 8/12,8-10, D2, Deadline project 2. [ Notes]
- 17/12,13-15, D2, Deadline homework 3.
The examinationen consists of two projects (each worth a maximum of 100 points) and three sets of homework problems (each worth a maximum of 40 points). The homework problems should be done individually while the projects can be done jointly in groups of two people.
Solutions should be written in English.
Grades are based on the total number of points obtained as follows.
Do not print but read on a good screen.
Cormen, Leiserson, et al.,
Introduction to Algorithms.
- Johan Håstad, Notes for the course advanced algorithms, Jan 2000.
Rivest, Shamir, and Adleman,
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, 1978.
The Fastest Sorting Algorithm?
Parallel Recursion: Batcher s Bitonic Sort.
Torbjörn Granlund: presentation of GMP
- D. S. Johnson and L. A. McGeoch: The Traveling Salesman Problem: A Case Study in Local Optimization
- Torbjörn Granlund: Att implementera kvadratiska sållet