[The University of Leicester]

Department of Mathematics & Computer Science



Next: MC205 Object-Oriented Programming Using C++ Up: Year 2 Previous: Year 2

MC204 Design and Analysis of Algorithms

MC204 Design and Analysis of Algorithms

Credits: 20 Convenor: Dr. V. Schmitt Semester: 2
Prerequisites: essential: MC103, MC104, MC111, MC211
Assessment: Continual assessment: 30% Three hour exam in May/June: 70%
Lectures: 36 Problem Classes: 12
Tutorials: none Private Study: 90
Labs: none Seminars: none
Project: none Other: none
Surgeries: 12 Total: 150

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.

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, algebra and number theory.

Objectives

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.

Transferable Skills

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.

Syllabus

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; algebra; number 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.

Details of Assessment

The coursework for the continual assessment consists of 5 assignments staggered throughout the course at approximately one assignment every two weeks.

Next: MC205 Object-Oriented Programming Using C++ Up: Year 2 Previous: Year 2

[University Home] [MCS Home] [University Index A-Z] [University Search] [University Help]

Author: S. J. Ambler, tel: +44 (0)116 252 3884
Last updated: 2001-09-20
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.