FIT4010 Advanced topics in algorithms and discrete structures - Semester 2, 2015 (Information Technology)

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

Dr Kerri Morgan

Campus Lecturer

Clayton

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
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
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/ 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 - 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

Faculty Policy - Unit Assessment Hurdles (http://intranet.monash.edu.au/infotech/resources/staff/edgov/policies/assessment-examinations/assessment-hurdles.html)

Academic Integrity - Please see resources and tutorials at http://www.monash.edu/library/skills/resources/tutorials/academic-integrity/

Assessment Tasks

Participation

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

Assessment task 1
Title:

Assignment 1 - Graph algorithms

Description:

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.

Weighting:

35%

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

Remarks:

This assessment relates to learning outcomes 1-4

Assessment task 2
Title:

Assignment 2 - 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:

35

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

Remarks:

This assessment relates to learning outcomes 1-4

Assessment task 3

Title:

Preparation Work for Labs

Description:

Preparation work to be completed prior to lab class (Weeks 2--11) and handed to lecturer at the start of each lab class.

Weighting:

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)

Remarks:

This assessment relates to learning outcomes 1-4

Assessment task 4

Title:

Weekly Quiz

Description:

Weekly Quiz in Moodle (Weeks 2--11).

Weighting:

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)

Remarks:

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)
http://readinglists.lib.monash.edu/index.html

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

Submission must be made by the due date otherwise penalties will be enforced.

You must negotiate any extensions formally with your campus unit leader via the in-semester special consideration process: http://www.monash.edu.au/exams/special-consideration.html

Returning assignments

Students can expect assignments to be returned within two weeks of the submission date or after receipt, whichever is later.

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

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

Faculty resources and policies

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

Website: http://www.monash.edu/equity-diversity/disability/index.html
Telephone: 03 9905 5704 to book an appointment with a DLO; or contact the Student Advisor, Student Commuity Services at 03 55146018 at Malaysia
Email: dlu@monash.edu
Drop In: Equity and Diversity Centre, Level 1, Building 55, Clayton Campus, or Student Community Services Department, Level 2, Building 2, Monash University, Malaysia Campus

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