Matlab Examples

Here is a code for averaging a set of signals, note that my input is taken from a .wav file and thus is of different making it a little more code. This is for who got stuck and can't find a way out.Using the saved .jpeg files you can see how it works visually.

Douglas-Peucker Algorithm

An algorithm for smoothing a 2-d plot . You can read a good explanation of it at wikipedia Wiki Link . Following is the matlab code that I wrote for it:

SPOJ:Insertion Sort

The problem asks us to find the number of swaps an insertion sorts does, which in a way is a measure of efficiency of the sort.

The basic logic is answer is the sum of ( for each element the number of elements greater than itself occuring before it .)

One way to implement it is Employ merge sort on it and during each merge operations if you are copying an element from the right array (swaps +=no. of elements in the left array) .

A novice mistake which I made what that I dynamically allocating and de-allocating a temporary array during each merge operation, BEWARE this is a very costly operation and should not be used. Allocate memory once and pass that array .

Modular Exponentiation

For performing exponentiation we can take the linear route or we can take the binary route. What is the main idea behind it

Suppose you are to calculate ( x^p) mod n

You can do this in a linear fashion and using the following property of modular operations
(a*b) mod n = (a mod n * b mod n) mod n
 but that is O(n) time complexity and we can do better. 

Observe the following
exponential(x,p) = exponential(x,p/2)<<2           // if p is even
                               x*exponential(x,(p-1)/2)<<2 // if p is odd

Now the number of times the functions is called is log2(b), which is a definite improvement over the linear case. But we can still do better by expressing the power in its binary form. Read the following wikipedia article for understanding
right to left binary method

following is C++ code for modular exponentiation .

Here is problem on SPOJ using the above concept http://www.spoj.com/problems/ZSUM/ . 

Comments are welcome.

           

sieve of eratosthenes

Sieve of Erathosthenes : a find of quick ways to generate primes upto generally less than a million . below is the code for it .

what the sieve of eratosthenes does it that it eliminates all the multiples of previously determined primes .

optimization 1: start eliminating numbers  for prime i starting from i*i
optimization 2: i ends at i*i<upper since any composite below upper will atleast have one prime factor below sqrt(upper)
optimization 3 : any prime can be of type 6k+1 or 6k+5 only .

Using these optimization I have coded the following program which on my i-5 machine takes 2.5s to calculate primes upto 9e7.

Permutations

Hey following is a method using backtracking to print all permutations of a number in C++.

// A program using backtracking to generate premutations of 1,n numbers .

#include <cstdio>

#define MAXCANDIDATES 20

void backtrack(int a[],int k,int n);

int is_a_solution(int k,int n);

void process_solution(int a[],int n);

void construct_candidates(int a[],int c[],int k,int n, int *ncandidates);

int main()
{
    int n;
    scanf("%d",&n);
    int a[n+1];
    for(int i=1;i<n;i++)a[i]=0;
    backtrack(a,0,n+1);
    return 0;
}

int is_a_solution(int k,int n)
{
return (k==(n-1));
}

void process_solution(int a[],int n)
{
     printf("{");
     for(int i=1;i<n;i++) printf("%d,",a[i]);
     printf("\b}\n");
}

void construct_candidates(int a[],int c[],int k,int n,int *ncandidates)
{  
     bool in_perm[n];
     for(int i=1;i<n;i++)in_perm[i]=false;
     for(int i=1;i<k;i++)in_perm[a[i]]=true;
   
     *ncandidates =0;
     for(int i=1;i<n;i++){
           if(!in_perm[i]){
                           c[(*ncandidates)++]=i;
           }
   
     }
}
void backtrack(int a[],int k,int n)
{
     int c[MAXCANDIDATES];
     int ncandidates;
   
     if(is_a_solution(k,n)){
             process_solution(a,n);
     }
     else {
          k=k+1;
          construct_candidates(a,c,k,n,&ncandidates);
          for(int i=0;i<ncandidates;i++){
             a[k]=c[i];
             backtrack(a,k,n);
             }
     }    
}