FIT3014 Analysis and design of algorithms - Semester 2, 2010

Clayton

Malaysia

Prerequisites

FIT2004 or CSE2304

Prohibitions

CSE3305

Teaching approach

FIT3014 provides students with lectures, tutorials/pracs to facilitate your learning.

Timetable information

For information on timetabling for on-campus classes please refer to MUTTS, http://mutts.monash.edu.au/MUTTS/

Tutorial allocation

On-campus students should register for tutorials/laboratories using the Allocate+ system: http://allocate.its.monash.edu.au/

Unit Schedule

Week	Date*	Topic	Study guide	Key dates
1	19/07/10	Introduction - analysing algorithms and their complexity
2	26/07/10	Introduction to search	There is a Workbook ``study guide'' to accompany most of this subject
3	02/08/10	Local search and intro' to (faster) brute force search
4	09/08/10	More on faster brute force search; intro' to probability and information
5	16/08/10	Probability and information		20 Aug: Assignment 1 due
6	23/08/10	Randomness, complexity and coding theory overview
7	30/08/10	Random number generation and transforming distributions
8	06/09/10	Monte Carlo simulation, simulated annealing and evolutionary algorithms
9	13/09/10	the Halting Problem, ?paradoxes? and the Church-Turing thesis		17 Sept: Assignment 2 due
10	20/09/10	P, NP, NP-Completeness and the Cook-Levin theorem
Mid semester break
11	04/10/10	Catch-up, revision
12	11/10/10	Catch-up, revision		15 Oct: Assignment 3 due
13	18/10/10	Revision

*Please note that these dates may only apply to Australian campuses of Monash University. Off-shore students need to check the dates with their unit leader.

Prescribed text(s) and readings

Recommended text(s) and readings

Jon Kleinberg and Eva Tardos (2006).  Algorithm design.  Addison Wesley Pearson.

Zbigniew Michalewicz, David B. Fogel (2004). How to Solve It: Modern Heuristics. Springer.

Supplementary Reading

Sheldon Ross (2002). Simulation, 3rd edition. Academic Press.

Vijay V. Vazirani (2001). Approximation Algorithms. Springer.

Thomas M. Cover, Joy A. Thomas (1991). Elements of Information Theory. Wiley-Interscience.

Christopher S. Wallace (2005).  Statistical and Inductive Inference by Minimum Message Length. Springer.

Sara Baase, Allen Van Gelder (1999). Computer Algorithms: Introduction to Design and Analysis, 3rd Edition. Addison Wesley.

