CS2G7-Essential Algorithms

Module Provider: Computer Science
Number of credits: 10 [5ECTS credits]
Level: 5
Terms in which taught: Autumn
Module Convenor: Dr M Manjunathaiah
Pre-requisites: SE1SA5 SE1SC5
Co-requisites:
Modules excluded:
Module version for: 2009/0

Email: m.manjunathaiah@reading.ac.uk

Aims:
The refinement of the concept called 'Algorithms' is one of the cornerstones of computer science and the aim of this module is to provide an appreciation of the concepts involved in the design and analysis of algorithms. This module gives an introduction to fundamental algorithm design strategies that are common to many concrete applications. A secondary aim is to consolidate the notion of mechanisation of abstraction that is introduced in previous modules with more general principles of design.

Assessable learning outcomes:
Fundamental algorithm design principles such as Divide and Conquer, Greedy Algorithms and Dynamic Programming, are introduced and explored through case studies to demonstrate the design of efficient solutions to computational problems. On completion of the module a student should be able to:

Identify the fundamental strategies in algorithmic design;
Distinguish which strategy is appropriate to solve a given problem;
Classify different algorithmic strategies;
Analyse a given algorithm and assess its efficiency;
Apply techniques of proof by induction to verify certain properties of algorithms.

Additional outcomes:
Students will have seen a number of useful case study examples illustrating the techniques which can be transported to other areas of the course. Students will also be introduced, through group studies, to recent developments in applications of the design strategies by reviewing current literature. Coursework will enhance a student's algorithm design and program implementation skills.

Outline content:
Additional Data structures (Heaps, Graphs, Hash Tables);
Divide and Conquer (General method, Analysis, examples - Sorting, Convex, Hull);
The Greedy method (General method, Analysis, examples - Job Sequencing, Shortest Paths, Spanning Trees);
Dynamic Programming (General method, Analysis, examples - Knapsack, Travelling salesperson, Transitive Closure);
Consolidation (revisit examples using alternative methods).

Brief description of teaching and learning methods:
Lectures and supervised practical coursework
Practical classes to introduce theory

Contact hours:

	Autumn	Spring	Summer
Lectures	20
Tutorials/seminars	5
Practicals	10
Other contact (eg study visits)
Total hours	35
Number of essays or assignments	2
Other (eg major seminar paper)

Assessment:
Examination : 60%
Coursework : 40%

Coursework:
Two programming assignments to implement a selection of methods
Relative percentage of coursework : 40%
Penalties for late submission in accordance with University policy#

Examinations:
One 2 hour written examination
Requirements for a pass:
Pass with 40% combined examination and coursework

Reassessment arrangements:
By examination only in August/September

Last updated: 23 November 2009