Algorithmics II (H) COMPSCI4003

  • Academic Session: 2016-17
  • School: School of Computing Science
  • Credits: 10
  • Level: Level 4 (SCQF level 10)
  • Typically Offered: Semester 1
  • Available to Visiting Students: Yes
  • Available to Erasmus Students: Yes

Short Description

The aims of the course are:

To present a broad range of algorithm design methods, with examples chosen to reflect practical applications;

To enable students to make educated choices between strategies for algorithmic problem-solving;

To convey the significance of computational complexity, and to present a range of methods for dealing with it in practice.

Timetable

3 hours per week

Requirements of Entry

Algorithmics I (H) (or equivalent)

Excluded Courses

None 

Co-requisites

None 

Assessment

Examination 70%, Written Assignment 10%, Set Exercise 20%.

Main Assessment In: April/May

Are reassessment opportunities available for all summative assessments? No

Reassessments are normally available for all courses, except those which contribute to the Honours classification. For non Honours courses, students are offered reassessment in all or any of the components of assessment if the satisfactory (threshold) grade for the overall course is not achieved at the first attempt. This is normally grade D3 for undergraduate students and grade C3 for postgraduate students. Exceptionally it may not be possible to offer reassessment of some coursework items, in which case the mark achieved at the first attempt will be counted towards the final course grade. Any such exceptions for this course are described below. 

 

Resit examinations ARE NOT ALLOWED for Honours students.

Resit examinations ARE ALLOWED for Masters students.

 

The coursework cannot be redone because the nature of the coursework is such that it would take a significant number of days to produce it and this effort is infeasible for supporting the re-doing of such coursework over the summer.

Course Aims

The aims of the course are:

To present a broad range of algorithm design methods, with examples chosen to reflect practical applications; to enable students to make educated choices between strategies for algorithmic problem-solving; to convey the significance of computational complexity, and to present a range of methods for dealing with it in practice.

Intended Learning Outcomes of Course

By the end of the course students will be able to:

1. Describe a wide range of efficient algorithms for problems with important applications in domains such as computational geometry, string processing and graph theory;

2. Discuss why these algorithms are correct, and prove their correctness;

3. Demonstrate the execution of such algorithms as applied to typical problem instances;

4. Characterise and manipulate advanced data structures such as the suffix tree;

5. Apply algorithmic techniques to specific problems motivated by practical applications;

6. Analyse the worst-case complexity of algorithms using a variety of mathematical techniques;

7. Discuss the theory and practical implications of NP-completeness;

8. Explain techniques for coping with complexity, such as backtracking algorithms, pseudo-polynomial-time algorithms, constant-factor approximation algorithms, and polynomial-time approximation schemes;

9. Construct proofs of NP-completeness and inapproximability results.

Minimum Requirement for Award of Credits

Students must submit at least 75% by weight of the components (including examinations) of the course's summative assessment.