Algorithms and Complexity

This subject has the following teaching availabilities in 2012:

120 hours.

An undergraduate degree in a cognate discipline.

None

Basic proficienty in mathermatics and computing.

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/

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.

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.

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

This subject is not available as a breadth subject.

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