2D1440 Advanced algorithms, 4p
Course for graduate and undergraduate students. It is expected to
be given every other year starting in spring 1995.
Goal
The aim of this course is to cover
a number of efficient algorithms that exists for
basic computational problems. Each problem will
be described in detail, an algorithm presented
and analyzed. The course is theoretical in nature
and thus no implementation details will be discussed.
The plan is the cover the problems listed below.
The list is preliminary and might be changed depending
on the interest of the participants in the course.
-
Primality, i.e. deciding whether a given large integer is a prime.
-
Factorization of large integers.
-
Computing discrete logarithms in finite fields.
-
Factorization of polynomials over finite fields and
over the rational numbers.
-
Computing square roots in $Z_p$.
-
Lovasz lattice basis reduction algorithm with some application.
-
Fast multiplication using FFT.
-
Planarity of graphs.
-
Computing the median in deterministic linear time.
-
The Kernighan-Lin heuristic for TSP.
-
Fast matrix multiplication
<johanh@nada.kth.se>