Outline

Overview

This unit of study will provide a rigorous introduction to a range of techniques and paradigms central to modern algorithm design, with a focus on randomised algorithms. The unit will emphasise the theoretical underpinnings of these algorithms and their mathematical guarantees, and provide intuition and understanding through a range of practical applications and examples such as probabilistic data structures, hashing, approximation algorithms, and streaming algorithms.

Unit details and rules

Academic unit	Computer Science
Credit points	6
Prerequisites ?	COMP9123 or COMP2123 or COMP2823
Corequisites ?	None
Prohibitions ?	COMP4270
Assumed knowledge ?	COMP3027 or equivalent; discrete mathematics and probability (e.g. MATH1064 or equivalent)
Available to study abroad and exchange students	Yes

Teaching staff

Coordinator	Clement Canonne, clement.canonne@sydney.edu.au

Assessment

The census date for this unit availability is 31 March 2025

Details
Criteria

Type	Description	Weight	Due	Length
Supervised exam ?	Final exam Final exam, on paper.	40%	Formal exam period	2 hours
Outcomes assessed:
Assignment	Assignment 1 Written assignment, with a programming component	15%	Week 04 Due date: 21 Mar 2025 at 23:59	No time limit.
Outcomes assessed:
Assignment	Assignment 2 Written assignment, with a programming component	15%	Week 07 Due date: 11 Apr 2025 at 23:59	No time limit.
Outcomes assessed:
Assignment	Assignment 3 Written assignment, with a programming component	15%	Week 10 Due date: 10 May 2025 at 23:59	No time limit.
Outcomes assessed:
Assignment	Communication of knowledge Identify and draft a contribution to Wikipedia related to the unit.	6%	Week 12 Due date: 23 May 2025 at 23:59 Closing date: 28 May 2025	No time limit
Outcomes assessed:
Participation	Weekly quiz Weekly MCQ to assess your understanding of the lectures.	9%	Weekly	No time limit
Outcomes assessed:
= AI allowed ?

Assessment summary

Detailed information for each assessment can be found on the ed forum of the unit.

Assessment criteria

The University awards common result grades, set out in the Coursework Policy 2021 (Schedule 1).

As a general guide, a high distinction indicates work of an exceptional standard, a distinction a very high standard, a credit a good standard, and a pass an acceptable standard.

Result name	Mark range	Description
High distinction	85 - 100
Distinction	75 - 84
Credit	65 - 74
Pass	50 - 64
Fail	0 - 49	When you don’t meet the learning outcomes of the unit to a satisfactory standard.

guide to grades

For more information see guide to grades.

Use of generative artificial intelligence (AI) and automated writing tools

Except for supervised exams or in-semester tests, you may use generative AI and automated writing tools in assessments unless expressly prohibited by your unit coordinator.

For exams and in-semester tests, the use of AI and automated writing tools is not allowed unless expressly permitted in the assessment instructions.

The icons in the assessment table above indicate whether AI is allowed – whether full AI, or only some AI (the latter is referred to as “AI restricted”). If no icon is shown, AI use is not permitted at all for the task. Refer to Canvas for full instructions on assessment tasks for this unit.

Your final submission must be your own, original work. You must acknowledge any use of automated writing tools or generative AI, and any material generated that you include in your final submission must be properly referenced. You may be required to submit generative AI inputs and outputs that you used during your assessment process, or drafts of your original work. Inappropriate use of generative AI is considered a breach of the Academic Integrity Policy and penalties may apply.

The Current Students website provides information on artificial intelligence in assessments. For help on how to correctly acknowledge the use of AI, please refer to the  AI in Education Canvas site.

Late submission

In accordance with University policy, these penalties apply when written work is submitted after 11:59pm on the due date:

Deduction of 5% of the maximum mark for each calendar day after the due date.
After ten calendar days late, a mark of zero will be awarded.

This unit has an exception to the standard University policy or supplementary information has been provided by the unit coordinator. This information is displayed below:

These penalties apply when written work is submitted after 11:59pm on the due date. Deduction of 5% of the maximum mark for each of the first 2 calendar days after the due date. Submissions made after the 2nd calendar day will receive 0 marks.

Academic integrity

The Current Student website provides information on academic integrity and the resources available to all students. The University expects students and staff to act ethically and honestly and will treat all allegations of academic integrity breaches seriously.

We use similarity detection software to detect potential instances of plagiarism or other forms of academic integrity breach. If such matches indicate evidence of plagiarism or other forms of academic integrity breaches, your teacher is required to report your work for further investigation.

Learning support

Simple extensions

If you encounter a problem submitting your work on time, you may be able to apply for an extension of five calendar days through a simple extension.  The application process will be different depending on the type of assessment and extensions cannot be granted for some assessment types like exams.

Special consideration

If exceptional circumstances mean you can’t complete an assessment, you need consideration for a longer period of time, or if you have essential commitments which impact your performance in an assessment, you may be eligible for special consideration or special arrangements.

