MC104 Algorithms and Data Structures

Next: MC106 Software Engineering and Up: Year 1 Previous: MC103 Program Design

MC104 Algorithms and Data Structures

Credits: 20

Convenor: Dr. N. Measor

Semester: 2

Prerequisites:	essential: MC103
Assessment:	Continuous assessment: 40%	Three hour exam in May/June: 60%

Lectures:	36	Classes:	24
Tutorials:	12	Private Study:	78
Labs:	none	Seminars:	none
Project:	none	Other:	none
Total:	150

Explanation of Pre-requisites

Since its purpose is to lead the student on to more advanced programming concepts, the module assumes that MC103, Program Design, has already been taken.

Course Description

The purpose of the module MC104 is to take the student beyond the elementary parts of the Java language as covered in MC103, introducing advanced features of the language which require sophisticated design techniques and algorithms if they are to be used effectively. The module leads on to the second year modules MC206, Software Engineering and System Design, and MC204, Design and Analysis of Algorithms.

Aims

The aim of this module is to build on the fundamentals of object-oriented programming presented in MC103 by extending the coverage of objects to include more sophisticated concepts such as inheritance which enhance their usefulness to the software engineer. We also introduce Graphical User Interfaces and applets.

The module introduces students to various kinds of complex data structures, and shows how these can be specified as abstract data types. Simple algorithms are presented to process such data structures, and students are shown how to implement both the data structures and the algorithms in Java, thus learning more advanced features of the language.

We also discuss in an elementary way the fundamental notions of the analysis of algorithms and their complexity.

Objectives

To understand advanced object-oriented techniques such as inheritance and interfaces.
To understand Graphical User Interface concepts and the event-driven model of programming.
To be able to construct simple GUIs and applets in Java.
To be able to understand the fundamental types of dynamic data structure, their specification as abstract data types, and their implementation in Java.
To be familiar with some of the main algorithms for processing dynamic datatypes, and to be able to write Java programs using these algorithms.
To understand the basic principles of the analysis of algorithms, and to be able to compare programs with respect to their efficiency.

Transferable Skills

The ability to specify complex data structures as ADTs, and to implement such structures in an object-oriented language.
The ability to design algorithms to process dynamic data structures.
Object-oriented programming skills at an intermediate level, including experience with GUIs and applets.
The ability to use the principles of complexity theory to assess the efficiency of programs.

Syllabus

1.: Advanced object-oriented concepts: inheritance, interfaces, abstract classes.
2.: Structured data objects: stacks, linked lists, queues, hash tables.
3.: Abstract data types and their implementation in Java.
4.: Graphical User Interfaces and their implementation in Java.
5.: Event-driven programming in Java.
6.: Introduction to applets.
7.: Algorithms to handle structured data objects: sorting and searching.
8.: Basic concepts of algorithm analysis; big O notation, asymptotic analysis; algorithm analysis applied to algorithms already introduced elsewhere in the course.

Reading list

Essential:

Judy Bishop, Java Gently, 2d edition, Addison-Wesley.

Background:

I. Sommerville, Software Engineering, 5th edition, Addison-Wesley.

Background:

U. Manber, Introduction to Algorithms: a Creative Approach, Addison-Wesley.

Details of Assessment

The coursework for the continuous assessment consists of six worksheets containing both programming and pencil and paper problems.

The written Midsummer examination contains six questions, and the best four questions will be taken into account in determining the mark. The examination will test candidates' knowledge of algorithm analysis as well as their programming ability.

Next: MC106 Software Engineering and Up: Year 1 Previous: MC103 Program Design

S. J. Ambler
11/20/1999