Hello everyone,i think i know quick sort algorithm.But i need help in figuring out its worst case.

Lets look at the below quicksort code---->

``````void quicksort(int arr[],int low,int high) //low and high are pased from main()
{
int m;
if(low<high)
{
m=partition(arr,low,high);
quicksort(arr,low,m-1);
quicksort(arr,m+1,high);
}
}

int partition(int arr[],int low,int high)
{
int pivot=arr[low],i=low,j=high;
while(i<j)
{
while((arr[i]<=pivot)&&(i<=high))
i++;
while(arr[j]>pivot)
j--;
if(i<j)
swap(arr,i,j);               //swaps arr[i]and arr[j]
}
swap(arr,low,j);             //swaps arr[low] and arr[j]
return j;
}``````

I am not writing the definition of swap function here as it is self explanatory.

Now lets trace the above code for arr 1 2 3 4 5

``````0   4    0         partion swaps 1 with 1 and returns 0 which is assigned to m
low high m
__________________________
0   0    *
0   4    0
low high m
___________________________
0   0    *
1   4    1         partition swaps 2 with 2
0   4    0
low high m
____________________________
2   4    2         partition swaps 3 with 3
1   4    1
0   4    0
low high m
____________________________
2   1    *
2   4    2
1   4    1
0   4    0
low high m
______________________________
3   4    3            partition swaps 4 with 4
2   4    2
1   4    1
0   4    0
low high m
________________________________
3   2    *
3   4    3
2   4    2
1   4    1
0   4    0
low high m
_________________________________
4   4    *
3   4    3
2   4    2
1   4    1
0   4    0
low high m
_________________________________
Stack empty
low high m``````

ques1.Is my ...

What do you mean by a critical section?
A critical section is a piece of code of a process that accesses a shared resource that must not be accessed by more than 1 thread of execn.
1.a thread is smallest seq of programmed instrns and process is made of many threads.plz xplain in a bit detail....
2.Does a process have only 1 critical section?
3.Can 2 or more processes be in their critical section at the same time?If no why? bcoz whats the prob if the critical sections are accessing diff shared resources?
4.Also tell me what is a semaphore...i only know it is used to avoid access by multiple processes to a common resource...

thanks a lot :)

Please can anybody explain me the following things below::
1.What is a hashmap
2.Its use
3.What do we do to avoid collisions....

Problem:
input:square matrix of order n and a query which will denote the submatrix.(x1,y1,x2,y2)
output:no of distinct elements in this submatrix.
constraint:time limit=1 sec

this is what i tried

``````#include<stdio.h>
//#include<conio.h>
int main()
{
//clrscr();
int a[300][300],test[100000],count[10],m,n,c,j,p,q,r,s;
long qu,re,i;
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
scanf("%ld",&qu);
for(re=0;re<qu;re++)
{
c=0;
for(i=0;i<10;i++)
count[i]=0;
scanf("%d %d %d %d",&p,&q,&r,&s);
for(i=(p-1);i<r;i++)
for(j=(q-1);j<s;j++)
{
m=a[i][j];
count[--m]++;
}
for(i=0;i<10;i++)
if(count[i]!=0)
c++;
test[re]=c;
}
for(i=0;i<qu;i++)
printf("%d\n",test[i]);
//getch();
return 0;
}``````

but got a TLE(time limit exceeded) error.
It has to do something with cumulative frequency of each number.
Guys i have been working for over 3 days now on this problem but still didn't get it.
Please suggest me an approach to tackle this.

i don't want to overwrite the characters.
i want to append the characters at the end.

c

suppose there are two strings str1 and str2.
suppose i filled str1 with some characters.Now what i want to do is copying string str2 at some specified location in str1.
How can i do it?

``````#include<stdio.h>
#include<conio.h>
int main()
{
char cyp[150],eng[26];
scanf("%s",eng);
gets(cyp);
getch();
return 0;
}``````

eng is accepted but only one letter is accepted for cyp.

break down your data set into something manageable.
How can i do this?

i tried doing this

``````#include<stdio.h>
#include<stdlib.h>

