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

COMP3927: Algorithm Design (Adv) (2019 - Semester 1)

Download UoS Outline

Unit: COMP3927: Algorithm Design (Adv) (6 CP)
Mode: Normal-Day
On Offer: Yes
Level: Senior Advanced
Faculty/School: School of Computer Science
Unit Coordinator/s: Umboh, Seeun William
Session options: Semester 1
Versions for this Unit:
Site(s) for this Unit:
Campus: Camperdown/Darlington
Pre-Requisites: COMP2123 OR COMP2823 OR INFO1105 OR INFO1905.
Prohibitions: COMP2007 OR COMP2907 OR COMP3927.
Brief Handbook Description: This unit provides an introduction to the design techniques that are used to find efficient algorithmic solutions for given problems. The techniques covered included greedy, divide-and-conquer, dynamic programming, and adjusting flows in networks. Students will extend their skills in algorithm analysis. The unit also provides an introduction to the concepts of computational complexity and reductions between problems.
Assumed Knowledge: MATH1004 OR MATH1904 OR MATH1064.
Timetable: COMP3927 Timetable
Time Commitment:
# Activity Name Hours per Week Sessions per Week Weeks per Semester
1 Lecture 3.00 1 13
2 Tutorial 2.00 1 12
3 Independent Study 8.00 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
Lectures: Introduction to fundamental concepts that are relevant in many areas of science and engineering (1) Maths/ Science Methods and Tools (Level 3)
Lectures: Apply general algorithmic techniques and analytical tools (2) Engineering/ IT Specialisation (Level 2)
Lectures: Designing efficient solutions to given problems and scenarios, critical thinking, creativity, critically evaluate existing understanding and evaluate limitations of own knowledge (4) Design (Level 3)
Assignments: Locate required information efficiently and effectively (6) Communication and Inquiry/ Research (Level 2)

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

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.

(6) Communication and Inquiry/ Research (Level 2)
1. Can produce a clear account of an algorithm, that would allow others to understand and implement it.
2. Can learn about an algorithm that is not previously known to the student, by searching for descriptions in textbooks or online.
(4) Design (Level 3)
3. Ability to read, understand, analyze and modify a given algorithm. Ability to design efficient algorithmic solutions for given problems and evaluate the proposal.
(2) Engineering/ IT Specialisation (Level 2)
4. Basic experience of implementing algorithms
5. Ability to analyze the complexity of a given algorithm
(1) Maths/ Science Methods and Tools (Level 3)
6. 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
7. Understanding of the fundamental concepts of computational hardness.
8. Understanding of NP-hardness and the ways of dealing with hardness. Knowledge of randomized algorithms and approximation algorithms.
9. Knowledge of basic Complexity classes and understanding of reductions between problems
Assessment Methods:
# Name Group Weight Due Week Outcomes
1 Assignment No 25.00 Multiple Weeks 3, 4, 5,
2 Quiz No 15.00 Multiple Weeks 4, 6, 7, 8,
3 Final Exam No 60.00 Exam Period 3, 5, 6, 7, 8,
Assessment Description: Assignment: Five assignments, 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: USyd 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 Graphs
Transitive closure
Bipartite graphs
Minimum number of links paths
Graph traversal
Week 3 Technique 1: Greedy algorithms
Shortest-path algorithm
Interval scheduling/partitioning
Minimum spanning trees
Scheduling to minimize lateness
Week 4 Technique 2: Divide-and-Conquer
Closest points
Counting inversions
Search and sort
Recursion and the Master Theorem
Week 5 Technique 3: Dynamic Programming
Longest increasing subsequence
Knapsack
Weighted interval scheduling
Maximum-sum contiguous subarray
Week 6 Technique 3: Dynamic Programming (cont'd)
Bellman-Ford algorithm
RNA Secondary Structure
Segmented Least Squares
Week 7 Technique 4: Flow Networks
Theory: Max-flow Min-cut
Ford-Fulkerson algorithm
Week 8 Technique 4: Flow Networks (cont'd)
Applications: Bipartite matching, Perfect matching, Disjoint paths, Network connectivity, Circulation problems, Image segmentation
Week 9 Complexity classes: P, NP
NP-Completeness and Computational Intractability
Polynomial-time reductions
Week 10 Coping with hardness
Exact algorithms and restricted instances
Approximation algorithms
Week 11 Randomized algorithms
Randomized selection
Contention resolution
Week 12 Spare for public holiday or for a guest lecture
Week 13 Review of Unit of Study
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) 2017, 2016
Bachelor of Advanced Computing/Bachelor of Commerce 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science (Health) 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science (Medical Science) 2018, 2019, 2020
Bachelor of Advanced Computing (Computational Data Science) 2018, 2019, 2020
Bachelor of Advanced Computing (Computer Science Major) 2018, 2019, 2020
Bachelor of Advanced Computing (Information Systems Major) 2018, 2019, 2020
Bachelor of Advanced Computing (Software Development) 2018, 2019, 2020
Bachelor of Computer Science & Tech. Mid-Year 2016, 2017
Biomedical Mid-Year 2016, 2017, 2018, 2019, 2020
Biomedical 2016, 2017, 2018, 2019, 2020
Bachelor of Computer Science and Technology 2016, 2017
Bachelor of Information Technology 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Arts 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Commerce 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Medical Science 2016, 2017
Bachelor of Information Technology/Bachelor of Science 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Laws 2015, 2016, 2017

Course Goals

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

Attribute Practiced Assessed
(5) Interdisciplinary, Inclusiveness, Influence (Level 3) No 0%
(6) Communication and Inquiry/ Research (Level 2) Yes 0%
(4) Design (Level 3) Yes 20.33%
(3) Problem Solving and Inventiveness (Level 3) No 0%
(2) Engineering/ IT Specialisation (Level 2) Yes 33.17%
(1) Maths/ Science Methods and Tools (Level 3) Yes 46.5%

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.