Question : In a BST to every element add sum of elements greater than it.

Answer: The first thing is to notice that on doing this the resulting tree would be the reverse of the binary search tree. Implementing this  you should notice that the inorder travesal prints the elements in increasing order.Hence we need to modify the inorder traversal a bit to do this.Here is a sample C++/C code for insert and inorder for a BST.

#include<iostream>
#include<cstdlib>

using namespace std;

struct node
{
    int data;
    struct node *parent;
    struct node *left;
    struct node *right;
}*root;

typedef struct node node;

/**
*Makes a new node from the integer
*value and returns a pointer to the
*new created node
*/
node* makeNode(int num)
{
    node *temp=(node*)malloc(sizeof(node));
    temp->data=num;
    temp->right=NULL;
    temp->left=NULL;
    return temp;
}

/**
 * Inserting a node in a BST
 */
void insert(int num,node *T)
{
    if(T==NULL)
    root=makeNode(num);
    else
    {
        if(T->data>num)
        {
            if(T->left==NULL)
            T->left=makeNode(num);
            else
            insert(num,T->left);
        }
        else
        {
            if(T->right==NULL)
            T->right=makeNode(num);
            else
            insert(num,T->right);
        }
    }
}

/**
*Inorder traversal of the tree
*/
void inorder(node* T)
{
    if(T!=NULL)
    {
        inorder(T->left);
        cout<<T->data<<" ";
        inorder(T->right);
    }
}

Now to add the elements which are greater than a particular node we need to reverse the inorder by accessing the bigger elements i.e. right first and then the left. On accessing the right add the data to the data already collected and then change the node value accordingly.Hope you better understand by the code.

void chorder(node *T,int *data)
{
    if(T!=NULL)
    {
        chorder(T->right,data);
        *data+=T->data;
        T->data=*data;
        chorder(T->left,data);
    }
}

Notice that that data needs to be reference so that after being updated it is assigned to the other nodes.

PROBLEM : The problem is to rotate a matrix by 90. Fairly easy , just focus on double pointers if you are using C/C++ and make it for Clock Wise and anti clockwise.The code is as follows:

#include<iostream>
#include<cstdlib>
#define CL 0
#define ACL 1

using namespace std;

void printMatrix(int **matrix,int width,int height)
{
  for(int i=0;i<width;i++)
    {
      for(int j=0;j<height;j++)
 cout<<*(*(matrix+i)+j)<<" ";
      cout<<endl;
    }
}

void matrixRot90(int **matrix,int width,int height,int dir)
{
  //dir 0 for CL and 1 for ACL
  if(dir==CL)
    {
      for(int j=0;j<height;j++)
 {
   for(int i=width-1;i>=0;i--)
     cout<<*(*(matrix+i)+j)<<" ";
   cout<<endl;
 }
    }
  else
    {
      for(int j=height-1;j>=0;j--)
 {
   for(int i=0;i<width;i++)
     cout<<*(*(matrix+i)+j)<<" ";
   cout<<endl;
 }
    }
}

int main(void)
{
  int width,height;
  cin>>width>>height;
  int **matrix=(int**)malloc(sizeof(int**)*width);
  for(int i=0;i<width;i++)
    *(matrix+i)=(int*)malloc(sizeof(int)*height);
  for(int i=0;i<width;i++)
    for(int j=0;j<height;j++)
      cin>>*(*(matrix+i)+j);
  cout<<"Original Matrix::";
  printMatrix(matrix,width,height);
  cout<<"After clockwise rotation ::\n\n";
  matrixRot90(matrix,width,height,CL);
  cout<<"After anticlockwise rotation ::\n\n";
  matrixRot90(matrix,width,height,ACL);
  return 0;
}

PROBLEM : Given a directed graph check whether the graph contains a cycle or not.

SOLUTION : In a graph containing a cycle suppose vi,...vk are the vertices that constitute the cycle and suppose that the backedge is from vk to vi then on applying dfs to the graph "when the dfs covers the edge from vk to vi then vi must have already been visited." vi will already be in the recursion stack when the edge will be covered.Hence we know a cycle is present.Thus the given graph will not be cyclic.

Thus for each node visited earlier we need to store the recursion stack to tell whether a edge points to a node already in the recursion stack.Then it would be a back edge.In this way this algorithm can be modified to find in a graph:

• The number of back edges
• The components i.e. the trees in a forest
• The number of cycles = number of back edges .. etc

The cpp code for the following :

#include<iostream>
#include<list>

