[The University of Leicester]

Department of Mathematics & Computer Science



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

CO2004 Design and Analysis of Algorithms

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.

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

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

Author: N. Rahman, tel: +44 (0)116 252 3902
Last updated: 2003-09-23
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.