Mathematics and Computer Science

Computer science is no more about computers than astronomy is about telescopes.

Edsger Dijkstra

Given some program, and some input to that program, is it possible to know whether that program will finish or continue running forever? If we look at a program that stops if and only if $x \neq x$, then of course that program won't stop. This is known as the halting problem. However, in 1936 Alan Turing proved mathematically that it is impossible for a general algorithm to decide for all program and input pairs whether the program will stop. 

Maths is very powerful as a tool for proving statements. Because computers are based on language - that is, they interpret a sequence of commands using logic - we can use mathematics to prove things about the capability of computers. This is a very pure approach to computer science, since many mathematicians also use computers to solve mathematical problems which would be intractable by hand. 

In the first year you split your time equally between maths and computer science. The maths you study is mostly pure maths - there is no statistics, though you do study probability - and this gives you a good understanding of the theoretical underpinnings of the computer science side of the degree. In the second year, you continue the 50/50 split, though you now have a choice of options on the maths side of the degree. In the third and fourth years you can specialise from very abstract computer science, such as computational complexity, to practical courses like computer animation. Mathematics complements both types of course well. 

• You want to develop a flexible toolkit to solve problems.
• You enjoy thinking logically about algorithms.
• You want to understand the theoretical capabilities of computers in a rigorous, mathematical way.

Imagine a 100 storey building. You want to find the highest floor from which an iphone, when dropped, will not break. If an iphone is dropped and does not break, it can be used again with no adverse consequences. However, once a dropped iphone breaks it cannot be used again. You can assume that if an iphone is dropped from floor $n$ and does not break, then it will not break when dropped from floors $< n$.

1. With an unlimited number of iphones, what's the fewest drops that you can guarantee finding the answer in?
2. If you have two iphones, how many drops do you need in order to guarantee finding the highest floor in? 

Please note: This is a theoretical problem. We recommend you do not attempt this in real life with any kind of smart phone.

For more information about the Maths and Computer Science course, you can look at the departmental prospectus.

You can also visit the Department of Computer Science's website for more details about that half of the course.

If you're interested in learning how to code (even though it's not a prerequisite for the course) you can try Codecademy. For something more mathematical you can try Project Euler. 

Some recommended reading includes The Code Book by Simon Singth, The Pleasures of Counting by Tom Körner, and Computational Fairytales by Jeremy Kubica.