Note: This unit is an archived version! See Overview tab for delivered versions.

COMP2907: Algorithms and Complexity (Advanced) (2017 - Semester 2)

Download UoS Outline

Unit: COMP2907: Algorithms and Complexity (Advanced) (6 CP)
Mode: Normal-Day
On Offer: Yes
Level: Intermediate
Faculty/School: School of Computer Science
Unit Coordinator/s: Dr Gudmundsson, Joachim
Session options: Semester 2
Versions for this Unit:
Site(s) for this Unit:
Campus: Camperdown/Darlington
Pre-Requisites: [Distinction level result in INFO1105 OR INFO1905]. OR Distinction level result in SOFT(1002 or 1902)
Brief Handbook Description: An advanced alternative to COMP2007; covers material at an advanced and challenging level.

This unit provides an introduction to the design and analysis of algorithms. The main aims are: To learn how to develop algorithmic solutions to computational problem, and; To develop understanding of algorithm efficiency and the notion of computational hardness.
Assumed Knowledge: MATH1004.
Lecturer/s: Dr Gudmundsson, Joachim
Timetable: COMP2907 Timetable
Time Commitment:
# Activity Name Hours per Week Sessions per Week Weeks per Semester
1 Independent Study 7.00 13
2 Lecture 3.00 1 13
3 Tutorial 2.00 1 13

Attributes listed here represent the key course goals (see Course Map tab) designated for this unit. The list below describes how these attributes are developed through practice in the unit. See Learning Outcomes and Assessment tabs for details of how these attributes are assessed.

Attribute Development Method Attribute Developed
designing efficient solutions to given
problems and scenarios, critical thinking,
creativity, critically evaluate existing
understanding and evaluate limitations of
own knowledge
Design (Level 3)
algorithmic problem solving, Computational Thinking Engineering/IT Specialisation (Level 3)
Fundamental concepts of ``Computational Thinking``, that are relevant in many areas of science and engineering Maths/Science Methods and Tools (Level 3)
Locating required information efficiently and effectively Information Seeking (Level 3)
Collaboration in tutorials and exchange of
ideas to solve algorithmic problems
Communication (Level 3)

For explanation of attributes and levels see Engineering & IT Graduate Outcomes Table.

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.

Maths/Science Methods and Tools (Level 3)
1. Knowledge of fundamental algorithms for several problems, especially graph problems, testing graph properties and solving optimization problems on graphs. Knowledge of fundamental general algorithmic design techniques, such as greedy, dynamic programming and divide-and-conquer
2. Understanding of the fundamental concepts of computational hardness Knowledge of basic Complexity classes and understanding of reductions between problems
3. Understanding of NP-hardness and the ways of dealing with hardness. Knowledge of randomized algorithms and approximation algorithms.
4. Experience and knowledge of mathematical proof techniques used for algorithmic properties.
Design (Level 3)
5. Ability to read, understand, analyze and modify a given algorithm. Ability to design algorithmic solutions for given problems
6. Ability to analyze the complexity of a given algorithm
Engineering/IT Specialisation (Level 3)
7. Experience of implementing algorithms
Assessment Methods:
# Name Group Weight Due Week Outcomes
1 Assignment No 30.00 Multiple Weeks 4, 5, 6, 7,
2 Quiz No 20.00 Multiple Weeks 1, 2, 3, 4, 5, 6,
3 Final Exam No 50.00 Exam Period 1, 2, 3, 4, 5, 6,
Assessment Description: Assignment: Five assignment, that may include implementations of algorithms.

