Week 1Introduction and mathematical background
Official weekly topics for Week 1: - Lecture: Introduction and mathematical background - Time and space complexity: the desire for an implementation independent measure; worst-case and average-case complexity. Evaluating efficiency: rate of growth, asymptotic time complexity; notation. Iterative algorithms: analysis of "while" and "for" loops; summations. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 2Divide and conquer algorithms and recurrences
Official weekly topics for Week 2: - 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. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 3Applied Class / Graph algorithms / Dynamic programming / Complexity classes
No separate week-by-week topic is publicly listed for Week 3; official repeated teaching activities are shown below: - Applied Class: Applied Class - The applied classes provide weekly opportunities to apply the skills learnt in lectures to complete revision exercises with guidance from course staff. - Lecture: Graph algorithms - Directed and undirected graphs: vertex, edge, predecessor, successor, in-degree, out-degree, path, reachable, simple, cycle; weighted graphs. Graph representations: adjacency list and matrix representations. Graph algorithms: breadth-first search; depth-first search; topological sort. Minimal spanning tree: generic form, greedy choice strategy. - Lecture: Dynamic programming - Optimal substructure; overlapping sub-problems; table of sub-problem solutions; memoization; order of evaluation; dynamic programming. - 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. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 4Applied Class / Graph algorithms / Dynamic programming / Complexity classes
No separate week-by-week topic is publicly listed for Week 4; official repeated teaching activities are shown below: - Applied Class: Applied Class - The applied classes provide weekly opportunities to apply the skills learnt in lectures to complete revision exercises with guidance from course staff. - Lecture: Graph algorithms - Directed and undirected graphs: vertex, edge, predecessor, successor, in-degree, out-degree, path, reachable, simple, cycle; weighted graphs. Graph representations: adjacency list and matrix representations. Graph algorithms: breadth-first search; depth-first search; topological sort. Minimal spanning tree: generic form, greedy choice strategy. - Lecture: Dynamic programming - Optimal substructure; overlapping sub-problems; table of sub-problem solutions; memoization; order of evaluation; dynamic programming. - 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. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 5Applied Class / Graph algorithms / Dynamic programming / Complexity classes
No separate week-by-week topic is publicly listed for Week 5; official repeated teaching activities are shown below: - Applied Class: Applied Class - The applied classes provide weekly opportunities to apply the skills learnt in lectures to complete revision exercises with guidance from course staff. - Lecture: Graph algorithms - Directed and undirected graphs: vertex, edge, predecessor, successor, in-degree, out-degree, path, reachable, simple, cycle; weighted graphs. Graph representations: adjacency list and matrix representations. Graph algorithms: breadth-first search; depth-first search; topological sort. Minimal spanning tree: generic form, greedy choice strategy. - Lecture: Dynamic programming - Optimal substructure; overlapping sub-problems; table of sub-problem solutions; memoization; order of evaluation; dynamic programming. - 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. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 6Applied Class / Graph algorithms / Dynamic programming / Complexity classes
No separate week-by-week topic is publicly listed for Week 6; official repeated teaching activities are shown below: - Applied Class: Applied Class - The applied classes provide weekly opportunities to apply the skills learnt in lectures to complete revision exercises with guidance from course staff. - Lecture: Graph algorithms - Directed and undirected graphs: vertex, edge, predecessor, successor, in-degree, out-degree, path, reachable, simple, cycle; weighted graphs. Graph representations: adjacency list and matrix representations. Graph algorithms: breadth-first search; depth-first search; topological sort. Minimal spanning tree: generic form, greedy choice strategy. - Lecture: Dynamic programming - Optimal substructure; overlapping sub-problems; table of sub-problem solutions; memoization; order of evaluation; dynamic programming. - 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. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 7Applied Class / Graph algorithms / Dynamic programming / Complexity classes
No separate week-by-week topic is publicly listed for Week 7; official repeated teaching activities are shown below: - Applied Class: Applied Class - The applied classes provide weekly opportunities to apply the skills learnt in lectures to complete revision exercises with guidance from course staff. - Lecture: Graph algorithms - Directed and undirected graphs: vertex, edge, predecessor, successor, in-degree, out-degree, path, reachable, simple, cycle; weighted graphs. Graph representations: adjacency list and matrix representations. Graph algorithms: breadth-first search; depth-first search; topological sort. Minimal spanning tree: generic form, greedy choice strategy. - Lecture: Dynamic programming - Optimal substructure; overlapping sub-problems; table of sub-problem solutions; memoization; order of evaluation; dynamic programming. - 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. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 8Greedy algorithms
Official weekly topics for Week 8: - Lecture: Greedy algorithms - Greedy method: optimal substructure; greedy choice property; comparison of dynamic programming and greedy paradigms. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 9Amortised analysis
Official weekly topics for Week 9: - Lecture: Amortised analysis - Efficiency analysis in terms of sequences of operations; crude analysis; global analysis; the accounting method; the potential method. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 10Applied Class / Graph algorithms / Dynamic programming / Complexity classes
No separate week-by-week topic is publicly listed for Week 10; official repeated teaching activities are shown below: - Applied Class: Applied Class - The applied classes provide weekly opportunities to apply the skills learnt in lectures to complete revision exercises with guidance from course staff. - Lecture: Graph algorithms - Directed and undirected graphs: vertex, edge, predecessor, successor, in-degree, out-degree, path, reachable, simple, cycle; weighted graphs. Graph representations: adjacency list and matrix representations. Graph algorithms: breadth-first search; depth-first search; topological sort. Minimal spanning tree: generic form, greedy choice strategy. - Lecture: Dynamic programming - Optimal substructure; overlapping sub-problems; table of sub-problem solutions; memoization; order of evaluation; dynamic programming. - 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. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 11Applied Class / Graph algorithms / Dynamic programming / Complexity classes
No separate week-by-week topic is publicly listed for Week 11; official repeated teaching activities are shown below: - Applied Class: Applied Class - The applied classes provide weekly opportunities to apply the skills learnt in lectures to complete revision exercises with guidance from course staff. - Lecture: Graph algorithms - Directed and undirected graphs: vertex, edge, predecessor, successor, in-degree, out-degree, path, reachable, simple, cycle; weighted graphs. Graph representations: adjacency list and matrix representations. Graph algorithms: breadth-first search; depth-first search; topological sort. Minimal spanning tree: generic form, greedy choice strategy. - Lecture: Dynamic programming - Optimal substructure; overlapping sub-problems; table of sub-problem solutions; memoization; order of evaluation; dynamic programming. - 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. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
Week 12Randomised algorithms
Official weekly topics for Week 12: - Lecture: Randomised algorithms - Probabilistic analysis, randomised quicksort. Official timetable activities: - Lecture | Mon 11:00 | 60 mins | 42-115 Prentice Building, Learning Theatre - Lecture | Thu 10:00 | 120 mins | 80-2171 Queensland Bioscience Precinct, Learning Theatre - Tutorial | Thu 12:00 | 60 mins | 39A-208 General Purpose North 3, Collaborative Room Source: 2026 S2 UQ Course Profile - https://course-profiles.uq.edu.au/course-profiles/COMP4500-60804-7560
