Skip to main content

Unit information: Advanced Topics in Theoretical Computer Science (Teaching Unit) in 2021/22

Unit name Advanced Topics in Theoretical Computer Science (Teaching Unit)
Unit code COMSM0068
Credit points 0
Level of study M/7
Teaching block(s) Teaching Block 1 (weeks 1 - 12)
Unit director Dr. Clifford
Open unit status Not open
Pre-requisites

COMS10014 Mathematics for Computer Science A and COMS10013 Mathematics for Computer Science B or equivalent.

COMS10017 Object-Oriented Programming and Algorithms I or equivalent.

COMS20010 Introduction to Algorithms II.

COMS30042 Advanced Algorithms.

Co-requisites

Assessment Unit COMSM0069 Advanced Topics in Theoretical Computer Science.

School/department Department of Computer Science
Faculty Faculty of Engineering

Description including Unit Aims

This topics course exposes the students to a selection of advanced topics in theoretical computer science related to “Theory A” and complexity. These may include (but are not restricted to) time, space, circuit or communication complexity, and distributed, randomised, parameterised, streaming or approximate counting algorithms.

While results and problems of recent origin may be included in the syllabus, the instructors aim to make the material accessible to all students fulfilling the prerequisites by providing complete lecture notes and including all necessary background material.

The unit is suitable for students with a firm grasp of the basic concepts in the 2nd and 3rd year algorithms courses, and likely of interest to those planning to move into industrial or academic research.

Intended Learning Outcomes

On successful completion of this unit, students will:

  1. Understand and recall elements of the state of the art in “Theory A” research.
  2. Understand, recall and analyse a variety of advanced algorithms and data structures.
  3. Be able to apply sophisticated design techniques to create new algorithms or new hardness proofs in different paradigms.
  4. Demonstrate an understanding of the role of randomness in complexity theory and algorithm design.

Teaching Information

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

Teaching will take place over Weeks 1-7, and for students assessed by examination, consolidation and revision sessions in Weeks 11 and 12.

Assessment Information

Exam (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. COMSM0068).

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