Friday, August 20, 2010

Links from today's class plus *Thinking Cap* Questions (that you should respond to if you can)

It is equally relevant to any university..

Questions from the class that you can comment on (comment on all or some or none. If you have nothing to say this time, I am sure you will have opportunities later in the semester. I would only be worried if you never had anything to say... The following link from Love and Death has some insightful comments on the quantity vs. quality tradeoff: expounded in the context of a slightly different situation (start at min 3:30)

1. What is i^i  

2. If we have access to a program that tests a sequence of numbers to see if they are sorted or not (and returns yes if they are and no if they aren't), we can use it to *make* a sequence sorted by 
       Generate each permutation of the sequence
       Test if the sequence is sorted; if it is, exit loop and return the sequence
   end Loop

What do you think of this as a sorting algorithm?

3. What is the "famous" CS theorem that someone claimed to have proved recently and why is that theorem famous to begin with?



  1. 1.
    We need the euler form of i, which is e^(i * pi/2).
    i^i = e^(i * pi/2 )^i = e^(i^2 * pi/2)
    i^i = e^(-1 ^ pi/2)
    i^i = e^(-pi/2)

    2. It works fine for small n, but larger n's can take forever to sort this way.

    3. P vs NP. It would show that problems that can be checked by computers can also be solved by computers.

  2. My hat comes off to aofst for number 1. I didn't know that i had an euler form that could be written like that.

    For number 2, I also have to agree. Even for a small number of n, this would be quite time consuming.

    P vs NP essentially means if a problem can be verified very quickly, can it also be solved very quickly?

  3. Actually, there is no separate euler formula for i. What Ivan is using is the general formula which says

    e^{i theta] = cos(theta) + i sin(theta)
    if you substitute theta= pi/2
    then you have
    e^[i pi/2] = cos(pi/2) + i sin(pi/2)
    = 0 + i *1
    = i


    ps: the euler's formula itself comes from the power series for e^x (and if you put x to be iy then you can separate the power series expansion into cos(y) series and i * sin(y) series.

  4. ..and by the way, e^(-pi/2) = e^(-1.57) which is about 0.20 (in other words, imaginary power imaginary is real ;-)

    If you type i^i into google search window, you get
    i^i = 0.207879576



Note: Only a member of this blog may post a comment.