Algorithms and Complexity

Subject COMP90038 (2012)

Note: This is an archived Handbook entry from 2012.

Credit Points: 12.50
Level: 9 (Graduate/Postgraduate)
Dates & Locations:

This subject has the following teaching availabilities in 2012:

Semester 1, Parkville - Taught on campus.
Pre-teaching Period Start not applicable
Teaching Period not applicable
Assessment Period End not applicable
Last date to Self-Enrol not applicable
Census Date not applicable
Last date to Withdraw without fail not applicable

Semester 2, Parkville - Taught on campus.
Pre-teaching Period Start not applicable
Teaching Period not applicable
Assessment Period End not applicable
Last date to Self-Enrol not applicable
Census Date not applicable
Last date to Withdraw without fail not applicable


Timetable can be viewed here. For information about these dates, click here.
Time Commitment: Contact Hours: one, 3 hour lecture per week
Total Time Commitment:

120 hours.

Prerequisites:

An undergraduate degree in a cognate discipline.

Corequisites:

None

Recommended Background Knowledge:

Basic proficienty in mathermatics and computing.

Non Allowed Subjects:
Subject

Core Participation Requirements:

For the purposes of considering request for Reasonable Adjustments under the Disability Standards for Education (Cwth 2005), and Students Experiencing
Academic Disadvantage Policy, academic requirements for this subject are articulated in the Subject Description, Subject Objectives, Generic Skills and
Assessment Requirements of this entry. The University is dedicated to provide support to those with special requirements. Further details on the
disability support scheme can be found at the Disability Liaison Unit
website: http://www.services.unimelb.edu.au/disability/

Coordinator

Dr Antonette Mendoza, Dr Tony Wirth, Dr Udaya Parampalli

Contact

Dr Aaron Harwood

email: aharwood@unimelb.edu.au

Subject Overview:

Topics covered include complexity classes and asymptotic notations; empirical analysis of algorithms; abstract data types including queues, trees, heaps and graphs; algorithmic techniques including brute force, divide-and-conquer, dynamic programming and greedy approaches; space and time trade-offs; and the theoretical limits of algorithm power.

Objectives:

On successful completion of this subject students should:

  • Understand a range of programming languages and their application
  • Know a variety of techniques for solving, sorting and searching problems
  • Understand graph algorithms
  • Have experience with using complex algorithms and data structures in a variety of programming languages
  • Know the concepts of computability, tractability and problem complexity
  • Be able to perform complexity analyses of algorithms.
Assessment:
  • Project work during semester expected to take approximately 36 hours (40%)
  • And one written examination not exceeding 3-hours at the end of the semester (60%)
  • Details of assessment components will be advised at the commencement of the subject
  • Both components must be completed satisfactorily to pass the subject.
Prescribed Texts: None
Breadth Options:

This subject is not available as a breadth subject.

Fees Information: Subject EFTSL, Level, Discipline & Census Date
Generic Skills:

On successful completion students should:

  • Understand a range of programming languages and their application
  • Knowledge a variety of techniques for solving, sorting and searching problems
  • An understanding of graph algorithms
  • Experience with using complex algorithms and data structures in a variety of programming languages
  • Knowledge of the concepts of computability, tractability and problem complexity
  • The ablity to perform complexity analyses of algorithms
  • Be able to undertake problem identification, formulation and solution
  • Have a capacity for independent critical thought, rational inquiry and self-directed learning; and
  • Have a profound respect for truth and intellectual integrity, and for the ethics of scholarship
Related Course(s): Bachelor of Computer Science (Honours)
Master of Engineering in Distributed Computing
Master of Information Technology
Master of Operations Research and Management Science
Master of Science (Bioinformatics)
Postgraduate Certificate in Engineering
Related Majors/Minors/Specialisations: Master of Engineering (Mechatronics)
Master of Engineering (Software)

Download PDF version.