Source Code of Some Well Known Algorithms

Hello [username]

I have decided to create a Collection of Codes based on Data Structures and Algorithms Problems or puzzle. HC Dev has a new Project and this collection will help others and so I came up with this idea. After we have solved more than 20 or 30 problems then if Deque allows then we can create a repository for this with all the codes in it, but I don't have any thing to say here, her decision will be final.

Rules to contribute:-

1. You must test your code properly for every aspect and conditions, make it as flexible as possible.
2. Use pastebin or github gist or bitbucket or anything else, for serving the purpose of syntax highlighting.
3. You can use any programming language you want but you must mention the programming language used.
4. Always give a link as a reference to the problem or puzzle you have solved.
5. You must not use any external library that has the implemention of the problem or datastructures that you use. See this reply http://www.hackcommunity.com/Thread-Resource-Source-Code-of-Some-Well-Known-Algorithms?pid=157017#pid157017 , even if you use any give the link or provide the source of that file as well. You must not use any copyrighted code. Many programming languages have in built data structures in their library, try to avoid using them and make the data structures yourself (it hardly takes much time opnce you understand it properly) or if you have already coded them earlier then use that file (import it in your source). Example :- Suppose you want to solve Josephus problem and you have want to use Circular Queue as the data structure to solve it. Then first implement Circular Queue and then import that and use it in your Josephus problem code.
6. If any problem has already been solved by another member using one technique example bruteforce and you want to implement it again but using a different technique like backtracking then you may do it. If you want to implement the same problem and using the same technique as another member solved then in that case you may do so but you must implement it in a different language. Example :- I have implemented NQueens using backtracking in C and if you want to implement the same using the same technique then you must do it in a different language like python, java, php, etc. etc.

Hope I made myself clear. If you have problems understand the rules then feel free to ask. I am not a demon and I won't devour you till the last morsel if you have doubt.

Sample Examples (How to Contribute ?):

Spoiler:

N-Queens or 8 Queens Puzzle

Language : C

Spoiler:Code:
#include<stdio.h>

char a[10][10];
int n = 4;

void printmatrix() {
    int i, j;
    printf("\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            printf("%c\t", a[i][j]);
        printf("\n\n");
    }
    printf("-------------------------------------------\n\n");
}

int getmarkedcol(int row) {
    int i, j;
    for (i = 0; i < n; i++)
        if (a[row][i] == 'Q') {
            return (i);
            break;
        }
}

int probable(int row, int col) {
    int i, tcol;
    for (i = 0; i < n; i++) {
        tcol = getmarkedcol(i);
        if (col == tcol || abs(row - i) == abs(col - tcol))
            return 0;
    }
    return 1;
}

void nqueen(int row) {
    int i, j;
    if (row < n) {
        for (i = 0; i < n; i++) {
            if (probable(row, i)) {
                a[row][i] = 'Q';
                nqueen(row + 1);
                a[row][i] = '.';
            }
        }
    } else {
        printmatrix();
    }
}

int main() {
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            a[i][j] = '.';
    printf("\nThe solution's are:- \n\n");
    nqueen(0);
    return 0;
}


/*

The solution's are:- 


.	Q	.	.	

.	.	.	Q	

Q	.	.	.	

.	.	Q	.	

---------------------------------------------------


.	.	Q	.	

Q	.	.	.	

.	.	.	Q	

.	Q	.	.	

---------------------------------------------------


*/

Visit this for Syntax Highlighting : https://gist.github.com/PsychoCoderHC/6514289

Language : C

Longest Common Subsequence Using Recursion

Spoiler:Code:
#include<stdio.h>
 
int max(int a, int b)
{
    return (a > b)? a : b;
}
 
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
   if (m == 0 || n == 0)
     return 0;
   if (X[m-1] == Y[n-1])
     return 1 + lcs(X, Y, m-1, n-1);
   else
     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
 
int main()
{
  char X[] = "GGXATAB";
  char Y[] = "GXTXAYB";
 
  int m = strlen(X);
  int n = strlen(Y);
 
  printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );

  return 0;
}

Visit this for Syntax Highlighting : http://codepad.org/WWGCWVzJ

Language : C

Longest Common Subsequence Using Dynamic Programming

Spoiler:Code:
#include<stdio.h>
#include<string.h>

int max(int a, int b) {
    return a > b ? a : b;
}//end max()

