in Algorithm Design Manual - Solutions, Doing Books

The Algorithm Design Manual: Chapter 2

2-1. What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using the Big Oh notation.

function mystery(n) 
  r := 0
  for i := 1 to n − 1 do 
    for j := i + 1 to n do 
      for k := 1 to j do
        r := r + 1   
  return(r)

Solution: To find out what value is returned just represent this function mathematically and simplify it.

\sum_{i=1}^{n-1}\sum_{j=i+1}^n\sum{}_{k=1}^{j} 1
= \sum_{i=1}^{n-1}\sum_{j=i+1}^n j
= \sum_{i=1}^{n-1} (\frac{n(n+1)}{2} - \frac{i(i+1)}{2})
= \frac{1}{2} \sum_{i=1}^{n-1} (n^2 + n - i^2 - i)
= \frac{1}{2} ( (n-1)n^2 + (n-1)n - \sum_{i=1}^{n-1} i^2 - \frac{(n-1)n}{2})
= \frac{1}{2} {  ( n^3 - n) - (\frac{n(n+1)(2n+1)}{6} - n^2) - \frac{n^2 -n}{2} }
= \frac{1}{2} { \frac{1}{6} * (6n^3 - 6n - (2n^3+n^2+2n^2+n-6n^2)  - 3n^2 +3n)    }
= \frac{1}{12} { 6n^3 - 6n - 2n^3 - n^2 - 2n^2 - n + 6n^2 - 3n^2 + 3n }
= \frac{1}{12} (4n^3 - 4n) = \frac{n^3 - n}{3}

The complexity is O(n^3).

2-10. Prove that n^3 - 3n^2 - n + 1 = \Theta(n^3).
Solution: O(n^3): For c > 1: n^3 - 3n^2 - n + 1 \leq c \cdot n^3.
Omega(n^3): For 0 \leq c \leq 1: n^3 - 3n^2 - n + 1 \geq c \cdot n^3.

2-34. Assume that Christmas has n days. Exactly how many presents did my “true love” send me? (Do some research if you do not understand this question.)
Solution: I made this table of the first three days:

Day    Presents                        \sum of Presents
1       1                               1
2       1 + 2                           1 + 1 + 2
3       1 + 2 + 3                       1 + 1 + 2 + 1 + 2 + 3

We can break this down into sub steps. On the ith day we get p_i = \sum_{k=1}^{i} k presents.
The total amount of presents is: \sum_{i=1}^{n} p_i = \sum_{i=1}^{n} \sum_{k=1}^{i} k = \sum_{i=1}^{n} \frac{i^2+i}{2}
We can be simplified as:
= \frac{1}{2}  { \sum_{i=1}^{n} i^2 + \sum_{i=1}^{n} i  } = \frac{1}{2}  { \frac{n(n+1)(2n+1)}{6}  + \frac{3n^2 + 3n)}{6} }
= \frac{1}{12}  { 2n^3+3n^2+n + 3n^2 + 3n}
= \frac{2n^3 + 6n^2 + 4n}{12} = \frac{n^3+3n^2+2n}{6}

2-39. Prove the following identities on \logarithms:
(a) Prove that \log_a(xy) = \log_a x + \log_a y
(b) Prove that \log_a x^y = y \log_a x
(c) Prove that \log x = \frac{\log_b x}{\log_b a}
(d) Prove that x^{\log_b y} = y^{\log_b x}
Solution:
(a) The first proof is straight forward: a^{\log_a(x) + \log_a(y)} = a^{\log_a(x)} \cdot a^{\log_a(y)} = x \cdot y = a^{\log_a(xy)}
(b) The trick here is to see that x^y = \prod_{i=1}^{y} x. Therefore we can use the identity from (a): \log_a x^y = \log_a (\prod_{i=1}^{y} x) = \sum_{i=1}^{y} \log_a x = y \log_a x
(c) Here you try to form around a variable (z) to get the right term:
\log_a x = z \Leftrightarrow a^{\log_a x} = a^z \Leftrightarrow x = a^z
\log_b x = \log_b a^z \Leftrightarrow \log_b x = z \log_b a
\frac{\log_b x}{\log_b a} = z = \log_a x
(d) The last one is quite easy. x^{\log_b y} = y^{\log_b x}. Now we have just to \log_b on the equation and use the identity from (b) and we get: \log_b y \cdot \log_b x = \log_b x \cdot \log_b y

2-44. We have 1,000 data items to store on 1,000 nodes. Each node can store copies of exactly three different items. Propose a replication scheme to minimize data loss as nodes fail. What is the expected number of data entries that get lost when three random nodes fail?
Solution: My first idea was a kind of a binary tree which then evolved into this:

The idea is to save on each node the value of the corresponding left and right nodes and of course the main value. In the last nodes we got some free space were we can save item10 because it isn’t backed up yet.
So what happens if three nodes fall out? There are various scenarios.
1. 3 corresponding nodes fall out, e.g. Node 1, 2 and 3. Then Item 11 and 12 are completely lost. (Remember Item10 is saved further down again)
2. A node and its parent fall out, e.g. Node 1 and 2. Here we just lose Item 11.
3. A random node falls out, e.g. Node 3. No problem whatsoever. We can retrieve Item12 from Node 1.

We got about 500 free storages in the last row of nodes which could be used to backup half of the total items again. Which would reduce our loss further

2-46. You have a 100-story building and a couple of marbles. You must identify the lowest floor for which a marble will break if you drop it from this floor. How fast can you find this floor if you are given an infinite supply of marbles? What if you have only two marbles?
Solution: The first case with infinite supply of marbles is very easy. We just do a binary search on the story building, i.e. we need about 7 marbles.
The second case is a bit more demanding. I would start to try to minimize the possible interval as much as possible by starting with a marble in the middle of the whole interval, i.e. at the 50th story.
If it’s broken we have to work our way up from 1 to at max 50.
If it’s still alive we can cut the next interval into half till we find our floor.

2-50. A Ramanujam number can be written two different ways as the sum of two cubes—i.e. , there exist distinct a, b, c, and d such that a^3 +b^3 = c^3 +d^3. Generate all Ramanujam numbers where a, b, c, d < n. Solution:

def RamanujamNumbersBF(n):
    numbers = []
    for a in xrange(0, n):
        for b in xrange(0, n):
            for c in xrange(0, n):
                for d in xrange(0, n):
                    if a != b and a != c and a != d and b != c and b != d and c != d:
                        if a ** 3 + b ** 3 == c ** 3 + d ** 3:
                            numbers.append((a, b, c, d))
    
    return numbers


def RamanujamNumbersDP(n):
    numbers = []
    Ds = dict()
    
    # Init List
    for d in xrange(0, n ** 3):
        Ds[d] = False
    
    # Fill list
    for d in xrange(0, n):
        Ds[d**3] = d

    for a in xrange(0, n):
        for b in xrange(0, n):
            for c in xrange(0, n):

                if a != b and a != c and b != c:
                    d = a ** 3 + b ** 3 - c ** 3

                    if a != d and b != d and c != d and d >= 0 and d < n ** 3:
                        if Ds[d] != False:
                            numbers.append((a, b, c, Ds[d]))
                
    return numbers           
        




print "Brute Force"
print RamanujamNumbersBF(50)

print "Dynamic Programming"
print RamanujamNumbersDP(50)

The DP approach works must faster than raw BF which you can see quite fast because complexity of BF is O(n^4) and DP only takes O(n^3).

Write a Comment

Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  1. 2-44 you must prove it mathematically why having 3 copies in 3 different random buckets is the best solution. forget about the implementation. the question is not how you would implement it.