Special consideration applications will not be affected by a simple extension application.

Using AI responsibly

Co-created with students, AI in Education includes lots of helpful examples of how students use generative AI tools to support their learning. It explains how generative AI works, the different tools available and how to use them responsibly and productively.

Support for students

The Support for Students Policy reflects the University’s commitment to supporting students in their academic journey and making the University safe for students. It is important that you read and understand this policy so that you are familiar with the range of support services available to you and understand how to engage with them.

The University uses email as its primary source of communication with students who need support under the Support for Students Policy. Make sure you check your University email regularly and respond to any communications received from the University.

Learning resources and detailed information about weekly assessment and learning activities can be accessed via Canvas. It is essential that you visit your unit of study Canvas site to ensure you are up to date with all of your tasks.

If you are having difficulties completing your studies, or are feeling unsure about your progress, we are here to help. You can access the support services offered by the University at any time:

Support and Services (including health and wellbeing services, financial support and learning support)
Course planning and administration
Meet with an Academic Adviser

Weekly schedule

WK	Topic	Learning activity
Week 01	Basics of discrete probability, randomised algorithms, linearity of expectation; application to some specific algorithms	Lecture (2 hr)
Week 02	Concentration bounds, probability amplification, median trick	Lecture (2 hr)
Week 03	Coupon Collector, Load Balancing, Power of Two Choices	Lecture (2 hr)
Week 04	Derandomisation: Max-Cut, Method of Conditional Expectations	Lecture (2 hr)
Week 05	Graph algorithms: Randomised Min-Cut, MST in expected linear time	Lecture (2 hr)
Week 06	Probabilistic data structures I: Hashing and Bloom filters	Lecture (2 hr)
Week 07	Probabilistic data structures II: Johnson-Lindenstrauss, LSH	Lecture (2 hr)
Week 08	Streaming and Sketching I: definitions, examples, first algorithms	Lecture (2 hr)
Week 09	Streaming and Sketching II: CountSketch, Count–min Sketch	Lecture (2 hr)
Week 10	Linear Programming and Randomised Rounding	Lecture (2 hr)
Week 11	Learning and testing probability distributions	Lecture (2 hr)
Week 12	Special topic	Lecture (2 hr)
Week 13	Review	Lecture (2 hr)
Weekly	Discussion and practice (exercise solving) related to the week's lecture.	Tutorial (2 hr)

Study commitment

Typically, there is a minimum expectation of 1.5-2 hours of student effort per week per credit point for units of study offered over a full semester. For a 6 credit point unit, this equates to roughly 120-150 hours of student effort in total.

Required readings

All required readings for this unit will be provided on the Ed forum of the unit.

