DATA STRUCTURES AND ALGORITHMS

SHE Level 2
SCQF Credit Points 20.00
ECTS Credit Points 10.00
Module Code M2I225088
Module Leader Sajid Nazir
School School of Computing, Engineering and Built Environment
Subject Computing
Trimesters
  • B (January start)
  • A (September 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. The percentage of Work Based Learning for this module, as represented by the Independent Learning 'Activity Type', is 61%. The percentage of Work Based Assessment for this module is 0%.

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

Work based education aims to maximise the direct and digitally mediated contact time with students by practicing teaching and learning strategies that use authentic work based scenarios and encourage action learning, enquiry based learning and peer learning. All these approaches aim to directly involve the students in the process of learning and to encourage sharing of learning between students. The module team will determine the level and accuracy of knowledge acquisition at key points in the delivery, inputting when necessary either directly or with the support of external experts who will add to the authenticity, the credibility and application of the education and learning in the workplace. The university 'Strategy for Learning' documentation has informed the learning and teaching strategy for this module. The module's material will be introduced through online copies of lectures, while practical exercises, based on the lecture material, will be made available to students for their laboratory sessions. Tutorials will be used to help explain and elaborate on both the lecture material and the laboratory exercises. To support students GCULearn will be used to provide all lecture, laboratory and tutorial materials. 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(s) 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. Students will be encouraged to use elements of work-related activity to underpin the learning on this module.

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

Specialist knowledge and application Critical thinking and problem solving Communication skills, written, oral and listening Numeracy Computer literacy Self confidence, self discipline & self reliance (independent working) Creativity, innovation & independent thinking Ability to prioritise tasks and time management Develop an understanding of the practical considerations that constrain the application of theory in the workplace. Communicate and interact effectively in a work place environment.

Module Structure

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

Assessment Methods

Component Duration Weighting Threshold Description
Coursework 1 n/a 50.00 35% Practically based programming assignment
Exam (Exams Office) 2.00 50.00 35% Written Examination