1. Handbook
  2. Subjects
  3. Advanced Theoretical Computer Science

Advanced Theoretical Computer Science (COMP90057)

Graduate courseworkPoints: 12.5On Campus (Parkville)

You’re viewing the 2017 Handbook:
Or view archived Handbooks
You’re currently viewing the 2017 version of this subject

Overview

Availability
Semester 2
FeesLook up fees

AIMS

At the heart of theoretical computer science are questions of both philosophical and practical importance. What does it mean for a problem to be solvable by computer? What are the limits of computability? Which types of problems can be solved efficiently? What are our options in the face of intractability? This subject covers such questions in the content of a wide-ranging exploration of the nexus between logic, complexity and algorithms, and examines many important (and sometimes surprising) results about the nature of computing.

INDICATIVE CONTENT

  • Turing machines
  • The Church-Turing Thesis
  • Decidable languages
  • Reducability
  • Time Complexity: The classes P and NP, NP-complete problems
  • Space complexity: including sub-linear space
  • Circuit complexity
  • Approximation algorithms
  • Probabilistic complexity classes
  • Additional topics may include descriptive complexity, interactive proofs, communication complexity, complexity as applied to cryptography
  • Space complexity, including sub-linear space
  • Finite state automata, pushdown automata, regular languages, context-free languages to the Recommended Background Knowledge.

 

Example of assignment

  • Proving the equivalence of a variant of a standard machine to the original version
  • Describing an NP-hardness reduction
  • Designing an approximation algorithm for an NP-hard problem.

Intended learning outcomes

INTENDED LEARNING OUTCOMES (ILO)


On completion of this subject the student is expected to:



  • Design, manipulate, and reason about Turing machines
  • Account for the inherent complexity of many computational problems of practical importance
  • Conduct formal reasoning about machines, circuits, problems and algorithms, including reduction-based proof
  • Design approximation algorithms for intractable problems
  • Apply complexity arguments to related fundamental computational problems, such as randomized computations, interactive proof systems and cryptographic pseudorandom generators

Generic skills

On completion of this subject, students should have developed the following skills:

  • Ability to apply knowledge of science and engineering fundamentals
  • Ability to communicate effectively, with the engineering team and with the community at large
  • Capacity for lifelong learning and professional development
  • Profound respect for truth and intellectual integrity, and for the ethics of scholarship.

Last updated: 3 November 2022