- Homepage
- Key Information
- Students
- Taught programmes (UG / PGT)
- Student Services and Procedures
- Student Support
- Events and Colloquia
- International Students
- Students as Change Agents (SACA)
- Student Staff Liaison Committees (SSLC)
- The Exeter Award
- Peer Support
- Skills Development
- Equality and Diversity
- Athena SWAN
- Outreach
- Living Systems Institute Webpage
- Alumni
- Info points and hubs
- Inbound Exchange Students

- Staff
- PGR
- Health and Safety
- Computer Support
- National Student Survey (NSS)
- Intranet Help
- College Website

## ECM3428 - Algorithms that Changed the World (2015)

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

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**

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

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

**Module Specific Skills and Knowledge**

2. Analyse the time complexity of some important classes of algorithm

**Discipline Specific Skills and Knowledge**

5. Demonstrate an analytical approach to computational problems.

**Personal and Key Transferable / Employment Skills and Knowledge**

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.

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

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 |

Form of Assessment | Size of Assessment (e.g. duration/length) | ILOs Assessed | Feedback Method |
---|---|---|---|

Class test | 1 hour | 1 | In class |

Coursework | 30 | Written Exams | 70 | Practical Exams | 0 |
---|

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 |

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 |

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.

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