Suggested (optional) readings (all available through the University of Sydney's library):

Mitzenmacher, M., & Upfal, E. (2005). Probability and computing : randomized algorithms and probabilistic analysis. Cambridge University Press.
Motwani, R., & Raghavan, P. (1996). Randomized algorithms. ACM Computing Surveys, 28(1), 33–37. https://doi.org/10.1145/234313.234327

Learning outcomes

Learning outcomes are what students know, understand and are able to do on completion of a unit of study. They are aligned with the University's graduate qualities and are assessed as part of the curriculum.

At the completion of this unit, you should be able to:

LO1. Produce a clear account of an algorithm, that would allow others to understand and implement it
LO2. Learn about new algorithms by searching for descriptions in textbooks or online
LO3. Read, understand, analyze and modify a given algorithm. Ability to design efficient algorithmic solutions for given problems and evaluate the proposal
LO4. Analyze the complexity of a given algorithm, in terms of the different computational resources involved (time, memory, etc.)
LO5. Understand the fundamental concepts of randomisation and randomness in computing
LO6. Knowledge and mastery of key techniques to design and analyse randomised algorithms.
LO7. Apply knowledge of fundamental randomized algorithms and algorithmic techniques to several problems, especially streaming, optimization, scheduling, and graph problems.

Graduate qualities

The graduate qualities are the qualities and skills that all University of Sydney graduates must demonstrate on successful completion of an award course. As a future Sydney graduate, the set of qualities have been designed to equip you for the contemporary world.

GQ1	Depth of disciplinary expertise Deep disciplinary expertise is the ability to integrate and rigorously apply knowledge, understanding and skills of a recognised discipline defined by scholarly activity, as well as familiarity with evolving practice of the discipline.
GQ2	Critical thinking and problem solving Critical thinking and problem solving are the questioning of ideas, evidence and assumptions in order to propose and evaluate hypotheses or alternative arguments before formulating a conclusion or a solution to an identified problem.
GQ3	Oral and written communication Effective communication, in both oral and written form, is the clear exchange of meaning in a manner that is appropriate to audience and context.
GQ4	Information and digital literacy Information and digital literacy is the ability to locate, interpret, evaluate, manage, adapt, integrate, create and convey information using appropriate resources, tools and strategies.
GQ5	Inventiveness Generating novel ideas and solutions.
GQ6	Cultural competence Cultural Competence is the ability to actively, ethically, respectfully, and successfully engage across and between cultures. In the Australian context, this includes and celebrates Aboriginal and Torres Strait Islander cultures, knowledge systems, and a mature understanding of contemporary issues.
GQ7	Interdisciplinary effectiveness Interdisciplinary effectiveness is the integration and synthesis of multiple viewpoints and practices, working effectively across disciplinary boundaries.
GQ8	Integrated professional, ethical, and personal identity An integrated professional, ethical and personal identity is understanding the interaction between one’s personal and professional selves in an ethical context.
GQ9	Influence Engaging others in a process, idea or vision.

Outcome map

Learning outcomes	Graduate qualities
Learning outcomes

Alignment with Competency standards

Outcomes	Competency standards
	Stage 1 Competency Standard for Professional Engineer (UG) - 1.2 (L2). Mathematical and computational methods. (Level 2- Attaining required standard (Bachelor Honours standard)) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline. 1.2 (L3). Mathematical and computational methods. (Exceeding required standard) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline.
	Stage 1 Competency Standard for Professional Engineer (UG) - 1.2 (L1). Mathematical and computational methods. (Level 1- Contributing to required standard) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline. 1.2 (L2). Mathematical and computational methods. (Level 2- Attaining required standard (Bachelor Honours standard)) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline. 1.2 (L3). Mathematical and computational methods. (Exceeding required standard) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline.
	Stage 1 Competency Standard for Professional Engineer (UG) - 1.2 (L2). Mathematical and computational methods. (Level 2- Attaining required standard (Bachelor Honours standard)) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline. 1.2 (L3). Mathematical and computational methods. (Exceeding required standard) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline.
	Stage 1 Competency Standard for Professional Engineer (UG) - 1.2 (L2). Mathematical and computational methods. (Level 2- Attaining required standard (Bachelor Honours standard)) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline. 1.2 (L3). Mathematical and computational methods. (Exceeding required standard) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline.
	Stage 1 Competency Standard for Professional Engineer (UG) - 1.2 (L2). Mathematical and computational methods. (Level 2- Attaining required standard (Bachelor Honours standard)) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline. 1.2 (L3). Mathematical and computational methods. (Exceeding required standard) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline.
	Stage 1 Competency Standard for Professional Engineer (UG) - 1.2 (L2). Mathematical and computational methods. (Level 2- Attaining required standard (Bachelor Honours standard)) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline. 1.2 (L3). Mathematical and computational methods. (Exceeding required standard) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline.
	Stage 1 Competency Standard for Professional Engineer (UG) - 1.2 (L2). Mathematical and computational methods. (Level 2- Attaining required standard (Bachelor Honours standard)) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline. 1.2 (L3). Mathematical and computational methods. (Exceeding required standard) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline.

Stage 1 Competency Standard for Professional Engineer (UG) -

Competency code	Taught, Practiced or Assessed	Competency standard
1.2 (L2)		Mathematical and computational methods. (Level 2- Attaining required standard (Bachelor Honours standard)) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline.
1.2 (L3)		Mathematical and computational methods. (Exceeding required standard) Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline.

Responding to student feedback

This section outlines changes made to this unit following staff and student reviews.

- Providing additional resources ("Week 0") - Editing tutorial sheets to clarify the expectations for the tutorials - Adding programming exercises and assignments

Disclaimer

The University reserves the right to amend units of study or no longer offer certain units, including where there are low enrolment numbers.

To help you understand common terms that we use at the University, we offer an online glossary.

Current students

Overview

Overview

Unit details and rules

Teaching staff

Assessment

Assessment

Assessment summary

Assessment criteria

Use of generative artificial intelligence (AI) and automated writing tools

Late submission

Academic integrity

Learning support

Learning support

Simple extensions

Special consideration

Using AI responsibly

Support for students

Weekly schedule

Weekly schedule

Study commitment

Required readings

Learning outcomes

Learning outcomes

Graduate qualities

Outcome map

Alignment with Competency standards

Responding to student feedback

Responding to student feedback

Disclaimer

On this page

Useful links

COMP5270: Randomised and Advanced Algorithms

Semester 1, 2025 [Normal day] - Camperdown/Darlington, Sydney

Overview

Overview

Unit details and rules

Teaching staff

Assessment

Assessment

Assessment summary

Assessment criteria

Use of generative artificial intelligence (AI) and automated writing tools

Late submission

Academic integrity

Learning support

Learning support

Simple extensions

Special consideration

Using AI responsibly

Support for students

Weekly schedule

Weekly schedule

Study commitment

Required readings

Learning outcomes

Learning outcomes

Graduate qualities

Outcome map

Alignment with Competency standards

Responding to student feedback

Responding to student feedback

Disclaimer

On this page

Useful links