Assessment | Last updated | Lecture and Tutorial Schedule | Staff | Reference Material
Topics covered include complexity of algorithms and complexity
classes; abstract data types; algorithms for
sorting arrays, lists and files; algorithms and
data structures for searching: tree structures and
hashing; and graph representations and algorithms.
This subject consists of 36 hours, which will be roughly divided as
24 lecture hours and 12 tutorials.
A lecture outline will be kept current on this
page.
Preparation of exercises will be expected before the tutorial sessions.
A
problem sheet was handed out in class 14 May, due 28 May.
Marks for the quiz.
The animations can be found at
http://www.cs.mu.oz.au/muaia
Content
The objective of this subject is for students to become familiar with a
variety of techniques for
solving, sorting and searching problems and develop
a basic understanding of graph algorithms; to
develop experience with using complex algorithms
and data structures;
to be able to perform basic complexity
analyses of algorithms; and to acquire some
knowledge of the concepts of computability,
tractability and problem complexity.
Textbook
The prescribed text is : R. Sedgewick, Algorithms in Java, Parts 1-4,
Addison-Wesley, third edition.
It is strongly recommended that you obtain a copy of the
book for study. The book is a very useful reference, and the subject
follows the book closely.
The bookroom has copies for sale.
Two copies of the text are on reserve at the Engineering
Library.
Subject Structure
Lectures/Tutorials
Lectures/tutorial are held Wednesday 2:15-5:15 in the ICT Seminar
Room, Room 2.05b. (Note: The entrance to this room is located directly
to the left (north) of Lecture Theatre 3; At present there is no
room number sign.)
| Week | Starting | Lectures | Tutorial |
|---|---|---|---|
| Week 1 | 3 March | Introduction: why algorithms? Complexity | No tutorials or labs in Week 1. |
| Week 2 | 10 March | Complexity analysis | 4,6,10,11,slide 14 (section I). Solutions. |
| Week 3 | 17 March | Data Structures | 9, 12, 16, 17. Solutions. |
| Week 4 | 21 March | Data Structures: Trees | 18, 19, 20, 21. Solutions. |
| Week 5 | 28 March | Sorting: Simple Sorts | 20, 21, 25, 26. Solutions. |
| Week 6 | 4 April | Sorting: Shell and Quick Sorts | 27. Solutions. |
| Week 7 | 11 April | Sorting: Heap Sort | 34, 35, 36. Solutions. |
| Easter Break | 18 April | no class | no tutorial |
| Week 8 | 28 April | Mid-semester Test | Open tutorial. |
| Week 9 | 5 May | Searching: Simple Searches | 44, 45. Solutions. |
| Week 10 | 12 May | Searching: Red-black trees & Hashing. | 49, 52a. Solutions. |
| Week 11 | 19 May | Searching: Hashing & Radix Searching. | 52b, 52c, 56, 58, 59. Solutions. |
| Week 12 | 26 May | Revision Session | Revision Session |
| Topic | Text Reading |
|---|---|
| Complexity | Chapter 2 |
Linda Stern
linda@cs.mu.oz.au
Room 608
It is usually best to ask questions at the time of the lecture
(or before or after)
e-mail enquiries in should
have 521 in the subject line.
Ben Rubinstein
bir@cs.mu.oz.au
Room 4.31b
Hurdles of 50% apply to both the exam and the project.
Students who fail any hurdle will have their final mark adjusted so as to ensure that they fail the subject as a whole by at least the amount by which they failed the hurdle. For example, student with a mark of 40/40 for the practical work and 20/60 on the exam (10 marks short of the hurdle) will be assigned a final mark of 40 (10 marks short of a pass).
All assessment in this subject is to be done on an individual basis. Students who submit for assessment the work of other individuals, or who collaborate excessively, will be penalised by the Department and risk formal prosecution under the University's Disciplinary Regulations. Punishment is also extended to those who supply projects to other students. Showing code to another student is considered excessive collaboration.