The Algorithm Design Manual: Chapter 1

Yeah, new book series! I had laying this book around for about two and an half years and only read about a quarter of it but never worked through it. So, I decided to work through it and post interesting problems and solutions online.
The book consists of two parts. The first part treats the algorithmic basics. The second part is just a reference of different algorithmic problems and ways to solve it. I won’t cover the second part, mainly because there are no exercises.

1-1. Show that a + b can be less than min(a, b).
Solution: 1-1. For any a, b < 0: a + b < \text{min}(a,b). For example:
a = -5, b = -3. a + b = -8 < \text{min}(-5, -3) = -5.

1-2. Show that a × b can be less than min(a, b).
Solution For example for a = -5 and b = 3 the result is -5 * 3 = -15 < \text{min}(-5, 3) = -5.

1-5. The knapsack problem is as follows: given a set of integers S = {s_1, s_2, . . . , s_n}, and a target number T, find a subset of S which adds up exactly to T. For example, there exists a subset within S = {1,2,5,9,10} that adds up to T = 22 but not T = 23.
Find counterexamples to each of the following algorithms for the knapsack problem. That is, giving an S and T such that the subset is selected using the algorithm does not leave the knapsack completely full, even though such a solution exists.
(a) Put the elements of S in the knapsack in left to right order if they fit, i.e. the first-fit algorithm.
(b) Put the elements of S in the knapsack from smallest to largest, i.e. the best-fit algorithm.
(c) Put the elements of S in the knapsack from largest to smallest.
(a) S = {1, 2}, T = 2
(b) S = {1, 2}, T = 2
(c) S = {2, 3, 4}, T = 5

1-16. Prove by induction that n3 + 2n is divisible by 3 for all n ≥ 0.
Solution: The base case is n = 0, 0^3 + 2*0 = 0 \text{ mod } 3 = 0 which is true.
We can assume that this holds up to n. For n + 1 we get:
(n+1)^3 + 2(n+1) = n^3 + 3n^2 + 3n + 1 + 2n + 1
= n^3 + 3n^2 + 5n + 2 = (n^3 + 2n) + (3 (n^2 + n)).
The first term is parenthesis is our assumption and the second term is obviously divisible by 3, therefore we showed that our assumption is true.

1-26. Implement the two TSP heuristics of Section 1.1 (page 5). Which of them gives better-quality solutions in practice? Can you devise a heuristic that works better than both of them?

from random import randint

class Point:
    def __init__(self, ID, x, y):
        self.ID = ID
        self.x = x
        self.y = y

    def distance(self, other):
        return ( (self.x - other.x) ** 2 + (self.y - other.y) ** 2 ) ** 0.5

def closestPoint(P, visited, p):
    shortestDistance = float("Inf")
    shortestPoint = None

    for pi in P:
        if visited[pi.ID] == False:
            if p.distance(pi) < shortestDistance:
                shortestDistance = p.distance(pi)
                shortestPoint = pi

    return shortestPoint

def nearestNeighbour(P):
    visited = [False] * ( len(P) + 1) # ID starts with 1
    p = P[0]

    visited[0] = True # not existing
    visited[1] = True # first node

    i = 0

    finalPath = [p]

    while False in visited:
        i += 1
        pi = closestPoint(P, visited, p)

        if pi == None: # last point

        visited[pi.ID] = True

        p = pi


    return finalPath

def closestPair(P):
    n = len(P)
    finalPath = []

    vertexChain = [[p] for p in P]

    d = float("INF")
    for i in xrange(1, n-1):
        d = float("INF")
        for i1, v1 in enumerate(vertexChain):
            for i2, v2 in enumerate(vertexChain):
                if i1 != i2:
                    s = v1[-1]
                    t = v2[-1]

                    if s.distance(t) <= d:
                        sm = i1
                        tm = i2
                        d = s.distance(t)

        vertexChain[sm] += vertexChain[tm]

    vertexChain[0] += vertexChain.pop(1)

    return vertexChain[0]
    return finalPath

def getPathSum(P):
    distance = 0
    for i in xrange(1, len(P)):
        distance += ((P[i].x - P[i-1].x) ** 2 + (P[i].y - P[i-1].y) ** 2)

    return distance ** 0.5

P_rect = [Point(1, 0, 0), Point(2, 0, 5), Point(3, 5, 0), Point(4, 5, 5)] 
P_line = [Point(1, 0, 5), Point(2, 0, 0), Point(3, 0, 10), Point(3, 0, 15)]
P_rand = [Point(i, randint(0, 15), randint(0,15)) for i in xrange(0, 10)] 

print "**Rectangle**"
print "> NearestNeighbour: %i" % getPathSum(nearestNeighbour(P_rect))
print "> ClosestPair: %i" % getPathSum(closestPair(P_rect))

print "**Line**"
print "> NearestNeighbour: %i" % getPathSum(nearestNeighbour(P_line))
print "> ClosestPair: %i" % getPathSum(closestPair(P_line))

