Notes for the Course of Advanced Algorithms

Describe a couple of the classical algorithms which are not taught in a first algorithms course. Also give a general understanding of efficient algorithms and a better understanding for how to design and analyze efficient algorithms.

Publication date: 01 Jan 2000

ISBN-10: n/a

ISBN-13: n/a

Paperback: n/a

Views: 22,928

Type: N/A

Publisher: n/a

Post time: 13 Feb 2007 09:46:13

Notes for the Course of Advanced Algorithms

Describe a couple of the classical algorithms which are not taught in a first algorithms course. Also give a general understanding of efficient algorithms and a better understanding for how to design and analyze efficient algorithms.
Tag(s): Algorithms and Data Structures
Publication date: 01 Jan 2000
ISBN-10: n/a
ISBN-13: n/a
Paperback: n/a
Views: 22,928
Document Type: N/A
Publisher: n/a
Post time: 13 Feb 2007 09:46:13
From the Introduction:

The aim of the course "Advanced Algorithms" is at least twofold. One aim is to describe a couple of the classical algorithms which are not taught in a first algorithms course. The second is to give a general understanding of efficient algorithms and to give the student a better understanding for how to design and analyze efficient algorithms. The overall approach of the course is theoretical, we work with pencil and paper. The main emphasis of the course is to get an algorithm with a good asymptotic running time. In most cases this coincides with efficient in practice and the most notable example where this is not true is matrix multiplication where the implied constants are too large to make the algorithms be of practical value.

Although the lectures are theoretical, students are asked to implement some basic algorithms in the homework sets. Our hope is that this gives at least some balance between practice and theory.

The current set of lecture notes include all topics covered in the course in its past four appearances in spring 1995, spring 1997, fall 1997, and fall 1998. The course in 1995 was mostly taken by graduate student while the later courses were mostly taken by undergraduate students. Thus some of the more advanced topics, like matrix multiplication, lattice basis reduction and provable polynomial time for integer polynomial factorization, was only covered in 1995 and may not be covered in coming years. However, for the interested reader we have kept those sections in these notes. Also when it comes to the rest of the material we do not expect to cover all algorithms each time the course is given. The choice of which algorithms to cover is done at the beginning of a course to make it possible for the participants to influence this decision. The choice is not limited to the algorithms included in these notes and I would be happy to include any desired new topic that would be on a topic agreeing with the course philosophy.