Module Specifications..
Current Academic Year 2023  2024
Please note that this information is subject to change.
 
Repeat examination 

Description The aim of this module is to develop the student’s knowledge and implementation skills in the area of 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, Monte Carlo method, computational methods) and gain practical experience in their implementation using Java. 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 wellfounded approach to design and evaluation of algorithms based on computational complexity analysis and runtime measurements. Problemreduction and problemsolving ability will be developed by working through problems, from abstract solution concept to concrete implementation and by designing and evaluating solutions to openended problems.  
Learning Outcomes 1. Implement abstract data types including lists, stacks, queues, trees and graphs and implement elementary sorting, searching and traversal and pathfinding 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 objectoriented programming principles to develop reusable implementations of abstract data types and generalpurpose 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 machinesolvable form. Computational complexity as a key algorithm evaluation criterion. Exploring and evaluating solution approaches to a nontrivial example problem – convex hulls and robot pathfinding. Java elements for Algorithm Implementation Types in Java. Primitive types, promotion and casting, computational pitfalls and machine epsilon. Class types, objects, references, arrays of objects, primitive wrappers, strings. Generic types and interfaces and the Java Collections Framework. Abstract Data Types & Data Structures Introduction to ADTs. Sets, Bags, Lists, Stacks, Queues, Graphs, Trees. ADTs versus Data Structures. Sets and Stacks as arraybacked data structures. Linked Lists. Stacks and Queues as Linked Lists. Sorting and Searching Characterisation of sorting algorithms: integer vs comparison sort, inplace, 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 Java. 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 Java. 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. NPHardness, TSP and Heuristic Methods Tractable and intractable problems. Travelling Salesman Problem (TSP). Exhaustive search method, TSP complexity. Nearest Neighbour heuristic. 2opt tour improvement method and its complexity. Game Trees Strategicform games vs extensiveform games, game trees and utilities. Nim example. Backwards induction, Minimax algorithm as depthfirstsearch, game tree construction (tictactoe), game complexity, tree pruning. Nash Equilibrium.  
 
Indicative Reading List
 
Other Resources None  
Programme or List of Programmes
 
Archives: 
