Algorithmics I (H) COMPSCI4009

  • Academic Session: 2017-18
  • 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

To develop the student's skills in the design and analysis of algorithms; To study algorithms for a range of important standard problems; To introduce the student to the theory of NP-completeness together with its practical implications;To make the student aware of fundamental concepts of computability.

Timetable

Two one-hour lectures and one one-hour tutorial per week.

Requirements of Entry

Algorithmic Foundations 2 (or equivalent)

Algorithms and Data Structures 2 (or equivalent)

Object Oriented Software Engineering 2 (or equivalent)

Java Programming 2 (or equivalent) 

40 credits of Level 1 Mathematics is strongly recommended.

This course is only available to Honours students.

Excluded Courses

None

Co-requisites

None

Assessment

Examination 80% Coursework 20%.

Main Assessment In: April/May

Are reassessment opportunities available for all summative assessments? Not applicable

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. 

 

The coursework cannot be redone because the nature of the coursework is such that it takes 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

To develop the student's skills in the design and analysis of algorithms;

To study algorithms for a range of important standard problems;

To introduce the student to the theory of NP-completeness together with its practical implications;

To make the student aware of fundamental concepts of computability.

Intended Learning Outcomes of Course

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

1. Recognise, and be able to use, standard algorithmic design methods;

2. Apply the basic principles of algorithm analysis;

3. Code standard efficient sorting algorithms;

4. Code fundamental graph algorithms - for search and traversal, shortest paths, minimum spanning trees, and topological sorting;

5. Describe classical algorithms for string searching, string comparison, and text compression;

6. Expound on the basic principles, and the practical implications of, the theory of NP-completeness;

7. Follow NP-completeness proofs for particular problems;

8. Deploy various strategies for dealing with computational problems that are apparently intractable;

9. Provide examples of the computability and unsolvability, and know some standard examples of unsolvable problems.

Minimum Requirement for Award of Credits

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