Exam (elaborations) Foundations of Computer Science

This course has two aims. The first is to teach programming. The second is to present some fundamental principles of computer science, especially algorithm design. Most students will have some programming experience already, but there are few people whose programming cannot be improved through greater knowledge of basic principles. Please bear this point in mind if you have extensive experience and find parts of the course rather slow. The programming in this course is based on the language ML and mostly concerns the functional programming style. Functional programs tend to be shorter and easier to understand than their counterparts in conventional languages such as C. In the space of a few weeks, we shall be able to cover most of the forms of data structures seen in programming. The course also covers basic methods for estimating efficiency. Learning Guide. Suggestions for further reading, discussion topics, exercises and past exam questions appear at the end of each lecture. Extra reading is mostly drawn from my book ML for the Working Programmer (second edition), which also contains many exercises. You can find relevant exam questions in the Part IA papers from 1998 onwards. (Earlier papers pertain to a predecessor of this course.) Thanks to David Allsopp, Stuart Becker, Gavin Bierman, Chlo¨e Brown, Silas Brown, Qi Chen, David Cottingham, Daniel Hulme, Frank King, Joseph Lord, James Margetson, David Morgan, Frank Stajano and Assel Zhiyenbayeva for pointing out errors in these notes. Please inform me of further errors and of passages that are particularly hard to understand. If I use your suggestion, I’ll acknowledge it in the next printing. Reading List My own book is not based on these notes, but there is some overlap. The Hansen/Rischel and Ullman books are good alternatives. The Little MLer is a rather quirky tutorial on recursion and types. See Introduction to Algorithms for O-notation. • Paulson, Lawrence C. (1996). ML for the Working Programmer. Cambridge University Press (2nd ed.). • Hansen, Michael and Rischel, Hans (1999) Introduction to Programming Using SML. Addison-Wesley. • Ullman, Jeffrey D. (1998) Elements of ML97 Programming. Prentice Hall. • Mattias Felleisen and Daniel P. Friedman (1998). The Little MLer. MIT Press. • Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest (1990). Introduction to Algorithms. MIT Press. I Foundations of Computer Science 2 Slide 101 Computers: a child can use them; NOBODY can fully understand them! We can master complexity through levels of abstraction. Focus on 2 or 3 levels at most! Recurring issues: • what services to provide at each level • how to implement them using lower-level services • the interface: how the two levels should communicate A basic concept in computer science is that large systems can only be understood in levels, with each level further subdivided into functions or services of some sort. The interface to the higher level should supply the advertised services. Just as important, it should block access to the means by which those services are implemented. This abstraction barrier allows one level to be changed without affecting levels above. For example, when a manufacturer designs a faster version of a processor, it is essential that existing programs continue to run on it. Any differences between the old and new processors should be invisible to the program. Modern processors have elaborate specifications, which still sometimes leave out important details. In the old days, you then had to consult the circuit diagrams.