Registry

Module Specifications

Current Academic Year 2009 - 2010
This information is provisional and subject to change.

Module Title	Data Structures and Algorithms
Module Code	CA213
School	Computing
Online Module Resources
Module Co-ordinator	Mr Ray Walshe	Office Number	LG02
Level	2	Credit Rating	5
Pre-requisite	None
Co-requisite	None

Module Aims

The aims of this module are to give students an in-depth understanding of: 7 The wide range of data structures and algorithms that are available to build software.7 The techniques that can be used to measure the performance of different data structures and algorithms. While much of the material presented in this module is independent of the programming languages used for implementation, Java will be used and this will provide further opportunities for students to gain experience in developing Java software.

Learning Outcomes

As a result of this module, students should be able to select and use the most appropriate data structures and algorithms to solve programming problems. They should also be able to estimate the performance characteristics of their chosen solution.

Indicative Time Allowances
	Hours
Lectures	24
Tutorials	0
Laboratories	24
Seminars	0
Independent Learning Time	27

Total	75
Placements
Assignments

NOTE

Assume that a 5 credit module load represents approximately 75 hours' work, which includes all teaching, in-course assignments, laboratory work or other specialised training and an estimated private learning time associated with the module.

Indicative Syllabus

· Review of Java: Object-Oriented Programming. Recursion. Arrays & Multi-Dimensional Arrays. Dynamic Data Structures - linked lists, doubly linked lists and circular linked lists. Abstract Data Types using Java. · Algorithm Analysis & Asymptotic Notation.· Stacks, Queues and Sequences. Array verses linked list implementations. The Java Vector class. · Strings. Parsing. Pattern Matching. Support for string manipulation in Java. · Trees. Definition & Terminology - nodes, the root node, sub-trees, paths, path length, depth, ... Binary Trees - implementation, tree traversal, expression trees, ordered & balanced trees, tree searching, AVL-Trees, ... General Trees. ·Graphs Definition & Terminology - nodes, the root node, sub-trees, paths, path length, cycles, sub-graphs,Connected.Implementation of graphs.Weighted & directed graphs.Graph algorithms-depth-& breadth-first searching, topological sorting, shortest-part problems, spanning tree algorithms, ... · Dictionaries. Implementation options. Hash tables. The Java Hashtable class. · Sorting and Searching Algorithms - insertion sort, bubble sort,Quicksort · File Processing and External Sorting. Sequential Files. Random Access Files. Searching and sorting files· Java collection classes - Set, Map, List · Advanced Data Structures & algorithms.

Assessment
Continuous Assessment	30%	Examination Weight	70%

Indicative Reading List

Essential Supplementary A Practical Introduction to Data Structures and Algorithm Analysis , Clifford A. Shaffer, Prentice-Hall Inc., 1998 ISBN: 0-13-660911-2 Data Structures and Algorithms with Object-Oriented Design Patterns in Java , Bruno R. Preiss, John Wiley & Sons, 2000 ISBN: 0-471-34613-6 Data Structures and Algorithms in Java , Michael T. Goodrich & Roberto Tamassia, John Wiley & Sons, 1998 ISBN: 0-471-19308-9

Programme or List of Programmes

BSSA

Study Abroad (DCU Business School)

BSSAO

Study Abroad (DCU Business School)

CASE

BSc in Computer Applications (Sft.Eng.)

DME

B.Eng. in Digital Media Engineering

ECSA

Study Abroad (Engineering & Computing)

ECSAO