Transcript Computer Science at Oxford

Computer Science at
Oxford
Stephen Drape
Access/Schools Liaison Officer
(Adapted from Mike Spivey’s slides)
1
Four myths about Oxford




There’s little chance of getting in
It’s expensive
College choice is very important
You have to be very bright
2
Myth 1: Little chance of getting in

False!
Statistically: you have a 30–50% chance
 Logistically: it’s never been easier

3
Myth 2: It’s very expensive

False!
Most colleges provide cheap accommodation for
three years.
 College libraries and dining halls also help you save
money.
 Increasingly, bursaries help students from poorer
backgrounds.

4
Myth 3: College Choice Matters

False!
If the college you choose is unable to offer you a
place because of space constraints, they will pass
your application on to a second, computerallocated college.
 Application loads are intelligently redistributed in
this way.
 Lectures are given centrally by the department as
are many classes for courses in later years.

5
Myth 3: College Choice Matters

However…
Choose a college that you like as you have to live
and work there for 3 or 4 years – visit if possible.
 Look at accommodation & facilities offered.
 Choose a college that has a tutor in your subject.

6
Myth 4: You have to be bright

True!
We find it takes special qualities to benefit from the
kind of teaching we provide.
 So we are looking for the very best in ability and
motivation.

7
Our courses

Computer Science


Mathematics and Computer Science


Computer Science firmly based on Mathematics
Closer to a half/half split between CS and Maths
Courses can be for three or four years
8
Computer Science
Year 1
Year 2
Year 3
Year 4
Mathematics
Computing
Project work
9
Computer Science
Year 1
Core CS 1
(75%)
Core Maths
(25%)
Year 2
Core CS 2
(50%)
CS Options
(50%)
Year 3
Year 4
(optional)
CS Options
(25%)
Advanced
Options
(50%)
Project
(25%)
Advanced
Options
(66%)
Project
(33%)
10
Mathematics & Computer Science
Year 1
Year 2
Year 3
Year 4
Mathematics
Computing
Project work
11
Mathematics & Computer Science
Year 1
Core 1
(100%)
Year 2
Core 2
(58%)
Maths
Options
(17%)
CS Options
(25%)
Year 3
Maths
Options
(25-75%)
CS Options
(25-75%)
Year 4
(optional)
Maths
Options
(25-75%)
CS Options
(25-75%)
Optional
Project
(33%)
12
Some of the different courses







Functional Programming
Design and Analysis of Algorithms
Imperative Programming
Digital Hardware
Calculus
Linear Algebra
Logic and Proof
13
Useful Sources of Information

Admissions:


Computing Laboratory:


http://www.admissions.ox.ac.uk/
http://web.comlab.ox.ac.uk/oucl/
Mike Spivey’s info pages:
http://web.comlab.ox.ac.uk/oucl/prospective/ugrad/csatox/


College admissions tutors
14
What is Computer Science?




It’s not about learning new programming
languages.
It is about understanding why programs work,
and how to design them.
If you know how programs work then you can
use a variety of languages.
It is the study of the Mathematics behind lots
of different computing concepts.
15
Finding the Highest Common Factor
Example:
Find the HCF of 308 and 1001.
1) Find the factors of both numbers:
308 – [1,2,4,7,11,14,22,28,44,77,154,308]
1001 – [1,7,11,13,77,91,143,1001]
2) Find those in common
[1,7,11,77]
3) Find the highest
Answer = 77
16
Creating an algorithm
For our example, we had three steps:
1)
Find the factors
2)
Find those factors in common
3)
Find the highest factor in common
These steps allow us to construct an algorithm.
17
Creating a program




We are going to use a programming language
called Haskell.
Haskell is used throughout the course at
Oxford.
It is very powerful as it allows you write
programs that look very similar to
mathematical equations.
You can easily prove properties about Haskell
programs.
18
Step 1






We need produce a list of factors for a number n
– call this list factor(n).
A simple way is to check whether each number d
between 1 and n is a factor of n.
We do this by checking what the remainder is
when we divide n by d.
If the remainder is 0 then d is a factor of n.
We are done when d=n.
We create factor lists for both numbers.
19
Function for Step 1
20
Step 2




Now that we have our factor lists, which we
will call f1 and f2, we create a list of common
factors.
We do this by looking at all the numbers in f1
to see if they are in f2.
We there are no more numbers in f1 then we
are done.
Call this function: common(f1,f2).
21
Function for Step 2
22
Step 3



Now that we have a list of common factors we
now check which number in our list is the
biggest.
We do this by going through the list
remembering which is the biggest number
that we have seen so far.
Call this function: highest(list).
23
Function for Step 3
If list is empty then return 0, otherwise we
check whether the first member of list is higher
than the rest of list.
24
Putting the three steps together
To calculate the hcf for two numbers a and b,
we just follow the three steps in order.
So, in Haskell, we can define
Remember that when composing functions, we
do the innermost operation first.
25
Problems with this method



Although this method is fairly easy to explain,
it is quite slow for large numbers.
It also wastes quite a lot of space calculating
the factors of both numbers when we only
need one of them.
Can we think of any ways to improve this
method?
26
Possible improvements




Remember factors occur in pairs so that we
actually find two factors at the same time.
If we find the factors in pairs then we only
need to check up to n.
We could combine common and highest to
find the hcf more quickly (this kind of
technique is called fusion).
Could use prime numbers.
27
A Faster Algorithm
This algorithm was apparently first given by the
famous mathematician Euclid around 300 BC.
28
An example of this algorithm
hcf(308,1001)
= hcf(308,693)
= hcf(308,385)
= hcf(308,77)
= hcf(231,77)
= hcf(154,77)
= hcf(77,77)
= 77
The algorithm works
because any factor
of a and b is also a
factor of a – b
29
Writing this algorithm in Haskell
30
An even faster algorithm
hcf(1001,308) 1001 = 3 × 308 + 77
= hcf(308,77)
308 = 4 × 77
= hcf(77,0)
= 77
31
Algorithm Design
When designing algorithms, we have to consider a
number of things:
 Our algorithm should be efficient – that is, where
possible, it should not take too long or use too
much memory.
 We should look at ways of improving existing
algorithms.
 We may have to try a number of different
approaches.
 We should make sure that our algorithms are
correct.
32
Comments and Questions


If there’s any comments or questions then
please ask.
There should be staff and students available
to talk to
Thank You
33