01Knapsack in php

<?php
/* PHP is pass by value semantics.
   To pass by reference one uses the $& symbol for the
   parameters.
   Take the array of weights and array of benefits/value and
   try to infer the best possible combination for value M.
 */
    $b = array(50, 40, 30, 10);
    $w = array(3,   4,  6,  5);
    $b1 = array(4,   3,  6,  5);
    $w1 = array(3,   2,  5,  4);
    
    function listItems(array & $B, $n, $M)
    {
       $i = $n;
       $j = $M;  
       global $w, $b;
       $maxb = 0;
      
       while ($i > 0 && $j > 0)
       {
          if ($B[$i][$j] !=  $B[$i-1][$j])
          {
            print ("Take item number: $i ");
            echo "<BR/>\n";           
           
            $j = $j - $w[$i-1];
            $i = $i - 1;
            $maxb += $b[$i];
          }
          else 
            $i = $i - 1;
       }
       print ("Max benefit: $maxb ");
       echo "<BR/>\n";           
    }
   
    function printTable(array & $B, & $n, & $M)
    {
       $maxv = 0;
      
       $mw = 0;
       $mb = 0;
      
       for ($i = 0 ; $i <= $n; $i++)
       {
         for ($j = 0 ; $j <= $M; $j++)
         {
            printf("%02d ", $B[$i][$j]);
            if ($maxv < $B[$i][$j])
            {
               $mw = $i;
               $mb = $j;
               $maxv = $B[$i][$j];
            }           
         }
         echo "<BR/>\n";
       }
       echo "<BR/>\n";
      
       # Set the index where maximum exists
       $n = $mw;
       $M = $mb;
       printf("%02d \n", $B[$n][$M]); echo "<BR/>\n";
    }
   
    function knapsack01 (array & $w, array & $b, $M)
    {
        /* Two dimensional array to pre-compute */
        $B = array(array());
        $n = count($w);
       
        for ($indx = 0; $indx <= $n ; $indx++)
           $B[$indx][0] = 0;
  
        for ($indx = 0; $indx <= $M ; $indx++)
           $B[0][$indx] = 0;
      
        for ($i = 1; $i <= $n ; $i++)
        {
           for ($j = 0; $j <= $M ; $j++)
           {
              if ($w[$i-1] <= $j &&
                  ($B[$i-1][$j-$w[$i-1]] + $b[$i-1]) > $B[$i-1][$w[$i-1]])
              {
                 $B[$i][$j] = $B[$i-1][$j-$w[$i-1]] + $b[$i-1];             
              }
              else
                 $B[$i][$j] = $B[$i-1][$j];
           }
        }
        printTable ($B, $n, $M);
        listItems  ($B, $n, $M);
    }
   
    knapsack01 ($w, $b, 9);
?>

01 Knapsack in Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class KnapSack01 {
 
  List b = Arrays.asList(10, 40, 30, 50);
  List w = Arrays.asList(5, 4, 6, 3);
  private int B[][];
 
  public int getNum() { return w.size(); }
 
  public KnapSack01(int M)
  {
    doAlloc(w.size()+1, M+1);
    doAllot(w.size(), M+1);
    printTable(w.size()+1, M+1);
  }
 
  public static void main(String args[])
  {
    KnapSack01 ks = new KnapSack01(10);    
   
    ks.listItems(10);
  }
 
  public void listItems(int M)
  {
    int i = getNum();
    int k = M;
   
    while (i > 0 && k >0)
    {
      if (B[i][k] != B[i-1][k])
      {
        System.out.println(i + " is in the knapsack");
        i = i - 1;
        k = k - (int)w.get(i-1);
      }
      else
        i = i - 1;
    }
  }
 
  public void printTable(int n, int M)
  {
    for (int i = 0 ; i < n; i++)
    {
      for (int j = 0 ; j < M; j++)
        System.out.printf("%02d ", B[i][j]);
      System.out.println();
    }
  }
 
  public void doAlloc(int n, int M)
  {
    B  = new int[n][M];
   
    for (int i = 0 ; i < n; i++)
      B[i][0] = 0;
    for (int j = 0 ; j < M; j++)
      B[0][j] = 0;   
  }
 
  public void doAllot(int n, int M)
  {
    for (int i = 1 ; i <= n; i++)
    {
      for (int j = 0 ; j < M; j++) 
      {
        if ((int)w.get(i-1) <= j &&
            (((int)b.get(i-1) + B[i-1][j-(int)w.get(i-1)]) > B[i-1][(int)w.get(i-1)]))
        {
          B[i][j] = (int)b.get(i-1) + B[i-1][j-(int)w.get(i-1)];           
        }
        else
          B[i][j] = B[i-1][j];
      }     
    }
  }
}

Merging sorted arrays in Java

