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.

LINK :: Question

Required Concepts : Partial Difference

Explanation : A number n will be a possible answer if the number of people having n in their range is exactly n (Byteknights always tell truth and knaves lie ). Therefore for each a and b input we need to increment its value by 1 so that in the end we have an array that represents how many people have told element i to be in their range . Let this array be KNUM, then element i can be a byteknight if KNUM[i]=i

         Instead we store a partial difference array with diff[i]=knight[i]-knight[i-1] . Thus for each a,b we need to increase diff[a] and decrease diff[b+1] for ith entry.

Thus ,

                                      KNUM[i]=diff[0]+diff[1]...diff[i]

If every n is a value in between limits of ith bytelandian then he has to be a knight else for a value he can become a byteknave and this is needed to print the lexicographic smallest one. And since he will be a byteknave his limit should be excluded from the range of n we have taken as possible because he speaks lie always.

CODE EXPLAINED :

#include <cstdio>
#include <set>
using namespace std;

int main(){
    int T;          //the number of test cases
    for(scanf("%d", &T); T--; ){
        int N, lo[50000], hi[50000], diff[50002]={0};     

        //the arrays to store ranges and diff
        scanf("%d", &N);
        for(int i=0; i<N; i++){
            scanf("%d%d", lo+i, hi+i);
            diff[lo[i]]++;
            diff[hi[i]+1]--;
        }
        set<int> good;      //set of all possible byteknights
        int ans=0, count=0;
        //if knights[n]=n then it can be a byteknight and
        //knights[n]=sum diff[i] from 0 to n
        for(int i=0; i<=N; i++){
            count+=diff[i];
            if(count==i){
                ans++;
                good.insert(i);
            }
        }
        printf("%d\n", ans);
        for(int i=0; i<N; i++){
        //tells truth i.e all possible knights are in his range
         //he has to be a byteknight
            if(lo[i]<=*good.begin() && *good.rbegin()<=hi[i])  
                putchar('1');
            else{
                putchar('0');
      //is made a knave and his range can be excluded from good set
                good.erase(good.lower_bound(lo[i]), good.upper_bound(hi[i]));
            }
        }
        putchar('\n');
    }
    return 0;
}

From this week on we start solving problems on Codechef, Interviewstreet etc. . with the view to improve your problem solving skills ..
          Apart from the code we will give a detailed mathematical and logical explanation about the problem.So lets start with something easy ..

LINK :: Question 1

Required Concepts : Euclid Algorithm

Well for both chefs we have A,B and C,D units that they can go .. so any length that is traversable by first chef is a multiple of gcd(A,B) and similarly any length that is traversable by second chef is a multiple of gcd(C,D) .. Hence units which are traversable by both are multiples of lcm=LCM(gcd(A,B),gcd(C,D)).Thus for the positive half of 1 to K number of such units equals K/lcm which is same on the other side of the rope. Hence our answer is 2*(K/lcm) + 1(bcz 0 is traversable by both as both can go forward and come back by same value).

typedef unsigned long long LL;
int T;
LL A,B,C,D,K;

LL gcd(LL a,LL b)    //euclid method for fast gcd
{
    if(b>a)
    return gcd(b,a);
    else
    return b==0?a:gcd(b,a%b);
}

int main()
{
    cin>>T;
    for(int i=0;i<T;i++)
    {
        cin>>A>>B>>C>>D>>K;
        LL n1=gcd(A,B);
        LL n2=gcd(C,D);
        LL den=gcd(n1,n2);
        LL S=n1/den;     //split the LCM part 1
        LL R=K/S;        //LCM part 2
        LL n4=R/n2;      //the final value
        cout<<(2*n4)+1<<endl;
    }
    return 0;
}

For finding LCM of a and b we used (a*b/gcd(a,b)) ..

Ever been troubled by segmentation faults .. now use gdb to take a closer inspection..

GDB stands for GNU Debugger which is a debugger for C and C++ .For any file you need to add -g to enable default debugging support.For enabling gdb just type gdb or gdb <filename> .If you did not mention the file earlier you can mention it by using the file command.
(gdb) file prog1.x
To run the program:
(gdb)run
If the program does have issues you will get information about where the program crashed i.e the line number and parameters to the function that caused the error.

The break command is used for setting the breakpoints in the program.For setting breakpoints in the file line pair use:
(gdb) break file.c:8
For breaking at a particular function use:
(gdb)break fib_func

To proceed to the next breakpoint use the continue statement:
(gdb)continue
To proceed one step at a time use the step statement:
(gdb)step

To print the value of the variables at any given time use the print command which prints the value of the variables and the print/x which gives the value of the variables mentioned in the program as hexadecimal.

Breakpoints stop the program at the points in the program ..whereas watchpoints watch over changes in the variables .
(gdb) watch i
whenever i is modified the program interrupts and prints out the old and the new values.Other useful commands are:
backtrace - produces a stack trace of the function calls that lead to a seg fault
finish - runs until the current function is finished
delete - deletes a specified breakpoint
info breakpoints - shows information about all declared breakpoints
                                                                                                                                                                                                                                                
Breakpoints are a tedious task of getting data always out of programs.To get specific
parts you can use conditional breakpoints like:
(gdb)break file1.c:6 if i >= ARRAYSIZE

So now you can try out various commands in your terminal and check out the gdb
manual for more details.

A Randomized Algorithm is one in which we use a randomizer or some kind of random number.Some decisions made in the algorithm depend on the output of the randomizer.Hence they have different runtime each time they are run even if the input is correct.
      Randomized algorithms can be divided into two categories:
Las Vegas Algorithms : These algorithms always give the correct output, however their runtime differ based on the output of the randomizer
Monte Carlo Algorithms: These algorithms give the correct answer for most of the cases however they may give incorrect answers for a small percent of values.

Primality testing using Miller-Rabin's Method: This algorithm makes use of Fermat theorem i.e. if n is prime than a^(n-1) %n=1 for any a<n.

Th2: The equation x^2%n=1 has exactly two solutions namely 1 and n-1
Th3: The equation x^2(mod n)=1 has roots other than 1 and n-1 then n is composite

The algorithm fails for some composite numbers (Carmichael numbers) for which every a that is less than and relatively prime to n will satisfy Fermats theorem.e.g 561 and 1105

Implementation:

int prime(int n,int alpha)
{
  int q=n-1;int i;
  int up=(int)alpha*log(n);
  int m,y,a,z,x;
  for(i=0;i<up;i++)
    {
      m=q;y=1;
      a=rand()%q+1;
      //choosing a random number in the range [1,n-1]
      z=a;
      //compute a^n-1 mod n
      while(m>0)
    {
      while(m%2==0)
        {
          x=z;
          z=(z*z)%n;
          if((z==1)&&(x!=1)&&(x!=q))
        return 0;
          m=(int)m/2;
        }
      m=m-1;y=(y*z)%n;
    }
      if(y!=1)
    return 0;
      //if a^n-1 mod n is not 1 n is not a prime
    }
  return 1;
}