using namespace std;

class Graph
{
    int V; //number of vertices
    list<int> *adj; //pointer to array containing adjacency lists
    bool isCyclicUtil(int v,bool visited[],bool *rs);

    public:
        Graph(int v);
        void addEdge(int v,int w);
        bool isCyclic();
};

Graph::Graph(int v)
{
    this->V=v;
    adj=new list<int>[V];
}

void Graph::addEdge(int v,int w)
{
    adj[v].push_back(w);
}

bool Graph::isCyclicUtil(int v,bool visited[],bool *rs)
{
    if(visited[v]==false)
    {
        visited[v]=true;
        rs[v]=true;
        list<int>::iterator i;
        for(i=adj[v].begin();i!=adj[v].end();++i)
        {
            if(!visited[*i] && isCyclicUtil(*i,visited,rs))
            return true;
            else if(rs[*i])
            return true;
        }
    }
    rs[v]=false;
    return false;
}

bool Graph::isCyclic()
{
    bool *visited=new bool[V];
    bool *rs=new bool[V];
    for(int i=0;i<V;i++)
    {
        visited[i]=false;
        rs[i]=false;
    }
    for(int i=0;i<V;i++)
    if(isCyclicUtil(i,visited,rs))
        return true;
    return false;
}

int main()
{
    Graph g(4);
    g.addEdge(0,1);
    g.addEdge(0,2);
    g.addEdge(1,2);
    g.addEdge(2,0);
    g.addEdge(2,3);
    g.addEdge(3,3);

    if(g.isCyclic())
    cout<<"Graph contains a cycle"<<endl;
    else
    cout<<"Graph doesnot contain a cycle"<<endl;
    return 0;
}

Given a binary tree, print all the nodes in the Zigzag order.For eg.


 
 For the given tree the answer should be : 1324567

Answer:This question is fairly simple if we keep a flag to decide whether we want to print it in normal order or to print it in reverse order.The pseudo algorithm for the implementation of this is as follows:

def print(Queue Q,int order)
{
    newQueue=new Queue();
    while(iterate over Q)
    {
      node=Q[iter];
      newQueue.enqueue(node.rightchild());
      newQueue.enqueue(node.leftchild());
    }
    if(order==0)
    Q.reverse();
    while(Q.size()>0)
    print(Q.dequeue());
    if(newQueue.size()>0)
    print(newQueue,~order);
}

You should also start with:

Q.enqueue(Tree.root);
print(Q,0);

So you always used sqrt() function to find out the square roots of a number .. So what if i ask you to write a function that will display the square root without using the math library functions.. STUNNED ?
       Well lets try to figure out what we do in finding the square root of a number.So how do we start.The first thing that comes into my mind is that square root can be any real value less than the given number.Hence there are infinite possibilities and we cannot loop through to check if multiplying the number to itself will give us the number.That would be a never ending process and we do not know the increment value.So what do we do now ?
       Ok.What if we take any number as the initial guess and start.When we find the square of the number is greater than the number than we know we have to select a number that is less than the current and if it is smaller than choose a greater number.In this way after a fixed number of iterations we will eventually reach near to the square root.This method is also called as Approximation by Bisection.

def sqrt(x,epsilon):
    assert((x>0)&&(epsilon>0)),"Initial Conditions not met"
    low=0
    high=x
    val=(low+high)/2
    count=1
    while val**2-x>epsilon and crt<100:
        crt+=1
        if(val**2>x)
            high=val
        else:
            low=val
        val=(high+low)/2
   return val

However even this cannot find to much approximation and what if in count number of times it doesn't reach the required value.For this we have another method called the Newtons method where we use the initial guess to make a better guess.It works like taking 1 as the initial guess.Then

1+(2/1)=3  3/2=1.5
1.5+(2/1.5)=2.83  2.83/2=1.416 ~ 1.414 sqrt of 2

Hence using Newtons Method of Approximation we get:

float sqrt(float x)
{
 float ng;
 float g=x/2;
 float d=(g*g)-x;
 d=(d>0)?d:-d;
 while(d>EPS)
 {
  ng=(g+(x/g))*0.5;
  g=ng;
  d=(g*g)-x;
  d=(d>0)?d:-d;
  //cout<<g<<endl;
 }
 return g;
}

Credits : Excerpt taken from here

NACHOS was rewritten in JAVA and thus it is now platform independent and can run on any machine ( provided jre and jdk are installed on it , ofcourse ).