//#define MAX 10001
void quicksort(long long[],long long,long long);
int partition(long long[],long long,long long);
void swap(long long[],long long,long long);

int main()
{
int t,k,q,i,j,qi,c;
long long *mot,*sat,*res,p;
//printf("Enter no of test cases");
scanf("%d",&t);
for(i=0;i<t;i++)
{
p=0;
printf("Enter no of chefs and no of queries");
scanf("%d %d",&k,&q);
long long *mot=(long long*)malloc(k*sizeof(long long));
long long *sat=(long long*)malloc(k*sizeof(long long));
long long *res=(long long*)malloc(k*k*sizeof(long long));
//printf("Enter motivation levels");
for(j=0;j<k;j++)
scanf("%lld",&mot[j]);
//printf("Enter satisfaction levels");
for(j=0;j<k;j++)
scanf("%lld",&sat[j]);
//calc sum[]
for(c=0;c<k;c++)
for(j=0;j<k;j++)
res[p++]=mot[c]+sat[j];
free(mot);
free(sat);
quicksort(res,0,p-1);       //partition,swap
for(j=0;j<q;j++)
{
//printf("\n qith lowest sum");
scanf("%d",&qi);
if(qi<=(k*k))
printf("%lld\n",res[qi-1]);
}
free(res);
}
return 0;
}

void quicksort(long long sum[],long long low,long long high)
{
long long m;
if(low<high)
{
m=partition(sum,low,high);
quicksort(sum,low,m-1);
quicksort(sum,m+1,high);
}
}

int partition(long long sum[],long long low,long long high)
{
long long pivot=sum[low];
long long i=low,j=high;
while(i<j)
{
while(sum[i]<=pivot&&i<high)
i++;
while(sum[j]>pivot)
j--;
if(i<j)
swap(sum,i,j);
}
swap(sum,low,j);
return j;
}

void swap(long long sum[],long long i,long long j)
{
long long temp;
temp=sum[i];
sum[i]=sum[j];
sum[j]=temp;
}``````

still failed and gave the same error as previous when i submitted

Questions:
1.CAN MALLOC allocate space for res
`long long *res=(long long*)malloc(k*k*sizeof(long long));`
when k=20,000
res would have 20,00020,000 elements & space needed=400000000 sizeof(long long)

2.I also tried static allocation for sat,mot and res
So does C support

``long long res[10^9];``

basically i posted the code on codechef.So i don't know for what input does it fail.But it works fine for small test cases.Now the constraints as i have mentioned above specify the limit for input data .So i think it would fail for some large value but i don't know which and how can we input such large value.(eg k=20,000)how can we input sat and mot for each chef?Also i have another doubt.Is there any fault in memory allocation i.e malloc cannot allocate large memory?

still i am not getting it I have been working on it since 2 days now and still couldn't find anything

``````#include<stdio.h>
#include<stdlib.h>

//#define MAX 10001
void quicksort(long long[],int,int);
int partition(long long[],int,int);
void swap(long long[],int,int);

int main()
{
int t,k,q,i,j,qi,c,p;
long long *mot,*sat,*res;
//printf("Enter no of test cases");
scanf("%d",&t);
for(i=0;i<t;i++)
{
p=0;
//printf("Enter no of chefs and no of queries");
scanf("\n%d %d",&k,&q);
mot=(long long*)malloc(k*sizeof(long long));
sat=(long long*)malloc(k*sizeof(long long));
res=(long long*)malloc(k*k*sizeof(long long));
//printf("Enter motivation levels");
for(j=0;j<k;j++)
scanf("%lld",&mot[j]);
//printf("Enter satisfaction levels");
for(j=0;j<k;j++)
scanf("%lld",&sat[j]);
//calc sum[]
for(c=0;c<k;c++)
for(j=0;j<k;j++)
res[p++]=mot[c]+sat[j];
free(mot);
free(sat);
quicksort(res,0,p-1);       //partition,swap
for(j=0;j<q;j++)
{
//printf("\n qith lowest sum");
scanf("%d",&qi);
if(qi<=(k*k))
printf("%lld\n",res[qi-1]);
}
free(res);
}
return 0;
}

