Algorithms Design – Chapter 2, Exercise 8


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”

Sponsored Post Learn from the experts: Create a successful blog with our brand new courseThe WordPress.com Blog

WordPress.com is excited to announce our newest offering: a course just for beginning bloggers where you’ll learn everything you need to know about blogging from the most trusted experts in the industry. We have helped millions of blogs get up and running, we know what works, and we want you to to know everything we know. This course provides all the fundamental skills and inspiration you need to get your blog started, an interactive community forum, and content updated annually.

Algorithms Design – Chapter 2, Exercise 7


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 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


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 =).

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 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


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 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)}})

(b) 2^{f(n)} is O({2^{g(n)}})

(C) {f(n)}^2 is O({g(n)}^2)

Continue reading “Algorithms Design – Chapter 2, Exercise 5”