print "**Rand**"
print "> NearestNeighbour: %i" % getPathSum(nearestNeighbour(P_rand))
print "> ClosestPair: %i" % getPathSum(closestPair(P_rand))

NearestNeighbour createst shorter paths for small input graphs. For midsize input paths and big input graphs closestPair creates smaller paths. However nearestNeighbour is much faster. In conclusion, it depends on the application which heuristic is more suitable.

1-28. Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.
Solution: A simple way to perform integer division is substracting the divisor and counting each substraction. This only works for positive numbers. (more in the comments)

def divideBySub(a, b):
    count = 0
    while a >= 0:
        a -= b
        count += 1

    return count

If we can find a bigger divisor we could speed it up. An easy way is to multipy the divisor by itself as long as it divides the denominator with a rest.

def divideBySubFaster(a, b):
    countB = 0
    lastB = b

    while a % b == 0:
        lastB = b
        b += b
        countB += 1

    b -= lastB # revert last change
    countB -= 1 # revert last change

    result = divideBySub(a, b)
    for i in xrange(0, countB):
        result += result
    return result

This works quite nice and can speed up the process substantially.

SPOJ: 8132. Street Trees

A group of trees is planted along a straight line.

KOI is planning to plant more trees so that the distance between two adjacent trees is equal for all trees.

For simplicity, each tree can only be planted on an integer coordinate.

Problem: Sphere Online Judge (SPOJ) – Problem STREETR

To illustrate this problem I drew this small graphic:

The large trees are given and we have to find the small ones. You can see pretty fast that the maximum difference between trees is the minimum difference between already planted trees. But we’re not only looking for one arbitrary solution (which would be zero difference), we’re looking for the greatest difference or more generally the Greatest common divisor.

def gcd(a, b):
    if b == 0:
        return a
        return gcd(b, a % b)

def gcdList(lst):
    myGcd = gcd(lst[0], lst[1])
    for c in lst[1:]:
        myGcd = gcd(myGcd, c)

    return myGcd

N = int(raw_input())
diff = []
lastTree = int(raw_input())
for i in xrange(1, N):
    newTree = int(raw_input())
    diff.append(newTree - lastTree)
    lastTree = newTree

myGcd = gcdList(diff)

trees = map(lambda x: (x / myGcd) - 1, diff)
print sum(trees)

SPOJ: 3374. Scavenger Hunt

He does a poor job, though, and wants to learn from Bill’s routes. Unfortunately Bill has left only a few notes for his successor. Bill never wrote his routes completely, he only left lots of little sheets on which he had written two consecutive steps of the routes. […]
This made much sense, since one step always required something from the previous step. George however would like to have a route written down as one long sequence of all the steps in the correct order.

Problem: Sphere Online Judge (SPOJ) – Problem SCAVHUNT


scenarios = int(raw_input())

for i in xrange(0, scenarios):
    S = int(raw_input())

    myDict = dict()
    myRevDict = dict()

    for j in xrange(0, S - 1):
        fromLocation, toLocation = raw_input().split()
        myDict[fromLocation] = toLocation
        myRevDict[toLocation] = fromLocation

    # find start
    start = ""
    for key in myDict.keys():
        if key not in myRevDict:
            start = key
    # print message
    print "Scenario #%i:" % (i + 1)

    # print path
    currentKey = start
    for l in xrange(0, S - 1):
        print currentKey
        currentKey = myDict[currentKey]

    print currentKey
    print ""


SPOJ: 1268. CN Tower (Easy)

On the way, she stops in Toronto to do some sightseeing. The unfortunate thing about travelling is that everyone back home expects her to bring back pictures of everything. […] 351 m up the tower is the “360” rotating restaurant, which rotates a full 360 degrees every 72 minutes. From there, Christy can see the whole city, and take close-up pictures of all the landmarks using her fancy new 100x optical zoom camera. Since the restaurant itself rotates, she only needs to stand in one place to take pictures in all directions. […] Since the restaurant staff only realize she is a tourist once she starts taking pictures, we begin measuring the time required once she takes her first picture.

Problem: Sphere Online Judge (SPOJ) – Problem CNEASY

Solution: Afterwards this problem is really easy, however I first made it too hard. The trick is pretty easy we are looking for the biggest distance between each consecutive degree. To check the difference between the highest and the lowest I appended (lowest + 360) to the list of degrees. The + 360 helps to calculate the distance more easily. Afterwards just select the biggest difference and calculate the minimum time.

from math import ceil

for i in xrange(0, int(raw_input())):
    n = int(raw_input())
    degrees = []
    for i in xrange(0, n):

    degrees.append(degrees[0] + 360)
    maxDegrees = max([(degrees[i] - degrees[i-1]) for i in xrange(1, n + 1)])

    print "%i" % (ceil ((360 - maxDegrees) * 12))