Note: This unit version has not been officially published yet and is subject to change!

COMP3530: Discrete Optimization (2019 - Semester 2)

Download UoS Outline

Unit: COMP3530: Discrete Optimization (6 CP)
Mode: Normal-Day
On Offer: Yes
Level: Senior
Faculty/School: School of Computer Science
Unit Coordinator/s: Dr Mestre, Julian
Session options: Semester 2
Versions for this Unit:
Campus: Camperdown/Darlington
Pre-Requisites: COMP2123 OR COMP2823 OR COMP2007 OR COMP2907.
Brief Handbook Description: This unit introduces students to the algorithmic theory and applications of discrete optimization. The main aims of this unit are: (i) learn how to model various practical problems as abstract optimization problems, (ii) learn the theory underlying efficient algorithms for solving these problems, (iii) learn how to use these tools in practice.

Specific topics include: Linear and integer programming, polyhedral theory, and approximation algorithms.
Assumed Knowledge: None.
Lecturer/s: Dr Mestre, Julian
Timetable: COMP3530 Timetable
Time Commitment:
# Activity Name Hours per Week Sessions per Week Weeks per Semester
1 Lecture 2.00 1 13
2 Tutorial 1.00 1 13
3 Independent Study 9.00 13

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.

Unassigned Outcomes
1. Knowledge of fundamental algorithms for several optimization problems such as linear and integer programming, approximation algorithms, and fixed-parameter tractability.
2. Experience implementing algorithms and using standard tools for solving real life problems
3. Ability to model application problems as optimization problems
4. Ability to apply and tailor know algorithms for solving new challenging problems
Assessment Methods:
# Name Group Weight Due Week Outcomes
1 Assignment 1 No 10.00 Week 3 1, 2, 3, 4,
2 Assignment 2 No 10.00 Week 5 1, 2, 3, 4,
3 Assignment 3 No 10.00 Week 8 1, 2, 3, 4,
4 Assignment 4 No 10.00 Week 10 1, 2, 3, 4,
5 Assignment 5 No 10.00 Week 12 1, 2, 3, 4,
6 Final Exam* No 50.00 Exam Period 1, 3, 4,
Assessment Description: Assignments: There will be five individual assignments. These will be consist of pen-and-paper type problems as well as implementation/experimental problems where students will have to solve concrete instances of discrete optimization problems using a state-of-the-art LP and IP solvers.

Final Exam: A written examination covering all the material covered in class.

Minimum performance: There is a final exam barrier of 40%, meaning that if you score less than 40% in the final you will automatically fail the unit.

Late penalties: For the assignments, a late penalty will be imposed that subtracts 20% of the possible marks per day (or part day) after the due date.
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.
Recommended Reference/s: Note: References are provided for guidance purposes only. Students are advised to consult these books in the university library. Purchase is not required.

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 Introduction to optimization
Week 2 Simplex
Week 3 Modeling
Assessment Due: Assignment 1
Week 4 Duality Theory
Week 5 Applications of linear programming
Assessment Due: Assignment 2
Week 6 Integral polyhedra
Week 7 Integer programming
Week 8 Large scale optimization
Assessment Due: Assignment 3
Week 9 Lagrangian relaxation
Week 10 Maximum submodular coverage
Assessment Due: Assignment 4
Week 11 Minimum submodular covering
Week 12 LP rounding
Assessment Due: Assignment 5
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 2015, 2016
Bachelor of Computer Science and Technology (Advanced) 2015, 2016, 2017
Bachelor of Computer Science and Technology (Computer Science) 2014 and earlier 2013, 2014
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 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 2014
Aeronautical Engineering (Space) / Science 2014
Biomedical Engineering / Science 2014
Electrical Engineering / Science 2014
Electrical Engineering (Computer) / Science 2014
Electrical Engineering (Power) / Science 2014
Electrical Engineering (Telecommunications) / Science 2014
Aeronautical / Science 2015, 2016, 2017
Aeronautical (Space) / Science 2015
Biomedical Mid-Year 2016
Biomedical 2016
Biomedical /Science 2015, 2016, 2017
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 / Science 2014
Mechanical Engineering (Space) / Science 2014
Mechatronic Engineering / Science 2014
Mechatronic Engineering (Space) / Science 2014
Bachelor of Information Technology 2015, 2016
Bachelor of Information Technology/Bachelor of Arts 2015, 2016
Bachelor of Information Technology/Bachelor of Commerce 2015, 2016
Bachelor of Information Technology/Bachelor of Medical Science 2015, 2016
Bachelor of Information Technology/Bachelor of Science 2015, 2016
Bachelor of Information Technology (Computer Science) 2014 and earlier 2013, 2014
Information Technology (Computer Science)/Arts 2013, 2014
Information Technology (Computer Science) / Commerce 2013, 2014
Information Technology (Computer Science) / Medical Science 2013, 2014
Information Technology (Computer Science) / Science 2013, 2014
Information Technology (Computer Science) / Law 2013, 2014
Bachelor of Information Technology (Information Systems) 2014 and earlier 2013, 2014
Bachelor of Information Technology/Bachelor of Laws 2015, 2016

Course Goals

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

Attribute Practiced Assessed
(5) Interdisciplinary, Inclusiveness, Influence (Level 3) No 0%
(4) Design (Level 3) No 0%
(3) Problem Solving and Inventiveness (Level 3) No 0%
(2) Engineering/ IT Specialisation (Level 3) No 0%
(1) Maths/ Science Methods and Tools (Level 3) 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.