void quicksort(long long *sum,int low,int high)
{
int m;
if(low<high)
{
m=partition(sum,low,high);
quicksort(sum,low,m-1);
quicksort(sum,m+1,high);
}
}

int partition(long long *sum,int low,int high)
{
long long pivot=sum[low];
int i=low,j=high;
while(i<j)
{
while(sum[i]<=pivot&&i<high)
i++;
while(sum[j]>pivot)
j--;
if(i<j)
swap(sum,i,j);
}
swap(sum,low,j);
return j;
}

void swap(long long *sum,int i,int j)
{
long long temp;
temp=sum[i];
sum[i]=sum[j];
sum[j]=temp;
}``````

This is a code that i posted on codechef but i am getting this SIGSGEV error.I cracked my head a lot but in vain.
The constraints for the problem statement were
1 ≤ t ≤ 5
1 ≤ k ≤ 20000
1 ≤ q ≤ 500
1 ≤ qi ( for i = 1 to Q ) ≤ 10000
1 ≤ Ai ≤ 10^18 ( for i = 1 to K ) (value of element of mot[] can be)
1 ≤ Bi ≤ 10^18 ( for i = 1 to K ) (value of element of sat[] can be)

I am not getting the difference between branch and bound and backtracking.I know what backtracking is but i am not able to figure out how does branch and bound actually work?

``````Algorithm NQueens ( k, n) //Prints all Solution to the n-queens problem
{
for i := 1 to n do
{
if Place (k, i) then
{
x[k] := i;
if ( k = n) then write ( x [1 : n]
else NQueens ( k+1, n);
}
}
}
Algorithm Place (k, i)
{
for j := 1 to k-1 do
if (( x[ j ] = // in the same column
or (Abs( x [ j ] - i) =Abs ( j – k ))) // or in the same diagonal
then return false;
return true;
}``````

The above code is for solving 8Queens problem using backtracking.I think that it can place the first 2 queens of two rows in respective columns and then when it comes to 3rd row queen it can't be placed as no queen needs to be attacking and it will simply exit from Algorithm Nqueens...So how is this algorithm implements backtracking?

Yes you happen to be right.I have been reading a book on compiler construction but still the picture was blur in my mind.

So,in dynamic scoping if the varibles are declared in main and then assigned values there and then main calls fact() then the fact() would be able to access the variables(local) of main() because the activation record of main()
is still on the stack?

Suppose i have 2 functions (main) and (fact).The activation record for main knows the address of fact so that it can call it.How? Do main and fact functions link before compiling?

also had another doubt....what is meant by static scope and dynamic scope?

We trace recursion using an internal stack.How can we relate this to an activation record ?i.e I want to know the relation between an internal stack and an activation record.

How can i write a recursive formula for a code and then solve it by substitution/master method ?

Ok so that's the input instance size.I also have one more doubt.How can i write a recursive formula for any code?

Suppose i have an algorithm whose time is represented by th function T(n)=n^3+2n^2
So what does n mean?

Suppose i have a 4 queens problem then i know what state space tree means but i am not able to get what does solution space mean?Also what is difference between brute force and backtracking techniques.I know that in backtracking if you don't get to a state whose bounded function is true ,we backtrack and that's how we build a solution and it requires much less states to reach to the problem.But we have to store the entire state space tree somewhere then inspite it takes less states to get to the solution what's the advantage comparing it with brute force.Is it that in both the techniques the entire state space tree is stored but the time required to find the solution is less in backtracking as it involves backtracking.

what do you mean by deterministic and non-determinstic algorithms?

For NP hard problems is it proved that there no algorithms that can solve this problem in polynomial time?
For NP complete problems there have not yet been algorithms that can solve this problems in polynomial time but you cannot completely rule out the possibility.

What is meant by deterministic and non deteministic algorithms? I read them but not getting them.I only got an abstract defintion for them.

So NP hard problems are those the scientists believe they can't be solved in polynomial time(no algorithm to solve it in polynomial time ).NP complete problems are problems that haven't been solved by any algorithm in polynomial time but can be solved in polynomial time(open research field).
right?

I know that NP problems can't be solved in polynomial time.But what do NP complete and NP hard problems mean?