Skip to the content | Change text size
PDF unit guide

FIT4010 Advanced topics in algorithms and discrete structures - Semester 2, 2014

Algorithms are the most fundamental area for all aspects of computer science and software engineering. Discrete structures, such as those treated in graph theory, set theory, combinatorics and symbolic logic form the mathematical underpinning of the study of algorithms. As well-designed algorithms and data structures are essential for the good performance of an information system, an in-depth understanding of the theoretical properties of algorithms is essential for any computer scientist. As importantly, the theoretical investigation of algorithms leads to a deeper understanding of problem structures and classes of problems and the knowledge of a large variety of algorithm types enables the designer to approach a new problem from different angles. Topics for this unit include: Computability and Complexity Automata Theory Advanced Analysis and Design of Algorithms Parallel and Distributed Algorithms Numerical Algorithms Cryptographic algorithms Spatial/geometric algorithms

Mode of Delivery

Clayton (Day)

Workload Requirements

Minimum total expected workload equals 12 hours per week comprising:

(a.) Contact hours for on-campus students:

  • Two hours of lectures
  • One 2-hour laboratory or tutorial

(b.) Additional requirements (all students):

  • A minimum of 2-3 hours of personal study per one hour of contact time in order to satisfy the reading and assignment expectations.

Unit Relationships

Prerequisites

Completion of the Bachelor of Computer Science or equivalent to the entry requirements for the Honours program. Students must also have enrolment approval from the Honours Coordinator.

Chief Examiner

Campus Lecturer

Clayton

Kerri Morgan

Consultation hours: TBD

Guido Tack

Consultation hours: TBD

Your feedback to Us

Monash is committed to excellence in education and regularly seeks feedback from students, employers and staff. One of the key formal ways students have to provide feedback is through the Student Evaluation of Teaching and Units (SETU) survey. The University’s student evaluation policy requires that every unit is evaluated each year. Students are strongly encouraged to complete the surveys. The feedback is anonymous and provides the Faculty with evidence of aspects that students are satisfied and areas for improvement.

For more information on Monash’s educational strategy, see:

www.monash.edu.au/about/monash-directions/ and on student evaluations, see: www.policy.monash.edu/policy-bank/academic/education/quality/student-evaluation-policy.html

Previous Student Evaluations of this Unit

The changes made last year worked well and the unit received a high student evaluation.  The teaching material will be updated to reflect advances in the field when necessary.

If you wish to view how previous students rated this unit, please go to
https://emuapps.monash.edu.au/unitevaluations/index.jsp

Academic Overview

Learning Outcomes

On successful completion of this unit, students should be able to:
  • critically analyse and assess algorithms for use in the chosen specialisation area;
  • be able to formally analyse algorithms in this specialisation area;
  • choose and apply algorithms and data structures in the specialisation area;
  • design and implement modified algorithms in the chosen area to suit particular problem structures.

Unit Schedule

Week Activities Assessment
0   No formal assessment or activities are undertaken in week 0
1 Introduction, computational complexity  
2 Constrained optimisation and modelling with MiniZinc Assignment 1 handed out
3 Constraint Programming (CP) and Propagation  
4 Advanced constraint modelling techniques  
5 Graph concepts  
6 Matchings and flows  
7 Matchings and flows  
8 Boolean satisfiability Assignment 1 due 15 September 2014. Assignment 2 handed out
9 Linear and Mixed Integer Programming (LP/MIP)  
10 Approximation algorithms  
11 Planarity separators and treewidth  
12 Research directions in combinatorial structures  
  SWOT VAC No formal assessment is undertaken in SWOT VAC. Assignment 2 due Week 14, 3 November 2014
  Examination period LINK to Assessment Policy: http://policy.monash.edu.au/policy-bank/
academic/education/assessment/
assessment-in-coursework-policy.html

*Unit Schedule details will be maintained and communicated to you via your learning system.

Teaching Approach

Lecture and tutorials or problem classes
This teaching and learning approach provides facilitated learning, practical exploration and peer learning.

Assessment Summary

Assignment and Examination, relative weight depending on topic composition. When no exam is given students will be expected to demonstrate their knowledge by solving practical problems and maybe required to give an oral report.

Assessment Task Value Due Date
Assignment 1 - Modelling with MiniZinc 50% 15 September 2014
Assignment 2 - Graph and flow algorithms in Combinatorial Optimisation 50% 3 November 2014

Assessment Requirements

Assessment Policy

Assessment Tasks

Participation

