CO2004 Design and Analysis of Algorithms
||Convenor: Dr. V. Schmitt
||essential: CO1003, CO1004, CO1011
||Three hour exam in January: 70%
The course aims to introduce students to the algorithmic solution and
analysis of problems and algorithms.
Students will learn how evaluate the complexity of
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.
Students should be able to demonstrate 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. They should be able to design efficient
Class sessions together with course notes, recommended textbook,
worksheets, printed solutions, and some additional hand-outs and
Marked courseworks, traditional written
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
Students will be able to solve problems which are algorithm based
by using a mixture of analysis and design techniques. They should
be able to produce concise technical writing, and present written
conclusions to problems. They should be able to explain the
concept of numerical data, and issues in processing such data.
Class sessions together with worksheets.
Marked coursework, one class test, traditional written
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.
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
The main methods used to design algorithms
will be illustrated through examples of fundamental
importance in computer science and engineering.
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
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.
T. Cormen, C. E. Leiserson and R. L. Rivest,
Introduction to Algorithms,
MIT Press, 1990.
G. Brassard and P. Bratley,
Fundamentals of Algorithms,
A. V. Aho, J. E. Hopcroft and J. D. Ullman,
The Design and Analysis of Computer Algorithms,
R. Sedgewick and P. Flajolet,
An Introduction to the Analysis of Algorithms,
Course notes, web page, study guide, worksheets, handouts, lecture
rooms with one OHP, past examination papers.
Course questionnaires, course review.
Author: N. Rahman, tel: +44 (0)116 252 2593
Last updated: 2004-09-29
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.