FIT2004 Algorithms and data structures - Semester 1, 2013

This unit introduces students to problem solving concepts and techniques fundamental to the science of programming. In doing this it covers problem specification, algorithmic design, analysis and implementation. Detailed topics include analysis of best, average and worst-case time and space complexity; introduction to numerical algorithms; recursion; advanced data structures such as heaps and B-trees; hashing; sorting algorithms; searching algorithms; graph algorithms; and numerical computing.

Mode of Delivery

• Clayton (Day)
• Sunway (Day)

Contact Hours

2 hrs lectures/wk, 3 hr laboratory/fortnight, 1 hr tutorial/fortnight

Workload requirements

Students will be expected to spend a total of 12 hours per week during semester on this unit as follows:

• Lectures: 2 hours per week
• Tutorials/Lab Sessions: 4 hours fortnightly (1 hour tutorial, 3 hours lab) 
• Reading: 4 hours per week
• Lab Preparation: 4 hours per week.

Unit Relationships

Prohibitions

CSE2304, FIT2009

Prerequisites

One of FIT1008, FIT1015 or CSE1303 and 6 points of Level 1 mathematics.

Chief Examiner

Campus Lecturer

Academic Overview

Learning Outcomes

At the completion of this unit students will have:

• understanding of a formal specification;
• ability to create a formal specification for an informal problem;
• knowledge and understanding of algorithmic properties such as correctness, termination and complexity;
• ability to, given a non-trivial algorithm, formally prove certain properties, such as correctness and termination;
• ability, given a non-trivial algorithm, to determine its best, average and worst-case, time and space-complexity;
• knowledge and understanding of reasonably complex data structures such as minimum spanning trees, and Directed and Undirected, Weighted and Unweighted Graphs;
• ability to design and implement new non-trivial algorithms using complex data structures;
• knowledge of and ability to use algorithmic paradigms such as divide and conquer, greedy, dynamic programming and so on;
• ability to identify these paradigms in diverse algorithms;
• knowledge and understanding of the issues involved in implementing a non-trivial algorithm efficiently.

Developed attitudes that enable them to:

• carefully design and/or analyse the algorithms they are using in order to verify important properties such as correctness, termination, and complexity;
• identify the key features of a brief informal problem description and abstract the underlying formal problem.

Developed the skills to:

• create their own data structures.
• create a new algorithm to solve a new problem.
• make a formal argument about desirable properties of the solution.
• adapt an existing algorithm and/or data-structure where that is possible and appropriate.
• implement a non-trivial algorithm efficiently.

Demonstrated the communication skills necessary to:

• make a formal argument that an algorithm and/or data-structure has a given property, such as correctness, termination or complexity.

Unit Schedule

Week	Activities	Assessment
0		No formal assessment or activities are undertaken in week 0
1	Overview and Revision of Required Concepts
2	Algorithm Analysis
3	Trees I
4	Trees II	Assignment 1 due
5	Trees III & Amortised Analysis
6	Suffi Arrays, Tries, & Disjoint Sets	Assignment 2 due
7	Heaps, Graphs and Graph Search
8	Path Problems	Assignment 3 due
9	Flow Problems and Compleity
10	Algorithm Design I	Assignment 4 due
11	Algorithm Design II
12	Selected Topics	Assignment 5 due
	SWOT VAC	No formal assessment is undertaken in SWOT VAC
	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.

Assessment Summary

Examination (3 hours): 70%; In-semester assessment: 30%

Assessment Task	Value	Due Date
Assignment 1	6 %	Week 4
Assignment 2	6 %	Week 6
Assignment 3	6 %	Week 8
Assignment 4	6 %	Week 10
Assignment 5	6 %	Week 12
Examination 1	70%	To be advised

Teaching Approach

Lecture and tutorials or problem classes

Assessment Requirements

Assessment Policy

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

Academic Integrity - Please see the Demystifying Citing and Referencing tutorial at http://lib.monash.edu/tutorials/citing/

Assessment Tasks

Participation

• Assessment task 1

  Title:

  Assignment 1

  Description:

  Practical problems arising from the material covered in lectures and tutorials.

  Weighting:

  6 %

  Criteria for assessment:

  • Demonstrate code where applicable
  • Explain your solutions

  Due date:

  Week 4

• Assessment task 2

  Title:

  Assignment 2

  Description:

  Practical problems arising from the material covered in lectures and tutorials.

  Weighting:

  6 %

  Criteria for assessment:

  • Demonstrate code where applicable
  • Explain your solutions

  Due date:

  Week 6

• Assessment task 3

  Title:

  Assignment 3

  Description:

  Practical problems arising from the material covered in lectures and tutorials.

  Weighting:

  6 %

  Criteria for assessment:

  • Demonstrate code where applicable
  • Explain your solutions

  Due date:

  Week 8

• Assessment task 4

  Title:

  Assignment 4

  Description:

  Practical problems arising from the material covered in lectures and tutorials.

  Weighting:

  6 %

  Criteria for assessment:

  • Demonstrate code where applicable
  • Explain your solutions

  Due date:

  Week 10

• Assessment task 5

  Title:

  Assignment 5

  Description:

  Practical problems arising from the material covered in lectures and tutorials.

  Weighting:

  6 %

  Criteria for assessment:

  • Demonstrate code where applicable
  • Explain your solutions

  Due date:

  Week 12

Examinations

• Examination 1

  Weighting:

  70%

  Length:

  3 hours

  Type (open/closed book):

  Closed book

  Electronic devices allowed in the exam:

  None

Learning resources

Reading list

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 2nd Edition, EHT MIT Press & McGraw Hill

Duane Bailey. Java Structures: Data Structures in Java for the Principled Programmer. International Edition, May 1999, Mc Graw Hill. This book is available for free online at http://www.cs.williams.edu/~bailey/JavaStructures/Welcome.html

Feedback to you

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

Extensions and penalties

Returning assignments

Assignment submission

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

Java (latest version) installed in the labs, you can download a free copy from Sun Microsystems.

Prescribed text(s)

Mark Allen Weiss. (2012). Data Structures and Algorithm Analysis in Java. (3rd Edition) Pearson (ISBN: 9780132576277).

Recommended text(s)

Michael T. Goodrich and Roberto Tamassia. (2010). Data Structures and Algorithms in Java. (5th Edition) Wiley (ISBN: 978-0-470-38326-1).

Examination material or equipment

Closed book. No calculators.

Other Information

Policies

Graduate Attributes Policy

Student services

Monash University Library

Disability Liaison Unit

Your feedback to Us

Previous Student Evaluations of this Unit

Student feedback has informed a substantive revision to the unit that includes reorienting the content to be supported by a single principal text book and reorganisation to improve the incremental progression of unit content.