Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

myininaya Group Title

Anyone interested in talking about dynamic algorithms vs static algorithms. I mean can anyone give me an example of each maybe by drawing a tree or something.

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    I would like if you could treat me as if I were dumb.

    • 2 years ago
  2. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    |dw:1329374236354:dw| so this is a static algorithm re-computes from scratch in time O(n) we change the max input to 15 but why 15 how is 15 found? is it just a random number I wonder?... I mean does the algorithm choose a random number to replace the max

    • 2 years ago
  3. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    dynamic algorithm |dw:1329374475415:dw|

    • 2 years ago
  4. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    so here we don't have to start from scratch

    • 2 years ago
  5. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i think that is what it is saying we don't have to start from scratch anyways

    • 2 years ago
  6. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    |dw:1329374645988:dw| then for some reason the inputs are arranged in a different order on the tree

    • 2 years ago
  7. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i think it would make sense to say 15 is a random pick

    • 2 years ago
  8. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    oops and then the inputs are arranged again |dw:1329374799217:dw|

    • 2 years ago
  9. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    and we throw 36 back in the mix

    • 2 years ago
  10. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i like static better lol it is easier to undertand

    • 2 years ago
  11. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Hmmmm, I'm lost! lol

    • 2 years ago
  12. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    do you have any example of dynamic algorithm that you do understand?

    • 2 years ago
  13. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    http://www.mpi-sws.org/~bhatotia/pubs/talk/HotCloud-11.pdf

    • 2 years ago
  14. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    I guess I just don't know how he is arranging the inputs of the tree

    • 2 years ago
  15. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    hee hee looking.

    • 2 years ago
  16. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    ok so yes, 15 is a random number

    • 2 years ago
  17. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    wait maybe...we go by the max of the next level 31>25 so we move 31 up and 19 up and put 15 on the bottom (the other side remains unchanged)

    • 2 years ago
  18. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i wonder why the tree is chosen the way it is too begin with though

    • 2 years ago
  19. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    the point is basically that for static algorithms, you don't use the results of previous computations as information for future results. for dynamic algorithms you can do so, and an example of this is a heap (tree by definition, not the memory kind) http://en.wikipedia.org/wiki/Heap_(data_structure)

    • 2 years ago
  20. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    now reading about heap trees!

    • 2 years ago
  21. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    http://en.wikipedia.org/wiki/Binary_heap

    • 2 years ago
  22. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    This is a nice little example. It isn't that complicated but I'm sure for inputs it would be ugly

    • 2 years ago
  23. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    for more inputs*

    • 2 years ago
  24. maitre_kaio Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Hello, I'm currently following the OCW Intro Computer Science and Dynamic programming is one of the topics studied. You could try to see those videos: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-12 http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-13 To me, the example that shows clearly what dynamic programmings is about is the Fibonnaci sequence program. There is a good explanation here: http://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence

    • 2 years ago
  25. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks maitre! Great resource =). myin - also check this out, through at least slide 23 http://www.slideshare.net/TraianRebedea/adc-4

    • 2 years ago
  26. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    it's dynamic because heap insertion is determined in a bottom-up fashion of smaller sub problems, and an optimal state is stored after each run (making it dynamic)

    • 2 years ago
  27. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    so yes, 15 is just the random example of changing input, and showing you one algorithm that just goes through the whole list to find the right spot, and another example that has the precomputation stored that in the case of heaps allows you to skip to the end and compare upwards (> or < parent) for a max of O(log n)

    • 2 years ago
  28. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I guess the author is going on to describe why dynamic algorithms are good because they can be distributed - each machine only needs some of the information

    • 2 years ago
  29. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Ok thanks for the links you guys and confirming 15 is random. This is my 2nd semester of learning anything "computer sciency" hopefully i can learn enough about clouds and cryptography (definitely including ABE) and secure computation to construct my own crypto-algorithm i feel so behind the other phd students that my computer science adviser has since they know all of these terms :( but i'm gonna try really hard to learn all that i can so thank you guys so much you guys are the best!

    • 2 years ago
  30. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    if you guys think of anything else you want to say please feel free to jot it down

    • 2 years ago
  31. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    lol, well, only that you'll be a genius once you understand this whole presentation haha

    • 2 years ago
  32. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    (I do not)

    • 2 years ago
  33. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i notice slide 17-21 look like a mess to me too lol

    • 2 years ago
  34. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i have to look through it some more and just do some searches and hopefully find what i'm looking for

    • 2 years ago
  35. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    so chris you are rating this presentation as hard?

    • 2 years ago
  36. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i honestly don't know if it is considered to be hard by normal computer people lol everything is hard to me

    • 2 years ago
  37. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    normal meaning people who actually have a bs in computer science (compare to my math degree i know nothing )

    • 2 years ago
  38. chris Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Well good luck myin! I'm off to sleep! This is a tough one - is there a full paper? Combiners are a bit vague to me. "precompute" reduce. Haha, well I think you need to be at least very well versed in algorithms, and at least understand map reduce as exists, and figure out what the combiners exactly are precomputing, the stored computation is the big gain.

    • 2 years ago
  39. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    yes i have been looking at the full paper also he didn't have these drawings described in there (or if he did I misunderstood ) i will keep rereading

    • 2 years ago
  40. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    it will be okay if i don't know everything i will just have to lead the discussion it will be okay! :) thank you guys so much again you are the best for helping me

    • 2 years ago
  41. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    http://www.mpi-sws.org/~bhatotia/pubs/hotcloud-11.pdf this is the paper i'm reading

    • 2 years ago
  42. maitre_kaio Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    I just read the link myininaya posted earlier. Finding the max of an array is typically a problem where you can use dynamic programming because it fills the two requirements: 1. Optimal substructure: you can find the optimal solution of the problem by finding the optimal solution of its subproblems. It's easy to see that you can divide the array into subarrays, find the max of each subarrays and combine the solutions until you find the max of the array. 2. Overlapping subproblems. You can walk the tree recursively.

    • 2 years ago
  43. myininaya Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    Thanks again you guys. I stayed up all night looking at some stuff posted here and I had a good enough understanding of the paper to give what I would call a pretty good discussion on the topic. You guys rule! :)

    • 2 years ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.