Programming II

Module aims

Aims of the course: The aims of this module are: To give students a good understanding of basic concepts of object-oriented program design; introduce them to the fundamental principles of abstraction, modularity and reusability; and illustrate object diagrams as a basic object-oriented design and modelling technique.

To teach and enable students to develop object-oriented programming skills within the Java language; to enable students to develop object-oriented Java program solutions to small application problems.

To help students gain a good understanding of, and ability to use, abstract data types; familiarise students with common abstract data types and associated operations.

To teach various design and implementation solutions for abstract data types; illustrate the practical effects of the different implementation choices; and illustrate their practical use in developing Java programs for real application problems.

Learning outcomes

Learning Outcomes

1) Knowledge and Understanding Upon successful completion of the module, a student will: Understand basic principles of object-oriented program design. Understand the basic and some advanced issues related to writing classes and methods - such as data, visibility, scope, method parameters, object references, and nested classes. Understand the basic ideas behind class hierarchies, polymorphism, and programming to interfaces. Get exposure to exceptions and basic I/O streams. Understand basic principles, main features and operations of abstract data types, in particular of lists, stacks, queues, trees, heaps, hash tables and graphs. Differentiate specifications of abstract data types from particular implementation techniques. Learn about fundamental algorithms associated with the above data types, including tree traversal, treesort, heapsort and graph traversal algorithms.

2) Intellectual and Practical skills Upon successful completion of the module, a student will: Be able to solve a given application problem by going through the basic steps of program specifications, analysis, design, implementation and testing --- within the context of the object-oriented paradigm. Be able to competently read 'foreign' Java source code and object diagrams. Have developed solid Java programming skills and the ability to put in practice the acquired knowledge and understanding of the Java language and object-oriented design in relatively simple case studies. Be able to develop Java implementations of abstract data types using different approaches, and evaluate their differences. Be able to use abstract data types and related implementations in designing and implementing efficient solutions to straightforward application problems.

Module syllabus

Part I

Specification and design: Programming in Java: control, data-structures, simple algorithm construction, testing, debugging.

Part II

Outline syllabus The module will cover the following main themes and associated topics:

Object-oriented program design Key issues related to a contemporary software development process. Adaptation of the standard five-step approach to software development (problem specification, analysis, design, implementation and testing) to the object-oriented paradigm. Object diagrams as an object-oriented design and modelling technique.

Objects, primitive data and program statements Definition and use of objects. Use of predefined classes from the Java standard library. Primitive types, operators and expressions. Procedural statements and basic control structures in Java.

Classes Issues related to writing classes and methods, such as instance data, visibility, scope, method parameters and return types, constructors, object relationships, method overloading and decomposition. Various examples of related program design and implementations. Some advanced topics such as static modifiers, and interfaces for implementing polymorphism.

Interfaces and Abstract classes Definition and use of Interfaces and Abstract classes in Java. A brief introduction to inheritance and its role in software design.

Exceptions and I/O Streams Exposure (through example programs) to: exception messages, exception propagation, and checked and unchecked exceptions; I/O streams including the IOException class; Standard Java I/O; and the keyboard class.

Vectors and Iterators.

Introducing Abstract Data Types A brief introduction to data abstraction and definition of the concept of Abstract Data Types (ADT).

Lists Definition of lists and associated operations for manipulating individual elements or entire lists, such as addition and deletion of an element, search for an element, replacement of an element in a list, computing the length of a list, sorting a list and copying a list. Array and reference-based implementation techniques. Examples of list variations, including double linked lists, circular lists.

Stacks, queues and recursion. Definition of stacks and associated operations. Array and linked-list implementation of stacks. A brief introduction to iteration and recursion. Queue and related access operations. Array and linked-list implementation of queues. Priority queues and double-ended queues. Example applications of stacks and queues.

Trees Definition of binary trees and associated operations. Array and reference-based implementation of binary trees. Various examples of tree traversal algorithms. Binary search trees and related operations such as finding, inserting, removing an element. Illustration of the Treesort algorithm.

Heaps and hash tables Definition of heaps and basic operations. Priority queues with heaps. Illustration of the Heapsort algorithm. An introduction to hash tables, hash function, and illustration of some of the issues related with the choice of hash functions and the use of double hashing.

Graphs Introduction of undirected and directed graphs and implementation of graphs. Illustration of basic graph algorithms such as depth-first and breadth-first search.

Pre-requisites

Part I

Pre/Co-requisites: None

Part II

Pre-requisites: Programming I

Teaching methods

Weekly lectures, catch-up tutorials, small-group tutorials, timetabled laboratory sessions, supervised catch-up laboratory sessions.

Reading list

Supplementary

Module leaders

Dr Madasar Shah
Dr Antonio Filieri
Dr Alastair Donaldson