1. Handbook
  2. Subjects
  3. Algorithms and Complexity
  4. Print

Algorithms and Complexity (COMP90038)

Graduate courseworkPoints: 12.5On Campus (Parkville)

You’re viewing the 2017 Handbook:
Or view archived Handbooks
You’re currently viewing the 2017 version of this subject

Overview

Availability
Semester 1
Semester 2
FeesLook up fees

AIMS

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.

INDICATIVE CONTENT

Topics covered include complexity classes and asymptotic notation; empirical analysis of algorithms; abstract data types including queues, trees, priority queues 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.

Intended learning outcomes

INTENDED LEARNING OUTCOMES (ILO)


On completion of this subject the student should be able to:




  • 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

Generic skills

On completion of this subject students should have the following skills:

  • 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.

Last updated: 3 November 2022

Eligibility and requirements

Prerequisites

An undergraduate degree in a cognate discipline.

Corequisites

None

Non-allowed subjects

Code Name Teaching period Credit Points
COMP20003 Algorithms and Data Structures
Semester 2 (On Campus - Parkville)
 12.5
COMP20007 Design of Algorithms
Semester 1 (On Campus - Parkville)
 12.5

Recommended background knowledge

Basic discrete mathematics (sets and relations); elementary data structures (arrays, records, and linked lists).

Inherent requirements (core participation requirements)

The University of Melbourne is committed to providing students with reasonable adjustments to assessment and participation under the Disability Standards for Education (2005), and the Assessment and Results Policy (MPF1326). Students are expected to meet the core participation requirements for their course. These can be viewed under Entry and Participation Requirements for the course outlines in the Handbook.

Further details on how to seek academic adjustments can be found on the Student Equity and Disability Support website: http://services.unimelb.edu.au/student-equity/home

Last updated: 3 November 2022

Assessment

Additional details

  • Project work during semester due around weeks 6 and 11, expected to take approximately 25 - 30 hours of work (20%). Addresses all Intended Learning Ootcomes, (ILOs) 1 - 4.
  • A written 50-minute test (ILOs 1, 3, and 4), around week 7 (10%)
  • A written 3-hour closed book examination (70%)


Hurdle requirements:

The examination is a hurdle and must be passed to pass the subject

The student must also successfully complete at least eight of the weekly online quizzes.

Last updated: 3 November 2022

Dates & times

  • Semester 1
    Principal coordinatorLars Kulik
    Mode of deliveryOn Campus (Parkville)
    Contact hours36 hours, comprising of one 2-hour lecture and one 1-hour tutorial.
    Total time commitment200 hours
    Teaching period27 February 2017 to 28 May 2017
    Last self-enrol date10 March 2017
    Census date31 March 2017
    Last date to withdraw without fail 5 May 2017
    Assessment period ends23 June 2017

    Semester 1 contact information

    Semester 1
    Prof Lars Kulik
    lkulik@unimelb.edu.au


    Semester 2
    A/Prof Harald Sondergaard
    harald@unimelb.edu.au

  • Semester 2
    Principal coordinatorHarald Sondergaard
    Mode of deliveryOn Campus (Parkville)
    Contact hours36 hours, comprising of one 2-hour lecture and one 1-hour tutorial.
    Total time commitment200 hours
    Teaching period24 July 2017 to 22 October 2017
    Last self-enrol date 4 August 2017
    Census date31 August 2017
    Last date to withdraw without fail22 September 2017
    Assessment period ends17 November 2017

    Semester 2 contact information

    Semester 1
    Prof Lars Kulik
    lkulik@unimelb.edu.au


    Semester 2
    A/Prof Harald Sondergaard
    harald@unimelb.edu.au

Time commitment details

200 hours

Last updated: 3 November 2022

Further information

Last updated: 3 November 2022