CSC2016 : Algorithm Design and Analysis

  • Module Leader(s): Prof. Maciej Koutny
  • Owning School:
Semesters
Semester 1 Credit Value: 10
Semester 2 Credit Value: 10
ECTS Credits: 10.0

Aims

Knowledge of a range of key application areas where algorithmic solutions are required.
Understand the key issues in algorithm design.
Understand what makes a "good" algorithm.
Explore range of techniques that can be employed in the design of various types of algorithm.
Analyse the properties of key algorithms in terms of their time and space complexity.
Provide practical experience of implementing a range of algorithms.

This module provides an introduction to the design and analysis of algorithms. It begins by considering a range of illustrative application areas including sorting, searching and numerical algorithms. It then looks in more detail at key techniques for designing algorithmic solutions and introduces approaches for analysing algorithms.

Outline Of Syllabus

Introduction to Algorithms: general introduction to algorithms.
Numerical Algorithm Applications: Root Finding; Solving a set of linear equations.
Analysing Algorithms: Basic concepts of complexity analysis;
Counting operations and memory usage; Use of order notations, hierarchy of complexity functions, and its practical importance.
Non-numerical Algorithm Applications: Sorting; Searching; Geometric Algorithms.
Algorithm Design Techniques: The various algorithm design techniques will be introduced in the context of a variety sample problems (some of which will recur); complexity measures will be discussed for many algorithms. The principal design techniques covered are:
Brute Force (exhaustive search).
Divide and Conquer
Greedy Algorithms.
Dynamic Programming.
Backtracking.
Branch and Bound.

Teaching Methods

Teaching Activities
Category Activity Number Length Student Hours Comment
Scheduled Learning And Teaching ActivitiesLecture441:0044:00Lectures
Guided Independent StudyAssessment preparation and completion500:3025:00Revision for end of Semester exam and exam duration.
Guided Independent StudyAssessment preparation and completion441:0044:00Lecture follow-up
Scheduled Learning And Teaching ActivitiesSmall group teaching221:0022:00Tutorials
Guided Independent StudyProject work221:0022:00Coursework
Guided Independent StudyIndependent study431:0043:00Background reading
Total200:00
Teaching Rationale And Relationship

Lectures will be used to introduce the learning material and for demonstrating the key concepts by example. Students are expected to follow-up lectures within a few days by re-reading and annotating lecture notes to aid deep learning.

Tutorials will be used to emphasise the learning material and its application to the solution of problems and exercises set as coursework, during which students will analyse problems as individuals and in teams. Students are expected to spend time on coursework outside timetabled tutorial classes.

Students aiming for 1st class marks are expected to widen their knowledge beyond the content of lecture notes through background reading.

Students should set aside sufficient time to revise for the end of semester exam.

Assessment Methods

The format of resits will be determined by the Board of Examiners

Exams
Description Length Semester When Set Percentage Comment
Written Examination901A40N/A
Written Examination902A40N/A
Other Assessment
Description Semester When Set Percentage Comment
Practical/lab report1M10programming coursework on algorithms (10 hours)
Practical/lab report2M10programming coursework on algorithms (10 hours)
Assessment Rationale And Relationship

Each examination will cover the material taught in that Semester.
An important objective of the course is to develop students' practical abilities in designing, analysing and implementing algorithms. This will be assessed by coursework that cover these key aspects.

N.B. This module has both an “Exam Assessment” and an “Other Assessment” (e.g. coursework). If either Assessment has a failing mark below 35%, the maximum mark returned for the module will normally be 35%.

Reading Lists

Timetable

Disclaimer: The University will use all reasonable endeavours to deliver modules in accordance with the descriptions set out in this catalogue. Every effort has been made to ensure the accuracy of the information, however, the University reserves the right to introduce changes to the information given including the addition, withdrawal or restructuring of modules if it considers such action to be necessary.