52.219 Aims and Objectives
-
Pre-requisites: 52.135, 52.136; 52.131 recommended but not mandatory
-
Contact Hours: 20 lectures, 24 practicals
-
Semester: 1
-
Credit: 1
-
Examination: Written [2hr 00]
-
Lecturer: Patrick Prosser.
-
Availability: Compulsory for Computer Science Honours Students, as
an option elective for other students
Aims
To provide knowledge of ways of structuring and operating on
data, the nature of some fundamental problems, methods for addressing
those problems, and to foster an analytical and empirical appreciation
of the behaviour of algorithms.
Objectives
Upon completion of the course the student should
-
be knowledgeable of certain abstract data types, such as lists,
hash tables, trees, and graphs
-
be able to make a critical assessment of different implementations
of an ADT (abstract data type)
-
be familiar with a number of fundamental computational problems,
and be aware of real world instances of those problems.
-
have carried out a number of empirical studies of the performance
of algorithms
-
be aware of, and understand, a number of fundamental algorithms
relating to ADT's and practical problems.
-
to be acquainted with the lambda calculus, and be aware of its
relation to scheme (and other functional languages)
Syllabus
-
Introduction to algorithms, classification of algorithms, example of algorithms.
Introduction to abstract data types (ADT's), and coding conventions used throughout
course (ie. do, records, simple syntax)
-
The abstract data types for Lists, Stacks and Queues: different implementations of
these structures and examples of their usage.
-
A quick introduction to Complexity, estimating run times t(n). The Big-oh
notation. The tyranny of growth, some examples and typical problems
-
Sorting and Searching. Sorting: insertion sort, bubble sort, merge sort
as examples. Complexity of sorting. Lab examples to show relative performance of
these algorithms as data set size increases. Searching: sequential search and
the binary chop. Open and closed hashing.
-
Permutations. The TSP and related problems, branch and bound
and the use and value of lower bounds. Greedy algorithms such as 2-opt for TSP.
A study of the TSP, from a naive solution onwards.
-
Combinations. Typical problems, selection, the power set. Backtracking search.
Example, 0/1 knapsack problem. Complete versus greedy techniques.
-
Trees, n-ary and binary. Typical instances and uses of trees.
Implementing ADT's for trees. Insertion into a tree, traversal of trees
and what those traversals correspond to.
-
Binary trees. Two implementations, using records and arrays.
Expressions in binary trees, binary tree implementation of sorted list,
access time. Traversals, interpretation of those traversals, example of
traversal using stack rather than recursion. Deletion from a binary tree.
-
Graphs, directed and undirected. Applications of graphs to real
world problems (telecommunications, design of transportation systems (roads,
power, water, sewage, etc), dependencies between objects). Representation of
graphs and graph algorithms.
-
The practicals associated with this course will involve the implementation of
some of the abstract data types described, and some of the algorithms.
In addition students will be given working algorithms and data structures
and will carry out experiments measuring the relative performance of
different techniques (for example comparing different sorting algorithms
as problem size grows, and comparing different search techniques).
-
All course material is available electronically in /home/s7/pat/scheme/pub
(see file README and README.overview). All lecture notes are on line and have
supporting software demonstrators.