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,13-15, D2 [ Notes1], [ Notes2]

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

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.

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 Public-Key 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