2015/16 | Engineering, Mathematics and Physical Sciences Intranet

MODULE TITLE	Algorithms that Changed the World	CREDIT VALUE	15
MODULE CODE	ECM3428	MODULE CONVENER	Prof Geyong Min (Coordinator)

DURATION: TERM	1	2	3
DURATION: WEEKS	12	0	0

Number of Students Taking Module (anticipated)	15

DESCRIPTION - summary of the module content

Algorithms are precisely defined procedures designed to solve computational tasks: they are the life-blood of computing. This module is designed to highlight the importance of algorithms in Computer Science, providing you with an understanding of what algorithms are, how they can be specified and evaluated, and what they can be used for. These general ideas will be illustrated throughout by means of an in-depth study of a range of example algorithms which have played an important part in the development of Computer Science and underpin current computing practice. The prerequisite knowledge may be obtained from two first-year computer science and mathematics modules.

PRE-REQUISITE MODULES: ECM1408, ECM1414

AIMS - intentions of the module

In this module, you will build on the knowledge acquired in ECM1414 (Data Structures and Algorithms) with a more systematic exploration of a range of different types of algorithms and the principles of their design and analysis. A range of specific computational problems will be covered (e.g., sorting, searching, operations on strings, graphs, and other data structures, numerical problems), and different algorithms for these problems analysed..

INTENDED LEARNING OUTCOMES (ILOs) (see assessment section below for how ILOs will be assessed)

On successful completion of this module you should be able to:

Module Specific Skills and Knowledge

1. Appreciate the principles of algorithm design and implementation
2. Analyse the time complexity of some important classes of algorithm

3. Implement and analyse some fundamental algorithms

Discipline Specific Skills and Knowledge

4. Apply programming skills to convert abstract specifications into practical realisations
5. Demonstrate an analytical approach to computational problems.

6. Appreciate the importance of complexity considerations in the practical deployment of programs at different scales

Personal and Key Transferable / Employment Skills and Knowledge

7. Approach problem-solving tasks in a systematic and disciplined way.

SYLLABUS PLAN - summary of the structure and academic content of the module

Introduction: What is an algorithm? Specification and pseudo-code.

Recapitulation of: correctness; algorithms versus heuristics; space and time complexity; iteration and recursion; NP-completeness.

A study of specific algorithms, problems, and techniques selected from:

Sorting (merge-sort, quick-sort)
Searching (depth-first, breadth-first search, etc)
Algorithms on graphs,
Hashing,
String-matching,
Dynamic programming,
Fast Fourier transform,
Simplex algorithm,
Public-key encryption,
Algorithms for graphics (line drawing, filling polygons, painter’s and z-buffer algorithms),
Matrix algorithms,
Page rank algorithm,
Monte Carlo integration,

Other examples as appropriate.

LEARNING AND TEACHING

LEARNING ACTIVITIES AND TEACHING METHODS (given in hours of study time)

Scheduled Learning & Teaching Activities	38.00	Guided Independent Study	112.00	Placement / Study Abroad	0.00

DETAILS OF LEARNING ACTIVITIES AND TEACHING METHODS

Category	Hours of study time	Description
Scheduled learning and teaching	22	Lectures
Scheduled learning and teaching	11	Workshops to gain practical experience working with algorithms
Scheduled learning and teaching	5	Tutorials involving theoretical exercises and discussions
Guided independent study	30	Coursework
Guided independent study	82	Reading, programming

ASSESSMENT

FORMATIVE ASSESSMENT - for feedback and development purposes; does not count towards module grade

Form of Assessment	Size of Assessment (e.g. duration/length)	ILOs Assessed	Feedback Method
Class test	1 hour	1	In class

SUMMATIVE ASSESSMENT (% of credit)

Coursework	30	Written Exams	70	Practical Exams	0

DETAILS OF SUMMATIVE ASSESSMENT

Form of Assessment	% of Credit	Size of Assessment (e.g. duration/length)	ILOs Assessed	Feedback Method
Coursework (paper exercise)	10	10 hours	1,2,5	Individual feedback sheet
Coursework (programming)	20	20 hours	3,4,6,7	Individual feedback sheet
Examination	70	2 hours	1,2,5,6	Model answers supplied on request

DETAILS OF RE-ASSESSMENT (where required by referral or deferral)

Original Form of Assessment	Form of Re-assessment	ILOs Re-assessed	Time Scale for Re-assessment
Coursework (programming)	Coursework (programming)	3, 4, 6, 7	To be completed over the summer and submitted in referred exam week
Coursework (paper) and Examination	Referred examination	1,2,5,6	Ref/Def Exam Period

RE-ASSESSMENT NOTES

Failure in programming coursework will result in referral, whether or not the remaining components are passed; the referred programming coursework will contribute 20% to the final mark.

The referred exam will be required if the combined mark for the paper coursework and exam is a fail mark; the referred exam will contribute 80% to the final mark.

RESOURCES

INDICATIVE LEARNING RESOURCES - The following list is offered as an indication of the type & level of
information that you are expected to consult. Further guidance will be provided by the Module Convener

Basic reading:

ELE: http://vle.exeter.ac.uk/

Web based and Electronic Resources:

Other Resources:

Donald Knuth, Fundamental Algorithms (vols 1-3), Addison-Wesley

Reading list for this module:

Type	Author	Title	Edition	Publisher	Year	ISBN	Search
Set	Cormen T, Leiserson C, Rivest R, Stein C	Introduction to Algorithms	3rd Edition	MIT Press	2009		[Library]
Set	MacCormick John	Nine Algorithms that Changed the Future: The Ingenious ideas that Drive Todays Computers		Princeton University Press	2012		[Library]

CREDIT VALUE	15	ECTS VALUE	7.5

PRE-REQUISITE MODULES	ECM1408, ECM1414
CO-REQUISITE MODULES

NQF LEVEL (FHEQ)	6	AVAILABLE AS DISTANCE LEARNING	No
ORIGIN DATE	Wednesday 22 January 2014	LAST REVISION DATE	Tuesday 27 January 2015

KEY WORDS SEARCH	Algorithms, Computational complexity

Computer Science

ECM3428 - Algorithms that Changed the World (2015)