Classes

Each week has three hours of face-to-face class. These classes will be a mixture lecture material, discussion and tutorial material.

Recommended Reading and References

There is no set text for the course, but the following far from exhaustive list of texts may be useful for reference, study and further reading:

• J. P. Ignizio and T. M. Cavalier, "Linear Programming", Prentice Hall, 1994.
• T. C. Hu, "Integer Programming and Network Flows", Addison Wesley, 1969.
• F. Rossi, P. van Beek and T. Walsh (eds.), "Handbook of Constraint Programming", Elsevier, 2006.
• R. K. Ahuja, T. L. Magnanti and J. B. Orlin, "Network Flows: Theory, Algorithms, and Applications", Prentice Hall, 1993.
• R. G. Downey and M. R. Fellows,  "Parameterized Complexity", Springer, 1999.
• R. G. Downey and M. R. Fellows, "Fundamentals of Parameterized Complexity", Springer, 2013.
• J. Flum and M. Grohe, "Parameterized Complexity Theory", Springer, 2006.
• R. Niedermeier, "An Invitation to Parameterized Algorithms", Springer, 2006.
• V. V. Vazirani, "Approximation Algorithms", Springer, 2001.
• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation: Combinatorial optimization problems and their approximability properties", Springer, 2009.

Unit Webpage, Materials and Technologies Used

The unit webpage "can be found" at http://comp.mq.edu.au/units/comp795.

The materials for the unit including notes, discussion fora, electronic submission links etc. will be through the iLearn system.

The programming assignment can be done in any programming language subject to prior approval of the course convener. The default expectation for programming language is Java, and as such does not require approval to use. Similarly, additional libraries may be used subject to prior approval of the course convener. In any case where libraries or code other than that of the student's is used, proper attribution must be given.

Algorithms are the essence of computer science. In this unit we build on the undergraduate understanding of algorithms and look at interesting and useful algorithms, both fundamental and cutting edge. 

The particular material covered will depend on the cohort but may include topics such as approximation algorithms, exponential-time exact and parameterized algorithms, linear and constraint programming and fundamental graph algorithms such as max-flow algorithms, matching algorithms and so on.

Throughout the unit there is an emphasis on developing not just a knowledge of algorithms, but of general algorithmic techniques alongside a deeper understanding of why algorithms work at a formal level. This helps facilitate the student's ability to construct a 'toolkit' of algorithmic techniques that can be adapted and employed to solve computational problems in their ongoing studies and work.

Part of this understanding will be the ongoing development of an intution and formal approaches for comparing and evaluating algorithms. As such the unit will also employ appropriate tools from complexity theory to analyse the performance of the algorithms studied.

Students entering this unit should have programming experience commensurate with the completion of an undergradute computing degree, a working knowledge of basic and intermediate algorithms and experience with discrete mathematics. Further algorithmic and mathematical studay will be of benefit, but is not necessary. Directly relevant undergraduate units offered at Macquarie include COMP225 - Algorithms and Data Structures, DMTH237 - Discrete Mathematics II and their prerequisites. Completion of COMP333 - Algorithm Theory and Design would be helpful.

The following is the initial schedule for topics in the unit, this may be subject to change depending on the cohort and the material.

COMP795 will be assessed and graded according to the University assessment and grading policies.

Submission Deadlines

Assessment deadlines are strict, unless an application for special consideration is received (preferably in advance) accompanied by appropriate documentary evidence. Late submissions will be penalised at the rate of 20% of the full marks for the assessment per day or part thereof late.

Standards

The following general standards of achievement will be used to assess each of the assessment tasks with respect to the letter grades. 

Pass: Has a basic undestanding of the algorithms and concepts as discussed in class. Can  describe and reproduce definitions and fundamental algorithms. Can perform a basic research investigation in the area and present the results of that research in rudimentary written and oral forms.

Credit: As for Pass plus: Is able to apply the algorithmic techniques we have discussed to derive solutions to computational problems. Can develop, generalise and apply the concepts discussed in class to address basic theoretical and practical questions, and can effectively communicate these insights. Shows more than basic insights into the results of a research investgiation and is able to communicate those insights.

Distinction/High Distinction: As for Credit plus: Is able to generalise and synthesise knowledge to address more complex topics beyond the material discussed in class. Can critically evaluate the limits of the techniques and algorithms discussed.

Assessment Process

These assessment standards will be used to give a numeric mark out of 100 to each assessment submission during marking. The mark will correspond to a letter grade for that task according to the University guidelines. The final raw mark for the unit will be calculated by combining the marks for all assessment tasks according to the percentage weightings shown in the assessment summary.

We will look at your overall performance on all assessments when determining your final grade. A total raw mark of at least 50% and a mark of at least 50% on each of the assessment categories will be sufficient to pass the unit. Students who do not meet this cut-off will be examined on a case-by-case basis.

On occasion your raw mark for the unit may not be the same as the Standardised Numeric Grade (SNG) which you receive as the result. Under the Senate guidelines, raw marks may be scaled to ensure that there is a degree of comparability across the university, so that units with the same past performances of their students should achieve similar results.