A static function is a function with the static qualifier applied:
static void foo ( void )
{
/* Blah blah */
}
What it does is restrict visibility of the function to the translation unit in which it's declared. Functions are implicitly declared as extern by default, which means they're visible across translation units.
Reference
http://www.daniweb.com/forums/thread82504.html
Wednesday, December 3, 2008
Monday, December 1, 2008
Maximum Sum Sub array
This is a interesting problem which can be solved in a variety of ways. This problem has a chunk of a chapter devoted in the Programming Pearls book by Jon Bentley.
Method 1. Brute Force O(n^2)
This involves taking each index i between 0 to len and for every other index j>i calculate the sum while keeping track of the maximum.
2. Method 2: Divide and Conquer: O(n log n)
This involves dividing the array recursively into 3 parts left, right and mid. And comparing max sum of the three.
Calculating max(left) and max(right) is trivial using recursion. For the mid element, we know the left bound (l) lies in left half and right bound (r) lies in right half. So we calculate l s.t sum of elements between l and mid is max and r s.t the sum is maximum for elements between mid and right.
3. Dynamic programming O(n)
An optimized DP solution takes O(n).
The naive DP solution acts exactly like method 1 and generates a matrix A[i,j] containing sum of elements with left bound i and right bound j.
The optimized DP constructs a single dimension table of array size, with
table[i]: Represents the sum of subarray with maximum sum terminating at i;
for i=0, table[0]=arr[0]
for i>0, table[i]= Max{ arr[i], arr[i]+table[i-1]}
Once we have the table finding max sum takes only a single pass through the above table, we can fasten the procedure up by keeping track of max side by side.
A simpler algorithm based on the same idea as the DP method is called Kadane's algorithm and it works without the need of maintaining the auxiliary table.
The code is derived from here
Method 1. Brute Force O(n^2)
This involves taking each index i between 0 to len and for every other index j>i calculate the sum while keeping track of the maximum.
private static int sumbruteforce(int [] arr){
int sum=0;
int max=Integer.MIN_VALUE;
int maxi=0;
int maxj=0;
for(int i=0;i<arr.length;i++){
sum=0;
for(int j=i;j<arr.length;j++){
sum+=arr[j];
if(sum>max){
max=sum;
maxi=i;
maxj=j;
}
}
}
System.out.println(maxi+" "+maxj);
return max;
}
2. Method 2: Divide and Conquer: O(n log n)
This involves dividing the array recursively into 3 parts left, right and mid. And comparing max sum of the three.
Calculating max(left) and max(right) is trivial using recursion. For the mid element, we know the left bound (l) lies in left half and right bound (r) lies in right half. So we calculate l s.t sum of elements between l and mid is max and r s.t the sum is maximum for elements between mid and right.
private static int sumDivConquer(int [] arr, int l, int h){
if(l>h)
return 0;
if(l==h)
return arr[l];
int m=(int) Math.floor((double)((l+h)/2));
int max=0;
max=sumDivConquer(arr, l, m);
max=Math.max(max,sumDivConquer(arr, m+1, h));
int L=0;
int R=0;
int S=0;
for(int i=m;i>=l;i--){
S+=arr[i];
L=S>L? S:L;
}
R=S=0;
for(int i=m+1;i<=h;i++){
S+=arr[i];
R=S>R? S:R;
}
max=Math.max(max, L+R);
return max;
}
3. Dynamic programming O(n)
An optimized DP solution takes O(n).
The naive DP solution acts exactly like method 1 and generates a matrix A[i,j] containing sum of elements with left bound i and right bound j.
The optimized DP constructs a single dimension table of array size, with
table[i]: Represents the sum of subarray with maximum sum terminating at i;
for i=0, table[0]=arr[0]
for i>0, table[i]= Max{ arr[i], arr[i]+table[i-1]}
Once we have the table finding max sum takes only a single pass through the above table, we can fasten the procedure up by keeping track of max side by side.
private static int sumDP(int [] arr){
int table[]=new int[arr.length];
table[0]=arr[0];
for(int i=1;i<arr.length;i++){
table[i]=Math.max(arr[i], arr[i]+table[i-1]);
}
int max=Integer.MIN_VALUE;
for(int i=0;i<arr.length;i++){
if(table[i]>max)
max=table[i];
}
return max;
}
A simpler algorithm based on the same idea as the DP method is called Kadane's algorithm and it works without the need of maintaining the auxiliary table.
The code is derived from here
private static int sumKadane(int arr[]){
int max=Integer.MIN_VALUE;
int a,b; a=b=0;
int curr = 0;
int aa = 1;
for (int bb= 1;bb<arr.length;bb++){
curr = curr + arr[bb];
if (curr > max) {
max=curr;
a=aa;
b=bb;
}
if (curr < 0) {
curr = 0;
aa = bb + 1;
}
}
System.out.println(a+" "+b);
return max;
}
Labels:
algorithms,
techniques
Counting Number of set bits in a number
1. Method 1
Complexity= O(n)
Method 2:
The method works as follows:
The operation:
n=n&(n-1)
resets the last set bit of n.
So the number of time the above operation can be done before n is equal to 0 are the number of set bits in n originally.
Complexity= O(m) where m is the number of set bits in n.
Also note that if count above is 1, then number n is a power of 2.
Complexity= O(n)
int numOfOnes(int n){
int count=0;
while(n!=0){
if((n & 1) == 1)
count++;
n=n>>>1;
}
return count;
}
Method 2:
The method works as follows:
The operation:
n=n&(n-1)
resets the last set bit of n.
So the number of time the above operation can be done before n is equal to 0 are the number of set bits in n originally.
Complexity= O(m) where m is the number of set bits in n.
int numOfOnes2(int n){
int count=0;
while(n!=0){
n=n&(n-1);
count++;
}
return count;
}
Also note that if count above is 1, then number n is a power of 2.
Labels:
algorithms
Generating Combinations
The algorithm for this is very similar to the algorithm for generating permutations.
Algorithm:
1. Remove Item i from elements and put in output array
2. Display Output
3. Generate combinations for rest of the array
Algorithm:
1. Remove Item i from elements and put in output array
2. Display Output
3. Generate combinations for rest of the array
public void combine(String str){
int l=str.length();
StringBuilder out=new StringBuilder();
char []in=str.toCharArray();
doCombine(in,out,l,0);
}
private void doCombine(char[] in, StringBuilder out, int n, int start){
for(int i=start;i<n;i++){
out.append(in[i]);
System.out.println(out);
if(i<n)
doCombine(in, out, n, i+1);
out.setLength(out.length()-1);
}
}
Labels:
algorithms
Generating Permutations
This has been a problem I always had difficulty with. The only resort I had till now was to memorize the solution and spit it out when needed. But now, with a algorithms class behind me and a little bit more insight into the problem, I can atlast cook up the logic here.
SO, the Question is:
Given n items (numbers, chars) generate/print all possible permutation of them
Algorithm:
1. Take a item i and put it in the perm array
2. Generate Permutation for rest of the n-1 elements (Print perm array when n==0)
3. Put back Item i in elements
References:
1. Programming Interviews Exposed
2. http://www.paulgriffiths.net/program/c/perm.php
SO, the Question is:
Given n items (numbers, chars) generate/print all possible permutation of them
Algorithm:
1. Take a item i and put it in the perm array
2. Generate Permutation for rest of the n-1 elements (Print perm array when n==0)
3. Put back Item i in elements
public class Permute {
public void permute(String str){
int l=str.length();
boolean [] used=new boolean[l];
StringBuilder out=new StringBuilder();
char []in=str.toCharArray();
doPermute(in,out,used, l, 0);
}
private void doPermute(char[] in, StringBuilder out, boolean[] used, int n,
int level) {
if (level==n){
System.out.println(out.toString());
return;
}
for(int i=0;i<n;i++){
if(used[i]) continue;
out.append(in[i]);
used[i]=true;
doPermute(in, out, used, n, level+1);
used[i]=false;
out.setLength(out.length()-1);
}
}
}
References:
1. Programming Interviews Exposed
2. http://www.paulgriffiths.net/program/c/perm.php
Labels:
algorithms
Sunday, November 16, 2008
Shuffling
Shuffling is a very interesting programming problem, Almost everybody can come up with a good algorithm using a simple rand() function, but it gets a little tricky when one has to perform a in place shuffle (i.e. w/o using any extra memory).
Knuth's Algorithm described in the Art of Computer programming, Vol 2 (which is based on Fisher Yates algorithm) is regarded as one the best known algorithm for the problem.
The description on wikipedia is a little clearer and goes like this:
1. Let A1 := 1, A2 := 2 and so on up to AN := N, and let n := N.
2. Pick a random number k between 1 and n inclusive.
3. If k ≠ n, swap the values of Ak and An.
4. Decrease n by one.
5. Repeat from step 2 until n is less than 2.
Alternately, instead of going n to 1 we can do a forward pass like here:
An alternative method is we can assign each element of the set to be shuffled a random number and the set is then sorted according to these numbers. This may be faster in practice, despite having worse asymptotic time complexity (O(n log n) vs. O(n)).
Like the Fisher-Yates shuffle, this method will also produce unbiased results if correctly implemented, and may be more tolerant of certain kinds of bias in the random numbers. However, care must be taken to ensure that the assigned random numbers are never duplicated, since sorting algorithms in general won't order elements randomly in case of a tie.
Wikipedia also defines a interesting algorithm very similar to the Knuth's algorithm called the Sattolo algorithm for generating uniformly distributed cyclic permutations. The only difference between the 2 algorithms is that in Sattolo's algorithm in step 2, the random number k is chosen from the range between 1 and n−1 (rather than between 1 and n) inclusive.
To turn the Java example above into an example of Sattolo's algorithm, simply replace rng.nextInt(n) with rng.nextInt(n-1) in the code. This simple change modifies the algorithm so that the resulting permutation always consists of a single cycle.
Reference:
1. TAOCP Vol 2 Section 3.4.5 by Donald Knuth
2. http://en.wikipedia.org/wiki/Knuth_shuffle
Knuth's Algorithm described in the Art of Computer programming, Vol 2 (which is based on Fisher Yates algorithm) is regarded as one the best known algorithm for the problem.
The description on wikipedia is a little clearer and goes like this:
1. Let A1 := 1, A2 := 2 and so on up to AN := N, and let n := N.
2. Pick a random number k between 1 and n inclusive.
3. If k ≠ n, swap the values of Ak and An.
4. Decrease n by one.
5. Repeat from step 2 until n is less than 2.
public static void shuffle (int[] array)
{
Random rng = new Random(); // i.e., java.util.Random.
// The number of items left to shuffle (loop invariant).
int n = array.length;
while (n > 1)
{
int k = rng.nextInt(n); // 0 <= k < n.
n--; // n is now the last pertinent index;
// swap array[n] with array[k] (does nothing if k == n).
int temp = array[n];
array[n] = array[k];
array[k] = temp;
}
}
Alternately, instead of going n to 1 we can do a forward pass like here:
int N = array.length;
for (int i = 0; i < N; i++)
{
int r = i + (int) (Math.random() * (N-i));
int t = array[r];
array[r] = array[i];
array[i] = t;
}
An alternative method is we can assign each element of the set to be shuffled a random number and the set is then sorted according to these numbers. This may be faster in practice, despite having worse asymptotic time complexity (O(n log n) vs. O(n)).
Like the Fisher-Yates shuffle, this method will also produce unbiased results if correctly implemented, and may be more tolerant of certain kinds of bias in the random numbers. However, care must be taken to ensure that the assigned random numbers are never duplicated, since sorting algorithms in general won't order elements randomly in case of a tie.
Wikipedia also defines a interesting algorithm very similar to the Knuth's algorithm called the Sattolo algorithm for generating uniformly distributed cyclic permutations. The only difference between the 2 algorithms is that in Sattolo's algorithm in step 2, the random number k is chosen from the range between 1 and n−1 (rather than between 1 and n) inclusive.
To turn the Java example above into an example of Sattolo's algorithm, simply replace rng.nextInt(n) with rng.nextInt(n-1) in the code. This simple change modifies the algorithm so that the resulting permutation always consists of a single cycle.
Reference:
1. TAOCP Vol 2 Section 3.4.5 by Donald Knuth
2. http://en.wikipedia.org/wiki/Knuth_shuffle
Labels:
algorithms,
tricks
Thursday, November 13, 2008
Finding a loop in a singly linked list
There are three "decent" solutions for it
1. Pass through the list, use a hashtable to store the addresses of the visited nodes, if 2 nodes hash to same key, there's a loop.
function boolean hasLoop(Node startNode){
HashSet nodesSeen = new HashSet();
Node currentNode = startNode;
do {
if (nodesSeen.contains(currentNode)) return true;
nodesSeen.add(currentNode);
} while (currentNode = currentNode.next());
return false;
}
2. Floyd's Cycle-Finding Algorithm
Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}
Alternately, in C
p=q=head;
do{
p=p->next->next;
q=q->next;
}while p!=q or p!=null;
if p==q
loop exists
else
no loop
To find the smallest index where the cycle starts:
// To find the smallest index where the cycle starts
// P is set from last algorithm
int index=0;
q=0;
while p!=q{
p=p->next;
q=q->next;
index ++;
}
return index;
To find cycle length
// P & Q is set from last algorithm
int len=0;
while p!=q{
p=p->next;
len ++;
}
return len;
See reasoning for len, index functions at wiki
3. Brent' Algorithm
power=len=1;
q=head;
p=head->next;
while p!=q {
if (power==len){
p=q;
power*=2 , len=0;
}
p=p->next; len++;
if(p==NULL) return (no cycle);
}
return (cycle), len;
For finding Index
i=index=0;
p=q=head;
while(i++<len)
p=p->next;
while p!=q {
q=q->next;
p=p->next;
index++;
}
return index;
Reference:
http://ostermiller.org/find_loop_singly_linked_list.html
wiki
Labels:
algorithms,
tricks
Subscribe to:
Posts (Atom)