DCU Home | Our Courses | Loop | Registry | Library | Search DCU


Module Specifications

Archived Version 2020 - 2021

Module Title
Module Code

Online Module Resources

NFQ level 8 Credit Rating 5
Pre-requisite None
Co-requisite None
Compatibles None
Incompatibles None

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 search trees, and how to package them using object-oriented programming methods. Students will learn a range of fundamental 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, graphs, trees 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 and space 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
Lecture24Theory, practice and examples
Laboratory20Completion of problem sets
Directed learning30Completion of problem sets
Independent Study76Review of lecture material, background reading and independent practice
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 OO Concepts: classes and methods, inheritance, abstract base classes/interfaces

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

Abstract Data Types
The notion of abstract data type (ADT). Sets, lists, sequences, maps, iterators, generators, stacks, queues as ADTs. Implementing and using them via the built-in collections.

Basic Data Structures
Linked lists, doubly-linked lists, binary search trees, balanced search trees, tree traversal; comparison of time complexities.

Hash Tables
Hash tables, implementation in arrays, collision resolution (e.g. chaining), extensible hash tables. Directory structures.

Searching and Sorting
Bubble sort, insertion sort, selection sort, quicksort, merge sort, radix sort, binary search, string search (Knuth-Pratt-Morris).

Graph Structures and Algorithms
Representation (adjacency matrix vs adjacency list). Graph colouring. Searching strategies (DFS vs BFS), Dijkstra’s Algorithm, Spanning Tree Algorithms (Kruskal, Prim).

Assessment Breakdown
Continuous Assessment% Examination Weight%
Course Work Breakdown
TypeDescription% of totalAssessment Date
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
Indicative Reading List

  • Brad Miller and David Ranum: 2014, Problem Solving with Algorithms and Data Structures, Franklin, 978-1590282571
  • M Goodrich: 2013, Data Structures and Algorithms in Python, Wiley, 978-1118290279
Other Resources

Programme or List of Programmes