<a https://www.thestudentroom.co.uk/showthread.php?t=7467335'> Year 12s: what will be the first way you research your future options? >>

TSR Computer Science Society

Scroll to see replies

Reply 80

joy_to_the_world

Hello, please could someone reply to this....
I've never known what i wanted to do, i decided to choose computer science because i enjoy Mathematics A LOT and now i'm doing research into computer science..i think it may just be the right thing for me :smile:

My problem is, i don't do computing..my a levels are Maths, Psychology and English i and have ZERO work experience in the computer science field...will this affect me tremendously? & do unis take this into consideration in great deal?
Please no rude comments & thanks.

Reply 81

Alexgadgetman

Original post by joy_to_the_world

I dont know whether you have considered this (and I realise that it isn't really an answer to your question), but have you looked at AI? Depending on whether you enjoyed Psychology you might find it (even) more interesting than CS (obviously they are interconnected).

Reply 82

joy_to_the_world

I have looked into AI albeit not thoroughly,...besides i've already completed my PS, so there's no going back now..i just wanted reassurance that i might get accepted...i guess :frown:

Reply 83

MrNeilPatel

Original post by joy_to_the_world

You shouldn't have too much a problem as most offers for Computer Science courses are based on the Maths A Level. Your Psychology A Level could show your interest in AI as Alex had said so that could provide you with some extra knowledge. Also maybe try learning basic programming, for example try http://www.codecademy.com

Reply 84

joy_to_the_world

Original post by MrNeilPatel

Thanks for the useful advice & i know about codeacademy as i have been attempting some of the activities. Crossed fingers, i get accepted to my chosen universities & i'll definitely post if i get some results. Again thanks guys for the response :smile:

Reply 85

Der_Melon

Reckon these problems are pretty useful in uni interviews, shall we go through them as a group? http://www.cs.ox.ac.uk/admissions/ugrad/Sample_interview_problems

Reply 86

SerialVelocity

Original post by Der_Melon

Reckon these problems are pretty useful in uni interviews, shall we go through them as a group? http://www.cs.ox.ac.uk/admissions/ugrad/Sample_interview_problems

That's a great idea! Let's start with 2, because the 1st problem has an interview transcript with the exact method on how it's done and I'm sure someone will just copy it. :P

2. Searching for the maximum. The real-valued function f(x), defined for 0 ≤ x ≤ 1, has a single maximum at x = m. If 0 ≤ u < v ≤ m then f(u) < f(v), and if m ≤ u < v ≤ 1 then f(u) >f(v). You are told nothing else about f, but you may ask for the value of f(x) for any values of x you choose. How would you find the approximate value of m? How accurately could you find m if you could choose only 10 values of x for which to evaluate f(x)?

Not really sure how to start this..

Reply 87

roblee

Original post by SerialVelocity

Not really sure how to start this..

First thing to do is look up binary search and ternary search. This is a trivial question given some basic knowledge of algorithms.

One way of doing it:
Let's say you know f'(x), ie. the gradient, for some x. Is m less than or greater than x? How can you find the gradient by sampling from f?

Another way:
Alternatively let's say you know f(a) and f(b) for some a and b. WLOG assume f(a) < f(b). Can you say anything about any of these statements?

•

m < a

•

a < m

•

m < b

•

b < m

Reply 88

SerialVelocity

Original post by roblee

First thing to do is look up binary search and ternary search. This is a trivial question given some basic knowledge of algorithms.

Never thought about using Binary Search, that does make it a lot easier.

If we assume we know the value of f'(x), we can infer from the inequalities in the question that f'(x) is positive when x < m, and f'(x) is negative when x > m, and f'(x) = 0 when x = m.

So first we can take the value f'(0.5), if this is positive then eliminate the area where x < 0.5, or if it's negative then eliminate the area where x > 0.5. Repeat using the middle values of x for the remaining area after subsequent iterations until you eventually reach m.

Now the next problem is finding f'(x). I guess one thing we could do here is numerically calculate it using two samples so f'(x) = ( f(x+a) - f(x) ) / a where a is a very small number, but this will give us a problem in the case that x < m < x + a.

(edited 11 years ago)

Reply 89

Chrosson

Original post by SerialVelocity

[...]

Now the next problem is finding f'(x). I guess one thing we could do here is numerically calculate it using two samples so f'(x) = ( f(x+a) - f(x) ) / a where a is a very small number, but this will give us a problem in the case that x < m < x + a.

It does indeed give you a problem. Presumably you can see why "f'(x) = 0 when x = m" is actually completely false?

And you need to think again about the size of your values of a, given a limited number of choices.

Reply 90

roblee

Original post by SerialVelocity

Now the next problem is finding f'(x). I guess one thing we could do here is numerically calculate it using two samples so f'(x) = ( f(x+a) - f(x) ) / a where a is a very small number, but this will give us a problem in the case that x < m < x + a.

The value of 'M' that will be found should converge to at most a from the correct one, and a can be arbitrarily small.
Getting closer than that depends on the pivot logic alluded to above.

You have 4 possible cases:

•

f(x) ≤ f(x+a), x ≤ m ≤ x+a

•

f(x) ≤ f(x+a), x+a ≤ m

•

f(x) > f(x+a), x ≤ m ≤ x+a

•

f(x) > f(x+a), m ≤ x

If you pivot on x, only 2 of those are being considered. How is this remedied?

(edited 11 years ago)

Reply 91

SerialVelocity

Original post by Chrosson

It does indeed give you a problem. Presumably you can see why "f'(x) = 0 when x = m" is actually completely false?

Why is that not true? If f(m) is the maximum in 0 ≤ x ≤ 1 then surely f(m) is also a turning point (where f'(m) = 0)?

Original post by roblee

•

f(x) ≤ f(x+a), x ≤ m ≤ x+a

•

f(x) ≤ f(x+a), x+a ≤ m

•

f(x) > f(x+a), x ≤ m ≤ x+a

•

f(x) > f(x+a), m ≤ x

If you pivot on x, only 2 of those are being considered. How is this remedied?

Okay, well the 2nd and 4th cases happen when m is not in the range of x and x+a as described in my previous post. To handle the other two cases, I guess what could be done is to sample f(x+a/2). From this we know that m will be either between x and x+a/2 or x+a/2 and x+a. If the magnitude of f(x) - f(x+a/2) is less than the magnitude of f(x+a/2) - f(x+a) then we know that m lies between x and x+a/2, as f'(m) = 0.

But to be honest, all we've done here is reduce the size of a, so surely it's not possible to get closer to m unless we reduce the size of a even more, unless I'm missing some obvious algorithm.

(edited 11 years ago)

Reply 92

roblee

But to be honest, all we've done here is reduce the size of a, so surely it's not possible to get closer to m unless we reduce the size of a even more, unless I'm missing some obvious algorithm.

Consider this one:


iterations = 5
left = 0.0
right = 1.0
while iterations --> 0 do
  a = (left+right) / 2.0
  b = (left+right) / 2.0 + epsilon 
  if (f(a) < f(b)) then
    left = a
  else
    right = b

Draw out those 4 cases to see why the "problem" won't happen any more, even without any additional samples, or Google ternary search as originally suggested for a better explanation.

Reply 93

Chrosson

Original post by SerialVelocity

Why is that not true? If f(m) is the maximum in 0 ≤ x ≤ 1 then surely f(m) is also a turning point (where f'(m) = 0)?

Yep, but you're constrained by the real world in CS (well...sometimes).
f'(x) = 0 means d/dx = 0. In the mathematical world, this means we're talking about an infinitesimal change (or 'delta') in x. Are you able to (in an algorithm) choose two values of x such that there is an infinitely small difference between them?

You do need to be aware that you could encounter a 0 gradient though. When might that be?

Reply 94

SerialVelocity

Original post by roblee

Consider this one:


iterations = 5
left = 0.0
right = 1.0
while iterations --> 0 do
  a = (left+right) / 2.0
  b = (left+right) / 2.0 + epsilon 
  if (f(a) < f(b)) then
    left = a
  else
    right = b

Draw out those 4 cases to see why the "problem" won't happen any more, even without any additional samples, or Google ternary search as originally suggested for a better explanation.

I see, that way seems much better. I feel stupid. :P

Original post by Chrosson

I know about that, I'm just talking about the "best case" where we knew each value of f'(x). You'd encounter a gradient of 0 using two values of x when f(x) = f(x+a).

Reply 95

zain1612

just been reading about sorting algorithms and their performance.

Our good friend bubble sort worst case can be worked out by O(n^2).

My question is what does O stand for?

Reply 96

D-Box

Original post by zain1612

just been reading about sorting algorithms and their performance.

Our good friend bubble sort worst case can be worked out by O(n^2).

My question is what does O stand for?

I'm not certain, but I'm fairly sure it stands for Order of (complexity). Generally O(log₂n) is the least complex/takes least time to complete, with something like O(n!) being the most complex.

Reply 97

ukdragon37

Original post by zain1612

just been reading about sorting algorithms and their performance.

Our good friend bubble sort worst case can be worked out by O(n^2).

My question is what does O stand for?

Original post by D-Box

I'm not certain, but I'm fairly sure it stands for Order of (complexity). Generally O(log₂n) is the least complex/takes least time to complete, with something like O(n!) being the most complex.

It doesn't really stand for anything. There are other notations too like big-

\Omega

and big-

\Theta

which are used for slightly different things.

O(log n) is not the least complex for algorithms in common use. O(log log n) is common, as well as O(α(n)) and of course O(1).

Reply 98

dvdhsu

Big-O notation basically denotes the number of steps your algorithm requires. So, because there are two loops spanning the entire array in bubble sort (I'm assuming there's no early kickout), bubble sort is O(n^2). Note that Big-O notation discards constants; if, say, you have f(x) = 5(x^2), then f(x) = O(x^2).

Big-O gives upper bounds, Big-Omega gives lower bounds, and Big-Theta gives tight bounds (so the previous two put together).

Here's an algorithm that is O(1):

(display "Hello world!") (yes, I'm going through SICP)

This guy takes constant time to execute, since it does something that doesn't change, no matter what the input size (although there really is no input here).

On the other hand, binary search is O(log(n)) time to execute; that means that if I feed it an array of 1024 elements, and then feed it an array of 2048 elements, the latter only take twice as long. Note that I'm trying to use fairly big numbers here, since Big-O notation is only concerned with asymptotic behavior.