Michael Sipser (2006). Introduction to the theory of computation, 2nd edition. Thomson.

 D. L. Dowe (2008). ``Foreword re C. S. Wallace'', Computer Journal, Vol. 51, No. 5 [Christopher Stewart WALLACE (1933-2004) memorial special issue {http://comjnl.oxfordjournals.org/content/vol51/issue5}], pp523-560.

There is a Workbook ``study guide'' to accompany most of this subject

Required software and/or hardware

You will need access to:

• Linux software
• C under Linux, C++ under Linux
• Java

On-campus students may use this software which is installed in the computing labs. Information about computer use for students is available from the ITS Student Resource Guide in the Monash University Handbook.

Equipment and consumables required or provided

Students studying off-campus are required to have the minimum system configuration specified by the Faculty as a condition of accepting admission, and regular Internet access.On-campus students, and those studying at supported study locations may use the facilities available in the computing labs.Information about computer use for students is available from the ITS Student Resource Guide in the Monash University Handbook. You will need to allocate up to approximately 8 or so hours per week for use of a computer, including time for newsgroups/discussion groups.

Study resources

Study resources we will provide for your study are:

• Weekly (detailed) lecture notes outlining the learning objectives, discussion of the content, required readings and exercises;
• (A workbook of) weekly (or perhaps occasionally fortnightly) tutorial or laboratory tasks and exercises - with sample solutions to be provided one to two weeks later;
• Assignment specifications;
• This Unit Guide outlining the administrative information for the unit;
• The unit web site on Blackboard (or MUSO), where resources outlined above will be made available.
• Solutions to assignments and a sample exam will be discussed in class, so please attend and be prepared and attentive with your questions.  But, printed worked solutions will most probably not be circulated.

Overview

Examination (3 hours): 60%; In-semester assessment: 40%

Faculty assessment policy

To pass a unit which includes an examination as part of the assessment a student must obtain:

• 40% or more in the unit's examination, and
• 40% or more in the unit's total non-examination assessment, and
• an overall unit mark of 50% or more.

If a student does not achieve 40% or more in the unit examination or the unit non-examination total assessment, and the total mark for the unit is greater than 50% then a mark of no greater than 49-N will be recorded for the unit.

Students should also be familiar with the consequences of plagiarism, for the students who copy and also to any (other) students who allow their work to be copied.  The best possible outcome for students in such an event is zero marks for the relevant question(s) and an official letter sent to them and kept on their file.  But students should also understand that is the best possible outcome, and other possible outcomes include zero marks for the entire assignment or even zero marks for the entire subject.  As a general  rule, penalties tend to be more severe for repeat offenders.  Please understand, be warned and take care.

Assignment tasks

Assignment coversheets

Assignment coversheets are available via "Student Forms" on the Faculty website: http://www.infotech.monash.edu.au/resources/student/forms/
You MUST submit a completed coversheet with all assignments, ensuring that the plagiarism declaration section is signed.

Assignment submission and return procedures, and assessment criteria will be specified with each assignment.

Assignment submission and preparation requirements will be detailed in each assignment specification. 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.infotech.monash.edu.au/resources/student/equity/special-consideration.html.

• Assignment task 1

  Title:

  Assignment 1

  Description:

  Roughly, we will assess the lecture (and workbook) material of up to approx. 1 week before the assignment deadline.  Assessed material will include matters like (e.g.) Order notation (O, Omega, Theta, o), Conjunctive Normal Form (CNF) and satisfiability (SAT), elementary computational complexity, search trees and their sizes, Bertrand's paradox and implementations of optimisations for problems such as (e.g.) Travelling Salesman/Salesperson Problem (TSP), Minimum Spanning Tree (MST) and shortest path.
  
  Tasks in the assignment include writing algorithms, writing proofs, demonstrating methods on examples, and explaining concepts and ideas.

  Weighting:

  15%

  Criteria for assessment:

  For algorithms: correctness, efficiency, effectiveness, elegance, clarity.

  For proofs: correctness, elegance, clarity.

  For demonstrations of methods: correctness, efficiency, accuracy, clarity.

  For explanations: correctness, precision, clarity.

  Due date:

  To be advised in assignment specification, approximately Week 6

• Assignment task 2

  Title:

  Assignment 2

  Description:

  Roughly, we will assess the lecture (and workbook) material of up to approx. 1 week before the assignment deadline.  Assessed material will include matters like (e.g.) elementary probability, elementary information theory, binary symmetrical (communication) channels (and bandwidth), conditional entropy, mutual entropy, (pseudo-)random number generation, inverse transform and rejection methods, random/stochastic search strategies (simulated annealing, genetic algorithms), computational complexity, Turing machines, algorithmic information theory (Kolmogorov complexity) and the Halting problem (Entscheidungsproblem), real-world applications.
  
  Tasks in the assignment include writing algorithms, writing proofs, demonstrating methods on examples, and explaining concepts and ideas.

  Weighting:

  15%

  Criteria for assessment:

  For algorithms: correctness, efficiency, effectiveness, elegance, clarity.

  For proofs: correctness, elegance, clarity.

  For demonstrations of methods: correctness, efficiency, accuracy, clarity.

  For explanations: correctness, precision, clarity.

  Due date:

  To be advised in assignment specification, approximately Week 10

• Assignment task 3

  Title:

  Assignment 3 - Assessed Practical (or Practical Assignment)

  Description:

  This is intended to be a programming exercise implementing various pieces of theory, etc. from earlier in semester.

  Weighting:

  10%

  Criteria for assessment:

  For programs: correctness, efficiency, effectiveness, elegance, clarity, verifiability, adherence to good software engineering practices.

  For results of programs:  correctness, accuracy, clarity, verifiability.

  For analysis and discussion of results of programs:  correctness, precision, clarity, insight.

  At least part of this assessment will be the attendance record kept at tutes and labs.

  Due date:

  Late in semester, probably the tute/lab of week 12; to be advised - and also to be discussed in lectures and tutes/pracs in the weeks leading up to this Practical Assignment

  Remarks:

  This will most probably be assessed in one of your tute/lab sessions.  You should have done the necessary work beforehand.  Details will quite probably be discussed in lectures and tutes/pracs in the weeks leading up to this Practical Assignment, so pay attention.

Examination

• Weighting:

  60%

  Length:

  3 hours

  Type (open/closed book):

  Closed book

  Electronic devices allowed in the exam:

  None

Due dates and extensions

Please make every effort to submit work by the due dates. It is your responsibility to structure your study program around assignment deadlines, family, work and other commitments. Factors such as normal work pressures, vacations, etc. are not regarded as appropriate reasons for granting extensions. Students are advised to NOT assume that granting of an extension is a matter of course.

Students requesting an extension for any assessment during semester (eg. Assignments, tests or presentations) are required to submit a Special Consideration application form (in-semester exam/assessment task), along with original copies of supporting documentation, directly to their lecturer within two working days before the assessment submission deadline. Lecturers will provide specific outcomes directly to students via email within 2 working days. The lecturer reserves the right to refuse late applications.

A copy of the email or other written communication of an extension must be attached to the assignment submission.

Refer to the Faculty Special consideration webpage or further details and to access application forms: http://www.infotech.monash.edu.au/resources/student/equity/special-consideration.html

Late assignment

Assignments received after the due date without adequate medical or other reason will be subject to a penalty of up to 5% per day, including weekends. An assignment is deemed late if any of the submitted versions (recall ``Assessment details'', ``Assignment submission'') is late.  Assignments received later than one week (seven days) after the due date will not normally be accepted. In some cases, this period may be shorter if there is a need to release sample solutions or discuss solutions in class.

Where multiple versions of an assignment are to be submitted (e.g., soft electronic copy on MUSO/Blackboard and/or Damocles, and hard copy to the General Office), versions must be identical and the time of submission will be deemed to be when the final version is submitted and received.  If versions are not identical (such as in the case where at least one version is not submitted at all), there is a distinct possibility of 0 marks being awarded.

This policy will often be strictly adhered to because comments or guidance will be given on assignments as they are returned, and sample solutions may also be published and distributed - after assignment marking or with the returned assignment.

Return dates

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

Feedback

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

Informal feedback on progress in labs/tutes

Graded assignments with comments