Course coordinator
Dr Larissa Meinicke
Course overview
- Study period
- Semester 2, 2024 (22/07/2024 - 18/11/2024)
- Study level
- Postgraduate Coursework
- Location
- St Lucia
- Attendance mode
- In Person
- Units
- 2
- Administrative campus
- St Lucia
- Coordinating unit
- Elec Engineering & Comp Science School
Analysis of algorithms. Solution of summation and recurrence equations. Algorithm paradigms: divide-and-conquer, greedy algorithms, dynamic programming, backtracking, branch-and-bound. Advanced graph algorithms. Amortised analysis. Self-adjusting data structures. Complexity classes, NP-completeness. Approximation algorithms. Randomized algorithms.
On entry to this subject, you have studied basic data structures and programming techniques. The objective of this subject is to build on these basic programming skills to develop an understanding of algorithm design and analysis techniques.
A number of general design paradigms, such as divide-and-conquer, play an important role in the development of algorithms. Familiarity with these paradigms can aid the programmer in the development of algorithms to solve new problems. The study of these design paradigms is an important component of this subject.
It is not enough just to derive an algorithm that solves a problem. If the algorithm is inefficient, it may be useless in practice. One can better appreciate an algorithm if one can analyse its use of resources, such as memory and computing time. Such analyses provide the basis for comparison of different algorithms to solve the same problem.
Overall, this subject can be viewed as an advanced course on programming, with an emphasis on developing both your ability to solve programming problems and to analyse your algorithms to ascertain their efficiency.
Course Changes in Response to Previous Student Feedback
The duration of the final examination was increased to 180 minutes.
Course requirements
Assumed background
The prerequisite knowledge required for the course is: programming experience, including basic data structures and recursive procedures; familiarity with a programming language; familiarity with proofs by mathematical induction; and knowledge of calculus, including differentiation, limits, L'Hpital's rule, and summations.
Prerequisites
You'll need to complete the following courses before enrolling in this one:
COMP7505
Incompatible
You can't enrol in this course if you've already completed the following:
COMP4500
Jointly taught details
This course is jointly-taught with:
- COMP4500
All learning activities are jointly taught.
Course contact
Course staff
Lecturer
Dr Larissa Meinicke
Timetable
The timetable for this course is available on the UQ Public Timetable.
Aims and outcomes
This course aims to expand your abilities to analyse, critique, design, and implement advanced data structures and algorithms.
Learning outcomes
After successfully completing this course you should be able to:
LO1.
Analyse, compare, and contrast algorithms and data structures by evaluating their time and space complexity.
LO2.
Apply algorithm design paradigms to generate novel solutions.
LO3.
Design abstract solutions based on graph algorithms, dynamic programming, and greedy methods.
LO4.
Develop efficient implementations to abstract solutions.
LO5.
Perform amortised analysis of data structures and algorithms.
LO6.
Explain the theory and relevance of theoretical complexity classes.
Assessment
Assessment summary
| Category | Assessment task | Weight | Due date |
|---|---|---|---|
| Quiz |
Online quizzes
|
10% |
9/08/2024 3:00 pm 16/08/2024 3:00 pm 23/08/2024 3:00 pm 6/09/2024 3:00 pm 11/10/2024 3:00 pm 25/10/2024 3:00 pm |
| Computer Code | Assignment 1 | 15% |
13/09/2024 3:00 pm |
| Computer Code | Assignment 2 | 15% |
18/10/2024 3:00 pm |
| Examination |
Final Examination
|
60% |
End of Semester Exam Period 2/11/2024 - 16/11/2024 |
A hurdle is an assessment requirement that must be satisfied in order to receive a specific grade for the course. Check the assessment details for more information about hurdle requirements.
Assessment details
Online quizzes
- Online
- Mode
- Written
- Category
- Quiz
- Weight
- 10%
- Due date
9/08/2024 3:00 pm
16/08/2024 3:00 pm
23/08/2024 3:00 pm
6/09/2024 3:00 pm
11/10/2024 3:00 pm
25/10/2024 3:00 pm
Task description
There will be 6 computer-based quizzes worth 2% each. Only the marks for your best 5 quizzes will contribute towards your final grade. They will be due at 3pm on Friday in weeks 3, 4, 5, 7, 11 and 13.
Submission guidelines
The quizzes are accessed via the course Blackboard site.
Deferral or extension
You cannot defer or apply for an extension for this assessment.
To accommodate unforeseen circumstances such as illness, your quiz score will be based on the best 5 out of 6 submissions.
Late submission
You will receive a mark of 0 if this assessment is submitted late.
Assignment 1
- Mode
- Written
- Category
- Computer Code
- Weight
- 15%
- Due date
13/09/2024 3:00 pm
Task description
The assignment covers algorithm analysis, graphs and graph algorithms.
All details of the assignment will be provided via the course blackboard site.
Submission guidelines
Assignments are to be submitted online via Blackboard unless otherwise specified for a particular assessment item.
Deferral or extension
You may be able to apply for an extension.
The maximum extension allowed is 7 days. Extensions are given in multiples of 24 hours.
Marked assignments with feedback and/or detailed solutions with feedback will be released to students within 7-14 days where the earlier time frame applies if no extensions.
Late submission
A penalty of 10% of the maximum possible mark will be deducted per 24 hours from time submission is due for up to 7 days. After 7 days, you will receive a mark of 0.
Assignment 2
- Mode
- Written
- Category
- Computer Code
- Weight
- 15%
- Due date
18/10/2024 3:00 pm
Task description
The assignment covers algorithm analysis, and algorithm design paradigms.
All details of the assignment will be provided via the course blackboard site.
Submission guidelines
Assignments are to be submitted online via Blackboard unless otherwise specified for a particular assessment item.
Deferral or extension
You may be able to apply for an extension.
The maximum extension allowed is 7 days. Extensions are given in multiples of 24 hours.
Marked assignments with feedback and/or detailed solutions with feedback will be released to students within 7-14 days where the earlier time frame applies if no extensions.
Late submission
A penalty of 10% of the maximum possible mark will be deducted per 24 hours from time submission is due for up to 7 days. After 7 days, you will receive a mark of 0.
Final Examination
- Hurdle
- Identity Verified
- In-person
- Mode
- Written
- Category
- Examination
- Weight
- 60%
- Due date
End of Semester Exam Period
2/11/2024 - 16/11/2024
Task description
The final examination is compulsory and covers the entire course. The final examination is not open book, but you may bring in one A4-size page crib sheet:
- it may be written on both sides
- it may be handwritten
- if machine produced it must be a minimum of 10-point font size
- it is to be handed in with your examination script
No calculators permitted.
Further details on the examination content and past examination papers will be provided at the end of semester and will be available from Blackboard.
Method of delivery: This exam will be held conducted as an invigilated on-campus exam.
Hurdle requirements
Refer to the course grading for details.Exam details
| Planning time | 10 minutes |
|---|---|
| Duration | 180 minutes |
| Calculator options | No calculators permitted |
| Open/closed book | Closed Book examination - specified written materials permitted |
| Materials | One A4 sheet of handwritten or typed notes, double sided, is permitted |
| Exam platform | Paper based |
| Invigilation | Invigilated in person |
Submission guidelines
Deferral or extension
You may be able to defer this exam.
Course grading
Full criteria for each grade is available in the Assessment Procedure.
| Grade | Description |
|---|---|
| 1 (Low Fail) |
Absence of evidence of achievement of course learning outcomes. Course grade description: At least one item of work submitted or examination attempted. Your final percentage mark is your composite mark. |
| 2 (Fail) |
Minimal evidence of achievement of course learning outcomes. Course grade description: Composite mark >= 20%. Your final percentage mark is the minimum of your composite mark and 44%. |
| 3 (Marginal Fail) |
Demonstrated evidence of developing achievement of course learning outcomes Course grade description: Composite mark >= 45% and final examination >= 35%. Your final percentage mark is the minimum of your composite mark and 49%. |
| 4 (Pass) |
Demonstrated evidence of functional achievement of course learning outcomes. Course grade description: Composite mark >= 50% and final examination >= 40%. Your final percentage mark is the minimum of your composite mark and 64%. |
| 5 (Credit) |
Demonstrated evidence of proficient achievement of course learning outcomes. Course grade description: Composite mark >= 65% and final examination >= 55%. Your final percentage mark is the minimum of your composite mark and 74%. |
| 6 (Distinction) |
Demonstrated evidence of advanced achievement of course learning outcomes. Course grade description: Composite mark >= 75% and final examination >= 65%. Your final percentage mark is the minimum of your composite mark and 84%. |
| 7 (High Distinction) |
Demonstrated evidence of exceptional achievement of course learning outcomes. Course grade description: Composite mark >= 85% and final examination >= 75%. Your final percentage mark is your composite mark. |
Additional course grading information
Your composite mark is the sumﾠ(rounded to the nearest whole number) of your marks for your best 5 quizzes, 2 assignments and final examination.
At the discretion of the course coordinator, marks for assessment items may be adjusted upwards, but not downwards.
Supplementary assessment
Supplementary assessment is available for this course.
Additional assessment information
Generative AI and Machine Translation in Assessment
The assessment tasks evaluate students' abilities, skills and knowledge without the aid of generative Artificial Intelligence (AI) or Machine Translation (MT). Students are advised that the use of AI technologies to develop responses is strictly prohibited and may constitute student misconduct under the Student Code of Conduct.
Having Troubles?
If you are having difficulties with any aspect of the course material, you should seek help. Speak to the course teaching staff.
If external circumstances are affecting your ability to work on the course, you should seek help as soon as possible. The University and UQ Union have organisations and staff who are able to help, for example, UQ Student Services are able to help with study and exam skills, tertiary learning skills, writing skills, financial assistance, personal issues, and disability services (among other things).
Complaints and criticisms should be directed in the first instance to the course coordinator. If you are not satisfied with the outcome, you may bring the matter to the attention of the School of EECS Director of Teaching and Learning.
Learning resources
You'll need the following resources to successfully complete the course. We've indicated below if you need a personal copy of the reading materials or your own item.
Library resources
Find the required and recommended resources for this course on the UQ Library website.
Additional learning resources information
Lecture notes, revision materials and assignments will be available from the course blackboard site. Some solutions will also be available from the course blackboard site.
ﾠ
Learning activities
The learning activities for this course are outlined below. Learn more about the learning outcomes that apply to this course.
Filter activity type by
Please select
| Learning period | Activity type | Topic |
|---|---|---|
Multiple weeks From Week 1 To Week 13 |
Tutorial |
Tutorials Weekly tutorials. |
Week 1 (22 Jul - 28 Jul) |
Lecture |
Introduction and mathematical background Time and space complexity: the desire for an implementation independent measure; worst-case and average-case complexity. |
Week 2 (29 Jul - 04 Aug) |
Lecture |
Divide and conquer algorithms and recurrences Divide-and conquer, recursion; divide, conquer and combine. Solving recurrences: substitution; iterating the recurrence to get a summation; recursion trees; master method. |
Multiple weeks From Week 3 To Week 5 |
Lecture |
Graph algorithms Directed and undirected graphs: vertex, edge, predecessor, successor, in-degree, out-degree, path, reachable, simple, cycle; weighted graphs. |
Multiple weeks From Week 6 To Week 7 |
Lecture |
Dynamic programming Optimal substructure; overlapping sub-problems; table of sub-problem solutions; memoization; order of evaluation; dynamic programming. |
Week 8 (09 Sep - 15 Sep) |
Lecture |
Greedy algorithms Greedy method: optimal substructure; greedy choice property; comparison of dynamic programming and greedy paradigms. |
Week 9 (16 Sep - 22 Sep) |
Lecture |
Amortised analysis Efficiency analysis in terms of sequences of operations; crude analysis; global analysis; the accounting method; the potential method. |
Multiple weeks From Week 10 To Week 11 |
Lecture |
Complexity classes Decision problems; tractable and intractable problems; Polynomial time; the class P; Polynomial time verification; the class NP; reducibility; NP-completeness. Traveling-salesman problem. |
Week 12 (14 Oct - 20 Oct) |
Lecture |
Randomised algorithms Probabilistic analysis, randomised quicksort. |
Policies and procedures
University policies and procedures apply to all aspects of student life. As a UQ student, you must comply with University-wide and program-specific requirements, including the:
- Student Code of Conduct Policy
- Student Integrity and Misconduct Policy and Procedure
- Assessment Procedure
- Examinations Procedure
- Reasonable Adjustments - Students Policy and Procedure
Learn more about UQ policies on my.UQ and the Policy and Procedure Library.
School guidelines
Your school has additional guidelines you'll need to follow for this course: