MC204 Design and Analysis of Algorithms

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

MC204 Design and Analysis of Algorithms

Credits: 20

Convenor: Dr. V. Schmitt

Semester: 2

Prerequisites:	essential: MC103, MC104, MC111
Assessment:	Continual assessment: 30%	Three hour exam in May/June: 70%

Lectures:	36	Classes:	none
Tutorials:	12	Private Study:	102
Labs:	none	Seminars:	none
Project:	none	Other:	none
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 algorithmic solution and analysis of problems that are of fundamental importance in computer science and engineering. 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.

Aims

The course aims to introduce students to the algorithmic solution and analysis of problems that are of fundamental importance in computer science and engineering. These problems will be drawn from areas such as sorting, searching, string matching, data compression, graph theory, algebra and number theory. Moreover, students will also be introduced to computational complexity; the theory of the inherent limitations of feasible computation.

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, and the drawbacks of this notation; 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.

Transferable Skills

Students will become more experienced in the application of logical and mathematical tools and techniques in computing, and 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.

Syllabus

Review of the basic notions regarding the asymptotic analysis of algorithms. A variety of algorithms drawn from the following list of topics will be presented and analysed, illustrating numerous design and analysis techniques such as divide-and-conquer, greedy algorithms, dynamic programming and backtracking: sorting; searching; string matching; data compression; graph theory; algebra; number theory. Introduction to computational complexity theory.

Reading list

Essential:

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

U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.

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

Background:

A. M. Gibbons and W. Rytter, Efficient Parallel Algorithms, Cambridge University Press, 1988.

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

M. A. Weiss, Algorithms, Data Structures, and Problem Solving with C++, Addison-Wesley, 1996.

C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

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 Up: Year 2 Previous: Year 2

S. J. Ambler
11/20/1999