Registry

Module Specifications

Current Academic Year 2012 - 2013
Please note that this information is subject to change.

Module Title	Data Structures and Algorithms
Module Code	CA213
School	School of Computing
Online Module Resources
Module Co-ordinator	Semester 1: Joseph Morris Semester 2: Joseph Morris Autumn: Joseph Morris
NFQ level	8	Credit Rating	5
Pre-requisite	None
Co-requisite	None
Compatibles	None
Incompatibles	None

Description

The module aims to give students an understanding of basic data structures and algorithms, most especially with respect to managing collections of data such as sets, sequences, and maps. Students will learn how to specify collections using abstract data types (ADTs), how to implement them using a variety of techniques such as linked lists and trees, and how to package them using object-oriented programming methods. Students will learn a range of basic algorithms including searching and sorting, and how to assess their computational cost. Students will also develop practical skills in implementing and testing algorithms on computers.

Learning Outcomes

1. Use iterative and recursive techniques to design and implement elementary algorithms.
2. Describe a variety of basic ADTs including sets, sequences, stacks, queues, and maps.
3. Implement the above ADTs using arrays, linked lists, search trees, and hash tables
4. Use object-oriented techniques such as interfaces, inheritance, and generics to package ADTs appropriately.
5. Analyse the time complexity of elementary algorithms, and justify the complexity of the above ADT implementations.
6. Incorporate ADTs and associated implementations appropriately into program solutions.
7. Describe and use a variety of searching and sorting algorithms.

Workload	Full-time hours per semester
*Type*	*Hours*	*Description*
Laboratory	20	Practical exercises and examples
Independent learning	76	Review of lecture material, background reading
Lecture	24	Theory, practice & examples
Directed learning	30	Completion of problem sets
Total Workload: 150

All module information is indicative and subject to change. For further information,students are advised to refer to the University's Marks and Standards and Programme Specific Regulations at: http://www.dcu.ie/registry/examinations/index.shtml

Indicative Content and Learning Activities

Object-oriented programming.
Review of Java; classes and methods. Interfaces, inheritance, abstract classes, nested classes. Generic programming..

Algorithms.
Designing algorithms using iteration and recursion. Basic algorithmic complexity, big-O notation, comparison of algorithms..

Abstract data types.
The notion of abstract data type (ADT). Sets, sequences, maps, stacks, queues as ADTs; using them via the Java collections framework..

Basic data structures.
Linked lists, doubly-linked lists, binary search trees, balanced search trees; comparison of time complexities..

Hash tables.
Hash tables, implementation in arrays, separate chaining, open addressing, extensible hash tables. Directory structures..

Sorting and searching.
Bubble sort, insertion sort, selection sort, quicksort, merge sort, radix sort, binary search.

Assessment Breakdown
Continuous Assessment	20%	Examination Weight	80%

Course Work Breakdown
Type	Description	% of total	Assessment Date
Practical/skills evaluation	Lab exam, programming exercise	15%	Week 5
Practical/skills evaluation	Lab exam, programming exercise	15%	Week 11

Reassessment Requirement
Resit arrangements are explained by the following categories; 1 = A resit is available for all components of the module 2 = No resit is available for 100% continuous assessment module 3 = No resit is available for the continuous assessment component
This module is category 3

Indicative Reading List