Note: This unit version is currently being edited and is subject to change!
COMP3530: Discrete Optimization (2020 - Semester 2)
| 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: |
|
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| Assessment Methods: |
|
||||||||||||||||||||||||||||||||||||||||||
| 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: |
|
||||||||||||||||||||||||||||||||||||||||||
| 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 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.
