FIT2009 Data structures and algorithms - Semester 2, 2013

Algorithm analysis. Application and implementation of some common data structures: stacks, queues, lists, priority queues, tables, sets and collections. Data representations including: arrays, linked lists, heaps, trees (including balanced trees) and hashing. Design of application programs making use of common data structures. Design and implementation of new data structures. Study of advanced algorithms in areas such as: graph theory, pattern searching and data compression. Access to the University's computer systems through an Internet service provider is compulsory for off-campus students.

Mode of Delivery

• Gippsland (Day)
• Gippsland (Off-campus)
• South Africa (Day)

Contact Hours

2 hrs lectures/wk, 2 hrs laboratories/wk

Workload requirements

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

For on-campus students:
Lectures: 2 hours per week
Tutorials/Lab Sessions: 2 hours per week per tutorial
and up to an additional 8 hours in some weeks for completing lab and project work, private study and revision.

Off-campus students generally do not attend lecture and tutorial sessions, however, you should plan to spend equivalent time working through the relevant resources and participating in discussion groups each week.

Unit Relationships

Prohibitions

FIT2004, FIT2071, FIT9015, GCO2817, GCO3512, GCO9807

Prerequisites

FIT1007 or GCO1812 or GCO9808 or FIT2034

Chief Examiner

Campus Lecturer

Academic Overview

Learning Outcomes

• the ability to analyse simple algorithms to work out an order of magnitude estimate of running time and space;
• familiarity with some of the most common data structures: stacks, queues, lists, priority queues, tables, sets, collections;
• the ability to implement these data structures using various common data representations: arrays, linked lists, heaps, trees (including balanced trees), hashing;
• the ability to evaluate which implementation would be most appropriate for a given data structure and application;
• the ability to apply the same principles used in implementing the common data structures to implement other data structures;
• ability to design and implement new data structures;
• an understanding of some more advanced algorithms in areas such as: graph theory (shortest path etc), pattern searching, data compression (precise selection of advanced algorithms will vary from year to year);
• the ability to design new algorithms to solve new problems;
• an enjoyment of programming as an intellectual exercise;
• an appreciation of the elegance of certain data structures and algorithms as a form of art;
• an interest in understanding how data structures and algorithms are implemented rather than merely using other peoples implementations (and consequently a preference for open source software.

Unit Schedule

*Unit Schedule details will be maintained and communicated to you via your learning system.

Assessment Summary

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

Teaching Approach

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:

  Students will be required to perform a number of tasks involving both analytical and practical (computer programming) skills from the syllabus covered in Study Guides 1 - 4.

  Weighting:

  20%

  Criteria for assessment:

  The assignment requires individual submission via Moodle. The specification and marking criteria will be released in Moodle four teaching weeks in advance of the due date. Solutions will be released after the cut-off date, which is one week after the due date.

  Broad criterial for assessment:

  1. How well underlying principles and theories are demonstrated in the student's answer
  2. The degree to which programs meet the problem specification
  3. The quality of the student's argument

  Due date:

  9 September 2013

• Assessment task 2

  Title:

  Assignment 2

  Description:

  Students will be required to perform a number of tasks involving both analytical and practical (computer programming) skills from the syllabus covered in Study Guides 5 - 8.

  Weighting:

  20%

  Criteria for assessment:

  The assignment requires individual submission via Moodle. The specification and marking criteria will be released in Moodle four teaching weeks in advance of the due date. Solutions will be released after the cut-off date, which is one week after the due date.

  Broad criterial for assessment:

  1. How well underlying principles and theories are demonstrated in the student's answer
  2. The degree to which programs meet the problem specification
  3. The quality of the student's argument

  Due date:

  14 October 2013

Examinations

• Examination 1

  Weighting:

  60%

  Length:

  3 hours

  Type (open/closed book):

  Closed book

  Electronic devices allowed in the exam:

  None

Learning resources

Feedback to you

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

Extensions and penalties

Returning assignments

Resubmission of assignments

• Late penalties will be enforced if an assignment is submitted after the due date.
• Students may resubmit an assignment any time before the cut-off date, which is usually a week after the due date.
• No assignment can be submitted after the cut-off date.

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 SE JDK version 1.5 (also known as version 5) or later. This software is included in the GSIT Unit Software CD-ROM, which will be sent to all students. This software may also be downloaded free from http://java.sun.com

• Prescribed texts are available from Monash University Bookshops. Availability from other suppliers cannot be assured. The Bookshop orders texts in specifically for this unit. You are advised to purchase your textbook early.

• Study Guides will be provided for students.

Prescribed text(s)

Mark Allen Weiss. (2010). Data Structures & Problem Solving using Java. (4th) Addison Wesley (ISBN: 0-321-54622-9).

Recommended text(s)

Ford, W. H. and Topp, W. R. (2005). Data Structures with Java. () Pearson Education International (ISBN: 0-131-29337-0).

Lafore, R. (2002). Data Structures & Algorithms in Java. (2nd) SAMS (ISBN: 0-672-32453-9).

Gray, S. (2007). Data Structures in Java. () Pearson Education Inc. (ISBN: 0-321-39279-5).

Other Information

Policies

Graduate Attributes Policy

Student services

Monash University Library

Disability Liaison Unit

Your feedback to Us

Previous Student Evaluations of this Unit

This unit has been consistently receiving very high satisfaction ratings in formal unit evaluations by the students. No significant weakness was highlighted in the student feedback.

Other

Study resources we will provide for your study are:

• A Unit Book containing 11 Study Guides at Moodle.
• This Unit Information, which outlines the administrative information for the unit.
• A CD-ROM (possibly sent at the start of the year if you were enrolled in a first semester unit that required it) with software required for all units (this includes all the software required to complete this unit).
• A unit web page at Moodle where lecture slides, weekly tutorial requirements, assignment specifications, sample solutions and supplementary material will be posted.
• Discussion forums at Moodle.