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: 30% |
Three hour exam in May/June: 70% |
| 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 Pascal 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
This 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 Pascal, thus learning more advanced features of the language. Further
software issues connected with code such as reusability and modularity are introduced. We
also discuss in an elementary way the fundamental notions of the analysis of algorithms and
their complexity.
Objectives
- To be able to understand the fundamental types of dynamic data
structure, their specification as abstract data types, and their
implementation in Pascal.
- To be familiar with some of the main algorithms for processing
dynamic datatypes, and to be able to write Pascal programs using these
algorithms.
- To understand the basic principles of modularity and reusable code.
- 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 design algorithms to process dynamic data structures.
- Programming skills at an intermediate level.
- The ability to use the principles of complexity theory to assess
the efficiency of programs.
Syllabus
Fundamental ideas of list processing; pointers in Pascal; implementing lists in Pascal using
pointers; algorithms for processing lists: searching and sorting, including binary search
and quicksort; queues. Lists and queues as examples of abstract dat types; implementing
abstract data types in Turbo Pascal -- units; variant records in Pascal; text and binary
files in Pascal; sequential and random access; searching and sorting algorithms extended to
files.
Basic concepts of algorithm analysis; big O notation, asymptotic analysis; algorithm
analysis applied to algorithms already introduced elsewhere in the course.
Fundamental idea of a binary tree and of tree operations; implementing trees in Pascal;
binary search trees; hash tables defined and compared with binary search trees.
The idea of a higher order function or procedure; map and fold discussed;
implementation of higher order programming in Pascal.
Reading list
Essential:
E. B. Koffman,
Turbo Pascal, 5th edition,
Addison-Wesley.
Recommended:
R. Pressman,
Software Engineering -- a Practitioner's Approach, European 3rd edition,
McGraw Hill.
Recommended:
T. Cormen, C. E. Leiserson and R. L. Rivest,
Introduction to Algorithms,
MIT Press.
Recommended:
D. Stubbs and N. Webre,
Data Structures with Abstract Data Types and Pascal, 2nd edition,
Brooks/Cole.
Background:
I. Sommerville,
Software Engineering, 5th edition,
Addison-Wesley.
Background:
D. Cooper,
Oh! Pascal!, 3rd edition,
W. W. Norton and Co. Inc.
Background:
M. A. Weiss,
Data Structures and Algorithm Analysis, 2nd edition,
Benjamin Cummings.
Background:
U. Manber,
Introduction to Algorithms: a Creative Approach,
Addison-Wesley.
Background:
S. Fisher and S. Reges,
Pascal and Beyond, Data Abstraction and Data Structures using Turbo Pascal,
Wiley.
Details of Assessment
The coursework for the continuous assessment consists of five 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
Roy L. Crole
10/22/1998