Note: This unit is an archived version! See Overview tab for delivered versions.
COMP2907: Algorithms and Complexity (Advanced) (2017 - Semester 2)
| 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: |
|
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)| Assessment Methods: |
|
||||||||||||||||||||||||
| Assessment Description: |
Assignment: Five assignment, that may include implementations of algorithms. Quiz: Short weekly quizzes on e-learning. Final Exam: Final Examination |
||||||||||||||||||||||||
| Grading: |
|
||||||||||||||||||||||||
| 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.
|
| 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 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.
