Cutting a Rod

Problem : 

Assume a company buys long steel rods and cuts them into shorter rods for sale to its customers. If each cut is free and rods of different lengths can be sold for different amounts, we wish to determine how to best cut the original rods to maximize the revenue.

Solution :

Counting Boolean Parenthesizations

Counting Boolean Parenthesizations: You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example, there are 2 ways to parenthesize 'true and false xor true' such that it evaluates to true.

The cost is :
checking subwords of size 1 + checking subwords of size 2 + ... + checking subwords of size N
= N + N-1 + 2*(N-2) + 2*(N-2) + .. + (N-1)*(1)
= O(N^3)
Auxiliary Space: O(n²)

Balanced Partition

Balanced Partition: You have a set of n integers each in the range 0 ... K. Partition these integers into two subsets such that you minimize |S1 - S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.

Equal Partition : 
Given a set of integers we need to find out all subsets of it which have sum equal to a number. Generic case would be given a set of integers and an integers S, find all subsets which have sum equal to S.
Note :  We can achieve this solution by little modification of above problem

Knapsack problem

Integer Knapsack Problem (Duplicate Items Forbidden): This is the same problem as the example above, except here it is forbidden to use more than one instance of each type of item.

Building Bridges

Building Bridges : Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a(1) ... a(n) and n cities on the northern bank with x-coordinates b(1) ... b(n). You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city i on the northern bank to city i on the southern bank. (Note: this problem was incorrectly stated on the paper copies of the handout given in recitation.)

Box Stacking

Box Stacking :  You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.

Longest Increasing Subsequence

Longest Increasing Subsequence :  Given a sequence of n real numbers A(1) ... A(n), determine a subsequence (not necessarily contiguous) of maximum length in which the values in the subsequence form a strictly increasing sequence.

Maximum Value Contiguous Subsequence :  Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized.

Kadane's algorithm

Kadane's algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position. Thus, the problem can be solved with the following code, expressed here in Python:

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Edit distance

Edit Distance Calculation : 

Edit Distance Algorithm : 

Minimum number of jumps to reach last element