FIT9015 - Data structures and algorithms
6 points, SCA Band 2, 0.125 EFTSL
Postgraduate Faculty of Information Technology
Leader(s): Manzur Murshed
Offered
Gippsland Second semester 2009 (Off-campus)
Synopsis
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
Objectives
- 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
- Ability to implement these data structures using various common data representations:
- arrays
- linked lists
- heaps
- trees (including balanced trees)
- hashing
- Ability to evaluate which implementation would be most appropriate for a given data structure and application.
- 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.
- 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)
- Ability to design new algorithms to solve new problems.
- Enjoyment of programming as an intellectual exercise.
- Appreciation of the elegance of certain data structures and algorithms as a form of art.
- Interest in understanding how data structures and algorithms are implemented rather than merely using other people's implementations (and consequently a preference for open source software.
Assessment
Assignments: 40%
Examination: 60%
Contact hours
One x 2 hr lecture/week
One x 2 hr laboratory (programming session in PC lab)/week. (Depending on on-campus class size a repeat laboratory may be required.)
Prerequisites
FIT1007 or GCO1812 or FIT9013 or GCO9808
Prohibitions
CSE2304, FIT2009, GCO2817, GCO3512, and GCO9807 (translation set)