int main() {
    char a[] = "train";
    char b[] = "rain";
    int n = strlen(a);
    int m = strlen(b);
    int i, j;
    for (i = n; i >= 1; i--)
        a[i] = a[i - 1];
    for (i = m; i >= 1; i--)
        b[i] = b[i - 1];
    int l[n + 1][m + 1];
    printf("\n\t");
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= m; j++) {
            if (i == 0 || j == 0)
                l[i][j] = 0;
            else if (a[i] == b[j])
                l[i][j] = l[i - 1][j - 1] + 1;
            else
                l[i][j] = max(l[i][j - 1], l[i - 1][j]);
            printf("%d |", l[i][j]);
        }
        printf("\n\t");
    }
    printf("Length of Longest Common Subsequence = %d\n", l[n][m]);
    return 0;
}

/*


Output:-


	0 |0 |0 |0 |0 |
	0 |0 |0 |0 |0 |
	0 |1 |1 |1 |1 |
	0 |1 |2 |2 |2 |
	0 |1 |2 |3 |3 |
	0 |1 |2 |3 |4 |
	Length of Longest Common Subsequence = 4

*/

Visit this for Syntax Highlighting : https://gist.github.com/PsychoCoderHC/6513795

Language : C

KnapSack Problem Using Dynamic Programming

Spoiler:Code:
#include <stdio.h>
#include <stdlib.h>

int w[10], p[10], v[10][10], n, i, j, capacity, x[10] = {0};

int max(int i, int j) {
    return ((i > j) ? i : j);
}

int KnapSack(int i, int j) {
    int value;
    if (v[i][j] < 0) {
        if (j < w[i])
            value = KnapSack(i - 1, j);
        else
            value = max(KnapSack(i - 1, j), p[i] + KnapSack(i - 1, j - w[i]));
        v[i][j] = value;
    }
    return (v[i][j]);
}

int main(int argc, char** argv) {
    int profit, count = 0;
    printf("\nEnter the number of elements : ");
    scanf("%d", &n);
    printf("\nEnter the profit and weights of the elements\n");
    for (i = 1; i <= n; i++) {
        printf("Item no : %d\n", i);
        scanf("%d %d", &p[i], &w[i]);
    }
    printf("\nEnter the capacity \n");
    scanf("%d", &capacity);
    for (i = 0; i <= n; i++)
        for (j = 0; j <= capacity; j++)
            if ((i == 0) || (j == 0))
                v[i][j] = 0;
            else
                v[i][j] = -1;
    profit = KnapSack(n, capacity);
    i = n;
    j = capacity;
    while (j != 0 && i != 0) {
        if (v[i][j] != v[i - 1][j]) {
            x[i] = 1;
            j = j - w[i];
            i--;
        } else
            i--;
    }
    printf("Items in the KnapSack are : \n\n");
    printf("Sl.no \t weight \t profit\n");
    printf("\n----------------------------------------\n");
    for (i = 1; i <= n; i++)
        if (x[i])
            printf("%d \t %d \t\t  %d\n", ++count, w[i], p[i]);
    printf("Total profit = %d\n", profit);
    return (EXIT_SUCCESS);
}


/*

Output:-

Enter the number of elements : 3

Enter the profit and weights of the elements
Item no : 1
4 6
Item no : 2
1 2
Item no : 3
7 3

Enter the capacity 
7
Items in the KnapSack are : 

Sl.no    weight          profit

----------------------------------------
1        2                1
2        3                7
Total profit = 8


*/

Visit this for Syntax Highlighting : https://gist.github.com/PsychoCoderHC/6524537

Some problems has been mentioned below :-

(this list contains some names of some well known problems or data structures but believe me there is a huge list)

1. Djkstras Algorithm.
2. Prims Algorithm.
3. Splay Trees.
4. Bubble, Selection, Insertion, Merge, Quick, Heap, Shuffle Sort.
5. BFS & DFS
6. Binary Tree.
7. AVL tree.
8. Set, HashTable and many more ....

Contributers By Now :

Psycho_Coder
Deque
Ex094

Problems Solved :-

Spoiler:

Knapsack Problem
NQueens Problem
LCS (Longest Common Subsequence) using Dynamic Programming and Recursive (See the sample examples enclosed above for the codes of the above problems.)

Bresenham algorithm
Jacobian matrix
Bisection method
Double Hashing
Brent Hashing
Ford-Fulkerson (Max-Flow-Algorithm)
Breadth First Search
BubbleSort (java)
Textcompression with Huffman
Textcompression with LZW

Selection Sort
Bubble Sort
Insertion Sort
Gnome Sort
Merge Sort
Kadanes' Algorithm - Maximum Subarray Sum

Thank you,
Sincerely,
Psycho_Coder