Design and Analysis of Algorithms

This course provides an introduction to algorithm design, with primary emphasis on topics which are not covered by other Risc-lectures. Only the last chapter deals with questions which belong to computer algebra, but advanced problems from this area, like polynomial factorization, are not dealt with. Nor does the course deal with topics like NP-completeness, which belong to computability theory.

A number of classical algorithms are presented, and mathematical methods for investigating the complexity are developed. The material is organized along areas in which algorithms play a role, not along principles of algorithm design like divide and conquer or dynamic programming (although such principles are also emphazised). After an introductory chapter, in which some general concepts are defined, the following topics are covered: sorting; graph algorithms and algorithms dealing with relations; string matching; artihmetic.

The course follows

Baase: Computer Algorithms,