Algorithms and Complexity

Subject COMP90038 (2013)

Note: This is an archived Handbook entry from 2013.

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

This subject is not offered in 2013.

Time Commitment: Contact Hours: 36 hours, comprising of three hours of lectures per week
Total Time Commitment:

120 hours

Prerequisites:

An undergraduate degree in a cognate discipline.

Corequisites:

None

Recommended Background Knowledge:

Basic proficienty in mathematics and computing.

Non Allowed Subjects:
Subject

Core Participation Requirements:

Contact

email: harald@unimelb.edu.au

Subject Overview:

The aim of this subject is for students to develop familiarity and competence in assessing and designing computer programs for computational efficiency. Although computers manipulate data very quickly, to solve large-scale problems, we must design strategies so that the calculations combine effectively. Over the latter half of the 20th century, an elegant theory of computational efficiency developed. This subject introduces students to the fundamentals of this theory and to many of the classical algorithms and data structures that solve key computational questions. These questions include distance computations in networks, searching items in large collections, and sorting them in order.

Objectives:

On successful completion of this subject students should:

  • Design, manipulate and reason about a variety of techniques for solving sorting, searching and graph problems.
  • Write efficient algorithms and data structures for a variety of fundamental problems.
  • Conduct formal reasoning about problem complexity and algorithmic efficiency.
  • Recognize the design techniques of standard algorithms, and apply these techniques to develop new computational solutions to problems.
Assessment:
  • Project work during semester, due around weeks 7 and 11, expected to take approximately up to 60 hours (40%)
  • A 3-hour end-of-semester written examination (60%)

To pass the subject, students must obtain at least: 50% overall 20/40 in project work 30/60 in the written examination

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:

  • Application of knowledge of basic science and engineering fundamentals
  • Effective communication about computational efficiency
  • Capacity to reason and solve problems
  • Ability to undertake problem identification, formulation and solution
  • Capacity for creativity and innovation
  • 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 Information Technology
Master of Information Technology
Master of Operations Research and Management Science
Master of Philosophy - Engineering
Master of Science (Bioinformatics)
Ph.D.- Engineering
Postgraduate Certificate in Engineering
Related Majors/Minors/Specialisations: Master of Engineering (Mechatronics)
Master of Engineering (Software)

Download PDF version.