Note: This unit version is currently under review and is subject to change!

COMP9007: Algorithms (2019 - Semester 2)

Download UoS Outline

Unit: COMP9007: Algorithms (6 CP)
Mode: Normal-Day
On Offer: Yes
Level: Postgraduate
Faculty/School: School of Computer Science
Unit Coordinator/s: Dr van Renssen, Andre
Session options: Semester 1, Semester 2
Versions for this Unit:
Campus: Camperdown/Darlington
Pre-Requisites: None.
Prohibitions: COMP5211.
Brief Handbook Description: The study of algorithms is a fundamental aspect of computing. This unit of study covers data structures, algorithms, and gives an overview of the main ways of computational thinking from simple list manipulation and data format conversion, up to shortest paths and cycle detection in graphs. Students will gain essential knowledge in computer science, including basic concepts in data structures, algorithms, and intractability, using paradigms such as dynamic programming, divide and conquer, greed, local search, and randomisation, as well NP-hardness.
Assumed Knowledge: This unit of study assumes that students have general knowledge of mathematics (especially Discrete Math) and problem solving. Having moderate knowledge about Data structure can also help students to better understand the concepts of Algorithms will be taught in this course.
Lecturer/s: Dr van Renssen, Andre
Timetable: COMP9007 Timetable
Time Commitment:
# Activity Name Hours per Week Sessions per Week Weeks per Semester
1 Independent Study 5.00 13
2 Lecture 2.00 1 13
3 Tutorial 1.00 2 13
T&L Activities: Lecture: Lecture

Tutorial: Tutorial

Learning outcomes are the key abilities and knowledge that will be assessed in this unit. They are listed according to the course goal supported by each. See Assessment Tab for details how each outcome is assessed.

Design (Level 2)
1. Knowledge of fundamental algorithms for several problems, including graphs, greedy agorithms, divide-and-conquer, dynamic programming, and network flow as well as basic concepts of NP-completeness.
2. Collaboration in lectures/tutorials and exchange of ideas to solve algorithmic problems.
3. Ability to understand and analyze given algorithms as well as ability to design algorithmic solutions for given problems.
4. Students will practice their writing presentation skills.
Assessment Methods:
# Name Group Weight Due Week Outcomes
1 Assignments No 20.00 Multiple Weeks 1, 2, 3, 4,
2 Quizzes No 20.00 Multiple Weeks 1, 3,
3 Final Exam No 60.00 Exam Period 1, 3,
Assessment Description: Assignment: There will be three assignments in total, due in Week 4, 8, and 12 respectively. These assignments will focus on the design and analysis of algorithms.

Quiz: There will be three short quizzes in total, during tutorial times in Week 4, 8, and 12 respectively, on canvas.

Final Exam: Final Examination
Grading:
Grade Type Description
Standards Based Assessment Final grades in this unit are awarded at levels of HD for High Distinction, DI (previously D) for Distinction, CR for Credit, PS (previously P) for Pass and FA (previously F) for Fail as defined by University of Sydney Assessment Policy. Details of the Assessment Policy are available on the Policies website at http://sydney.edu.au/policies . Standards for grades in individual assessment tasks and the summative method for obtaining a final mark in the unit will be set out in a marking guide supplied by the unit coordinator.
Minimum Pass Requirement It is a policy of the School of Computer Science that in order to pass this unit, a student must achieve at least 40% in the written examination. For subjects without a final exam, the 40% minimum requirement applies to the corresponding major assessment component specified by the lecturer. A student must also achieve an overall final mark of 50 or more. Any student not meeting these requirements may be given a maximum final mark of no more than 45 regardless of their average.
Policies & Procedures: IMPORTANT: School policy relating to Academic Dishonesty and Plagiarism.

In assessing a piece of submitted work, the School of Computer Science may reproduce it entirely, may provide a copy to another member of faculty, and/or to an external plagiarism checking service or in-house computer program and may also maintain a copy of the assignment for future checking purposes and/or allow an external service to do so.

Other policies

See the policies page of the faculty website at http://sydney.edu.au/engineering/student-policies/ for information regarding university policies and local provisions and procedures within the Faculty of Engineering and Information Technologies.
Prescribed Text/s: Note: Students are expected to have a personal copy of all books listed.
  • Algorithm Design

Note that the "Weeks" referred to in this Schedule are those of the official university semester calendar https://web.timetable.usyd.edu.au/calendar.jsp

Week Description
Week 1 Unit introduction, algorithms and complexity, motivation and course outline. Stable matching.
Week 2 Algorithms design and analysis, asymptotic growth
Week 3 Data structures and recursive algorithms
Week 4 Graph algorithms: BFS and DFS
Week 5 Greedy algorithms: Interval scheduling, Kruskal's algorithm, Dijkstra's algorithm
Week 6 Divide and conquer: Recurrences, sorting, integer multiplication, selection
Week 7 Dynamic programming I
Week 8 Dynamic programming II
Week 9 Network flows I
Week 10 Network flows II
Week 11 Advanced topic, e.g. NP-hardness
Week 12 Advanced topic continued and review
Week 13 Review and outlook
Exam Period Assessment Due: Final Exam

Course Relations

The following is a list of courses which have added this Unit to their structure.

Course Year(s) Offered
Graduate Certificate in Data Science 2016, 2017, 2018, 2019, 2020
Master of Professional Engineering (Software) 2015, 2016, 2017
Graduate Certificate in Information Technology 2015, 2016, 2017, 2018, 2019, 2020
Graduate Certificate in Information Technology Management 2015, 2016, 2017, 2018, 2019, 2020
Graduate Diploma in Computing 2015, 2016, 2017, 2018, 2019, 2020
Graduate Diploma in Health Technology Innovation 2015, 2016, 2017, 2018, 2019, 2020
Graduate Diploma in Information Technology 2015, 2016, 2017, 2018, 2019, 2020
Graduate Diploma in Information Technology Management 2015, 2016, 2017, 2018, 2019, 2020
Master of Engineering 2015, 2016, 2017, 2019, 2020
Master of Health Technology Innovation 2015, 2016, 2017, 2018, 2019, 2020
Master of Information Technology 2015, 2016, 2017, 2018, 2019, 2020
Master of Information Technology Management 2015, 2016, 2017, 2018, 2019, 2020
Master of IT/Master of IT Management 2015, 2016, 2017, 2018, 2019, 2020

Course Goals

This unit contributes to the achievement of the following course goals:

Attribute Practiced Assessed
Design (Level 2) No 100%
Maths/Science Methods and Tools (Level 2) No 0%
Engineering/IT Specialisation (Level 2) No 0%

These goals are selected from Engineering & IT Graduate Outcomes Table 2018 which defines overall goals for courses where this unit is primarily offered. See Engineering & IT Graduate Outcomes Table 2018 for details of the attributes and levels to be developed in the course as a whole. Percentage figures alongside each course goal provide a rough indication of their relative weighting in assessment for this unit. Note that not all goals are necessarily part of assessment. Some may be more about practice activity. See Learning outcomes for details of what is assessed in relation to each goal and Assessment for details of how the outcome is assessed. See Attributes for details of practice provided for each goal.