CM2307: Object Orientation, Algorithms and Data Structures
|School||Cardiff School of Computer Science and Informatics|
|External Subject Code||I100|
|Number of Credits||20|
|Language of Delivery||English|
|Module Leader||Dr Bailin Deng|
Outline Description of Module
This module aims to teach the principles of good Object Oriented Programming (OOP) practice and techniques for the design and analysis of algorithms and data structures. It focusses on ways in which computing concepts can be realised in an object-oriented fashion, and on the development and application of re-usable code and designs. It introduces the idea of classifying data according to its abstract behaviour, as distinct from its representation. It provides an understanding of the basic skills needed in the design of algorithms, emphaisisng the interactions between algorithms and data structures in creating efficient code. It explores how multi-threaded object-oriented programs and user interfaces can safely be implemented
On completion of the module a student should be able to
1. Appreciate the main features that are needed in a programming language in order to support the development of reliable, portable software and how key OO principles relate to those features
2. Apply principles of good OO software design to the creation of robust, elegant, maintainable code.
3. Understand the design of various fundamental data structures and know their advantages and disadvantages.
4. Explain the difference between various fundamental algorithmic techniques and employ these for simple algorithm design.
5. Understand and analyse the resource requirements of various algorithms and data structures.
6. Identify the most appropriate data structure and algorithm to solve a particular problem.
7. Explain and apply a range of design patterns.
8. Demonstrate understanding of object-oriented abstractions for concurrency and user interaction
How the module will be delivered
The module will be delivered through a combination of lectures, supervised lab sessions, example classes and tutorials as appropriate.
Skills that will be practised and developed
A. Design and implement fully OO Java programs.
B. Model systems using UML class diagrams.
C. Create and extend re-usable, maintainable code, applying appropriate “rules of thumb”.
D. Evaluate and make effective use of classes (such as data structures) from pre-existing libraries.
E. Develop and apply design patterns.
F. Use the facilities provided by Java to create threaded programs.
G. Design algorithms and data structures
H. Implement fundamental data structures and algorithms
I. Test and evaluate performance of algorithms and data structures
How the module will be assessed
Coursework: The coursework will allow the student to demonstrate their knowledge and practical skills and to apply the principles taught in lectures.
Exam: A written exam (2 h) will test the student's knowledge and understanding as elaborated under the learning outcomes.
The potential for reassessment in this module is a 100% resit examination during the summer.
|Examination - Spring Semester||50||Object Orientation, Algorithms And Data Structures||2|
|Written Assessment||25||Implementation And Performance Evaluation Of Data Structures/Algorithms For A Specified Problem||N/A|
|Written Assessment||25||Oo Modelling And Programming Assignment||N/A|
The influence of basic OO principles, including abstraction, encapsulation, inheritance and re-use, on design and implementation of OO programs.
"Rules of thumb" for good OO program design, including interface versus implementation, and cohesion & coupling.
OO modelling and communication of design using UML diagrams.
Object-oriented concurrent programming (tasks/executors, synchronization)
Single-threaded sub-systems, the model-view-controller pattern for graphical user interfaces (including SWING), and safe multi-threading of interactive applications.
Design of data structures and algorithms, abstract data types
Analysis of data structures and algorithms, complexity
Testing and measuring performance
Influence of data layout, algorithms and hardware on performance.
Data structures and basic algorithms:
- Review of basic data structures (arrays, lists, stacks and queues)
- Maps and dictionaries
- Trees and graphs
- Pointers, memory management and garbage collection
Algorithms and algorithmic techniques:
- Iteration and recursion
- Backtracking, divide-and-conquer, branch-and-bound, greedy algorithms
- Sorting and searching
- String processing
- Selected more advanced algorithmic techniques, e.g. dynamic programming, discrete optimisation, heuristics
Java is the primary programming language which will be used in concrete examples of the above topics; however, other languages such as C will be touched upon to illustrate certain points such as memory management and pointer manipulation.
Essential Reading and Resource List
Data structures and algorithms in Java, Michael T. Goodrich, Roberto Tamassia. 6th edition, Wiley, 2015
D Skrien, Object-Oriented Design using Java, McGraw-Hill, 2009.
Brian Goetz, Java Concurrency in Practice, Addison Wesley, 2006.
Online design patterns repository: http://www.oodesign.com/
Bruce Eckel, Thinking in Java, 3rd edition – downloadable from http://www.mindview.net/Books/TIJ/
Bruce Eckel, Thinking in Patterns – downloadable from http://mindview.net/Books/TIPatterns/
Oracle Java Concurrency tutorial: https://docs.oracle.com/javase/tutorial/essential/concurrency/
Background Reading and Resource List