Object-Orientated Programming: Data Structure & Algorithms

This module builds on students' past object oriented programming experience to explore in detail the design of algorithms and data structures of practical relevance. Topics include the following. Design and analysis of list-based, tree-based and graph-based data structures. Theoretical and empirical analysis of algorithms, including advanced search algorithms and algorithms for traversing trees. Dynamic programming. Data compression and Huffman encoding. Implementation of data structures and algorithms in an object-oriented programming language. Practical considerations of analysing, choosing, implementing and applying these algorithms and data structures in useful programs.

Learning Outcomes
1. Explain the structure, properties and use of data structures including Linked Lists, Stacks, Queues, Trees, Binary Search Trees, and Graphs, including algorithms to process them.
2. Implement these data structures, use the implementations, and explain them.
3. Explain concepts such as recursion and dynamic programming.
4. Define and apply concepts and notations related to algorithmic complexity including O-notation, big Omega, big Theata, P and NP problems
5. Analyse the space and time requirements of any algorithm encountered in this module, theoretically and empirically.
6. Evaluate algorithms and data structures, analyse their complexity, discuss their relative merits, and make rational choices about which is best for an application
7. Explain the general operation and algorithm details of a variety of sorting algorithms, and implement and analyse them
8. Explain the concepts of lossy and lossless compression and describe and implement lossless compression algorithms