Course syllabus

Jump to today

The aim of this course is to present mathematical models for computers and computation, classical and quantum, and to prove results about what can and cannot be computed. It deals with idealised computers which operate on idealised input and output. For example, one proves that it is impossible to write a computer program that takes as input any computer program and tells whether or not that program will finish running or continue forever (the halting problem).

 Various methods to evaluate algorithmic complexity and prove undecidability, as well as efficient strategies, classical and quantum, for problem solving will be presented. The Church‐Turing Thesis will be critically discussed.

 This course requires that students have a good knowledge of mathematical proofs and can write them properly.

 

Pre-requisites

  • COMPSCI 225
  • COMPSCI 220 or PHIL 222

The relevant background can be found in Chapter 0 of Michael Sipser's Introduction to the Theory of Computation (any edition). 

Course details

Content

  1. Mathematical backgrgound refresh
  2. Automata and regular languages
  3. Computability and decidability
  4. Algorithmic complexity
  5. Church-Turing Thesis
  6. Quantum computing

Expected learning outcomes

On completion, students will be able to:

  • explain the theoretical limits on computational solutions of undecidable and inherently complex problems
    describe concrete examples of computationally undecidable or inherently infeasible problems from different fields
  • understand formal definitions of machine models, classical and quantum
  • prove the undecidability or complexity of a variety of problems
  • understand the issue of whether there are limits of computability
  • understand the basic principles of quantum computing.

Course Coordinator

Professor Cristian (Cris) S. Calude, cristian@cs.auckland.ac.nz, webpage
Room 839, B810 Building.

Lecturers

Tutor and marker

Marker

Class rep

 Lectures

Monday, Wednesday, Friday 3.00pm - 4.00pm, OGHLecTh/102-G36

Tutorials

Once tutorial per week starting the second week, offered in two streams, Thursday and Friday, 1:00pm 2:00pm ClockT029/105-029. Stream distribution will be announced by 8 March  2019.

Tutorial attendance 0.3% per tutorial (can skip 1).

3 Marked tutorials worth 2% in total. The mark is best 2 out of 3.  These will be held on:

28th & 29th March

9th & 10th May

30th & 31st May

Assessment, Coursework, Final Examination

Assessment will be determined as follows:        

The coursework consists of one test worth 30%,  three assignments worth 5% each and tutorial work 5%.  The coursework thus contributes 50% of the final mark.

The test will be held in class on Monday 1 April 2019,  time: 3:05-3:55 pm in OGHLecTh/102-G36 and OCH1/104-G53. Room distribution will be announced by 29 March 2019.

Assignments:   Assignment 1 will be due on 7 April 2019.  Assignment 2 will be due on 19 May 2019. Assignment 3 will due on 2 June 2019. All assignments must be prepared using an appropriate word-processing application [diagrams may be hand-drawn], converted to PDF format, and uploaded in Canvas by 23.59 of the due date.

The final 2-hour examination is worth 50% of the final mark.

Useful links

Other sources of information and assistance

This course will make reasonably heavy use of Canvas.  Among other things, lecturers will use Canvas to provide you with lecture notes and useful readings.

General assistance: Student Learning Services offers help to students in developing effective academic learning and performance skills, and helps those who encounter difficulties in their studies.  One of the services on offer is English Language Enrichment (ELE), which offers students support in their English language development.

Course summary:

Date Details Due