# Sanstech

## Ideas, Knowledge, Technology, Computer Science, Experience associated with my work and some geeky stuff I progressively encounter during my journey towards enlightenment. Read on…

• • # Archive for the ‘Algorithm’ Category

## Exponentiation by Squaring

Posted by sanstechbytes on October 7, 2011

To compute the value of a raised to the power of b (a to power b) , Math.pow(a, b) or some appropriate library function (depending on which language we’re talking about) is often used, which, of course, is optimized. Another efficient approach is Exponentiation by Squaring using recursion. For the underlying idea behind it, read here.

Although optimization achieved with this approach doesn’t appear to be significant for smaller integer exponents, it’s worth considering this for bigger  integer exponents in your exponentiation code.

See the code (in Java) below:

The time complexity is ~ O(c log n): Takes O(log n) for squaring’s and O(log n) for multiplications.

class ExponentiationTest {

public static void main(String[] args) {
// TODO Auto-generated method stub
double a = 2, b = -10; //
double pow = powerWithRecurSquaring(a, b);
if (b < 0) {
pow = 1 / pow;
}
System.out.println(a + ” to the power of  ” + b + ” = ” + pow);
}

// a power b, runs in ~ O(2 log b) time
public static double powerWithRecurSquaring(double a, double b) {
if (b < 0) {
b = -b; //   b = Math.abs(b);
} else if (b == 0) {
return 1;
} else if (b == 1) {
return a;
} else if (b == 2) {
return a * a;
} else if (b % 2 == 0) {
return powerWithRecurSquaring(powerWithRecurSquaring(a, b / 2), 2);
}
return powerWithRecurSquaring(a, b – 1) * a;
}

}

Posted in Algorithm | 2 Comments »

## Sorting in Linear Time

Posted by sanstechbytes on August 17, 2011

Sorting in linear time is achievable using COUNTING SORT, RADIX SORT, BUCKET SORT algos under special cases. All these trade space for time.  The point in this post is, to sort in linear time, in-place, for special case of array-or-the-list-or-the-attribute-that-can-have-only-two-distinct-values problem.

I call the technique of using two pointers to rearrange(sort) elements based on comparisons or perform math operations like add, subtract, multiply, squaring, divide to yield the target output, the “Two-Pointer Technique”.  This technique is used to efficiently solve problems like:
a) Finding the pair in array that add up to the given target(it’s a sub-problem of EXACT-SUBSET-SUM problem (refer to Introduction to Algorithms by CLRS))
b) Sorting an array with 0’s and 1’s or in general, any array that contains only two distinct values.
c) Finding the Pythagorean triples in an array etc.

The thing is, most of us (I’m talking to the java developers here) just use Collections.sort(…) or Arrays.sort(…)   for all our sorting needs , even for special cases like, the array-or-the-list-can-have-only-two-distinct-values problem.  In a related note, for problem of sorting ‘Person’ objects by age, we can think of implementing BUCKET SORT (runs in O(kn) time) where k could be < 130(age) etc, instead of merge sort of Array.sort(…)  or Collections.sort(…) that runs in O(n log n) worst-case.

The below sort  algorithms run in linear time, in-place and I think, are worth considering for those cases. Below  sort implementations (in Java) are based on Two-Pointer Technique. Think of using this technique to solve many problems. Comments follow in line.

Special mention is for sort(…) method to sort objects based on one field that can contain only one of any two values(say, gender – can only be F or M), for all practical purposes. This implementation compares with Collections.sort(in Java) as follows:
b) Runs in O(n) compared to Merge-Sort O(n log n) used in Collections.sort(…)
c) Reduces space complexity (merge sort uses auxiliary array of length n, to copy the elements in the sorted array). This is done, in-place (constant amount of space).

Try yourself quantifying the above differences with sample input and run. You’ll notice the significant efficiency achieved.

//Code