import java.util.Arrays;

public class MergingSortedArrays
{
  private int C[];
 
  public void doSpill()
  {
    System.out.println(Arrays.toString(C)); 
  }
 
  public MergingSortedArrays(int a[], int b[])
  {
    int i = 0, j = 0, k = 0;
   
    C = new int[a.length+b.length];
   
    while ( i < a.length || j < b.length)
    {
      System.out.println("Values: " + i + " " + j + " " +  k);
     
      if (i >= a.length)
      {
        C[k++] = b[j++];
      }
      else if (j >= b.length || a[i] < b[j])
      {
        C[k++] = a[i++];
      }
      else
      {
        C[k++] = b[j++];
      }
    }
  }
 
  public static void main(String args[])
  {
    int a[] = new int[] {8, 9, 9, 10, 10, 11, 12, 14};
    int b[] = new int[] {5, 6, 13, 37};
    MergingSortedArrays msr = new MergingSortedArrays(a,b);
   
    msr.doSpill();
  }
}

Merging sorted arrays in C

#include <stdio.h>
#include <stdlib.h>

/* Utility to spill the beans - print contents */
void spill(int *c, int len)
{
   int i;

   for (i = 0 ; i < len; i++)
      printf("%d ", c[i]);
   printf("\n");

}

/* The meat - If j index of second array crossed the maximum,
   of the second array, then populate with the first.
   Similarly, if the i index crossed the maximum of the first
   array, populate with the second.
   Else, populate the lesser of the two into the new array.
   For non-descending sort.
 */
int * mergesort(int A[], int la,  int B[], int lb)
{
    int i = 0, j = 0, k = 0;
    int *C = malloc(la + lb);

    while (i < la || j < lb)
    {
       if (j >= lb || (A[i] < B[j]))
       {
          C[k] = A[i];
          i++;
       }
       else
       {
          C[k] = B[j];
          j++;
       }
       k++;
    }
    return C;
}

int main()
{
    int A[] = {8, 9, 9, 10, 10, 11, 12, 14};
    int B[] = {5, 6, 13, 37};
    int *c;

    c = mergesort(A, sizeof(A)/sizeof(int), B, sizeof (B)/sizeof(B[0]));
    spill(c, sizeof(A)/sizeof(int) + sizeof (B)/sizeof(B[0]));
    return 0;
}

Linear sort for numbers in PHP

<?php
/* PHP is pass by value semantics.
   To pass by reference one uses the $& symbol for the
   parameters.
   Sorting numbers in a defined range 0 ... N-1 with no repeats
   Inspired from Programming Pearls : Jon Bentley
   O(n) linear cost.
   PHP does not support long bit arrays out of the box.
   Code assumption: 32-bits integer
 */
    $N = 1000000;
    $SHIFT = 5;
    $MASK  = 0x1f;
    $BITS  = 32;
    $TOPVAL = (1+$N/$BITS);
   
    function set (&$a, $i)
    {
       global $SHIFT;
       global $MASK;
      
       $shift = $i >> $SHIFT;   /* Which byte to set */
       $mask = $i & $MASK;      /* Which bit to set */
       $a[$shift] = $a[$shift] | (1 << $mask);
      
       return;
    }
   
    function get ($a, $i)
    {
       global $SHIFT, $MASK;
       return ( $a[$i >>$SHIFT] & (1 << ($i & $MASK)) );
    }
   
    function linearsort (array & $a)
    { 
        global $TOPVAL;
        $bitvec = [];
        $maxval = 0;
        $i = 0;
       
        for ($indx = 0; $indx < $TOPVAL ; $indx++)
        {
           $bitvec[$indx] = 0;
        }
       
       
        for ($indx = 0; $indx < count($a) ; $indx++)
        {
           if ($a[$indx] > $maxval) $maxval = $a[$indx];
              set($bitvec, $a[$indx]);
        }
         
        for ($indx = 0; $indx <= $maxval ; $indx++)
        {
           if (get($bitvec, $indx))
             $a[$i++] = $indx;
        }
    }

    $a = array(205, 10, 7, 5, 9, 8, 1, 2, 100);
    linearsort ($a);
    print_r ($a);
?>

Linear sort for range of numbers in Java

import java.util.BitSet;

/* Sorting numbers on disk
 * Linear sort
 * Inspired from Programming Pearls: Jon Bently
 * Java's ready availability of BitSet's makes
 * all the gory details of bit operations go away,
 * though essential.
 */
public class LinearPerfSort
{
  /* Printing routine */
  public void spill(int a[])
  {
    int indx;
    for (indx = 0 ; indx < a.length; indx++)
    {
      System.out.print(a[indx] + " ");
    }
    System.out.println();
  }
 
