![[The University of Leicester]](http://www.le.ac.uk/corporateid/departmentresource/000066/unilogo.gif) | Department of Mathematics & Computer Science |
 |
Next: MC106 Software Engineering and Professional Practice
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 |
Problem Classes: |
none |
Tutorials: |
none |
Private Study: |
78 |
Labs: |
24 |
Seminars: |
none |
Project: |
none |
Other: |
none |
Surgeries: |
12 |
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.
Recommended:
R. Pressman,
Software Engineering -- a Practitioner's Approach,
European 3rd edition,
McGraw Hill.
Recommended:
M. A. Weiss,
Data Structures and Problem Solving Using Java,
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 Professional Practice
Up: Year 1
Previous: MC103 Program Design
Author: S. J. Ambler, tel: +44 (0)116 252 3884
Last updated: 10/4/2000
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.