Advanced Theoretical Computer Science

This subject has the following teaching availabilities in 2016:

200 hours

OR Equivalent

(COMP20004 Discrete Structures prior to 2014)

Proficiency in discrete mathematics and propositional logic.

433-330 Theory of Computation

For the purposes of considering request for Reasonable Adjustments under the Disability Standards for Education (Cwth 2005), and Student Support and Engagement Policy, academic requirements for this subject are articulated in the Subject Overview, Learning Outcomes, Assessment and Generic Skills sections of this entry.

It is University policy to take all reasonable steps to minimise the impact of disability upon academic study, and reasonable adjustments will be made to enhance a student's participation in the University's programs. Students who feel their disability may impact on meeting the requirements of this subject are encouraged to discuss this matter with a Faculty Student Adviser and Student Equity and Disability Support: http://services.unimelb.edu.au/disability

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 (ILO)

On completion of this subject the student is expected to:

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

• Three individual assignments involving mathematical proof and possibly some programming, requiring approximately 35 - 40 hours of work in total, due in weeks 4, 7 and 11 (30%)
• 3-hour written examination held at the end of semester (70%).

Hurdle Requirement: To pass the subject, students must obtain at least:

• 15/30 in the assignments
• 35/70 on the examination.

Assessment addresses all Intended Learning Outcomes (ILOs)

Michael Sipser, "Introduction to the Theory of Computation", 3rd Edition.

This subject is not available as a breadth subject.

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.