Start with computer science. There are numerous links on this page to information, information theory, information entropy and algorithmic information theory. The article in Wikipedia concludes with a lengthy list of links to key areas of computer science and topics within each of these areas. While you may not read (or understand) all of these articles they serve nevertheless to reveal the mathematical and theoretical nature of the subject and the need to be prepared for this. The article quotes Edsger Dijkstra as saying that: "Computer science is no more about computers than astronomy is about telescopes."
An alternative starting point is computation (defined as information processing that can be represented mathematically). This leads to the theory of computation, computability and complexity theory. Discussion of computation leads to the study of Turing machines. This in turn leads to consideration of algorithms and here you should study as many examples as possible. Following Turing machines is the consideration of push-down automata and finite state automata.
Mention of the mathematician Turing might lead to some consideration of Godel and incompleteness theorem. The incompleteness theorem might be used as a proof that a machine (computer) can never emulate the intelligence of a human brain because a machine would never recognise the incompleteness property that Godel's proof identified.
Algorithms are a central topic in computer science. Turing, Post, Kleene and Church addressed a problem raised by David Hilbert known as the Entscheidungsproblem. Hilbert wanted mathematics to be formualted on a complete logical foundation, such that a machine could take as input a mathematical statement and output the result of whether it was true or false (a machine that later became known as a computer). Turing and Church showed that it was not possible to decide algorithmically whether statements in arithmetic are true or false. Gödel showed that a system that was powerful enough to include arithmetic could not demonstrate its completeness by its own axioms. This incompleteness was a fundamental flaw in Hilbert's programme. Algorithms are commonly formulated in imperative languages but there are alternatives in functional programming and logic programming.
Families of problems include:
P (can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time);
NP-complete (). Link to a list of NP-complete problems (probably intractable); specific problems such as Hamiltonian completion.
Additional topics might include artificial intelligence, cryptography and data compression. Naturally these lead to a plethora of further links. Students with an interest in photography may find it interesting to research image compression, the JPEG method in particular. Similar interest in music and/or video may lead to examination of compression methods including Vorbis, mp3 and mpeg. One final topic: NP complexity, which includes links to polynomial time, exponential time and Big O notation.
| Selection Sort | Insertion Sort | Bubble Sort |
| Binary Search | Travelling Salesman | Minimum Spanning Tree |
| Greatest Common Divisor | Euclid's Algorithm |
| Title | Author | Comment | Library? |
| The Turing Omnibus | A.K. Dewdney (library) | One of three titles on the Cambridge introductory reading list; work your way through this and you will have a good understanding of what computer science is about. | Yes |
| The Annotated Turing... | Charles Petzold | Essential reading for A Level and beyond. | Yes |
| Computer Science A Modern Introduction | L Goldsclager and A Lister | Basic introductory text that will tell you what the subject is about. | Yes |
| The Pleasures of Counting | T.W.Korner | Another title on the Cambridge introductory reading list; work your way through this and you will have a great appreciation of applied maths and algorithms. | Yes |
| Computers Ltd : What they really can't do | David Harel | Excellent short book that takes you through various issues of computability involving polynomial and exponential algorithms. Highly readable. | Yes |
| Prisoner's Dilemma: John Von Neumann, Game Theory and the Puzzle of the Bomb | William Poundstone | Interests and diversions of one of the greats of Computer Science. | Yes |
| The Emperor's New Mind | Roger Penrose Link | Includes discussion of what computers can and can't do and explores reasons why computers may never act like intelligent minds. The chapter on Turing (2) is particularly useful. | Yes |
| Database Nation | Simson Garfinkel | Not computer science but a very relevant survey of the impact of data and information collection in the USA. | Yes |
| Code: The Hidden Language | Charles Petzold | Prolific author of programming manuals (and Turing, see above) turns his mind to what goes on inside a computer: code! | Yes |
| Shadows of the Mind | Roger Penrose | Further work on similar lines to 'Emperor'. | Yes |
| The Computer and the Information Revolution | Georges Ifrah | History of the computer (volume 3 in The History of Mathematics) | Yes |
| Godel, Escher, Bach | Richard Hofstadter. Link | A stimulating journey through a range of theoretical topics. | Yes |
| The Code Book | Simon Singh | General introduction to and history of cryptography. | Yes |
| Cryptography: A Very Short Introduction | Fred Piper & Sean Murphy | Does what it says on the cover. | Yes |
| Cryptography: The Science of Secret Writing | LD Smith | Guide to cryptography. | Yes |
| Identity Cards: Nothing to Fear...? | Barry Tighe | A serious book with added comedy or a humorous book about a serious subject? Read it and decide for yourself! | Yes |
| The Music of the Primes: Why an Unsolved Problem in Mathematics Matters | Marcus DuSautoy | Yes | |
| The Mythical Man Month and other essays | Frederick Brooks | The third title on the Cambridge introductory list. Link | Yes |
| How Digital Photography Works | Ron White. Link | A digital camera is a special-purpose computer in miniature, the processing power packed into a small space is astonishing. For those interested in photography as well as computing this book is very good. | Yes |
| Computer Science Unplugged | Bell, Witten & Fellows | A teaching guide but with interesting practical exercises and technical sections that provide an introduction to complex topics. A good starting point. | here |
Web link: Information Theory, Inference and Learning Algorithms, David Mackay.
Another web link: Spam Filtering Using Statistical Data Compression Models
This should be more than enough to feed your mind through a summer holiday and beyond!