Module COMP4071: THEORETICAL COMPUTER SCIENCE IV

Department: Computer Science

COMP4071: THEORETICAL COMPUTER SCIENCE IV

Prerequisites

• COMP3391 Theoretical Computer Science III

Corequisites

• None

Excluded Combination of Modules

• None.

Aims

• To give students a detailed knowledge of algorithmic solutions for computationally hard problems.
• To extend the students' knowledge of the latest advances in understanding hardness theoretical aspects of computation.

Content

• Four strands will be selected that exemplify the width and depth of modern theoretical computer science. Such topics include, but are not limited to:
• Advanced Algorithms. Topics will be chosen from advanced data structures and hashing.
• Advanced topics in Complexity theory. Topics will be chosen from parameterized complexity, cryptography, circuit complexity, alternation and polynomial-time hierarchy and probabilistic complexity classes.
• Computational Complexity of Game Theory. Topics will be chosen from Nash equilibrium, complexity class PPAD and applications of game theory in computational complexity.
• Coding Theory. Topics will be chosen from error-correction codes and bounds on error correction.
• Probabilistic Methods. Topics will be chosen from randomised algorithms, random graphs, random walks, Markov chains, Martingale theory, mathematical tools from probability theory, e.g., tail inequalities.
• Theory of Big Data Processing. Topics will be chosen from streaming algorithms, sub-linear time algorithms, property testing.
• Advanced Graph Algorithms: Topics will be chosen from exponential algorithms, fixed parameter algorithms, hereditary graph classes, reconfiguration graphs, evolutionary algorithms, intersection graph classes.

Learning Outcomes

• On completion of this module, students will be able to demonstrate:
• a comprehensive understanding of how the theory of computation is applied
• a critical evaluation of a variety of approaches to the algorithmic solution for hard problems
• a critical awareness of the latest advances in research on theoretical aspects of computation.

• On completion of this module, students will be able to demonstrate:
• an ability to critically apply notions from the theory of computation
• an ability to choose and evaluate the best way to tackle hard computational problems
• an ability to demonstrate hardness of computational problems
• an ability to judge research on the cutting edge of the theory of computation.

• On completion of this module, students will be able to demonstrate: a capacity for independent self-learning and research.

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

• Lecturing demonstrates what is required to be learned and the application of the theory to practical examples.
• Homework problems identify areas where further independent research should be conducted.
• Summative assessments test the knowledge acquired and the students' ability to use this knowledge to solve complex problems.

Teaching Methods and Learning Hours

Summative Assessment

Formative Assessment:

Example formative exercises given during the course. Additional revision lectures may be arranged in the modules lecture slots in the 3rd term.

■ 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