Latest Module Specifications
Current Academic Year 2025 - 2026
No Banner module data is available
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Description The aim of this module is to develop the student’s theoretical knowledge and practical implementation skills in data structures and algorithms. Students will develop an understanding of a range of abstract data types (arrays, sets, lists, stacks, queues, trees, graphs) and algorithms (searching, sorting, tree and graph traversals, computational methods) and gain practical experience in their implementation using C++. The use of advanced OOP language features will be introduced to achieve generic algorithm implementations of practical value. Students will gain an understanding of selection criteria for different data structures and algorithms, suitable for a given application, and develop a well-founded approach to design and evaluation of algorithms based on computational complexity analysis and run-time measurements. Problem-reduction and problem-solving ability will be developed by working through problems, from abstract solution concept to concrete implementation and by designing and evaluating solutions to open-ended problems. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Learning Outcomes 1. Implement abstract data types including lists, stacks, queues, trees and graphs and implement elementary sorting, searching and traversal and path-finding algorithms 2. Implement solution methods using iterative or recursive approaches 3. Translate abstract solution concepts to concrete programming language implementations 4. Implement and evaluate appropriate data structures and algorithms for given application problems 5. Analyse and measure algorithm time complexity 6. Apply object-oriented programming principles to develop reusable implementations of abstract data types and general-purpose algorithms | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
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
Introduction Importance of algorithms to Engineering applications. Problem formulation and reduction to machine-solvable form. Computational complexity as a key algorithm evaluation criterion. Exploring and evaluating solution approaches to a non-trivial example problem – convex hulls and robot path-finding. C++ Elements of Algorithm Implementation C++ Review. Primitive types, number representation, promotion and casting, computational pitfalls, and machine epsilon. Class types, references, memory management, elementary data structures. Generic types and generic algorithm implementation – C++ templates and the Standard Template Library. Abstract Data Types & Data Structures Introduction to ADTs. Sets, Bags, Lists, Stacks, Queues, Graphs, Trees. ADTs versus Data Structures. Sets and Stacks as array-backed data structures. Linked Lists. Stacks and Queues as Linked Lists. Sorting and Searching Characterisation of sorting algorithms: integer vs comparison sort, in-place, stability. Pigeonhole sorting. Comparison sorting: set comparability, partial and total ordering. Selection sort, Insertion sort and their computational complexities. Quick Sort and its complexity. Binary Search and heuristic searches. Binary Search Trees Lower bound on searching complexity and relation to Binary Search Trees. BST implementation in C++. BST searching, insertion, deletion. BST Computational Complexity. Full tree traversals. Graphs Graphs: notation, definitions and applications. Graph ADT implementation choices. Graph traversal. Depth First Search, spanning trees and DFS recursive implementation in C++. Maze search with DFS. Breadth First Search, Minimum Spanning Trees. BFS implementation with a queue. Prim’s Algorithm (MST of weighted graph) and relation to Dijkstra. NP-Hardness, TSP and Heuristic Methods Tractable and intractable problems. Travelling Salesman Problem (TSP). Exhaustive search method, TSP complexity. Nearest Neighbour heuristic. 2-opt tour improvement method and its complexity. Game Trees Strategic-form games vs extensive-form games, game trees and utilities. Nim example. Backwards induction, Minimax algorithm as depth-first-search, game tree construction (tic-tac-toe), game complexity, tree pruning. Nash Equilibrium. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Indicative Reading List Books:
Articles: None | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Other Resources None | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||