  public void doSort(int a[])
  {
    int indx= 0;
    BitSet bs = new BitSet(0);
   
    for (int i = 0; i < a.length; i++)
      bs.set(a[i]);
   
    for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1))
    {
      // guard on indx i here, just to guard from additional phony bits
      //if (indx < a.length) -- not required.
        a[indx++] = i;
    }
  }
 
  public static void main(String args[])
  {
    int arr[] = {205, 10, 7, 5, 9, 8, 1, 2, 100};
   
    LinearPerfSort lps = new LinearPerfSort();
    lps.doSort(arr);
    lps.spill(arr);
  } 
}

Linear sort for range of numbers in C

#include <stdio.h>
#include <stdlib.h>

/* Sorting numbers in a defined range 0 ... N-1 with
 * no repeats
 * Inspired from Programming Pearls : Jon Bently
 * O(n) linear cost.
 */

#define N           10000000
#define BITSPERWORD 32
#define SHIFT        5
#define TOPVAL      (1+N/BITSPERWORD)
#define MASK        0x1f
/* Above is same as mod operation, i%32 == i&5 */
/* Complete intent of mask is to guard against value
 * of 32 or above.
 */
#define set(i)    (bitvec[i >> SHIFT] |= (1<<(i&MASK)))
#define test(i)   (bitvec[i >> SHIFT] & (1<<(i&MASK)))

/* Printing routine */
void spill(int *a, int sz)
{
    int indx;
    for (indx = 0 ; indx < sz; indx++)
    {
        printf("%d ", a[indx]);
    }
    printf("\n");
}

void bitsort(int *a, int sz)
{
  int maxval = 0;
  int indx   = 0;
  int i = 0;

  int *bitvec = calloc(TOPVAL, sizeof(int));

  for (indx = 0; indx < sz ; indx++)
  {
     if (a[indx] > maxval) maxval = a[indx];
     set(a[indx]);
  }

  for (indx = 0; indx <= maxval ; indx++)
  {
     if (test(indx))
        a[i++] = indx;
  }

  free(bitvec);
}

int main()
{
  int arr[] = {205, 10, 7, 5, 9, 8, 1, 2, 100};
  bitsort(arr, 9);
  spill(arr,9);
}

Maximum segment sum in PHP

<?php
/* PHP is pass by value semantics.
   To pass by reference one uses the $& symbol for the
   parameters.
 */
    function maxsegsum (array $arr, $sz, &$beg, &$end)
    {  
       $maxe = $arr[0];          /* maximum ending here 
                              * cumulative sum */
       $maxs = $arr[0];          /* maximum so far */
       $beg_tmp = 0;
   
       for ($i = 1 ; $i < $sz ; $i++)
       {
          if ($maxe < 0)
          {
             $maxe = $arr[$i];   
             $beg_tmp = $i;
          }
          else
          {
             $maxe += $arr[$i];
          }
   
          if ($maxe >= $maxs)
          {
             $beg = $beg_tmp;
             $end = $i;
             $maxs = $maxe;   
          }
       }
       return $maxs;
    }

 $a = array(1, -2, 3, -2, 4);
 $beg = 0;
 $end = 0;
 $sum = maxsegsum ($a, 5, $beg, $end);
 
 print "Value of begin: $beg and value of end: $end <br>";
 print $sum;
?>

Maximum segment sum in Java

public class MaxSegSum
{
  private int beg_tmp, end, beg = 0;
 
  /* maxe = maximum ending here <=> cumulative sum
   * maxs = maximum so far
   */
  public int doSegSum(int a[], int sz)
  {
    int maxe = a[0], maxs = a[0];
    for (int i = 1 ; i < sz ; i++)
    {
       if (maxe < 0)
       {
         beg_tmp = i;
         maxe = a[i];
       }
       else
         maxe += a[i];
      
       if (maxe >= maxs)
       {
          maxs = maxe;
          beg = beg_tmp;
          end = i; 
       }
    }
    return maxs;
  }
 
  public static void main(String args[])
  {
    int A[] = {1, -2, 2, -1, 3, 4};
    System.out.println("value is " + new MaxSegSum().doSegSum(A, 6));
  } 
}

Maximum Segment Sum in C

Given a list of numbers, the task is to compute the largest possible sum of a consecutive segment.


#include <stdio.h>
#include <stdlib.h>

#define max(a,b)  ((a) > (b) ? (a) : (b))

/* Order of algorithm O(n^2) */
int maxsegsumO2(int a[], int sz)
{
    int maxtillnow = 0, maxsofar = 0;
    int i,j;

    for (i = 0; i < sz; i++)
    {
        maxtillnow = 0;
        for (j = i ; j < sz; j++)
        {
           maxtillnow = max(0,a[j]+maxtillnow);
           maxsofar = max(maxtillnow,maxsofar);
        }
        printf("%5d, %5d\n", maxtillnow, maxsofar);

    }
    return maxsofar;
}

