CLRS Exercise 15.1-3 Rod Cutting Problem with cost

My Macroeconomics class starts to talk about dynamic optimization this week, so I think it might be a good idea for me to jump ahead to work on some dynamic programming problems in CLRS books. Knowing how to formulate a problem in a recursive manner is the key in this type of problems, but for programming (here I mean computer programming), it takes more thinking. In this case, the rod cutting problem is easy to formulate: \begin{equation*} \begin{aligned} & r(n,c) = \underset{I}{\text{maximize}} & & \sum\limits_{i \in I} p_i + r(n-i,c) - |I| * c\\ & \text{subject to} & & \sum\limits_{i \in I} i = n. \end{aligned} \end{equation*} That is we want to find a set \( I\) such that the objective function is maximized. In dynamic programming terminology, \( r(n,c)\) is called the value function, and \(n,c\) are the state variables. Our control variable is the set \(I\). What follows is the code that solves this problem. Things to notice.

• r and s have size n+1. These two arrays solve problems of size 1 up to n, the solution when size =0 is trivially set to 0.
• s[i+1] = j+1. This feels odd, but it is to conform to the interpretation of the point above. So s[i] gives us the cut that we need when the problem size is i.

import numpy as np
def rod_cutting_with_cost(p, n,c):
    r = [0 for i in range(n+1)]
    s = [0 for i in range(n+1)]
    
    for i in range(n):
        q = -np.inf
        for j in range(i+1):
            if j == i:
                if q < p[j] + r[i-j]:
                    q = p[j] + r[i-j]
                    s[i+1] = j+1
            else:
                if q < p[j] + r[i-j] - c:
                    q = p[j] + r[i-j] - c
                    s[i+1] = j+1
        r[i+1] = q
    return r,s

def print_cuts(s,n):
    i = n
    print i-s[i]
    i = s[i]
    while s[i] != i:
        print i-s[i]
        i = s[i]

p = [1,5, 8, 9, 10, 17,17,20,24,30]
print rod_cutting_with_cost(p,10,0)
print rod_cutting_with_cost(p,10,1)
print rod_cutting_with_cost(p,10,2)
print rod_cutting_with_cost(p,10,3)

CLRS Chapter 2.3.1 Merge Sort Implementation in Python

After reading this chapter, I would love to get my hand dirty and work out the mergesort in python. It ended up taking me almost and hour to implement this algorithm. There are several things that caught me unguarded.

• np.floor cannot be used in this case as it returns a float number which cannot be used in the range function.
• range function is inclusive on the left not the right. so range(1,4) gives you [1,2,3].
• Indexing also messes things up. Pay attention to the indexing. I find indexing starting from 1 to be more natural for the function argument.

import numpy as np
def merge(A,p,q,r):
    L = [A[i] for i in range(p-1,q)
    R = [A[i] for i in range(q,r)]
    #Add in sentinel
    L.append(np.inf)
    R.append(np.inf)
    for i in range(p-1,r):
        if L[0] < R[0]:
            A[i] = L[0]
            L.pop(0)
        else:
            A[i] = R[0]
            R.pop(0)
            
def mergesort(A,p,r):
    if p < r:
        q = (p+r)/2
        print q
        mergesort(A,p,q)
        mergesort(A,q+1,r)
        merge(A,p,q,r)

z = [0,3,2,1,4,5,8]
mergesort(z,1,len(z))
z

CLRS Exercise 2.1.4

Consider the problem of adding two n$n$-bit binary integers, stored in two n$n$-element arrays A$A$ and B$B$. The sum of the two integers should be stored in binary form in an (n+1)$(n+1)$-element array C$C$. State the problem formally and write pseudocode for adding the two integers.

This is an inefficient python implementation of the problem.

def add(A,B):
    n = len(A)
    C = [0 for x in range(n+1)]
    carry = 0
    A.insert(0,0)
    B.insert(0,0)
    for i in range(n,-1,-1):
        z = A[i] + B[i] + carry
        if z == 0:
            C[i] = 0
        elif z == 1:
            C[i] = 1
        elif z == 2:
            C[i] = 0
            carry = 1
        elif z == 3:
            C[i] = 1
            carry = 1
        else:
            raise "Something went wrong"
    return C

add([1,1,1],[1,1,1])