Friday, August 27, 2010

[ASU 101] Questions on Complexity...

Consider answering the following questions:

0. Write a brief summary of what you understood from today's class. [Each of you are encouraged to answer this--so I get an idea what is getting through]

1. There was a factual inaccuracy when I discussed Knuth. See if you can find what it is.

2. How long will it take for the world to end if the priests working in the Tower of Hanoi have been working out on the sly and are ready to do this problem round the clock, with 1 sec per move. 

3. For a given problem, your friend wrote an algorithm with 2^n steps (of unit time each). You wrote one with 4000*(n^5) steps  (where n is the problem size). Up to what input size is your friend going to beat you (alternately, beyond what input size are you going to cream your friend?)

4. In problem 3, suppose your friend, with his 2^n algorithm was able to solve instances of size up to n=K (K is some constant) in "reasonable time". His boss feels sorry for him and buys him a machine that is twice as fast. Now, what is the size of the largest instance that your friend can solve in reasonable time?



  1. For question three I believe the cut off is between n = 38, 39.
    For number 4 given a machine twice as fast then 2 ^ (n+1) is the advantage gained.

  2. This comment has been removed by the author.

  3. Try again number 2 may be(2n-1)secs / number of workers. Where n is the number of pieces.

  4. (2^n-1) /number workers. Shouldn't post on a Friday night.

  5. #0. I understood the discussion concerning P = NP and what problems belong to both subsets. I also understood the consequences of P = NP, including how it would affect modern cryptography techniques.

    #1. Knuth invented TeX, not LaTeX.

    #2. 2^64-1 sec/move. So... like... 5.85E11 years. To put this in perspective: This amount of time is about equal to:
    ~~ 43 × universe age ( 1 universe age )
    ~~ 130 × age of the sun (~~ 4.57 billion yr )
    ~~ 130 × age of the earth (~~ 4.5 billion yr )

    For #3, I couldn't solve it on my own, so I used wolfram alpha:^5%29%2F%282^n%29+-+1%2F4000+%3D+0 . The answer is approximately 38. The friend's algorithm will beat mine up to size 38.

    #4. Not exactly sure, but if the machine is twice as fast, then the equation should be (2^n)/2, which means that the largest size should be:

    (2^K) = R
    (2^n)/2 = R

    (2^K) = (2^n)/2
    log2 2^K = log2 (2^n)/2
    K = n-1
    K-1 = n

    Therefor, the size is now expanded by 1. How sad.

  6. 0. I gleamed two major pieces of information from Friday's lecture. One, P!=NP is what allows modern cryptography to even work. Although security is really the least interesting thing about CS to me, I found this interesting. Second, CS is almost more of a philosophy than being about programming. It's a way of thinking about problems in terms of computers in a different way.

    1. As Ivan stated above, Knuth invented TeX, not LaTeX. In order to add to the discussion, I will point out that TeX is a way of writing math equations, while LaTeX is a front end into that methodology that is widely used. If I'm not mistaken...

    2. The Hanoi Problem would take 18,446,744,073,709,551,615 seconds. Which as stated above will be much longer than any of us are around. This reminds me of the theory (can't remember who from) that if a problem will take too long, you may be better off waiting 10 years for technology to improve and then try the problem. This works because growth of technology double every two to three years (according to Moore's law).

    3. By taking log base 2 of both sides, you can get the problem in the form of n = log(4000n^5)/log(2). This isn't really the best way, but you can graph this and find where x = y. This happens around 38. So for less than 38 items, the friend will be faster, but over 38, you will be faster.

    4. I'm not sure how to answer number 4!

  7. Hi Nicolas:

    The answer to 4 would have put paid to your optimism about waiting for the technology to catch by doubling speed. As Ivan points out, the really depressing thing about exponential growth is that doubling the speed only allows you to increase the size of the instance you can solve by a measly "1".. So if you could solve a 10-instance before, then with moore's help you can solve an 11-instance a decade later (and a 12-instance another decade later and so on..)


    ps 1. Yes LaTex is a set of macros over TeX (and the macros are possible because TeX has a pretty powerful macro facility). LaTeX macros were written by Leslie Lamport.

  8. 0) Honestly in class i kind of understood everything, some of the math just went right over my head, but i understood that in the end, 2^n will always take longer than n^C where C = any constant.

    1) Well, seeing as the answer has already been posted, "ps 1. Yes LaTex is a set of macros over TeX (and the macros are possible because TeX has a pretty powerful macro facility). LaTeX macros were written by Leslie Lamport." - Rao.

    2) The tower of Hanoi problem will take
    18446744073709551616 seconds. Divide that by 60 to get minutes.
    3.074457E^17 Minutes. divide again by 60 for hours.
    5.124096^15 Hours. Divide by 24 for days.
    2.135040E^14 Days. Divide by 365.25 (leap years) for years.
    584542046091 years.

    3) I simply plugged both of the equations into a graphing calculator, and found the intersection point. The intersection point i found was at 34.102987.

    4) Well since i decided that changing 2^n was too weird to double, i simply halved the efficiency of my program and made it 800*x^5. The intersection point of the graphs then was 35.365136. So buying a faster computer really doesnt help too much.

  9. i didnt understand alot of the stuff we talked about especially the P!=NP and how it affects computers other than some problems will take a really really really long time to do but ill giv it a shot

    #1 i had no idea but from reading the other post i know that knuth did tex not latex

    #2 a very long time and since the others did the math im not gonna restate it but i understand why its so long

    #3 im guessin if you set them equal to each other you should get like 38 so he'll beat you up to 38 items but afterwards youll be faster

    #4 since the equation is 2^n and your multiplying by two each time that means your doubling the time every time n increases by one so if you double the speed of processing then itll only add 1 to n

  10. 0. I loved the idea of the Hanoi Towers. I feel bad though for the priests. Their homework (learning how to move the towers) must take longer then mine, after a few levels...

    1. Knuth invented TeX.

    2. Well if Chuck Norris were to do it, I would estimate that it would take a few days... but like everyone else said, over 584,542,046,091 years.

    3. At 1st I just plugged them straight into my calculator, but I did not get 38. Then I took another look and soon got 38 after google-ing how to cancel the exponents.

    4. Wouldn't it only be able to solve k+1 more steps? Because the problem doubles every step, and his machine was only doubled once. I think it is time for a new algorithm for my friend there...

  11. 0. I wish I could say that I understood a lot of the math we talked about in class on Friday. I understand the concepts, but I don't know how to do them I suppose. I remember that we talked about P vs. NP and how it is key to using computers to solve a lot of problems in computer science. Where NP are the problems, P is a subset of NP which are easily solvable and verifiable problems, and NP-complete are the hardest of the hard problems. People are trying to prove that P = NP and no one has been able to do so yet. We talked the tower of Hanoi and the priests and how when they solve the problem, it's the end of the world. Also, how it's very likely they won't complete it in our life times.

    1. Knuth invented TeX and not LaTeX. TeX is more low level programming where LaTeX has more high level commands, which makes it easier to use

    2. I understand the equation used to solve and the math has been done, so I as well will not repeat it :)

    3. I didn't take the time to do it by hand, so I used my graphing calculator. It intersects at about 38.

    4. I don't quite understand the math for number 4 :(

  12. 0. What I got of the lecture on Friday was that 2^n is a computer scientist nightmare, if class P problem could be solved in polynomial time in the size of the input then it is considered an "easy problem", if you can check the correctness of a solution in polynomial time then it is in class NP, and all polynomial problems are also NP problems.

    1. Knuth inevented TeX. I looked at this web site:

    2. (2^64)-1= 1.844674407E19
    {Thank goodness for calculators}

    3. Once again, thank goodness for calculator, I got around 38.

    4. After reading problem four, I would definitely need to see how this is solved. I tried to figure it out but I think I confused myself in the process. I also think I need a little more math lectures to understand it.

  13. 1.Apparently, as stated by others, Knuth invented Tex. Search it up…and you’ll come to find that that is indeed accurate.

    2.After doing some research, 18,446,744,073,709,551,615 turns to complete this puzzle. After proper calculation, which you can see from Greg’s post, you should come out to about 585 billion years.

    3.I don’t have a calculator so it would be pretty time consuming, in my opinion. Greg had the right idea with graphing it though. That should tell you where you’ll catch up and beat your friend.

    4.I had the same idea as people on here. Since the 2^n increases way too high, a better computer probably wouldn’t help all that much. It’s just the equation that sucks so much…..

  14. Last Friday I understood everything except for the math part for algorithms. :(
    I’ve haven’t learn anything about computer coding or programming so maybe that’s why.
    I found very interesting the idea of the Hanoi towers and how it all relates.

  15. I didnt understand much from the discussion last friday. The algorithms and most of the math is very confusing. i agree with gnovoa that the towers of hanoi was very interesting especially about the story behind it.

  16. 0. I understood part of the discussion today, but the P = NP got a little confusing.
    1. Knuth invented TeX.
    2. with 2^64 - 1 moves, it would take just under 585 billion years
    3. 38
    4. I'm clueless.


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