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
| |||||||||||||||||||||||||||||||||||||||||||
|
None |
|||||||||||||||||||||||||||||||||||||||||||
|
Description The module aims to give students an understanding of basic data structures and algorithms, most especially with respect to managing collections of data such as sets, sequences, and maps. Students will learn how to specify collections using abstract data types (ADTs), how to implement them using a variety of techniques such as linked lists and search trees, and how to package them using object-oriented programming methods. Students will learn a range of fundamental algorithms including searching and sorting, and how to assess their computational cost. Students will also develop practical skills in implementing and testing algorithms on computers. | |||||||||||||||||||||||||||||||||||||||||||
|
Learning Outcomes 1. Use iterative and recursive techniques to design and implement elementary algorithms. 2. Describe a variety of basic ADTs including sets, sequences, stacks, queues, graphs, trees and maps. 3. Implement the above ADTs using arrays, linked lists, search trees, and hash tables 4. Use object-oriented techniques such as interfaces, inheritance, and generics to package ADTs appropriately. 5. Analyse the time and space complexity of elementary algorithms, and justify the complexity of the above ADT implementations. 6. Incorporate ADTs and associated implementations appropriately into program solutions. 7. Describe and use a variety of searching and sorting 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
Object-oriented programmingReview of OO Concepts: classes and methods, inheritance, abstract base classes/interfacesAlgorithmsDesigning algorithms using iteration and recursion. Basic algorithmic complexity, big-O notation, time vs space complexity, comparison of algorithmsAbstract Data TypesThe notion of abstract data type (ADT). Sets, lists, sequences, maps, iterators, generators, stacks, queues as ADTs. Implementing and using them via the built-in collections.Basic Data StructuresLinked lists, doubly-linked lists, binary search trees, balanced search trees, tree traversal; comparison of time complexities.Hash TablesHash tables, implementation in arrays, collision resolution (e.g. chaining), extensible hash tables. Directory structures.Searching and SortingBubble sort, insertion sort, selection sort, quicksort, merge sort, radix sort, binary search, string search (Knuth-Pratt-Morris).Graph Structures and AlgorithmsRepresentation (adjacency matrix vs adjacency list). Graph colouring. Searching strategies (DFS vs BFS), Dijkstra’s Algorithm, Spanning Tree Algorithms (Kruskal, Prim). | |||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||
Indicative Reading List
| |||||||||||||||||||||||||||||||||||||||||||
|
Other Resources None | |||||||||||||||||||||||||||||||||||||||||||