Quiz: Short weekly quizzes on e-learning.

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 IT 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
Online Course Content: YSyd e-Learning (WebCT)

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. Overview of graphs, motivating example problems
Week 2 Greedy algorithms, scheduling and shortest paths
Week 3 More on greedy algorithms
Week 4 Divide and conquer, recurrences, sorting
Week 5 Dynamic programming, scheduling, subset sums, sequence alignment
Week 6 Network flows, maxflow mincut theorems, matching
Week 7 More on flows
Week 8 introduction to complexity theory, Polynomial time and NP
Week 9 more on P and NP, reductions and introduction to NP-completeness
Week 10 more on NP-completeness and complexity classes
Week 11 computational intractability and ways of dealing with hardness
Week 12 advanced topic in algorithms
Week 13 review
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
Bachelor of Computer Science and Technology (Advanced) 2015, 2016, 2017
Bachelor of Computer Science and Technology (Computer Science)(Advanced) 2014 and earlier 2013, 2014
Bachelor of Computer Science and Technology (Information Systems) 2014 and earlier 2010, 2011, 2012, 2013, 2014
Bachelor of Computer Science and Technology (Information Systems)(Advanced) 2014 and earlier 2013, 2014
Bachelor of Computer Science & Tech. Mid-Year 2016, 2017
Aeronautical Engineering / Science 2011, 2012, 2013, 2014
Aeronautical Engineering (Space) / Science 2011, 2012, 2013, 2014
Biomedical Engineering / Science 2013, 2014
Chemical & Biomolecular Engineering / Science 2011, 2012, 2013, 2014
Civil Engineering / Science 2011, 2012, 2013, 2014
Electrical Engineering (Bioelectronics) / Science 2011, 2012
Electrical Engineering / Science 2011, 2012, 2013, 2014
Electrical Engineering (Computer) / Science 2014
Electrical Engineering (Power) / Science 2011, 2012, 2013, 2014
Electrical Engineering (Telecommunications) / Science 2011, 2012, 2013, 2014
Aeronautical / Science 2015, 2016, 2017
Aeronautical (Space) / Science 2015
Biomedical Mid-Year 2016
Biomedical 2016
Biomedical /Science 2015, 2016, 2017
Chemical & Biomolecular / Science 2015
Civil / Science 2015
Electrical / Science 2015
Electrical (Computer) / Science 2015
Electrical (Power) / Science 2015
Electrical (Telecommunications) / Science 2015
Mechanical / Science 2015, 2016, 2017
Mechanical (Space) / Science 2015
Mechatronic / Science 2015, 2016, 2017
Mechatronic (Space) / Science 2015
Mechanical Engineering (Biomedical) / Science 2011, 2012
Mechanical Engineering / Science 2011, 2012, 2013, 2014
Mechanical Engineering (Space) / Science 2011, 2012, 2013, 2014
Mechatronic Engineering / Science 2011, 2012, 2013, 2014
Mechatronic Engineering (Space) / Science 2011, 2012, 2013, 2014
Project Engineering and Management (Civil) / Science 2011
Bachelor of Information Technology (Information Systems) 2014 and earlier 2011, 2012, 2013, 2014
Information Technology (Information Systems)/Arts 2012, 2013, 2014
Information Technology (Information Systems) / Science 2012, 2013, 2014
Flexible First Year (Stream A) / Science 2015, 2012, 2013, 2014
Bachelor of Computer Science and Technology 2015, 2016
Bachelor of Computer Science and Technology (Computer Science) 2014 and earlier 2013, 2014
Bachelor of Information Technology/Bachelor of Medical Science 2015
Bachelor of Information Technology (Computer Science) 2014 and earlier 2010, 2011, 2012, 2013, 2014
Information Technology (Computer Science)/Arts 2012, 2013, 2014
Information Technology (Computer Science) / Commerce 2012, 2013, 2014
Information Technology (Computer Science) / Medical Science 2012, 2013, 2014
Information Technology (Computer Science) / Science 2012, 2013, 2014
Information Technology (Computer Science) / Law 2012, 2013, 2014
Information Technology (Information Systems) / Commerce 2012, 2013, 2014
Information Technology (Information Systems) / Medical Science 2012, 2013, 2014
Information Technology (Information Systems) / Law 2012, 2013, 2014

Course Goals

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

Attribute Practiced Assessed
Maths/Science Methods and Tools (Level 3) Yes 54.18%
Design (Level 3) Yes 38.34%
Engineering/IT Specialisation (Level 3) Yes 7.5%
Information Seeking (Level 3) Yes 0%
Communication (Level 3) Yes 0%

These goals are selected from Engineering & IT Graduate Outcomes Table which defines overall goals for courses where this unit is primarily offered. See Engineering & IT Graduate Outcomes Table 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.