[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive]
[an error occurred while processing this directive]
Monash University

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

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.

See also Unit timetable information

Unit Relationships


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


Kerri Morgan

Consultation hours: Tuesday 10-11am.

Guido Tack

Consultation hours: Tuesday 10-11am

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

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  
2 Computational Complexity Assignment 1 handed out
3 Constraint Modelling  
4 Matchings  
5 Constraint Programming  
6 Network Flows  
7 Linear and Mixed Integer Programming (LP/MIP)  
8 Network Flows Assignment 1 due 15 September 2015. Assignment 2 handed out
9 Approximation Algorithms  
10 Advanced Modelling  
11 SAT  
12 Research directions in combinatorial structures  
  SWOT VAC No formal assessment is undertaken in SWOT VAC. Assignment 2 due Week 14, 3 November 2015
  Examination period LINK to Assessment Policy: http://policy.monash.edu.au/policy-bank/

*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 - Graph algorithms 35% 15 September, 2015
Assignment 2 - Modelling with MiniZinc 35 3 November, 2015
Preparation Work for Labs 20% (2% each week) Tuesdays 11am (Weeks 2--11)
Weekly Quiz 10% (1% each week) Tuesday 2pm (Weeks 2--11)

Assessment Requirements

Assessment Policy

Assessment Tasks


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

  • Assessment task 1
    Assignment 1 - Graph algorithms
    In this assignment students will investigate how graph algorithms can be applied to solve combinatorial problems. They will implement dedicated algorithms for specific problems and analyse their performance.

    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.
    Criteria for assessment:
    1. The design and/or modification of algorithms and data structures to suit particular problem/task.
    2. The quality and performance of the algorithms and code. 
    3. The formal analysis of these algorithms.
    4. The quality of the written report including the quality of the evaluation and analysis.
    Due date:
    15 September, 2015
    This assessment relates to learning outcomes 1-4
  • Assessment task 2
    Assignment 2 - Modelling with MiniZinc
    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.
    Criteria for assessment:
    1. The quality of the models: correctness, efficiency, clarity and documentation.
    2. The quality of the test data: coverage.
    3. The quality of the written report including the quality of the evaluation and analysis of the differences in behaviour.
    Due date:
    3 November, 2015
    This assessment relates to learning outcomes 1-4
  • Assessment task 3
    Preparation Work for Labs
    Preparation work to be completed prior to lab class (Weeks 2--11) and handed to lecturer at the start of each lab class. 
    20% (2% each week)
    Criteria for assessment:

    1.  Choose and apply algorithms and data structures;
    2.  Design and implement modified algorithms  to suit particular problem structures;
    3.  Implement code to perform fundamental tasks including file I/O. 

    Due date:
    Tuesdays 11am (Weeks 2--11)
    This assessment relates to learning outcomes 1-4
  • Assessment task 4
    Weekly Quiz
    Weekly Quiz in Moodle (Weeks 2--11).
    10% (1% each week)
    Criteria for assessment:

    Correctly answer quiz questions in Moodle prior to the weekly Lecture.   (Multiple attempts can be made).

    Due date:
    Tuesday 2pm (Weeks 2--11)
    This assessment relates to learning outcomes 1-4

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)

Feedback to you

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

  • Informal feedback on progress in labs/tutes
  • Graded assignments with comments
  • Quiz results

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 electronic submission). 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


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

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.

[an error occurred while processing this directive]