CM2307: Object Orientation, Algorithms and Data Structures

School Cardiff School of Computer Science and Informatics
Department Code COMSC
Module Code CM2307
External Subject Code I100
Number of Credits 20
Level L5
Language of Delivery English
Module Leader Dr Bailin Deng
Semester Double Semester
Academic Year 2018/9

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.
 

Assessment Breakdown

Type % Title Duration(hrs)
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

Syllabus content

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.

Refactoring.

Design Patterns.

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

Not applicable.


Copyright Cardiff University. Registered charity no. 1136855