31 August 2011 Comments Off

Some algorithms you will need all the time…

ReHash – A console-based hash calculator -

http://www.codeproject.com/cpp/rehash.asp
A console-based hash calculator. Supported algorithms: CRC-16, CRC-16-CCITT, CRC-32, FCS-16, FCS-32, GHash-32-3, GHash-32-5, GOST-Hash, HAVAL-5-256, MD2, MD4, MD5, SHA-1, SHA-256, SHA-384, SHA-512, Tiger.

Using PPMD for compression -

http://www.codeproject.com/cpp/ppmd.asp
This article presents a class for using PPM to compress a file.

Genetic and Ant Colony Optimization Algorithms -

http://www.codeproject.com/cpp/GeneticandAntAlgorithms.asp
Genetic and Ant Colony Optimization Algorithms

A Mersenne Twister Class -

http://www.codeproject.com/cpp/mersennetwisterclass.asp
A pseudorandom number generator.

CFraction – a double / fraction / string conversion class -

http://www.codeproject.com/cpp/fraction.asp
A class that converts between doubles, strings and fractional representations.

File Exist Algorithms -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=5186&lngWId=3
This function will check to see if a file exist in the computer if it doesnt it will return -1 else 0.

Resize the array -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=8553&lngWId=3
resize the array in the class while the run-time

Create and pass a 2D dynamic array -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=4770&lngWId=3
These program shows how to create and pass a 2D dynamic array to a function. It can be very useful for applications that you might create.

PAGE REPLACEMENT ALGORITHMS (FIFO) -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=4986&lngWId=3
A representation of the First In First Out Algorithm in Page Replacement Algorithms

A Alphabetic Diomond V 1.0 -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=6539&lngWId=3
This is my first submission on PSC.My this Code Prints the Alphabetic Diamond.Look Output here, it is so easy. It will take a number input for no. of alphabets should be in Diamond.It is the Demonstration of for loop

A Fraction Calculator -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=3684&lngWId=3
This is just a simple Calculator that allows someone to +,-,*,/ fractions. Was a class lab thought it might actually be useful to someone.

A Faster Way to “MOD” and how to grab a digit from an Integer -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=6567&lngWId=3
This program is to show how to get the last digit of an integer type without using “last_digit = num % 10″ It also shows that “%” is slower than my optimized code due to “%” using division My optimized code is faster than using “%” about 90% of the time

C++ Datastructures and Algorithms -

http://www.mathtools.net/C_C__/Algorithms_and_Data_structures/index.html

An Introduction to Data Structures with C++

-

http://www.intelligentedu.com/blogs/post/Best_New_Training_Sites/303/An-Introduction-to-Data-Structures-with-C

C++ Datastructures -

http://www.hermetic.ch/cfunlib.htm

C++ Algorithms

-

http://oopweb.com/Algorithms/Files/Algorithms.html

Computer science C++ programs and source code by James Pate Williams, Jr. -

http://www.mindspring.com/~pate/
Queen Search algorithm for solving the n-queens algorithm, Morris’ breakout algorithm, Dozier and Williams’ breakout algorithms, Simulated annealing solution of the n-queens problem.

Cenelia Gonzales C++ sources -

http://www.ai-search.4t.com
Collection of algorithm source code includes. String Tokenizer, Fuzzy String Matching, Rational Number Class, Simple FSM, Equation Solver, Guessing Games.

Vivek Patel C++ Sources -

http://www.vivekpatel.cjb.net/
Data Structures(Arrays, Linked List, Stack) and Algorithm related sources.

MTS-HOME -

http://www.mts-home.cjb.net/
Collection of sources C,C++ and other languages by Muhammad Tahir Shahzad. C++ sections includes. Algortihms, Data Structures, Numerical Analysis and other topics.

Solving NonLinear Equations -

http://www.cpp4u.com/files/progdize2/NA_ALIRAZA.zip
C# Author ALI RAZA SHAIKH

AVL Tree -

http://www.cpp4u.com/files/progdize2/5-1.zip
C++ Author ALI RAZA SHAIKH

Huffman Coding (Encryption) -

http://www.cpp4u.com/files/progdize2/5-2-a.zip
Huffman Coding Encryption. Huffman coding is to use an encryption key to. shuffle the Huffman tree before the encoding. C++ Author ALI RAZA SHAIKH

Gauss Jordon -

http://www.cpp4u.com/files/progdize2/Gauss-Jordan.zip
Solution of equation by Gauss-Jordan C# Author FIDA HUSSAIN

Rational Number Class -

http://www.cpp4u.com/files/ai/Rational_Numbers_Class-1.zip
Class to represent valid rational numbers

Tower of Hanoi -

http://cpp4u.com/files/MTS/Algorithms/ALGO-05.zip
A C++ Program to solve the Towers of Hanoi Problem (using Recursive Algorithm). Author:Muhammad Tahir Shahzad

Fibonacci series -

http://cpp4u.com/files/MTS/Algorithms/ALGO-09.zip
A C++ Program to computes the n_th term of the fibonacci series using Dynamic Programming Technique. Author:Muhammad Tahir Shahzad

