So, tonight, our (main) topic will be : algorithms. I assume that, all of you computers freaks know what they are! ;) Algorithm, or process... Proggie, or recipe... Basically, an algorithm is a quick computing tool which help us a lot. Obviously, in some cases, the recipe to reach the solution may be... long.... Let's go for an example! Do you remember what a prime number is? :) yes... okay I guess you will talk about Euclide's Algorithm so, let's say we want to build an algorithm who'll find all prime numbers up to N yay! i hate finding primes =/ why? quiet, children :) lol well, mu, I understand your pain :P So, if we want to find all those primes up to N. What our algorithm will have to is : explore all the possibilities of division of every number less than N by all the numbers less than sqrt(N) that would only be good for smaller numbers though wouldnt it? Intuitively, one can see that it's gonna be really long for any big N. So, yeah, fire, you're right ;) sieve of eratosthenes ;) eratosthenes? Anyway, this was just an illustrative example, and I won't go further into it, so yeah, like mentioned by riftor, google for "sieve or eratosthenes" or, check that out : http://www.cs.cmu.edu/~scandal/cacm/node8.html yeah k, ty for a simpler explanation (i.e. more understandable for the beginner), you can see : http://simple.wikipedia.org/wiki/Sieve_of_Erathostenes About what elda was saying, we can indeed mention that "Euclid's algorithm" is one of the oldest algorithms. This algorithm is used to find the GCD of two given numbers. This is a classic and it can be found everywhere on the web ;) You may have noticed that, at the time of Euclid, there was no.. computers (doh!) And, indeed, algorithms became more and more popular thanks to the developement of computers. So, basically, a program is an algorithm written in a language the computer can understand. ;) * Curryjoke (eternityfa@bu-7B2BD5EE.fbx.proxad.net) has joined #lecture * Fay (eternityfa@bu-7B2BD5EE.fbx.proxad.net) Quit (Ping timeout) Now, let's focus on a useful technique, namely, recursion! :) Riftor will introduce you to this topic. Assuming he isn't afk. okay Righty ho! Recursion is technique where by we define some solution in terms of itself now sounds a little strange at first, but don't worry, it turns out that it can be very natural to use It is a common concept in mathematics, where recursive functions are defined (have we looked at induction?) * tgo (tgo@bu-AD7ECA6A.no.no.cox.net) has joined #lecture no a recursive function is one that 'calls' itself from within itself okay so we haven't talked about induction but nevermind okay, so lets say we have a function called "f", that takes on argument so in maths we might write this as "f(x)" lets define the operations of f(x) lets say f(x) is f(x) = 2*f(x-1) this is saying that f(x) is equal to 2 multiplie by the same function, f, applied to x-1 so say we try and do f(5) we will get f(5) = 2*f(4) so if we expand this a bit we get f(5) = 2*(2*f(3)) and then again... and so on... f(5) = 2*(2*(2*(2*(2*f(0))))) now we could keep on going, and this would be an infinit function! If this was in a computer program we could end up getting in trouble! but we don't want this function to go on forever so we will also say that there is a "base case" for f we will say that if we get f(0) that equals 1 so we have the definition f(0) = 1 f(x) = 2*f(x-1) so if we go back to our f(5) expression we had f(5) = 2*(2*(2*(2*(2*f(0))))) this time we know that f(0) = 1 so we substitue that in f(5) = 2*(2*(2*(2*(2*1)))) and we get f(5) = 32 so our function f(x) is basically, 2 to the power of x but we never actually talked about 2 to the power of x, we just did all the intermediate steps with recursion now another slightly more complex, but not really example the factorial function in maths the factorial function takes a number and multiples that number by each number that is less than it (but greater than 1) so say we did factorial of 5 that would be 5*4*3*2*1 = 210 *120 looks like we could solve it with recursion aye? well yes we can would anyone that doesn't already know how to express factorial recursively like to have a go? ill give you a starting point, your going to need a definition for factorial(x) i have a question and also some base case so that we dont go on forever sure mu 17:11 how the hell can f*0=1? oh nvm i see it's not a * its a uhm whaddya call it uhm parenthesis? no it's a yep mu[lecture], function? :P no yep the numbers like, in the array not quite parameter? its a function, so f applied to 0 is 1 yeah what's 0 called again, i forgot, i haven't been coding lately uhm.. 0 ? zero a number? no, like 0, 1, 2 base case? no nvm natural number? go on, sorry no okay so does anyone want to have a go at defining factorial? f(x) = x * f(x-1) and f(1) = 1 f(0) = 1, actually what about the gamma function ? oh, ok (sorry for disturbing) Curryjoke, we're working with integers so, no gamma function needed ;) yep that's correct char, well you could have f(1) = 1 we don't really need to ,multiply by 1 at the end as 1*x = x factorial 5 could just be 5*4*3*2 and we don't need the 1 heh gamma function is quite similar yep in a way but we're not gonna go there indeed else, we'd need integrals etc. yeah and, since we work in integers, the only thing we could say is : gamma(n+1) = n!, which is, in our case, useless... yeah for integers so, let's get back to the point ;) anyway so yes char had it right factorial(1) = 1 factorial(n) = n*factorial(n-1) gets you the correct result element! lol how about 0! ? is what i was trying to say sorry =/ o.O 0! = 1 ah right yes my bad, qwerty was correct that's what I told : f(0) = 1 we want to say factorial(0) = 1 to be compleye *complete yes now this kind of definition where we define a function in one way and then another can be done in some languages for instance a language called haskell you could write almost exactly that definition in it fact 0 = 1 fact x = x*(fact x-1) this is called "pattern matching" and is awesome ;) so that's recursion in a basic form qwerty? yes, ok so, for those who know C for example here's how you can code the factorial recursively int fact{int n} ahem int fact (int n) { int res, i; for (res=1, i=1 ; i <= n ; i++) res *= i; return res; } or, in a more looking_like_what's_above way : int fact (int n) { if(n==0) that way would be iterative and not recursive return 1 ; return n * fact(n-1) ; } and the latter would be recursive ;) yip for more on recursion and lists with recursion see http://riftor.g615.co.uk/content.php?view=14&type=1 well, this little example shows that function is an important tool when coding, and, in another lecture, we'll discuss what's called "lambda calculus" ;) but now, let's see another thing I'm gonna tell you how to "draw a circle" 1st : take a compass :P just kidding ;) haha anyway, I hope you have the circle in your head I'll call "r" its radius and "theta" will be the angle between the y axis and the line joining O (the center) and a point M on the circle if we assume that O is the interesction of the x and y axis and "theta" will be the angle between the y axis --> typo, should be : x axis * Elda_Winslacks (loulou@bu-63B1AF92.w83-198.abo.wanadoo.fr) Quit (Ping timeout) Now, let's code the circle ;) what follows is in pseudo-code : 1: we define and initialize the variables : r := 8; theta := 0; x := 0; y := 0; 2: we make a loop on 360° 3: in each step, we compute x and y as a function of the radius (r) and the angle (theta) : for i from 0 to 359 do theta := I; x := r*cos(theta) y := r*sin(theta) ahem, forgot the semicolomns draw point(x,y); end; did you get it? :) * Sepheus nods head to indicate some form of life yep okay why does theta, x and y =0? i see theta but not x and y because, first of all, we place the origin :) O has coordinates x=0 and y=0 ok ty now, do you want more? :) i'm good ty alright, so, I'll propose you a list and I'll let you choose the algorithm you want me to explain ;) ok? k k Magic squares why not !!! ^-^ e no next oki : no ! (e being the euler constant) what else, pls? ha ha 10th Hilbert problem Euclid's algorithm (...) what's the 10th Hp ? Does there exist a universal algorithm for solving Diophantine equations? oki i dunno what those even are =/ what about einstein's uhm pi square root euh ... sorry, but, what's "uhm" ? that sounds good i forget what we discussed last week enigma qwerty said he'd show us how to solve it with an algo <_< find the date of the week well, let's chose one of the subjects ... mandelbrot sq root is good, mandelbrot, others speak up Newton's algorithm to find roots idc, but i wanna know the meaning of what is being explained, please y e h are the others asleep or what? its not just newton's ;) find the units digit and that's it so, mu? well, i'm ok with magic squares, if that's what curry wanted but, if you want me to explain the stuff behind the names don't hesitate ;) this way, you'll be able to choose by yourself no, I just don't know, why anybody else wouldn't give their voice ? not paying attn <_< sorry But I will be alright with mu's choice some idiot keeps IMing me >_> ok so flip a coin qwerty heh heads is magic square lol tails is sq root well, ok... :) but, first of all, do you all know what a magic square is? golden ratio? i do no fire well, read that first : http://en.wikipedia.org/wiki/Magic_square (for those who do not know) brb k ohh well :-D back alright * Curryjoke (eternityfa@bu-7B2BD5EE.fbx.proxad.net) Quit (Ping timeout) * Fay (eternityfa@bu-7B2BD5EE.fbx.proxad.net) has joined #lecture ... So, what I'll present you now is an algorithm originally created by De la Loubière to build magic squares of odd order It goes like this : 1) put the "1" in a cell of your choice 2) Move like a chess knight : one step on the right, two steps up, and put "2" ! same thing for the following numbers 3) when we get out of the square, continue just like the square was "looped", id est : the right side stuck with the left side, and the top with the bottom 4) if this rule leads you to put a number in a cell which already contains one then, place the number in the cell that is right at the bottom eh? 5) -> 2) ok so, did you get it? :) ok yeah got it I finally got off IM :D haha, w00t :p yes ty and, well, this algorithm ends tonight's lecture! :) class dismissed! :P