# 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

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 algorithms.

#### Methods

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

### 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.

#### Learning Outcomes

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.

#### 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.

### 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.

#### 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:

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.

### 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-09-29
MCS Web Maintainer
This document has been approved by the Head of Department.