```public static void testSort( ) {
int[] a = new int[] { 1, 0, 0, 0, 0, 0, 1 };
int x = 0, y = 1; // generalized to
System.out.println(“before sort”);
// printArray(a);
sortTwoVals(a, x, y); // for int’s
String[] s = new String[] { “Male”, “female”, “male”, “Female”, “male” };
// printArray(s);
String s1 = “Female”;
String s2 = “male”;
sortTwoVals(s, s1, s2); //for strings
List list = new ArrayList();
String F = “F”;
String M = “M”;
System.out.println(“Before sort…”);
// printArray(list.toArray());
String firstAfterSort = F, secondAfterSort = M;
list = sort(list, firstAfterSort, secondAfterSort);
System.out.println(“After sort…”);
System.out.println(“Persons sorted according to their gender”);
// printArray(list.toArray());
}

// When two pointers (‘start’ and ‘end’ converge), we’re done with sorting.
// For integers
public static int[] sortTwoVals(int[] a, int x, int y) {
int start = 0, end = a.length – 1;
while (start < end) {
if (a[start] == y) {
while (a[end] == y) {
if (end < start) {
break; // Sorted case
}
end–;
}

if (a[end] == x) {
a[end] = y;
a[start] = x;
}
}
start++;
}
return a;
}

// For Strings
public static String[] sortTwoVals(String[] s, String s1, String s2) {
int start = 0, end = s.length – 1;
while (start < end) {
if (s2.equalsIgnoreCase(s[start])) {
while (s2.equalsIgnoreCase(s[end])) {
if (end < start) {
break; // Sorted case
}
end–;
}

if (s1.equalsIgnoreCase(s[end])) {
s[end] = s2;
s[start] = s1;
}
}
start++;
}
return s;
}

// For objects
public static List sort(List personsList, String firstAfterSort,
String secondAfterSort) {
Object[] persons = personsList.toArray();
int start = 0, end = persons.length – 1;
// When two pointers converge, we’re done with sorting
while (start < end) {
if (secondAfterSort.equalsIgnoreCase(((Person) persons[start])
.getGender())) {
while (secondAfterSort.equalsIgnoreCase(((Person) persons[end])
.getGender())) {
if (end <= start) {
break; // Sorted case
}
end–;
}
if (firstAfterSort.equalsIgnoreCase(((Person) persons[end])
.getGender())) {
Person swap = (Person) persons[end];
persons[end] = persons[start];
persons[start] = swap;
}
}
start++;
}
return java.util.Arrays.asList(persons);
}

public class Person {
private String name;
private int age;
private String gender;
public Person(String name, int age, String gender) {
this.name = name;
this.age = age;
this.gender = gender;
}
}
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getGender() {
return gender;
}
public void setGender(String gender) {
this.gender = gender;
}
}

}

```

## Find the kth Smallest Element in Array in Linear Time

Posted by sanstechbytes on July 24, 2011

Finding the kth smallest element in array is an application related to Order Statistics problem. For details on the algo used here, watch the video lecture embedded below.

Robert Sedgewick, whose lecture this approach has been inspired from, proposes random shuffle mechanism and partitioning strategy to select the kth smallest element. The strategy requires maintaining variables lo and hi to delimit the subarray that contains the index k of the element to be selected, using partitioning to shrink the size of the subarray (Step 2). The assumption made is that the input array to the algo doesn’t contain duplicates (This can be carried out as a preprocessing step, which is performed as first step in the algo below, though). Runs in linear time, O(n).

Algo:
1) Preprocess array to remove duplicates.
2) Rearrange the array from a[lo] through a[hi] and return an integer j such that a[lo] through a[j-1] are less than a[j], and a[j+1] through a[hi] are greater than a[j].
a) If k is equal to j, done.
b) Else If k is less than j, then continue working in the right subarray (by changing the value of hi to j-1).
c) Else If k is greater than j, then continue working in the right subarray (by changing lo to j+1).
3) Repeat step (2), until the array consists just of k.

MIT Video Lecture on Order Statistics:

Java Code:

