COMPUTABILITY AND INTRACTABILITY

MAT4CI

2020

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.

School: Engineering and Mathematical Sciences (Pre 2022)

Credit points: 15

Subject Co-ordinator: Marcel Jackson

Available to Study Abroad/Exchange Students: Yes

Subject year level: Year Level 4 - UG/Hons/1st Yr PG

Exchange Students: No

Available as Elective: No

Learning Activities: N/A

Capstone subject: No

Subject particulars

Subject rules

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

Co-requisites: N/A

Incompatible subjects: N/A

Equivalent subjects: N/A

Quota Management Strategy: N/A

Quota-conditions or rules: N/A

Special conditions: Offered subject to sufficient enrolments.

Minimum credit point requirement: N/A

Assumed knowledge: N/A

Career Ready

Career-focused: No

Work-based learning: No

Self sourced or Uni sourced: N/A

Entire subject or partial subject: N/A

Total hours/days required: N/A

Location of WBL activity (region): N/A

WBL addtional requirements: N/A

Graduate capabilities & intended learning outcomes

Graduate Capabilities

Intended Learning Outcomes

01. Demonstrate advanced theoretical and technical knowledge in computational complexity

02. Use advanced cognitive and technical skills to select and apply methods to critically analyse, evaluate and interpret tasks relevant to computational complexity

03. Use advanced cognitive and technical skills to analyse, generate and transmit solutions to complex problems relevant to computational complexity.

04. Use advanced communication skills to transmit complexity-theoretic knowledge and ideas to others.

05. Demonstrate autonomy, well-developed judgement, adaptability and responsibility as a mathematician.

Melbourne (Bundoora), 2020, Semester 1, Day

Overview

Online enrolment: Yes

Maximum enrolment size: N/A

Enrolment information: N/A

Subject Instance Co-ordinator: Marcel Jackson

Class requirements

LectureWeek: 10 - 22
Two 1.00 hour 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 element	Comments	Category	Contribution	Hurdle	%	ILO*
One assignment equivalent to 2500 words	N/A	N/A	N/A	No	40	SILO1, SILO2, SILO3, SILO4, SILO5
Three assignments each equivalent to 800 words	N/A	N/A	N/A	No	60	SILO1, SILO2, SILO3, SILO4, SILO5

Melbourne (Bundoora), 2020, Semester 2, Day