Archive | Algorithms RSS feed for this section

26 March 2013 Comments Off

Bubble sort C++

//Bubble Sort

#include <iostream.h>
#include <conio.h>
#define MAX 10

class bubsort{
    int arr[MAX],n;
    public:
    void getdata();
    void showdata();
    void sortLogic();
};

void bubsort :: getdata(){
    cout<<"How many elements you require : ";
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>arr[i];
}

void bubsort :: showdata(){
    cout<<"\n--Display--\n";
    for(int i=0;i<n;i++)
        cout<<arr[i]<<"   ";
}

void bubsort :: sortLogic(){
    int temp;
    for(int i=0;i<n;i++){
        for(int j=0,exchange=0;j<n;j++){
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                exchange++;
                cout<<"\n arr[j] = "<<arr[j]<<"  arr[j+1] = "<<arr[j+1];
            }
        }
        cout<<endl;
        if(exchange==0)
            break;
    }
}

void main(){
    clrscr();
    cout<<"\n*****Bubble Sort*****\n";
    bubsort obj;
    obj.getdata();
    obj.sortLogic();
    obj.showdata();
    getch();
}
Tags:
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: ,
4 June 2011 Comments Off

Steven Halim’s book: Slides Download

Sample codes for the data structures and algorithms mentioned in the book:
NEW (but not yet stable): C++ and Java codes.zip (latest update 24 January 2011)

PDF slides for coaches/instructors/lecturers/students who wants to do self-study:

Material (public version)
sample_chapter_1.pdf ; skillset.xls ; and paper on CS32333
week02_ds_libraries.pdf ; and Fenwick Tree paper
(Union Find and Segment Tree are skipped)
week03_paradigms.pdf; A* search, and IDA* search
week04_dp_1.pdf; DP 0-1 Knapsack; and DP TSP
week05_graph_1.pdf (MST is skipped)
week06_graph_2.pdf (Euler graph is skipped)
week08_dp_2.pdf (some interesting examples are skipped)
week09_graph_3.pdf (max flow/bipartite graph variants are skipped)
week10_maths.pdf (there are so many topics…, many are skipped)
week11_string.pdf (DP on string has been discussed earlier)
week12_geometry.pdf (plane sweep; intersection problems skipped)
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

[...]

16 April 2011 Comments Off

Robert Sedgewick’s Algorithm Lectures

Hello programmers, Today I would like to give you the links of  Robert Sedgewick’s Algorithm Lectures. Robert Sedgewick works in the Department of Computer Science, Princeton University, Princeton, NJ 08544

Below are links to the lecture slides. This list is tentative and is to be considered subject to change. Minor updates are possible at any time. Substantive updates (not unlikely the evening before a lecture) will be marked with the date of change. Here are the reported errata.

LECTURE SLIDES DEMOS
Intro · Union find
Analysis of algorithms
Stacks and queues (new 2/7)
Elementary sorts sorting animations
Mergesort sorting animations
Quicksort
Priority queues
Symbol tables · BSTs
Balanced search trees
Hash tables · Applications
Undirected graphs (new 3/10) DFS BFS maze
Directed graphs (fixed 3/23) DFS topological sort
Minimum spanning trees (new 3/23) Graph applet
Shortest paths (new 3/28) Dijkstra
Radix sorts string sorting
Tries
Data compression
Substring search substring search
Regular expressions
Geometric primitives convex hull Voronoi
Geometric search·Intersection sweep line intersection
Reductions·Intractability
Combinatorial search The Longest Path [mp3]

This file with all the slides for Lectures 1-10 (28 MB) is suitable for uploading to a portable device, as is this file with all the slides for Lectures 12-24 (40 MB) and this file with all the slides for the course (66 MB). These files do not reflect changes made as the semester progresses

15 March 2011 Comments Off

Top Coder – Algorithm Tutorials

Q. How to do better in Contests?

A. Very nice place to start is the TopCoder Algorithm Tutorials. They have some very good articles. But at the end of the day, you will need to study a good book on algorithms. The most popular one is CLRS (“Introduction to Algorithms” by Cormen et. al.). I would also recommend “Algorithm Design” by Kleinberg and Tardos.

Also, sites like TopCoder, Google Code Jam and CodeForces have problem analyses and the code submitted during the contest available. Reading those is a great way learning new techniques and approaches.….

Writer                                         Tutorials

lbackstrom The Importance of Algorithms
antimatter How To Dissect a TopCoder Problem Statement
Dumitru How to Find a Solution
leadhyena_inran Planning an Approach to a TopCoder Problem:
Section 1
Section 2
dimkadimon Mathematics for TopCoders
lbackstrom Geometry Concepts:
Section 1: Basic Concepts
Section 2: Line Intersection and its Applications
Section 3: Using Geometry in TopCoder Problems
gladius Introduction to Graphs and Their Data Structures:
Section 1: Recognizing and Representing a Graph
Section 2: Searching a Graph
Section 3: Finding the Best Path through a Graph
supernova Greedy is Good
Dumitru Dynamic Programming: From novice to advanced
misof Computational Complexity
Section 1
Section 2
Dan[Popovici] & mariusmuja Using Regular Expressions
supernova Understanding Probabilities
timmac Data Structures
cucu New Features of Java 1.5
timmac Sorting
_efer_ Maximum Flow
Section 1
Section 2
misof Representation of Integers and Reals
Section 1
Section 2
lovro Binary Search
bmerry A bit of fun: fun with bits
danielp Range Minimum Query and Lowest Common Ancestor
DmitryKorolev Power up C++ with the Standard Template Library: Part I
DmitryKorolev Power up C++ with the Standard Template Library: Part II: Advanced Uses
medv Prime Numbers, Factorization and Euler Function
jmzero An Introduction to Recursion, Part 1
jmzero An Introduction to Recursion, Part 2
cpphamza An Introduction to Binary Search and Red-Black Trees
bmerry Line Sweep Algorithms
Zealint Minimum Cost Flow
Part 1 – Key Concepts
Part 2 – Algorithms
Part 3 – Applications
rasto6sk Algorithm Games
boba5551 Binary Indexed Trees
TheLlama Introduction to String Searching Algorithms
Zealint Maximum Flow: Augmenting Path Algorithms Comparison
x-ray Basics of combinatorics
NilayVaish A New Approach to the Maximum Flow Problem
vlad_D Disjoint-set Data Structures
luison9999 Using Tries
dcp An Introduction to Multidimensional Databases
zmij The Best Questions for Would-be C++ Programmers
Part 1
Part 2
innocentboy Primality Testing : Non-deterministic Algorithms
x-ray Assignment Problem and Hungarian Algorithm