/* Order of algorithm O(n) */
int maxsegsumO1(int a[], int sz)
{
    int maxtillnow = a[0],  maxsofar = a[0];
    int i, begin, end, begin_tmp;

    for (i = 1; i < sz; i++)
    {
        if (maxtillnow < 0)
        {
           begin_tmp = i;
           maxtillnow = a[i];
        }
        else
           maxtillnow += a[i];

        if (maxtillnow >= maxsofar)
        {
           maxsofar = maxtillnow;
           begin = begin_tmp;
           end = i;
        }
        /*
        maxtillnow = max(0,a[i]+maxtillnow);
        printf("%5d, %5d\n", maxtillnow, maxsofar);
        maxsofar = max(maxtillnow,maxsofar);
        */
    }

    printf("%d, %d\n", begin, end);
    return maxsofar;
}

int main()
{
   //int A[] = {3, 4, 5, -40, -20, 21, 25, 29, 31, 35};
 //  int A[] = {2, -3, 4, -1, 3};
   int A[] = {-2, -3, 4, -1, -2, 1, 5, -3};

   printf ("max seg sum: %d\n", maxsegsumO2(A, sizeof(A)/sizeof(int)));
   printf ("max seg sum: %d\n", maxsegsumO1(A, sizeof(A)/sizeof(int)));

   return 0;
}

Binary chop in PHP

<?php

/* PHP is pass by value for function arguments
 * http://www.php.net/call_user_func has the mechanism
 * inbuilt to make calls to different bchop implementations.
 * Using call_user_func is left as an exercise for whosoever
 * reads and wants to do it.
 */
    function bchop (array $arr, $n, $key)
    {
      $min = 0;
      $max = $n;
      while ($min < $max) {
        $middle = $min + (($max - $min) >> 1);
        if ($key > $arr [$middle])
          $min = $middle + 1;
        else
          $max = $middle;
      }
      if ($arr[$min] == $key) return $min;
      else
        return -1;
    }

    $a = array(3, 4, 5, 10, 20, 21, 25, 29, 31, 35);
    $idx = bchop($a, sizeof($a), 20);

    print $idx;
?>

Binary Chop in Java

class BinChop
{
  public interface Strategy
  {
    public int chop(final int a[], int sz, int value);
  }; 
 
  public class Chopper implements Strategy
  {
    public int chop (final int a[], int sz, int value)
    {
      int first = 0;
      int last  = sz;
     
      while (first <= last)
      {
        int mid = (first + last)/2;  // <== potential overflow
       
        if (value < a[mid])
          last = mid - 1;
        else if (value > a[mid])
          first = mid + 1;
        else
          return mid;
      }
      return -1;
    }
  }   
 
  public class ChopperOverflow implements Strategy
  {
    public int chop (final int arr[], int n, int key)
    {
      int min = 0, max = n;
      while (min < max) {
        int middle = min + ((max - min) >> 1);  // overflow fixedmin + ((max - min) >> 1)
        if (key > arr [middle])
          min = middle + 1;
        else
          max = middle;
      }
      if (arr[min] == key) return min;
      else
        return -1;
    }
  }
 
  public static void main(String args[])
  {
    int a[] = {3, 4, 5, 10, 20, 21, 25, 29, 31, 35};
   
    Strategy strat = new BinChop().new Chopper();
    System.out.println(strat.chop(a, 10, 20));
   
    strat = new BinChop().new ChopperOverflow();
    System.out.println(strat.chop(a, 10, 20));
  } 
}

Binary Chop in C

#include <stdio.h>

int binchop (const int *a, int sz, int value)
{
   int first = 0;
   int last  = sz;

   while (first <= last)
   {
      int mid = (first + last)/2;  // <== potential overflow

      if (value < a[mid])
         last = mid - 1;
      else if (value > a[mid])
         first = mid + 1;
      else
         return mid;
   }
   return -1;
}

int binchop1 (const int *arr, int n, int key)
{
   int min = 0, max = n;
   while (min < max) {
      int middle = min + ((max - min) >> 1);  // overflow fixedmin + ((max - min) >> 1)
      if (key > arr [middle])
         min = middle + 1;
      else
         max = middle;
   }
   if (arr[min] == key) return min;
   else
   return -1;
}

int main()
{
   int A[] = {3, 4, 5, 10, 20, 21, 25, 29, 31, 35};
   int (*bchop) (const int *a, int sz, int value);

   bchop = & binchop;
   printf("%d\n", (*bchop)(A, 10, 20));

   bchop = & binchop1;
   printf("%d\n", (*bchop)(A, 10, 20));
   return 0;
}