Algorithms Design – Chapter 2, Exercise 8

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

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

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

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

On 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 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” →

Algorithms Design – Chapter 2, Exercise 4

On By pdinizIn Algorithms Design, Book, Solved Exercise1 Comment

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 4

Question:

Take the following list of functions and arrange them in ascending order of growth rate. That is, if function g(n) immediately follows function f(n) in your list, then it should be the case that f(n) is O(g(n)).

g1(n) = 2^{\sqrt {\log {n}}}

g2(n) = 2^n

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

Algorithms Design – Chapter 2, Exercise 3

On By pdinizIn Algorithms Design, Book, Solved Exercise1 Comment

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 3

Question: Take the following list of functions and arrange them in ascending order
of growth rate. That is, if function g(n) immediately follows function f(n)
in your list, then it should be the case that f(n) is O(g(n)).

f1(n) = n^{2.5} = \sqrt [2] {n^5}

f2(n) = \sqrt{2n}

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

Algorithms Design – Chapter 2, Exercise 2

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

Question: Suppose you have algorithms with the six running times listed below.
(Assume these are the exact number of operations performed as a function
of the input size n.) Suppose you have a computer that can perform
10^{10} operations per second, and you need to compute a result in at most
an hour of computation. For each of the algorithms, what is the largest
input size n for which you would be able to get the result within an hour?

(a) n^2

(b) n^3

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