```
/** Sedgewick's partitioning approach */
public class QuickSelect {

private static Random random = new Random();

public static Comparable select(Comparable[] a, int k) {
if (k = a.length) {
throw new RuntimeException("Selected element out of bounds");
}

shuffle(a);

int lo = 0, hi = a.length - 1;
while (hi > lo) {
int i = partition(a, lo, hi);
if (i > k)
hi = i - 1;
else if (i < k)
lo = i + 1;
else
return a[i];
}
return a[lo];
}

private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) {
// find item on lo to swap
while (less(a[++i], v))
if (i == hi)
break;
// find item on hi to swap
while (less(v, a[--j]))
if (j == lo)
break; // redundant since a[lo] acts as sentinel
// check if pointers cross
if (i >= j)
break;
exch(a, i, j);
}
// put v = a[j] into position
exch(a, lo, j);
// with a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
}

public static void shuffle(Object[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int r = i + uniform(n - i); // between i and N-1
Object temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}

/**
* Return an integer uniformly between 0 and N-1.
*/
public static int uniform(int N) {
return random.nextInt(N);
}

// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}

// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}

// Read strings from standard input, sort them, and print.
public static void main(String[] args) {
// Read input from StdIn here
// String[] a = new String[]{"aa", "aaa", "bb", "ab", "ca", "bc",
Integer[] a = new Integer[] { 2, 11, 10, 6, 8, 99, 7, 100, 101, 28,
9 };
int k = 2;
Object kth = Quick.select(a, k - 1); // returns a[k-1]
System.out.println(k + "th smallest element in given array = "
+ kth);
}
}

```

## Pythagorean Triples

Posted by sanstechbytes on July 10, 2011

A quick background on properties of Pythagorean triples can be got from here and here.

When I was browsing through topics in algorithm forum on stackoverflow.com , I found , sort of, an interesting challenge in finding Pythagorean Triples in the given array, saying:  Can’t be achieved in no better than O(n*n) time complexity(a unanimous opinion). This enthused me to attempt writing a faster than O(n*n) algo, but after much analysis and code completion, I couldn’t help joining the participants. In below lines, the code snippet follows. I wonder, if any algorithm enthusiast or researcher could point me to a faster algorithm than O(n*n), if there exists any.

Follow comments in-line to help yourself understand the algorithm used. This algorithm achieves O(k*n*n) time complexity where k is nearly equal to n/3  in most cases. For brevity, it’s an O(n*n) algo.

// O(n+n*log n+k*n*n) = O(k*n*n)= O(n*n) algo where k is nearly n/3 in
// most cases
// Returns the number of triples found.
// Returns
// -1, when n < 3,
// 1 when n = 3 and/or a triple is found and
// 0 when no triple found
public static int pythtriples(int[] pyth) {
int n = pyth.length;

// No duplicate removal algo is used before sort, to avoid the cost of
// O(n),as this will be taken care of below,in for loop.
// (Trivial) Shifting mechanism should be used in
// array with new length in-place(trivial)in case,
// either the element occurring in multiple places is 0 or neg integer

// Square all the numbers – O(n) time complexity.
for (int i = 0; i < n; i++) {
pyth[i] = pyth[i] * pyth[i];
}

// Sort them – O(n * log n) time complexity
Arrays.sort(pyth);

if (n < 3) {
return -1; // error : No of elements must be >= 3
}

// Simple case
if (n == 3) {
if (pyth == pyth + pyth)
return 1;
else
return 0;
}

// Compare pair-wise: if(a[i] == (a[j] + a[k]) then, it’s a triple),
// k<i, j<i
// O(k* n * n) time complexity, where k is nearly n/3, can be
int triples = 0, foundtripleLarge = 0;
for (int i = 2; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int k = i – 1; k >= 0; k–) {
// If already found, don’t compare again for 3SUM. Avoids
// unnecessary check for duplicates
if (foundtripleLarge == pyth[i]) {
break;
}
if (pyth[i] == (pyth[j] + pyth[k])) {
System.out.println(“triples found: ” + pyth[i] + ” = ”
+ pyth[j] + ” + ” + pyth[k]);
triples++; // Counter for triples
foundtripleLarge = pyth[i];
break;
}
}
}
}
return triples;
}

Math: The pair-wise comparison follows: 1^2 + 2^2 + 3^2 + …..+n^2 = n(n+1)(2n+1)/6, nearly equal to 3n^2, same as our O(kn^2) algo above!