DCU Home | Our Courses | Loop | Registry | Library | Search DCU

Registry

Module Specifications

Archived Version 2021 - 2022

Module Title
Module Code
School

Online Module Resources

NFQ level 8 Credit Rating 5
Pre-requisite None
Co-requisite None
Compatibles None
Incompatibles None
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 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



Workload Full-time hours per semester
Type Hours Description
Lecture24Theory and worked application examples
Laboratory20Data structures and algorithms programming labs and class tests
Directed learning25Project assignment
Independent Study56Reviewing lecture material
Total Workload: 125

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.

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

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.

Assessment Breakdown
Continuous Assessment% Examination Weight%
Course Work Breakdown
TypeDescription% of totalAssessment Date
Reassessment Requirement
Resit arrangements are explained by the following categories;
1 = A resit is available for all components of the module
2 = No resit is available for 100% continuous assessment module
3 = No resit is available for the continuous assessment component
Unavailable
Indicative Reading List

  • Robert Sedgewick, Kevin Wayne: 2011, Algorithms, 4th Edition, Addison-Wesley Professional, 9780321573513
  • Thomas H. Cormen, et al.: 2009, Introduction to Algorithms, MIT Press, 9780262033848
  • Patrick Niemeyer and Daniel Leuck: 2013, Learning Java, 4th Edition, O'Reilly Media, 9781449319243
Other Resources

None
Programme or List of Programmes
Archives: