# 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.