Algorithms Design – Chapter 2, Exercise 8

On August 15, 2013September 30, 2013 By pdinizIn Algorithms Design, Book, Solved Exercise5 Comments

I’m having a hard time trying to find the solutions for this book on the web, so, to help others interested, i’m sharing what i’ve managed to solve at the moment =).

This is a solved exercise from the book “Algorithms Design” from Jon Kleinberg and Éva Tardos. All the answers / solutions in this blog were made from me, so it may contain errors, please check with your instructor in order validate it.

Algorithms Design – Chapter 2, Exercise 8

Question:

You’re doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with n rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call, this the highest safe rung.

It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung n/4 or 3n/4 depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer.

Continue reading “Algorithms Design – Chapter 2, Exercise 8” →

Algorithms Design – Chapter 2, Exercise 7

On August 8, 2013December 26, 2013 By pdinizIn Algorithms Design, Book, Solved Exercise6 Comments

I’m having a hard time trying to find the solutions for this book on the web, so, to help others interested, i’m sharing what i’ve managed to solve at the moment =).

Algorithms Design – Chapter 2, Exercise 7

Question: There’s a class of folk songs and holiday songs in which each verse consists of the previous verse, with one extra line added on. “The Twelve Days of Christmas” has this property; for example, when you get to the fifth verse, you sing about the five golden rings and then, reprising the lines from the fourth verse, also cover the four calling birds, the three French hens, the two turtle doves, and of course the partridge in the pear tree. The Aramaic song “Had gadya” from the PassoVer Haggadah works like this as well, as do many other songs.

Continue reading “Algorithms Design – Chapter 2, Exercise 7” →

Algorithms Design – Chapter 2, Exercise 6

On July 19, 2013July 19, 2013 By pdinizIn Algorithms Design, Book, Solved Exercise2 Comments

I’m having a hard time trying to find the solutions for this book on the web, so, to help ohers interested, i’m sharing what i’ve managed to solve at the moment =).

Algorithms Design – Chapter 2, Exercise 6

Question: Consider the following basic problem. You’re given an array A consisting A[n]. You’d like to output a two-dimensional n-by-n array B in which B[i,j] (for i <j) contains the sum of array entries A[i] through A[j]–that is, the sum A[i] +A[i + 1] +…+ A[j]. (The value of array entry B[i,j] is left unspecified whenever i >= j, so it doesn’t matter what is output for these values.) Here’s a simple algorithm to solve this problem.

Continue reading “Algorithms Design – Chapter 2, Exercise 6” →

Algorithms Design – Chapter 2, Exercise 5

On July 18, 2013September 2, 2013 By pdinizIn Algorithms Design, Book, Solved Exercise5 Comments

I’m having a hard time trying to find the solutions for this book on the web, so, to help others interested, i’m sharing what i’ve managed to solve at the moment =).

Algorithms Design – Chapter 2, Exercise 5

Question: Assume you have functions f and g such that f(n) is O(g(n)). For each of the following statements, decide whether you think it is true or false and give a proof or counterexample.

(a) $\log{f(n)}$ is $O({\log{g(n)}})$