fibonacci series using Toplogical Odering -

http://cpp4u.com/files/MTS/Algorithms/ALGO-10.zip
A C++ Program to computes the n_th term of the fibonacci series using Toplogical Odering and Dynamic Programming Technique. Author:Muhammad Tahir Shahzad

Prim’s Algorithm -

http://cpp4u.com/files/MTS/Algorithms/ALGO-11.zip
A C++ Program to implement the Prim’s Algorithm to solve Minimum Spanning Tree Problem (MST). Author:Muhammad Tahir Shahzad

Prim’s Algorithm with Graphics -

http://cpp4u.com/files/MTS/Algorithms/ALGO-12.zip
A C++ Program to implement the Prim’s Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics. Author:Muhammad Tahir Shahzad

Prim’s Algorithm -

http://cpp4u.com/files/MTS/Algorithms/ALGO-13.zip
A C++ Program to implement the Prim’s Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics and with Mouse support. Author:Muhammad Tahir Shahzad

Kurskal’s Algorithm -

http://cpp4u.com/files/MTS/Algorithms/ALGO-14.zip
A C++ Program to implement the Kurskal’s Algorithm to solve Minimum Cost Spanning Tree Problem (MST). Author:Muhammad Tahir Shahzad

Kurskal’s Algorithm -

http://cpp4u.com/files/MTS/Algorithms/ALGO-15.zip
A C++ Program to implement the Kurskal’s Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics. Author:Muhammad Tahir Shahzad

Kurskal’s Algorithm with Graphics with Mouse Support -

http://cpp4u.com/files/MTS/Algorithms/ALGO-16.zip
A C++ Program to implement the Kurskal’s Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics with Mouse Support. Author:Muhammad Tahir Shahzad

Towers of Hanoi -

http://cpp4u.com/files/MTS/data-structures/DS-37.zip
“A C++ Program to solve the mystery of Towers of Hanoi.Author:Muhammad Tahir Shahzad URL www.wol.net.pk/mtshome TurboC”

Blitz++ a C++ class library -

http://www.oonumerics.org/blitz/
Blitz++ is a C++ class library for scientific computing which provides performance on par with Fortran 77/90. It uses template techniques to achieve high performance. The current versions provide dense arrays and vectors, random number generators, and small vectors and matrices.
Tags: ,
2 May 2011 Comments Off

MIT: Algorithm Lectures Video

by Prof. Erik Demaine, Prof. Charles Leiserson

Lecture 1: Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort- Go to this video

Lecture 2: Asymptotic Notation; Recurrences; Substitution, Master Method- Go to this video

Lecture 3: Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication- Go to this video

Lecture 4: Quicksort, Randomized Algorithms- Go to this video

Lecture 5: Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort-Go to this video

Lecture 6: Order Statistics, Median- Go to this video

Lecture 7: Hashing, Hash Functions- Go to this video

Lecture 8: Universal Hashing, Perfect Hashing- Go to this video

Lecture 9: Relation of BSTs to Quicksort – Analysis of Random BST- Go to this video

Lecture 10: Red-black Trees, Rotations, Insertions, Deletions- Go to this video

[...]

23 March 2011 Comments Off

Computer Science/ Algorithm Lectures

Computer Science/ Algorithm Lectures by  Mr. Syed Monowar Hossain (Department of CSE, The University of Dhaka, Bangladesh). This is one of best lectures collection for Algorithm Course. Old lectures in a ZIP file.

Course Outline 0_syllabus.ppt
Breadth First Search 1_bfs.ppt
Depth First Search 2_dfs.ppt
Topological Sort 3_topological_sort.ppt
Strongly Connected Components 4_scc.ppt
Articulation Point 5_articulation.ppt
Minimum Spanning Tree (Prims Algorithm) 6_mst_prim.ppt
Minimum Spanning Tree (Kruskal’s Algorithm) 7_mst_kruskal.ppt
Single Source Shortest Path (Dijkstra) 8_dijkstra.ppt
Single Souce Shortest Path (Bellman Ford) 9_bellmanford.ppt
All Pairs of Shortest Path (Warshall’s Algorithm) 10_warshall.ppt
Types of Algorithm 11_AlgTypes.ppt
Divide and Conquer 12_DC.ppt
Greedy Algorithm (Part 1) 13_greedy I.ppt
Greedy Algorithm (Part 2) 14_greedy II.ppt
Dynamic Programming (Part 1) 15_dynamic I.ppt
Dynamic Programming (Part 2) 16_dynamic II.ppt
Dynamic Programming (Part 3) 17_dynamicIII.ppt
Network Flow (Part 1) 18_maxflow_1.ppt
Network Flow (Part 2) 19_maxflow_2.ppt
Network Flow (Part 3) 20_maxflow_3.ppt
Number Theory 21_Euclid.ppt
NP Complete Problems 22_NP.ppt
Approximation Algorithm 23_approx.ppt
Asymptotic Notation 24_asymptotic.ppt
Recurrence Relation I 25_recurrence.ppt
Recurrence Relation II 26_recurrence II.ppt
Computation Geometry _27_geometry_1.ppt
String Matching I 28_string_matching_1.ppt
String Matching II 29_string_matching_2.ppt
Review Class 30_review.ppt
29 August 2010 Comments Off

