Assessment Pattern

Unit(s) of Assessment	Weighting Towards Module Mark( %)
Exam: written examination. 30% of the examination will be devoted exclusively to testing students' understanding of the non-assessed coursework (see following).	100%
Non-assessed coursework (individual): students will be given assignments which they will be expected to tackle but which will not be for handing in. These assignments will be discussed in selected lectures. In due course solutions will be issued. Students' understanding of these assignments and the solutions will be tested in the exam as described above.	This coursework is not assessed directly. But 30% of the exam marks will be attributed solely to students' understanding of this coursework.
Qualifying Condition(s)

Module Overview

Appropriate choices of data structures can expedite algorithm efficiency and also aid clear thinking when designing algorithms. It is thus natural for data structures to be studied with algorithms. An algorithm is a sequence of steps for performing some process.  A computer program is not an algorithm but a representation of an algorithm. There is a need to be able to create effective algorithms, quantify their efficiency and classify them independently of any computing system or language.

Module Aims

To discover and examine various abstract data types (ADT).   To explore data structures based on those ADTs, including implementation and applications of  such data structures.   To explore algorithms as abstractions - independent of any computing facility.   To examine what is involved in creating algorithms and quantifying their efficiency.   To examine the importance of algorithm efficiency.   To examine the action of a small number of specific algorithms particularly in the areas sorting and searching.   To explore various strategies for algorithm design.   To classify algorithms.   To question what the future holds in terms of algorithm development and classification.

Learning Outcomes

At the end of the module you should:   Be able to describe and handle the taught data structures of linked lists, stacks, queues, trees, graphs.   Be able to describe and handle a number of applications of the taught data structures.   Be familiar with the big Oh measure of algorithm efficiency.   Know what is meant by recursive and non-recursive algorithms.   Be able to describe a number of searching strategies and trace any of the taught hashing schemes.   Be able to describe any of the taught sorting methods.   Be able to distinguish between different algorithm design strategies.   Be able to discuss the classification of algorithms and problems.

This module considers various data structures such as lists, stacks, queues, trees and graphs and the abstract data types on which they are based. The module also discusses algorithms. It defines a scheme for quantifying algorithm efficiency, devoid of any computing system or language. Several approaches for algorithm design are studied such as recursion, divide and conquer, brute force and greedy strategies. Towards the end of the module the classification of algorithms and the problems they solve is explored. The module finally concludes by asking how future technological developments could change the way we perceive algorithms.     Main topics     Abstract data types: discussed in general.   Basic data Structures: lists, linked-lists, stacks, queues, implementation/applications of these.   Trees: general trees ordered trees, multiway trees, implementations of trees, tree traversal, path lengths.   Binary trees: internal and external nodes, binary tree depth, logs.   Binary tree applications: expression trees, binary search trees, heaps, Huffman data compression.   Graphs: undirected/directed, connected, weakly/strongly connected, complete), adjacency matrix/list, topological ordering, weighted graphs/networks, path lengths, Dijkstra’s Algorithm, depth/breadth-first, traversals, minimum spanning trees, Prim’s Algorithm, Kruskal’s Algorithm.   Algorithm Efficiency: Big ‘Oh’, common time complexities, log time, binary search v linear search Recursion: why use it, the ground rules, Merge Sort in detail, Towers of Hanoi in detail.   Sorting: Bubble-, Selection-, Insertion-, Shell-, Bucket-, Radix-, Heap-, Quick-, external sorting.   Hashing: searching, hash function & table, collisions, separate chaining and open addressing.   Algorithm design strategies: brute force, greedy, divide and conquer, dynamic programming, incremental, probabilistic.   Algorithm and problem classification:  polynomial and exponential time, reasonable and unreasonable algorithms, tractable and intractable problems, the future.     You should be clear that the Algorithms material in the module is NOT intended to be a review of a comprehensive range of specific algorithms. Nevertheless, a limited number of specific algorithms within the areas of searching and sorting will be examined.

Three lectures per week: some of these will take the form of seminars.      The course is conceptual. Much of the material is independent of any computer language. Much of your coursework will be pen and paper (or word processor) based. But at the practical level you will also be handling Java programs which implement various data structures such as linked lists and algorithmic strategies such as recursion.

All of the material you need for the module will be provided. However, if you also wish to purchase a book you may find the following useful.     Main course text      Title:               Data Structures and Algorithm Analysis in Java. (2nd Edn)                                 Author:            Mark Allen Weiss                                 Publisher         Pearson International                                 ISBN               0-321-37319-7   Date: 2007     Other Books            Title                Algorithmics:  The Spirit Of Computing  (2nd or 3rd Edn)                                 Author:            David Harel (with Yishai Feldman for 3rd Edn only)                                 Publisher         Addison-Wesley Publishing Co                                 ISBN               2nd Edn:  0-201-50401-4   Date: 1996                                 ISBN               3rd Edn:  0-321-11784-0   Date: 2004

AUG 2010