myininaya
  • myininaya
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.
Computer Science
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
myininaya
  • myininaya
I would like if you could treat me as if I were dumb.
myininaya
  • myininaya
|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
myininaya
  • myininaya
dynamic algorithm |dw:1329374475415:dw|

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

myininaya
  • myininaya
so here we don't have to start from scratch
myininaya
  • myininaya
i think that is what it is saying we don't have to start from scratch anyways
myininaya
  • myininaya
|dw:1329374645988:dw| then for some reason the inputs are arranged in a different order on the tree
myininaya
  • myininaya
i think it would make sense to say 15 is a random pick
myininaya
  • myininaya
oops and then the inputs are arranged again |dw:1329374799217:dw|
myininaya
  • myininaya
and we throw 36 back in the mix
myininaya
  • myininaya
i like static better lol it is easier to undertand
chris
  • chris
Hmmmm, I'm lost! lol
myininaya
  • myininaya
do you have any example of dynamic algorithm that you do understand?
myininaya
  • myininaya
http://www.mpi-sws.org/~bhatotia/pubs/talk/HotCloud-11.pdf
myininaya
  • myininaya
I guess I just don't know how he is arranging the inputs of the tree
chris
  • chris
hee hee looking.
chris
  • chris
ok so yes, 15 is a random number
myininaya
  • myininaya
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)
myininaya
  • myininaya
i wonder why the tree is chosen the way it is too begin with though
chris
  • chris
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)
chris
  • chris
now reading about heap trees!
chris
  • chris
http://en.wikipedia.org/wiki/Binary_heap
myininaya
  • myininaya
This is a nice little example. It isn't that complicated but I'm sure for inputs it would be ugly
myininaya
  • myininaya
for more inputs*
maitre_kaio
  • maitre_kaio
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
chris
  • chris
Thanks maitre! Great resource =). myin - also check this out, through at least slide 23 http://www.slideshare.net/TraianRebedea/adc-4
chris
  • chris
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)
chris
  • chris
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)
chris
  • chris
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
myininaya
  • myininaya
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!
myininaya
  • myininaya
if you guys think of anything else you want to say please feel free to jot it down
chris
  • chris
lol, well, only that you'll be a genius once you understand this whole presentation haha
chris
  • chris
(I do not)
myininaya
  • myininaya
i notice slide 17-21 look like a mess to me too lol
myininaya
  • myininaya
i have to look through it some more and just do some searches and hopefully find what i'm looking for
myininaya
  • myininaya
so chris you are rating this presentation as hard?
myininaya
  • myininaya
i honestly don't know if it is considered to be hard by normal computer people lol everything is hard to me
myininaya
  • myininaya
normal meaning people who actually have a bs in computer science (compare to my math degree i know nothing )
chris
  • chris
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.
myininaya
  • myininaya
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
myininaya
  • myininaya
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
myininaya
  • myininaya
http://www.mpi-sws.org/~bhatotia/pubs/hotcloud-11.pdf this is the paper i'm reading
maitre_kaio
  • maitre_kaio
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.
myininaya
  • myininaya
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! :)

Looking for something else?

Not the answer you are looking for? Search for more explanations.