COMPUTABILITY AND INTRACTABILITY

MAT4CI

2014

Credit points: 15

Subject outline

When does a problem have an effective algorithmic solution? What does it mean for an algorithm to be effective? In this subject we attempt to give rigorous meaning to questions of this type and investigate some possible answers. Abstract computing machines and their role in the definitions of various notions of computational complexity will be discussed. Classes of problems such as P, NP will be defined and a number of well known problems in graph theory, algebra and applied discrete mathematics will be classified according to their computational complexity. The second half of the subject covers undecidability for decision problems: problems for which no algorithmic solution is possible. This property is found amongst problems from computing, abstract algebra, combinatorics, matrices and the theory of tilings.

FacultyFaculty of Science, Tech & Engineering

Credit points15

Subject Co-ordinatorMarcel Jackson

Available to Study Abroad StudentsYes

Subject year levelYear Level 4 - UG/Hons/1st Yr PG

Exchange StudentsYes

Subject particulars

Subject rules

Prerequisites MAT1DM and MAT2AAL and MAT1CLA, or any third year mathematics subject and requires co-ordinators approval

Co-requisitesN/A

Incompatible subjectsN/A

Equivalent subjectsN/A

Special conditions Offered subject to sufficient enrolments.

Subject options

Select to view your study options…

Start date between: and    Key dates

Melbourne, 2014, Semester 1, Day

Overview

Online enrolmentYes

Maximum enrolment sizeN/A

Enrolment information

Subject Instance Co-ordinatorMarcel Jackson

Class requirements

Lecture Week: 10 - 22
Two 1.0 hours lecture per week on weekdays during the day from week 10 to week 22 and delivered via face-to-face.
"requires extensive preparation for class presentations"

Assessments

Assessment elementComments%
Four assignments each equivalent to 700 words60
One assignment equivalent to 1,100 words40