Module COMP53215: Algorithms and Complexity

Department: Computer Science

COMP53215: Algorithms and Complexity

Prerequisites

• None

Corequisites

• None

Excluded Combination of Modules

• None

Aims

• Provide knowledge and critical understanding of paradigms, and fundamental ideas behind algorithms.
• Provide knowledge and critical understanding of paradigms, fundamental ideas and methods relating to computational complexity.
• Discuss the design and analysis of efficient algorithms.

Content

• Algorithmic methods: e.g. divide and conquer, dynamic programming.
• Mitigating hardness: e.g. approximation, branch and bound, exact methods.
• Computational complexity: e.g. classes between L and EXPTIME, time and space hierarchy theorems, FPT and the W-hierarchy.
• Randomised Algorithms: e.g. QuickSort, randomised data structures.
• Probabilistic Methods: e.g. Monte Carlo methods, tail inequalities

Learning Outcomes

• By the end of this module, students should be able to demonstrate:
• a systematic understanding of core techniques for constructing algorithms.
• an advanced understanding of core concepts from computational complexity theory.
• an ability to design novel algorithms to solve specific complex problems.

• By the end of this module, students should be able to demonstrate:
• familiarity with state-of-the-art algorithms to solve complex challenges and understanding of computational complexity implications.
• competence to translate abstract problem descriptions into algorithmic formulations; competent and educated selection of appropriate solution algorithms.

• By the end of this module, students should be able to demonstrate:
• familiarity with advanced paradigms and modern algorithms underlying computer science applications, and their analysis

Modes of Teaching, Learning and Assessment and how these contribute to the learning outcomes of the module

• Lectures enable students to learn the core material relevant to the topic and problem classes enable students to develop their theoretical understanding and problem-solving skills.
• Summative assessments and formative exercises encourage students to focus their ability to independently analyse and solve problems as it relates to the topic of algorithms and complexity.

Teaching Methods and Learning Hours

Summative Assessment

Formative Assessment:

Via problem classes.

■ Attendance at all activities marked with this symbol will be monitored. Students who fail to attend these activities, or to complete the summative or formative assessment specified above, will be subject to the procedures defined in the University's General Regulation V, and may be required to leave the University