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