[Psycho_Coder]

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-Reso...#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

[Slarek]

Are these just challenges without any points or something?

[Psycho_Coder]

Are these just challenges without any points or something?

No these are not challenges. You get no points for your contribution. You can contribute to the collectrion of the problems mentioned above or other problems related to data structures and algorithms. HC DEV group of HC has a new project and I am making this collection of source codes for that purpose so that everyone can learn and gets the codes for reference. If you want to contribute you can but you get no points for that as this is not a contest.

[Psycho_Coder]

Added Knapsack problem using dp

[Slarek]

Here's my contribution:


Challenge:Binary tree
Wikipedia: http://en.wikipedia.org/wiki/Binary_tree
Pastebin: http://pastebin.com/QzsK5Upm
Language: C/C++

Code:

#include <stdio.h> #include <stdlib.h> #include <iostream.h> #include <classlib\binimp.h> #include <string.h> void print(string &s,void *os) { (ostream &)os << s << " "; } #define print_tree(cout,tree) { tree.ForEach(print,(void *)cout); cout << "\n"; } int main(void) { TBinarySearchTreeImp<string> tree; string s; char ss[10]; cout << "--------------------------------------------------------------\n"; for (int i=0; i<15; i++) { //Fill the tree with random strings sprintf(ss,"%03d",(rand() % 1000)); cout << ss << " "; tree.Add(ss); } cout << "\n"; cout << "--------------------------------------------------------------\n"; cout << "Content of the tree:\n"; print_tree(cout,tree); while (1) { cout << "Give a string and I'll check if it's in the tree >"; getline(cin,s,'\n'); if ( s == "" ) break; if ( tree.Find(s) ) { tree.Detach(s); cout << s << " It was in the tree, it got deleted!\n"; print_tree(cout,tree); } else cout << "Not in the tree!\n"; } return 0; }

[Psycho_Coder]

Here's my contribution:


Challenge:Binary tree
Wikipedia: http://en.wikipedia.org/wiki/Binary_tree
Pastebin: http://pastebin.com/QzsK5Upm
Language: C/C++

Code:

#include <stdio.h> #include <stdlib.h> #include <iostream.h> #include <classlib\binimp.h> #include <string.h> void print(string &s,void *os) { (ostream &)os << s << " "; } #define print_tree(cout,tree) { tree.ForEach(print,(void *)cout); cout << "\n"; } int main(void) { TBinarySearchTreeImp<string> tree; string s; char ss[10]; cout << "--------------------------------------------------------------\n"; for (int i=0; i<15; i++) { //Fill the tree with random strings sprintf(ss,"%03d",(rand() % 1000)); cout << ss << " "; tree.Add(ss); } cout << "\n"; cout << "--------------------------------------------------------------\n"; cout << "Content of the tree:\n"; print_tree(cout,tree); while (1) { cout << "Give a string and I'll check if it's in the tree >"; getline(cin,s,'\n'); if ( s == "" ) break; if ( tree.Find(s) ) { tree.Detach(s); cout << s << " It was in the tree, it got deleted!\n"; print_tree(cout,tree); } else cout << "Not in the tree!\n"; } return 0; }

Sorry But I can't include this as you have not implementred the methods for Binary tree. The standard methods that Binary Tree ADT has. You are using #include <classlib\binimp.h> which may not be available to all the users. We want that all the methods should be included within file and not use any external file. Even if you use any external file and want to include it in your coede then that code must be yours and not any copyrighted code.

I will include this in the rules. Please retry and thanks as you are the first to try to contribute.

This should help you out :- http://phoenix.goucher.edu/~kelliher/cs23/may07.html

[Deque]

Thanks a lot @Psycho_Coder for taking this in your hands and sorry that I didn't do anything up to now. Let's see what I can contribute. I have done lot's of such codes years ago for university (not sure that I can find them all, though)

[Psycho_Coder]

Thanks a lot @Psycho_Coder for taking this in your hands and sorry that I didn't do anything up to now. Let's see what I can contribute. I have done lot's of such codes years ago for university (not sure that I can find them all, though)

Don't be sorry please Ma'am, it sounds awkward. You have contributed a lot in many ways. Do everything at your own ease!

[Deque]

Bresenham algorithm

Language: Java
Description: draws a line from starting point (x0, y0) to endpoint (xn, yn) with color f.
Code: http://pastebin.com/F5TxLzFD
Link: https://en.wikipedia.org/wiki/Bresenham%..._algorithm

Antialiasing for a line

Language: Java
Description: Draws an antialiased line with the starting point (x1, y1) and dx, dy being the difference from start to endpoint (dx = abs(x1 - x2) and dy = abs(y1 - y2))
The putPixel method tells where to put a pixel and how much it is colored with 1 being black and 0 being white.
Code: http://pastebin.com/ZE2bMpG2
Pixel class: http://pastebin.com/5e8WpVXU

Example picture:



Link: https://en.wikipedia.org/wiki/Spatial_anti-aliasing

Jacobian matrix

Language: Java
Description: Calculates the Jacobian Matrix
Link: https://en.wikipedia.org/wiki/Jacobian_m...eterminant
Code: http://pastebin.com/M1mfRiyn
Function class: http://pastebin.com/bQAdMss3

Bisection method

Language: Java
Description: Bisection method for a function f in the intervall (a,b)
Link: https://en.wikipedia.org/wiki/Bisection_method
Code: http://pastebin.com/eKkSMLG9

Double Hashing

Language: Java
Description: Demonstrates double hashing algorithm
Link: https://en.wikipedia.org/wiki/Double_hashing
Code: http://pastebin.com/bFPuB8TN

Brent Hashing

Language: Java
Description: Demonstrates brent hashing algorithm, which was made as an improvement to the double hashing
Link: http://www.minkhollow.ca/Courses/461/Not...ntex1.html
Code: http://pastebin.com/p8FzAESN

I have to admit that these codes could be better in some details. They are old, I was a programming beginner, when I wrote them.

[Psycho_Coder]

Language : Java 1.7
Link : Selection Sort

Code : https://gist.github.com/PsychoCoderHC/6541715