DATA STRUCTURES AND ALGORITHMS

SHE Level 2
SCQF Credit Points 20.00
ECTS Credit Points 10.00
Module Code M2I222994
Module Leader Bobby Law
School School of Computing, Engineering and Built Environment
Subject Computing
Trimester
  • B (January start)

Summary of Content

This module covers the concepts associated with data structures and algorithms including the design of algorithms considering factors such as efficiency and complexity. A range of widely employed data structures such as Arrays, Lists, Trees and Queues are investigated. Coverage of algorithms such as searching and sorting as well as those associated with graph data structures are also included. The topic is covered in the context of object-oriented development and enables students to develop an appropriate object-oriented software solution given a simple set of requirements where consideration has been given to the use of the most appropriate data-structures and algorithms.

Syllabus

Data Structure and Algorithm Concepts: - History - Data Structure Definition: Relationship to OO, Container Classes, ADT - Algorithm Definition: Representing algorithms, Flowcharts, UML, Pseudo Code - Cost Estimation: Algorithm Analysis, Trade-Offs, Recursion, Algorithm Complexity, Big-O Notation Data Structures and their Implementations: - Arrays: one-dimensional, two-dimensional, n-dimensional, jagged - Lists: Singly Linked, Doubly Linked, Circular, Array List - Maps and Sets - Collections and Generics - Hashing: Hash Tables, Rehashing, Perfect, Universal - Stacks and Queues - Trees: Binary, Binary Search, Expression, Splay, B-Trees and Tries - Graphs Sorting and Searching: - Bubble, Shell, Quicksort, Heap - Red-Black and AVL trees - Pattern matching and Regex expressions Graph Algorithms: - Shortest Path, Depth First/Breadth First, Maximum Flow, NP Complete Algorithm Design Techniques: - Divide and Conquer - Big-O - Compression (LZW, Huffman) - Encryption - Searching and Sorting - Data Structures

Learning Outcomes

On successful completion of this module, students should be able to:1. Understand the concepts which underpin data structures and algorithms such as cost estimation and algorithm complexity.2. Understand the fundamental data structures and algorithms commonly used when developing software systems. 3. Critically evaluate the data structures used with searching, sorting and graph algorithms.4. Develop an object-oriented solution which demonstrates the appropriate the use of a range of data structures and algorithms.

Teaching / Learning Strategy

The university 'Strategy for Learning' documentation has informed the learning and teaching strategy for this module. The module's material will be introduced through lectures, while practical exercises, based on the lecture material, will be given to students for their laboratory sessions. Tutorials will be used to help explain and elaborate on both the lecture material and the laboratory exercises. All lecture, laboratory and tutorial material will be made available on GCU Learn. During all lab and tutorial sessions students will receive formative feedback on their performance in undertaking the laboratory and tutorial exercises. Summative feedback and grades will also be provided for the coursework assignment undertaken as part of the module using GCU Learn. GCU Learn will also be used to provide the students with module specific discussion forums to stimulate student and lecturer interaction out with the normal lecture, laboratory and tutorial sessions.

Indicative Reading

Algorithms, Sedgewick R and Wayne K, 2011, Pearson Education Data Structures and Algorithms Using C#, McMillan M., 2010, Cambridge Data Structures and Algorithms in Java, Goodrich M and Tamassia R., 2010, Wiley Introduction to Algorithms, Cormen T, 2001, MIT Press Algorithms in a Nutshell, Heineman G, 2008, O'Reilly Algorithms and Data Structures, Wirth N, 1985, Prentice Hall The Art of Computer Programming, Vols. 1-3, 1998, Knuth D E, Addison-Wesley Professional Data Structures and Problem Solving Using Java, 2009,Weiss M, Addison-Wesley Data Structures and the Java Collections Framework, 2011, Collins W, McGraw-Hill

Transferrable Skills

D1 Specialist knowledge and application D2 Critical thinking and problem solving D4 Communication skills, written, oral and listening D5 Numeracy D7 Computer literacy D8 Self confidence, self discipline & self reliance (independent working) D10 Creativity, innovation & independent thinking D15 Ability to prioritise tasks and time management

Module Structure

Activity Total Hours
Practicals (FT) 24.00
Tutorials (FT) 12.00
Independent Learning (FT) 122.00
Assessment (FT) 18.00
Lectures (FT) 24.00

Assessment Methods

Component Duration Weighting Threshold Description
Course Work 02 n/a 50.00 35% Practically based programming assignment
Course Work 01 n/a 50.00 35% Practically based programming assignment