MATH2410 Automata and Algorithms is a course which addresses at an elementary level various topics of importance in mathematical computer science. The first part of the course deals with the analysis of algorithms, that is, working out how complicated it is to run a given computational procedure. We then concentrate on the specific problem of multiplying polynomials; it is found that the "obvious" way of doing this can be greatly improved upon by a method based upon the Discrete Fourier Transform. The third section of the course sets out some of the fundamental concepts of discrete mathematics: set theory, relations, Boolean operations and matrices. The course concludes with an introduction to languages, concentrating on regular languages. We do a good deal of work in constructing and using finite automata, and prove Kleene's Theorem (a language is recognisable by a finite automaton if and only if it is regular). Finally we prove and apply two practical methods of showing that a language is not regular: the Pumping Lemma and the Myhill–Nerode Theorem.
The notes are divided into four sections, corresponding to the four major parts of the course described in the previous paragraph. They were written by David Angell, some sections being based on work by David Wilson and other members of the School of Mathematics, University of New South Wales. The design, typesetting and production of the notes was carried out by David Angell from 1996 to 1998.
Some portraits of mathematicians are included in the notes; these were obtained from the History of Mathematics Archive maintained by the University of St.Andrews, Scotland. A visit to this marvellous site is warmly recommended!
The lecture notes are in the form of PostScript files. You will need Ghostview to access them. If you are a student at UNSW and have an account on sigma, Ghostview is available on your account. You can then obtain the notes just by clicking below. Brief information on the use of Ghostview can be found here.