Course Outline, Semester 2, 2001


Introduction

The material covered in Algorithms and Data Structures is an essential part of any computing education. Data structures and algorithms are central to practically every branch of computer science and of direct and practical relevance to any practitioner. The choice of inefficient algorithms and data structures can make an application useless, and, conversely, a careful choice of data structures and algorithms can result in a dramatic improvement in program performance.

Problem solving, in the sense of finding a good algorithm for a given computational problem, is something that is best learned by example. I will try to emphasize the creative side of algorithm design, but I think that, at least initially, the best way to learn is by looking at many and varied examples. You will be shown techniques for analysing the performance of algorithms, and shown, by example, a number of paradigms for the creation of efficient data structures. There are two problems that we will consider in some detail, namely sorting and searching, but we will also look at graph algorithms and if time, numerical algorithms, parsing, cryptology or probabilistic algorithms.

We shall begin by looking at a few advanced features of C, the main programming language used in the course. You are assumed to be familiar with C, but we will spend a little time recapitulating and discussing more complex aspects of C.

Algorithms and programming languages are not entirely orthogonal. Sometimes the choice of programming language may affect the choice of algorithms. We will use both C and Haskell when discussing algorithms and data structures. This way you will come out of 433-253 with a good grounding in algorithms and data structures for both imperative and declarative programming language paradigms.

The course objective is that you should

Prerequisites

Prerequisites are Computer Science 433-141 and either 433-142 or 433-162. If you are not familiar with the Haskell language you will need to do some additional catching up (Haskell is very similar to Miranda and knowledge of Miranda is sufficient).

Prior or concurrent enrolment in 433-252 Software Development Principles and Tools is strongly recommended.

Syllabus

Imperative and functional programming languages. Complexity of algorithms and complexity classes. Abstract data types. Algorithms for sorting arrays, lists and files. Algorithms and data structures for searching: balanced trees, hashing, strings. Graph representations and algorithms. Further topics chosen from: cryptology, parsing, and numerical algorithms.

Textbooks

Prescribed: R. Sedgewick. Algorithms in C (third edition) Addison-Wesley, 1998. The second edition is also sufficient, though additional reading would be necessary. This book is essential.
Recommended: B. Kernighan and D. Ritchie. The C Programming Language. Prentice-Hall, second edition, 1988.
Recommended: Recommended: S. Thompson, Haskell: The craft of functional programming Addison-Wesely, second edition, 1999 (or some other Haskell reference).


Martin Sulzmann
Last modified: Mon Jul 23 16:29:54 EST 2001