Students are expected to attend lectures and tutorials. However this is not mandatory.

  • Assessment task 1
    Title:
    Assignment 1 - Modelling with MiniZinc
    Description:
    In this assignment students will model a constrained optimization problem using MiniZinc. They will be required to create models that work with a variety of different underlying solving techniques: MIP, CP and SAT.

    They will need to construct test data and then evaluate their models with this data.

    Produce a written report that describes their models, test data and the results of the evaluation. The report should also try and explain reasons for differences in behaviour of these models.
    Weighting:
    50%
    Criteria for assessment:

    The quality of the models: correctness, efficiency, clarity and documentation.

    The quality of the test data: coverage.

    The quality of the written report including the quality of the evaluation and analysis of the differences in behaviour.

    Due date:
    15 September 2014
  • Assessment task 2
    Title:
    Assignment 2 - Graph and flow algorithms in Combinatorial Optimisation
    Description:
    In this assignment students will investigate how graph and flow algorithms can be applied to solve combinatorial problems. They will implement dedicated algorithms for specific problems and compare their performance with MiniZinc models solved by off-the-shelf tools such as SAT, CP, and MIP.

    Students will need to show that their algorithms work as desired on a number of different problem instances (of increasing difficulty).

    Students will need to produce a written report describing their algorithms and their evaluation.
    Weighting:
    50%
    Criteria for assessment:

    The quality of the algorithms: their correctness and performance, and their integration in an existing solver.

    The quality of the written report including the quality of the evaluation and analysis.

    Due date:
    3 November 2014

Learning resources

Reading list

There are several recommended books for this subject:

  • Introduction to Mathematical Programming. W. L.  Winston. Duxbury Press, 1995.
  • Introduction to Operations Research. F.S. Hillier and G.J. Lieberman. McGraw-Hill, 8th Ed, 2005.
  • Constraint Programming - An Introduction. K. Marriott and P. Stuckey. MIT Press, 1998.
  • Numerical Optimization. J. Nocedal & S. Wright. Springer, 2006.
  • Computers and Intractability. M. Garey & D.S. Johnson. Macmillan Higher Education, 1979.

In addition to this, selected research papers will be referenced throughout the unit.
The lecture material will be loosely based on this material and will be available through Moodle.

Monash Library Unit Reading List (if applicable to the unit)
http://readinglists.lib.monash.edu/index.html

Faculty of Information Technology Style Guide

Feedback to you

Examination/other end-of-semester assessment feedback may take the form of feedback classes, provision of sample answers or other group feedback after official results have been published. Please check with your lecturer on the feedback provided and take advantage of this prior to requesting individual consultations with staff. If your unit has an examination, you may request to view your examination script booklet, see http://intranet.monash.edu.au/infotech/resources/students/procedures/request-to-view-exam-scripts.html

Types of feedback you can expect to receive in this unit are:

  • Informal feedback on progress in labs/tutes
  • Graded assignments with comments
  • Solutions to tutes, labs and assignments

Extensions and penalties

Returning assignments

Resubmission of assignments

Resubmission is not allowed unless special consideration applies in which case the course leaders may allow the student to resubmit an assignment.

Assignment submission

It is a University requirement (http://www.policy.monash.edu/policy-bank/academic/education/conduct/student-academic-integrity-managing-plagiarism-collusion-procedures.html) for students to submit an assignment coversheet for each assessment item. Faculty Assignment coversheets can be found at http://www.infotech.monash.edu.au/resources/student/forms/. Please check with your Lecturer on the submission method for your assignment coversheet (e.g. attach a file to the online assignment submission, hand-in a hard copy, or use an online quiz). Please note that it is your responsibility to retain copies of your assessments.

Online submission

If Electronic Submission has been approved for your unit, please submit your work via the learning system for this unit, which you can access via links in the my.monash portal.

Required Resources

Please check with your lecturer before purchasing any Required Resources. Limited copies of prescribed texts are available for you to borrow in the library, and prescribed software is available in student labs.

You will be using the MiniZinc modelling language.

This is available from: http://www.minizinc.org/

Other Information

Policies

Monash has educational policies, procedures and guidelines, which are designed to ensure that staff and students are aware of the University’s academic standards, and to provide advice on how they might uphold them. You can find Monash’s Education Policies at: www.policy.monash.edu.au/policy-bank/academic/education/index.html

Key educational policies include:

Faculty resources and policies

Important student resources including Faculty policies are located at http://intranet.monash.edu.au/infotech/resources/students/

Graduate Attributes Policy

Student Charter

Student services

Monash University Library

Disability Liaison Unit

Students who have a disability or medical condition are welcome to contact the Disability Liaison Unit to discuss academic support services. Disability Liaison Officers (DLOs) visit all Victorian campuses on a regular basis.