The University of New South Wales

go to UNSW home page

Handbook Home

PRINT THIS PAGE
Algorithms and Computational Complexity - COMP9103
 Computing Logo

   
   
   
 
Campus: Kensington Campus
 
 
Career: Postgraduate
 
 
Units of Credit: 6
 
 
EFTSL: 0.12500 (more info)
 
 
Indicative Contact Hours per Week: 3
 
 
Enrolment Requirements:
 
 
Prerequisite: COMP9101 or COMP9801.
 
 
Fee Band: 2 (more info)
 
 
Further Information: See Class Timetable
 
  

Description

Introduction to the basic notions of computational complexity theory: polynomial time computability (P), non deterministic polynominal time computability (NP), polynomial time reductions and NP complete problems. We will show that various real-life problems are NP complete, which explains why no efficient algorithms for such problems have been found. We will also show how one can cope with such problems in an efficient way. We also study other computational complexity classess (polynomial time hierarchy, Polynomial Space and Logarithmic space, etc.)

URL for this page:

© The University of New South Wales (CRICOS Provider No.: 00098G), 2004-2011. The information contained in this Handbook is indicative only. While every effort is made to keep this information up-to-date, the University reserves the right to discontinue or vary arrangements, programs and courses at any time without notice and at its discretion. While the University will try to avoid or minimise any inconvenience, changes may also be made to programs, courses and staff after enrolment. The University may also set limits on the number of students in a course.