Skip to main content

Unit information: Advanced Algorithms (Teaching Unit) in 2021/22

Please note: you are viewing unit and programme information for a past academic year. Please see the current academic year for up to date information.

Unit name Advanced Algorithms (Teaching Unit)
Unit code COMS30042
Credit points 0
Level of study H/6
Teaching block(s) Teaching Block 1 (weeks 1 - 12)
Unit director Dr. Clifford
Open unit status Not open
Pre-requisites

COMS10017 Object-Oriented Programming and Algorithms I or equivalent.

COMS20010 Algorithms II or equivalent.

Solid understanding of O-notation and recurrence relations, the “greedy”, “divide-and-conquer” and “dynamic programming” paradigms of algorithm design, proof by induction and contradiction, discrete probability.

Previous exposure to pseudocode.

A solid understanding of arrays, linked lists, and priority queues.

Co-requisites

COMS30041 Advanced Algorithms (10 credit exam assessment unit).

School/department Department of Computer Science
Faculty Faculty of Engineering

Description including Unit Aims

This unit gives an overview of recent advances in the design of algorithms and data structures. These fall into two broad categories.

First, we will cover algorithms and data structures for fundamental problems surrounding storing, recovering and searching within data. For these problems we will see that nearly optimal solutions are possible.

Second are optimisation problems where sometimes only exponential-time algorithms are known. We will discuss when these problems admit exact efficient solutions, and when only approximation is possible.

Intended Learning Outcomes

On successful completion of this unit, students will:

  1. Be able to apply sophisticated analysis techniques to measure the time and space complexity of algorithms and also prove their correctness.
  2. Demonstrate a clear understanding of a variety of advanced data structures and their applications.
  3. Be aware of and able to apply standard approaches to approximating the answer to (NP-complete) problems where finding the exact answer is infeasible.

Teaching Information

Teaching will be delivered through a combination of synchronous and asynchronous sessions, including lectures, problem sheets and self-directed exercises.

Teaching will take place over Weeks 1-7, with consolidation and revision sessions in Weeks 11 and 12.

Assessment Information

Exam (January, 100%).

Resources

If this unit has a Resource List, you will normally find a link to it in the Blackboard area for the unit. Sometimes there will be a separate link for each weekly topic.

If you are unable to access a list through Blackboard, you can also find it via the Resource Lists homepage. Search for the list by the unit name or code (e.g. COMS30042).

How much time the unit requires
Each credit equates to 10 hours of total student input. For example a 20 credit unit will take you 200 hours of study to complete. Your total learning time is made up of contact time, directed learning tasks, independent learning and assessment activity.

See the Faculty workload statement relating to this unit for more information.

Assessment
The Board of Examiners will consider all cases where students have failed or not completed the assessments required for credit. The Board considers each student's outcomes across all the units which contribute to each year's programme of study. If you have self-certificated your absence from an assessment, you will normally be required to complete it the next time it runs (this is usually in the next assessment period).
The Board of Examiners will take into account any extenuating circumstances and operates within the Regulations and Code of Practice for Taught Programmes.

Feedback