Course Catalogue

Algorithmics II (H) COMPSCI4003

  • Academic Session: 2026-27
  • School: School of Computing Science
  • Credits: 10
  • Level: Level 4 (SCQF level 10)
  • Typically Offered: Semester 1
  • Available to Visiting Students: Yes
  • Collaborative Online International Learning: No
  • Curriculum For Life: No

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%, In-class quizzes 10%, Assessed practical exercise 20%.

Main Assessment In: April/May

Are reassessment opportunities available for all summative assessments? No

It is the default expectation that all courses will offer opportunities for reassessment or deferred assessment. Where it is not possible to offer this in some assessment components, the grade achieved at the first attempt will be counted towards the final course grade, and any exceptions for this course are described below.

[No exceptions]

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

No exceptions