LIS


#include<stdio.h>
#define MAXN 100

int A[MAXN], N;
int L[MAXN], P[MAXN];

void printPath(int x) {
if(P[x] == -1) {
printf("%d",x);
return;
}
printPath(P[x]);
printf(" %d",x);
}

int doLIS() {
int i, j;
int longest = 0, last = 0;
for(i = 1; i<=N; i++) {
int max = 0;
int parent = -1;
for(j = i-1; j>=0; j--) {
if(A[i] > A[j]) {
if(L[j] > max) {
max = L[j];
parent = j;
}
}
}
L[i] = max+1;
P[i] = parent;
if(L[i] > longest) {
longest = L[i];
last = i;
}
}
printf("LIS : ");
printPath(last);
puts("");
printf("Length: %d\n",longest);
return longest;
}

int main() {
int i;
while(scanf("%d",&N) == 1) {
A[0] = 0;
for(i = 1; i<= N; i++) {
scanf("%d",&A[i]);
}
doLIS();

}
return 0;
}
Tags: ,
29 August 2010 Comments Off

BFS algorithm in C++

/*

BFS algorithm in C++

*/
#include<stdio.h>
#define maxn 101

int Q[maxn];
int top ,back;
int Node, Edge;

char link[maxn][maxn];
char Fg[maxn];
int Path[maxn];

void Ini() {
int i, j;
for(i = 1; i<= Node; i++) {
for(j = 1; j<= Node; j++) {
link[i][j] = 0;
}
Path[i] = i;
Fg[i] = 0;
}
}

void Insert(int n) {
Q[back++] = n;
back %= maxn;
}

int Pop() {
int n = Q[top++];
top %= maxn;
return n;
}

int isEmpty() {
if(top == back) return 0;
return 1;
}

void PrintPath(int n) {
if(n == Path[n]) {
printf("%d",n);
return;
}
PrintPath(Path[n]);
printf(" %d",n);
}

int BFS(int s, int ter) {
int u, v, i;
Insert(s);
Fg[s] = 1;
while(isEmpty() == 1) {
v = Pop();
if(v == ter) {
PrintPath(v);
return 1;
}

for(i = 1; i<= Node; i++) {
if(link[v][i] == 1 && Fg[i] == 0)  {
Fg[i] = 1;
Insert(i);
Path[i] = v;
}
}
}
return -1;
}

void main() {
int i, u, v;
scanf("%d%d",&Node,&Edge);
Ini();
while(Edge--) {
scanf("%d%d",&u,&v);
link[u][v] = link[v][u] = 1;
}
scanf("%d%d",&u,&v);
BFS(u,v);
printf("\n");
}

/*
4 5
1 2
2 3
1 3
3 4
2 4
1 4
*/
Tags: ,
29 August 2010 Comments Off

MST(Kruskal’s Algorithm)


/*
MST(Kruskal's)
*/

#include<iostream.h>
#include<stdlib.h>

#define MAXN 102

int P[MAXN], Rank[MAXN];

int Node, edg, Cost;

struct edge {
int u, v;
int cost;
};

edge Edge[MAXN*MAXN];
edge Path[MAXN];

int com(const void *xy, const void *xz) {
edge *x = (edge*)xy;
edge *y = (edge*)xz;
return (x->cost - y->cost);
}

void In() { // initializing parent and rank for each node
int i;
for(i = 1; i<= Node; i++) {
P[i] = i;
Rank[i] = 1;
}
}

int Find(int n) { // find the parent of a node
if(P[n] != n)
P[n] = Find(P[n]);
return P[n];
}

void Link(int x, int y) { // joining the nodes
if(Rank[x] > Rank[y]) {
P[y] = x;
}
else {
P[x] = y;
if(Rank[x] == Rank[y])
Rank[y]++;
}
}

void Kruscal() {
int x, y, total = 0;
Cost = 0;
for(int i = 0; i<edg; i++) {
x = Find(Edge[i].u);
y = Find(Edge[i].v);
if(x != y) { // if not cycle

Path[total++] = Edge[i];
Link(x,y); // join those node
Cost += Edge[i].cost;
if(total == Node - 1) break; // already taken all nodes ?
}
}
}

void Cal() {
qsort(Edge,edg,sizeof(edge),com); // sorting the edges respect to cost
Kruscal();
cout<<"Total Cast :"<<Cost<<endl;
for(int i = 0; i<Node-1; i++) // printing the path
cout<<Path[i].u<<" "<<Path[i].v<<" "<<Path[i].cost<<endl;
}

void main() {
int i;
while(cin>>Node>>edg) { // reading number of node and edge
In();
for(i = 0; i<edg; i++)  // reading each edate with cost
cin>>Edge[i].u>>Edge[i].v>>Edge[i].cost;
Cal();
}
}