Module Specifications.
Current Academic Year 2024 - 2025
All Module information is indicative, and this portal is an interim interface pending the full upgrade of Coursebuilder and subsequent integration to the new DCU Student Information System (DCU Key).
As such, this is a point in time view of data which will be refreshed periodically. Some fields/data may not yet be available pending the completion of the full Coursebuilder upgrade and integration project. We will post status updates as they become available. Thank you for your patience and understanding.
Date posted: September 2024
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Repeat examination |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
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
IntroductionImportance 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 ImplementationC++ 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 StructuresIntroduction 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 SearchingCharacterisation 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 TreesLower bound on searching complexity and relation to Binary Search Trees. BST implementation in Java. BST searching, insertion, deletion. BST Computational Complexity. Full tree traversals.GraphsGraphs: 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.NP-Hardness, TSP and Heuristic MethodsTractable and intractable problems. Travelling Salesman Problem (TSP). Exhaustive search method, TSP complexity. Nearest Neighbour heuristic. 2-opt tour improvement method and its complexity.Game TreesStrategic-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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Other Resources None | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||