Algorithms and Complexity

Subject COMP90038 (2011)

Note: This is an archived Handbook entry from 2011.

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

This subject is not offered in 2011.
Time Commitment: Contact Hours: 1 x 3 hour lecture per week
Total Time Commitment: Not available
Prerequisites:

An undergraduate degree in a cognate discipline.
Corequisites: None
Recommended Background Knowledge: Basic proficienty in mathermatics and computing.
Non Allowed Subjects:

433-253 Algorithms & Data Structures

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/

Contact

Dr Adrian Pearce

email: adrianrp@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 applicationKnow 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 complexityBe 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): Master of Engineering in Distributed Computing
Master of Information Technology
Master of Operations Research and Management Science
Postgraduate Certificate in Engineering
Related Majors/Minors/Specialisations: Master of Engineering (Software)

Download PDF version.