Module: Algorithms for Engineers

Module Specifications..

Current Academic Year 2023 - 2024

Please note that this information is subject to change.

Module Title	Algorithms for Engineers
Module Code	EE324
School	School of Electronic Engineering
Module Co-ordinator	Semester 1: Conor McArdle Semester 2: Conor McArdle Autumn: Conor McArdle
Module Teachers	Conor McArdle
NFQ level	8	Credit Rating	5
Pre-requisite	None
Co-requisite	None
Compatibles	None
Incompatibles	None

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

*Type*	*Hours*	*Description*
Workload	Full-time hours per semester
Lecture	24	Theory and worked application examples
Laboratory	20	Data structures and algorithms programming labs and class tests
Directed learning	25	Project assignment
Independent Study	56	Reviewing 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	50%	Examination Weight	50%

Type	Description	% of total	Assessment Date
Course Work Breakdown
Assignment	Data structures and algorithms lab report	4%	Week 2
Loop Exam	Data structures and algorithms test	3%	Week 3
Assignment	Data structures and algorithms lab report	3%	Week 4
Loop Exam	Data structures and algorithms test	3%	Week 5
Assignment	Data structures and algorithms lab report	3%	Week 6
Loop Exam	Data structures and algorithms test	3%	Week 7
Assignment	Data structures and algorithms lab report	3%	Week 8
Loop Exam	Data structures and algorithms test	3%	Week 9
Project	Selection, design, implementation, testing and performance evaluation of algorithm solution to an open problem	25%	Week 11

Reassessment Requirement Type
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
This module is category 1

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

ECE	BEng Electronic & Computer Engineering
ECSAO	Study Abroad (Engineering & Computing)

Archives: