# CO2004 Design and Analysis of Algorithms

**Credits: **20 |
**Convenor: **Dr. V. Schmitt |
**Semester: **2 |

**Prerequisites:** |
essential: CO1003, CO1004, CO1011 |
desirable: CO2011 |

**Assessment:** |
Coursework: 30% |
Three hour exam in January: 70% |

**Lectures:** |
36 |
**Problem Classes:** |
12 |

**Tutorials:** |
none |
**Private Study:** |
90 |

**Labs:** |
none |
**Seminars:** |
none |

**Project:** |
none |
**Other:** |
none |

**Surgeries:** |
12 |
**Total:** |
150 |

### Subject Knowledge

#### Aims

The course aims to introduce students to the algorithmic solution and
analysis of problems and algorithms.
Students will learn how evaluate the complexity of
algorithms.
The main design methods
will be presented and illustated with famous problems.
These problems will be drawn from area such as sorting,
searching, string matching, data compression, graph theory.

#### Learning Outcomes

The course objectives are to ensure that students understand: how the
worst-case time complexity of an algorithm is defined; how asymptotic
notation is used to provide a rough classification of algorithms;
how a number of algorithms for fundamental
problems in computer science and engineering work and compare with one
another; and how there are still some problems for which it is unknown
whether there exist efficient algorithms; how to design efficient
algorithms.

#### Methods

Class sessions together with course notes, recommended textbook,
worksheets, printed solutions, and some additional hand-outs and
web support.

#### Assessment

Marked courseworks, traditional written
examination.

### Subject Skills

#### Aims

Students will become more experienced in the application of logical and
mathematical tools and techniques in computing. They will build a
library of algorithms for the solution of some fundamental problems that
they are sure to meet if they pursue a career in computing,
information technology or engineering. Moreover they will develop
the basic skills to analyse algorithms and to develop efficient
new ones.

#### Methods

Class sessions together with worksheets.

#### Assessment

Marked coursework, one class test, traditional written
examination.

### Explanation of Pre-requisites

Typical of the material assumed for this module are: the basic notions
associated with an imperative programming language such as arrays, while
loops, for loops, linked lists, recursion, etc.; and logical and discrete
mathematical notions such as induction, asymptotic notation, recurrence
relations and their solution, geometric and arithmetic series, etc.

### Course Description

This course introduces students to the design and analysis
of algorithms. Whilst there are problems for which there exist no
algorithms for their solution, just because a problem can theoretically be
solved, does not mean that there exists a practically
efficient solution. It is the goal of algorithm designers to
develop better and better algorithms for the solution of fundamental
problems; or, alternatively, to prove that no algorithms of a certain
quality exist.
The main methods used to design algorithms
will be illustrated through examples of fundamental
importance in computer science and engineering.
Both fundamental and practical aspects of complexity theory
will be presented.

### Syllabus

Examples throughout the course will be based on the MIPS
Instruction Set Architecture.
Review of the basic notions regarding the asymptotic
analysis of algorithms.
Review of the methods to design algorithms
(divide and conquer, greedy algorithms, heuristics, dynamic
programming).
A variety of algorithms will be presented to illustrate
these methods. They will be
drawn from the following list of topics:
sorting; searching; string matching;
data compression; graph theory.

### Reading list

#### Essential:

**T. Cormen, C. E. Leiserson and R. L. Rivest**,
*Introduction to Algorithms*,
MIT Press, 1990.

**G. Brassard and P. Bratley**,
*Fundamentals of Algorithms*,
Prentice-Hall, 1996.

#### Recommended:

**R. Sedgewick**,
*Algorithms*,
Addison-Wesley, 1988.

**A. V. Aho, J. E. Hopcroft and J. D. Ullman**,
*The Design and Analysis of Computer Algorithms*,
Addison-Wesley, 1974.

**R. Sedgewick and P. Flajolet**,
*An Introduction to the Analysis of Algorithms*,
Addison-Wesley, 1996.

#### Background:

**A. M. Gibbons**,
*Algorithmic Graph Theory*,
Cambridge University Press, 1985.

### Resources

Course notes, web page, study guide, worksheets, handouts, lecture
rooms with one OHP, past examination papers.

### Module Evaluation

Course questionnaires, course review.

Author: *N. Rahman*, tel: +44 (0)116 252 2593

Last updated: 2004-01-20

MCS Web Maintainer

This document has been approved by the Head of Department.

© University of Leicester.