Note: This unit has been running for many years, but had somehow managed to escape the Avatar to date!The current changes are required to make this unit fit into the new Bachelor of I.T. degree structure. In particular, the prerequisite unit, GCO1812, will now be introducing sorting, searching, algorithmic complexity analysis and the application of several of Java's standard collection interfaces (leaving GCO2817 free to concentrate on their implementation instead of needing to cover both application and implementation). This in turn will free some time to explore a few more advanced data structures and algorithms.

1. Ability to analyse simple algorithms to work out an order of magnitude estimate of running time and space

2. Familiarity with some of the most common data structures:

• stacks
• queues
• lists
• priority queues
• tables
• sets
• collections

3. Ability to implement these data structures using various common data representations:

• arrays
• linked lists
• heaps
• trees (including balanced trees)
• hashing

4. Ability to evaluate which implementation would be most appropriate for a given data structure and application.

5. Ability to apply the same principles used in implementing the common data structures to implement other data structures.

6. Ability to design and implement new data structures.

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

8. Ability to design new algorithms to solve new problems.

ASCED Discipline Group classification: 020111 Data Structures

Algorithm analysis. Application and implementation of some common data structures: stacks; queues; lists; priority queues; tables; sets; collections. Using various common data representations: arrays; linked lists; heaps; trees; (including balanced trees); hashing. Design of application programs making use of common data structures. Design and implementation of new data structures. Study of some more advanced algorithms in areas such as:

• graph theory (shortest path etc)
• pattern searching
• data compression

Handbook Entry

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

Prescribed Text

Mark Allen Weiss, Data Structures & Problem Solving using Java, 3rd Edition, Addison Wesley, 2005, ISBN: 0131293370.

Recommended Reading

William H. Ford and William R. Topp, Data Structures with Java, 2005, Pearson Education International, ISBN 0131293370

Lafore, R, Data Structures & Algorithms in Java, 2nd edition, 2002, SAMS, ISBN 0-672-32453-9

Robert Sedgewick and Michael Schidlowsky, Algorithms in Java, 3rd edition (Parts 1-4), Addison Wesley, 2002, ISBN: 0201361205.

Mitchell Waite and Robert Lafore, Data Structures & Algorithms in Java, Waite Group Press, 1998, ISBN: 1571690956.

Donald Ervin Knuth, Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd edition, Addison Wesley, 1997, ISBN: 0201896834.

Donald Ervin Knuth, Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, Addison Wesley, 1998, ISBN: 0201896850.

Students studying in off-campus mode work through week-by-week materials, provided in print form and on the unit web site. These materials guide students through reading and exercises.

On-campus students attend two hours of lectures and two hours of tutorials, in which the week-by-week content of the unit is delivered. These students are required to complete the same reading and exercises as the off-campus students.

All students and staff in the unit communicate through newsgroups that permit discussion of the week-by-week theoretical and practical activities, as well as assignment and other work.

Standard student computing environment as defined for on-campus and off-campus students, Java 5 SDK, version 1.5 or later.

GCO1812 or GCO9808