Finding the square root (of a perfect square) using binary search c#

Well, the logic is pretty straightforward. We start a binary search from a range of 0 to NUM, where NUM is the number whose root we are looking for. Each time, we calculate the middle item of the range and see if it is the square root. If not, we search further either in the right side or the left side of the mid item depending on whether the mid^2 is lesser or greater than NUM.

[code language="cpp"]
double GetRoot(double Num,double High=0, double Low=0)
{
if(High<Low || High-Low==1) return -1; //End case
if(High==Low && Low==0) High=Num; //Start case
int Mid= Low+((High-Low)/2);
if(Mid*Mid==Num) return Mid;
else
{
if(Mid*Mid>Num) return GetRoot(Num,Mid,Low);
else if(Mid*Mid<Num) return GetRoot(Num,High,Mid);
}
}

[/code]

If you have thoughts/ suggestions, post em on comments.

N Queens problem

Well, I can't possibly have an 'algorithm of the day' thread without solving the all famous N QUEENs problem.

Problem description:

Place the maximum amount of Queens on an N by N chess board and print the possible arrangements

Solution:

We will be placing 1 queen at a time per row. We would start  from the left most end of the row and move 1 step to the right if there is a collision. We keep doing this till we find a spot that does poses no collisions. If there is no such spot, then one of the previous queens must be moved elsewhere.

Code:

[code language="cpp"]
//NQueen problem
#include
using namespace std;

int N;
int Pos=0;

void NQueenDroid(int Board[100], int Remaining)
{
if(Remaining==0)
{
//found a solution
cout<<endl;
for(int i=0;i<N;i++) cout<<Board[i]<<" - ";
Pos++;
return;
}

int Cur= N-Remaining; //placement of current queen
for(int i=0;i<N;i++)
{
bool IsColliding= false;
for(int k=0;k<Cur;k++)
{
//Collision in columns
if(Board[k]==i) {IsColliding=true; break;}
if(abs(Board[k]-i)==abs(Cur-k))
{IsColliding=true; break;} //Collision in diagonals
}
if(IsColliding) continue;
Board[Cur]=i; //place queen
NQueenDroid(Board,Remaining-1);
}
}

int main()
{

N=0;
cout<<"Enter the board size :";
cin>>N;
int Board[100]={0};
NQueenDroid(Board,N);

//End of code
return 0;
}

[/code]

Dijkstra's Algorithm

Hi,

I'm revamping my algo skills and thought of putting up the code in my blog for fun and for other's reference.

Following is the Dijkstra's Algorithm, which is used to find the shortest path to all nodes of a graph from a single selected node.

[code language="cpp"]

//Dijkstra's Algorithm
//Shortest Path Algo

#include
using namespace std;
#define INF 999
#define SIZE 5
bool isMoreToVisit(bool VisitedArray[5])
{
for(int i=0;i<SIZE;i++)
if(VisitedArray[i]==false) return true;
return false;
}

int main()
{
int StartNode=0;
int Distances[SIZE]={INF};
bool Visited[SIZE]={false};
int Graph[SIZE][SIZE]={{0,10,5,15,INF},{INF,0,INF,INF,INF},{INF,6,0,INF,500},{INF,INF,INF,0,8},{3,INF,INF,INF,0}};
int CurrentNode=StartNode,CurrentTrace=0;

Distances[StartNode] =0;
while(isMoreToVisit(Visited)==true)
{
Visited[CurrentNode] = true;
for(int i=0;i<SIZE;i++)
if(Visited[i]==false) //Recalib all unvisited nodes
if(Graph[CurrentNode][i]+CurrentTrace<Distances[i])
Distances[i] = Graph[CurrentNode][i]+CurrentTrace;

//Fix next node to be visited
int MinNodeVal= INF;
for(int i=0;i<SIZE;i++)
if(Visited[i]==false)
if(Distances[i]<MinNodeVal)
{
MinNodeVal= Distances[i];
CurrentNode=i;
}
CurrentTrace=MinNodeVal;
};

cout<<endl<<"Resulting answer: \n\n";
for(int j=0;j<SIZE;j++) cout<<" - "<<Distances[j];
return 0;
}
[/code]