[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive]
[an error occurred while processing this directive]
Monash University

FIT2009 Data structures and algorithms - Semester 2, 2015

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 (Off-campus)
  • South Africa (Day)

Workload Requirements

Minimum total expected workload equals 12 hours per week comprising:

(a.) Contact hours for on-campus students:

  • One 2-hour lecture
  • One 2-hour laboratory

(b.) Study schedule for off-campus students:

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

(c.) Additional requirements (all students):

  • a minimum of 8 hours of independent study in some weeks for completing lab and project work, private study and revision.

See also Unit timetable information

Unit Relationships

Prohibitions

FIT2004, FIT2071, FIT9015, GCO2817, GCO3512, GCO9807

Prerequisites

FIT1007 or GCO1812 or GCO9808 or FIT2034

Chief Examiner

Campus Lecturer

Gippsland

Shane Moore

South Africa

Johan Vorster

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 the Student Evaluation of Teaching and Units (SETU) survey. 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, see:

www.monash.edu.au/about/monash-directions/ and on student evaluations, see: 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

Academic Overview

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

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) Assignment 1 due 6 September 2015
7 Graphs and Trees (Study Guide 7)  
8 Binary Search Trees (Study Guide 8)  
9 Hashing (Study Guide 9)  
10 Heaps (Study Guide 10) Assignment 2 due 11 October 2015
11 Some Applications of Data Structures (Study Guide 11)  
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 learning system.

Teaching Approach

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

Assessment Summary

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

Assessment Task Value Due Date
Assignment 1 20% 6 September 2015
Assignment 2 20% 11 October 2015
Examination 1 60% To be advised

Assessment Requirements

Assessment Policy

Assessment Tasks

Participation

  • Assessment task 1
    Title:
    Assignment 1
    Description:
    Learning Outcomes: 1,3,5,6,7. 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 on 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:
    6 September 2015
  • Assessment task 2
    Title:
    Assignment 2
    Description:
    Learning Outcomes: 1,2,3,5,6,7. 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 on 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:
    11 October 2015

Examinations

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

Learning resources

Monash Library Unit Reading List (if applicable to the unit)
http://readinglists.lib.monash.edu/index.html

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

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

It is a University requirement (http://www.policy.monash.edu/policy-bank/academic/education/conduct/student-academic-integrity-managing-plagiarism-collusion-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 electronic submission). Please note that it is your responsibility to retain copies of your assessments.

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

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

Other Information

Policies

Monash has educational policies, procedures and guidelines, which are designed to ensure that staff and students are aware of the University’s academic standards, and to provide advice on how they might uphold them. You can find Monash’s Education Policies at: www.policy.monash.edu.au/policy-bank/academic/education/index.html

Faculty resources and policies

Important student resources including Faculty policies are located at http://intranet.monash.edu.au/infotech/resources/students/

Graduate Attributes Policy

Student Charter

Student services

Monash University Library

Disability Liaison Unit

Students who have a disability or medical condition are welcome to contact the Disability Liaison Unit to discuss academic support services. Disability Liaison Officers (DLOs) visit all Victorian campuses on a regular basis.

Other

Study resources we will provide for your study are:

  • A Unit Book containing 11 Study Guides on Moodle.
  • This Unit Information, which outlines the administrative information for the unit.
  • A unit web page on Moodle where lecture slides, weekly tutorial requirements, assignment specifications, sample solutions and supplementary material will be posted.
  • Discussion forums on Moodle.
[an error occurred while processing this directive]