
Advanced algorithms, avalg14
The course evaluation is now complete. Here are the
[ results],
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
December 17.
The second project is now published. The deadline is
December 8.
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
Lectures
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
[ plan],
 24/9,1315, D2 [ Notes1],
[ Notes2]
 25/9,1012, K1 [ Notes]
 29/9,810, D2 [ Notes]
 7/10,1315, D2[ Notes]
 10/10,1315, F2[ Notes]
 17/10,13.00 Deadline homework 1 (no lecture).
 3/11,810, K1 [ Notes]
 5/11,1315, K1 Guest lecture by Torbjörn Granlund on GMP.
Slides
 12/11,1315, F1, [ Notes]
 19/11,1315, E1, Deadline project 1. [ Notes]
 21/11,1012, D2 [ Notes]
 24/11,810, F2 [ Notes]
Deadline homework 2.
 1/12,810, F1 [ Notes]
 3/12,1315, D1 [ Notes]
 8/12,810, D2, Deadline project 2. [ Notes]
 17/12,1315, D2, Deadline homework 3.
Examination
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.
A  241    320 
B  200    240 
C  175    199 
D  150    174 
E  125    149 
Fx  115    124 
F  0    114 
Material
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 PublicKey Cryptosystems, 1978.

Stefan Nilsson:
The Fastest Sorting Algorithm?

Greg Plaxton:
Parallel Recursion: Batcher s Bitonic Sort.
 Wikipedia:
Sorting networks,
Bitonic sorting

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
