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.