So here's how to install it in Ubuntu ( theres nothing which can be called as "Installation" , its juz copying and pasting ! )

So first you need to get this Nachos-java.tar.gz file from here.

Just "untar" it in your home folder by :

tar -xf nachos-java.tar.gz

Now you'll get a folder named nachos with various files in it . ( make sure you paste this folder in your home directory )

You need to grant executable permission to $HOME/nachos/bin/nachos file
To do this :
chmod  777  $HOME/nachos/bin/nachos

Next thing , download the mips.x86-linux.xgcc.tar.gz from here.

Untar this file also in your home directory :

tar -xf  mips.x86-linux.xgcc.tar.gz

Okey , now we need to edit some configuration files , here's how :

• The nachos/test/Makefile ,  open this file with gedit and add the following lines just after the comments at the top :

        ARCHDIR = $HOME/mips.x86-linux.xgcc  
        
        Or just download this edited Makefile and replace the original one.

• The .profile file in your home directory (its hidden !), editing it wrongly can lead to troubles , better download this edited .profile and replace the original one. 

And with this we must be done . Now goto nachos/proj1/ and run :

make 

this compiles the BLAHBLAH.java files to BLAHBLAH.class files and stuff .

nachos

This runs the nachOS !

If you see an output like this shown below , you're done !

For creating processes in Linux we need to use the library available in Unix unistd.h . The normal process for creating a child process is as follows:

#include<stdio.h>
#inlcude<unistd.h>
int main()
{
      pid_t pid;   //the process id
      if(pid=fork()<0)
      {
          printf("Failed to create the childd process\n");
          exit(0);
       }
      if(pid==0)
       {
           //work to be done by the parent process
        }
      else
       {
           //the child process here
        }
     return 0;
}

To find out how much over overhead does this cost to the system let us create multiple child processes.This is usually done this way:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<unistd.h>
#include<assert.h>
#define NUM_PROCESSES 100

struct timeval t1,t2;

int main()
{
      pid_t pid[NUM_PROCESSES];
      int i;
      //clock_t start,stop;
      //double t=0.0;
      //assert((start=clock())!=-1);
      gettimeofday(&t1,NULL);
      for(i=0;i<NUM_PROCESSES;i++)
      {
         if((pid[i]=fork())<0)
       {
         perror("fork error\n");
       }
     else if(pid[i]==0)
       {
         //do work with the child
         printf ("[log]Created child process number:%d\n",i);
         exit(0);
       }
      }
      int status;
      pid_t rstatus;
      int n=NUM_PROCESSES;
      while(n>0)
    {
      rstatus=wait(&status);
      --n;
    }
      //stop=clock();
      //t=(double)(stop-start);
      //printf("Time taken ::%f\n",t);
      gettimeofday(&t2,NULL);
      printf("---------------time taken is::%ld----------------\n",t2.tv_usec-t1.tv_usec);
      return 0;
}
So we calculated the system time taken for creating 10 processes was : In micro seconds the total amount of time taken was about 15,441.To compare this to thread creation process we wrote a program with same number of threads as the number of processes i.e. 100 .Again we use the gettimeofday function to get the time taken for spawning the threads.The program for thread is as follows:

#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>
#include<pthread.h>
#include<time.h>
#include<assert.h>
#define NUM_THREADS 100

struct timeval t1,t2;

void *PrintCreated(void *threadId)
{
  long tid;
  tid=(long)threadId;
  printf("[log]Created thread with thread id::%ld\n",tid);
  pthread_exit(NULL);
}

int main()
{
  pthread_t threads[NUM_THREADS];
  int rc;
  long t;
  /*clock_t start,stop;
  double tt=0.0;
  assert((start=clock())!=-1);*/
  gettimeofday(&t1,NULL);
  for(t=0;t<NUM_THREADS;t++)
    {
      //printf ("[log]Creating thread %ld\n",t);
      rc=pthread_create(&threads[t],NULL,PrintCreated,(void *)t);
      if(rc){
    perror("Error creating thread\n");
      }
    }
  /*stop=clock();
  tt=(double)(stop-start);
  printf("Cpu time taken:%f\n",tt);*/
  gettimeofday(&t2,NULL);
  printf("--------------time taken :: %ld----------------\n",t2.tv_usec-t1.tv_usec);
  pthread_exit(NULL);
}

The time taken for generating NUM_THREADS was 9453 milliseconds.Hence spawning of threads is 1.63 times faster than spawning of processes because in creating threads we donot need to create the data space and other things because threads share the data.