ANALYSIS OF ALGORITHMS
Third Year Course 1987
IAN HOLYER
CHAPTER 0
INTRODUCTION
0.0 Contents
------------
Chapter 1 Practical Estimation of Speed
Chapter 2 Analysing Data Structures
Chapter 3 Algorithm Design
Chapter 4 Network Algorithms
Chapter 5 Unsolvable and Intractable Problems
Chapter 6 Parallel Algorithms
Chapter 7 Miscellaneous Algorithms
These notes are available on the suns in the directory "~ian/algorithms", and
can be made available on other machines (e.g. MSA, QGB) in the directory
"~Holyer/algorithms" on request. They are suitable for printing on a line
printer (not laser printer, please).
Practicals (counting for 20% of the marks for the course) will be set in due
course. Exam questions can be obtained from papers for the Complexity Theory
short course 1983-4, and this course from 1984-5 onwards.
0.1 Books
---------
There is no single book which covers the material well, but the following may
be helpful.
Algorithms (good reference, poorly organised)
Sedgewick (Addison-Wesley)
Fundamentals of Computer Algorithms (very good, but large & expensive)
Horowitz and Sahni (Computer Science Press)
Data Structures and Program Design (doesn't cover all topics)
Kruse (Prentice Hall)
Data Structures and Algorithms
Aho Hopcroft and Ullman (Addison-Wesley)
The Design and Analysis of Computer Algorithms (older but broader version)
Aho Hopcroft and Ullman (Addison-Wesley)
Computers and Intractability (for the specialist)
Garey and Johnson (Freeman & Co.)
Algorithmics (a good read)
Harel (Addison-Wesley)
0.2 Aims of the course
----------------------
An idealised approach to program design is:
1. Design an informal algorithm to solve the problem.
2. Analyse the performance to be sure it is an efficient approach.
3. Write the program cleanly without using any "tricks".
4. Use a profiler to find out where the bulk of the time is spent.
5. Optimise accordingly.
The course is largely about step 1, and it provides you with some general
principles and some practical tricks for designing fast algorithms. Also, to
help with step 2, the course provides you with tools which enable you to
estimate quickly the running time of an algorithm. The remaining steps you are
expected to be familiar with already. Last, the course covers the study of
intractable problems, that is problems having no efficient algorithm for their
solution. If time permits, there may be a final section on parallel algorithms.
This is not a programming course. I assume you already know how to program.
By far the most important factor in speed of programs is the overall algorithm
design, and that is what we will be studying. The programming details usually
have relatively little effect, but you may pick up some programming tips from
the course.
The examples will be in an informal Pascal-like or C-like language. In
particular I will leave out semicolons, declarations of types, variables and
procedure parameters, and will use indenting instead of BEGIN and END (or {}).
You will be expected to do the exercises in Pascal or C. You should make sure
you have a good grasp of Pascal (C), including the use of records (structures),
pointers, and dynamic memory allocation procedures NEW and DISPOSE, (MALLOC
and FREE), and the use of recursion. It will also be useful to know about data
structures such as stacks, queues, linked lists, and (binary) trees.
Profiling can be done in several ways. The overall time for a program may be
found crudely in Unix using the "time" command and "$time" variable, or by
including calls to system routines (such as "etime"). More detailed profiling
is best done with the "prof" (or even "gprof") command as follows:
pc -p prog.p (or "cc -p prog.c" - produces a.out)
a.out (runs the program, producing mon.out)
prof (produces a profile from data in mon.out and a.out)
The profile is an estimate of the total time spent in each procedure, together
with the number of calls and the average time per call. This should help
pinpoint where optimisation would be most profitable.