Skip to the content | Change text size
PDF unit guide

FIT2009 Data structures and algorithms - Semester 2, 2012

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

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

Gippsland

Manzur Murshed

South Africa

Gregori Gregoriou

Academic Overview

Outcomes

At the completion of this unit students will have -
  • 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.

Graduate Attributes

Monash prepares its graduates to be:
  1. responsible and effective global citizens who:
    1. engage in an internationalised world
    2. exhibit cross-cultural competence
    3. demonstrate ethical values
  2. critical and creative scholars who:
    1. produce innovative solutions to problems
    2. apply research skills to a range of challenges
    3. communicate perceptively and effectively

Assessment Summary

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

Assessment Task Value Due Date
Assignment 1 20% 3 September 2012
Assignment 2 20% 8 October 2012
Examination 1 60% To be advised

Teaching Approach

Lecture and tutorials or problem classes
This teaching and learning approach provides facilitated learning, practical exploration and peer learning.

Feedback

Our 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
  • Solutions to tutes, labs and assignments

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 SETU, Student Evaluation of Teacher and Unit. 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, and on student evaluations, see:
http://www.monash.edu.au/about/monash-directions/directions.html
http://www.policy.monash.edu/policy-bank/academic/education/quality/student-evaluation-policy.html

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.

If you wish to view how previous students rated this unit, please go to
https://emuapps.monash.edu.au/unitevaluations/index.jsp

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.

  • 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)

Limited copies of prescribed texts are available for you to borrow in the library.

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).

Unit Schedule

Week Activities Assessment
0   No formal assessment or activities are undertaken in week 0
1 Generic Data Structures (Study Guide 1)  
2 Algorithm Analysis (Study Guide 2)  
3 Developing Algorithms (Study Guide 3)  
4 Sorting Algorithms (Study Guide 4)  
5 Lists (Study Guide 5)  
6 Stacks and Queues (Study Guide 6)  
7 Graphs and Trees (Study Guide 7) Assignment 1 due 3 September 2012
8 Binary Search Trees (Study Guide 8)  
9 Hashing (Study Guide 9)  
10 Heaps (Study Guide 10)  
11 Some Applications of Data Structures (Study Guide 11) Assignment 2 due 8 October 2012
12 Revision  
  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 MUSO (Blackboard or Moodle) learning system.

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 MUSO. The specification and marking criteria will be released in MUSO 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:
    3 September 2012
  • 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 MUSO. The specification and marking criteria will be released in MUSO 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:
    8 October 2012

Examinations

  • Examination 1
    Weighting:
    60%
    Length:
    3 hours
    Type (open/closed book):
    Closed book
    Electronic devices allowed in the exam:
    None

Assignment submission

It is a University requirement (http://www.policy.monash.edu/policy-bank/academic/education/conduct/plagiarism-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 online quiz).

Online submission

If Electronic Submission has been approved for your unit, please submit your work via the VLE site for this unit, which you can access via links in the my.monash portal.

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.

Other Information

Policies

Student services

The University provides many different kinds of support services for you. Contact your tutor if you need advice and see the range of services available at www.monash.edu.au/students. For Sunway see http://www.monash.edu.my/Student-services, and for South Africa see http://www.monash.ac.za/current/

The Monash University Library provides a range of services and resources that enable you to save time and be more effective in your learning and research. Go to http://www.lib.monash.edu.au or the library tab in my.monash portal for more information. At Sunway, visit the Library and Learning Commons at http://www.lib.monash.edu.my/. At South Africa visit http://www.lib.monash.ac.za/.

Academic support services may be available for students who have a disability or medical condition. Registration with the Disability Liaison Unit is required. Further information is available as follows:

  • Website: http://monash.edu/equity-diversity/disability/index.html;
  • Email: dlu@monash.edu
  • Drop In: Equity and Diversity Centre, Level 1 Gallery Building (Building 55), Monash University, Clayton Campus, or Student Community Services Department, Level 2, Building 2, Monash University, Sunway Campus
  • Telephone: 03 9905 5704, or contact the Student Advisor, Student Commuity Services at 03 55146018 at Sunway

Other

Study resources we will provide for your study are:

  • A Unit Book containing 11 Study Guides at MUSO.
  • 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 MUSO where lecture slides, weekly tutorial requirements, assignment specifications, sample solutions and supplementary material will be posted.
  • Discussion forums at MUSO.