Associate Professor David Dowe
Associate Professor
Phone: +61 3 990 55776
Fax: +61 3 990 55159
Associate Professor David Dowe
Associate Professor
Phone: +61 3 990 55776
Fax: +61 3 990 55159
Hi, and welcome to FIT3014 Analysis and design of algorithms. This 6-point unit is optional/core to many degrees. It is similar to its predecessor, CSE3305 (Formal Methods II) - and students are not permitted to do both CSE3305 and FIT3014, and students cannot count both subjects towards any degree. Students should make sure that they have obtained the relevant pre-requisite(s) before doing FIT3014. [An alternative name for the subject could be 'Formal Methods II'.] Turning up to all lectures and all tutes/pracs is encouraged, strongly recommended and in students' interests. At least tute/prac attendance will be recorded.
For on campus students, workload commitments are:
You will need to allocate up to 5 hours per week in some weeks, for use of a computer.
FIT3014 provides students with lectures, tutorials/pracs to facilitate your learning.
For information on timetabling for on-campus classes please refer to MUTTS, http://mutts.monash.edu.au/MUTTS/
On-campus students should register for tutorials/laboratories using the Allocate+ system: http://allocate.its.monash.edu.au/
| Week | Date* | Topic | Study guide | Key dates |
|---|---|---|---|---|
| 1 | 01/03/10 | Introduction - analysing algorithms and their complexity | ||
| 2 | 08/03/10 | Introduction to search | There is a Workbook ``study guide'' to accompany most of this subject | |
| 3 | 15/03/10 | Local search and intro' to (faster) brute force search | ||
| 4 | 22/03/10 | More on faster brute force search; intro' to probability and information | ||
| 5 | 29/03/10 | Probability and information | ||
| Mid semester break | ||||
| 6 | 12/04/10 | Randomness, complexity and coding theory overview | ||
| 7 | 19/04/10 | Random number generation and transforming distributions | ||
| 8 | 26/04/10 | Monte Carlo simulation, simulated annealing and evolutionary algorithms | ||
| 9 | 03/05/10 | Evolutionary Artificial Life (ALife) simulation, the Halting Problem, ?paradoxes? and the Church-Turing thesis | ||
| 10 | 10/05/10 | P, NP, NP-Completeness and the Cook-Levin theorem | ||
| 11 | 17/05/10 | Catch-up, revision | ||
| 12 | 24/05/10 | Catch-up, revision | ||
| 13 | 31/05/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.
The students seem happy with the content of the unit. Some have previously suggested that it include a little bit more on game theory, which would actually push it in a more mathematical direction. In 2nd sem. 2008, I added a new paradox of my own (independently re-visiting some work in the mid-1960s of some prominent philosophers) to the syllabus. The MonQuest evaluations throughout 2008 and 2009 were all very favourable. About the only thing that the students seem to want changed is the name of the unit.
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
You will need access to:
Study resources we will provide for your study are:
To pass a unit which includes an examination as part of the assessment a student must obtain:
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 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.
Weighting:
60%
Length:
3 hours
Type (open/closed book):
Closed book
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
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.
Students can expect assignments to be returned within two weeks of the submission date or after receipt, whichever is later.
Please visit the following URL: http://www.infotech.monash.edu.au/units/appendix.html for further information about: