yeasir007

Tuesday, January 30, 2018

Insertion Sort

Insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there in each iteration. It repeats until no input elements remain. It always maintains a sorted sub list in the lower position of the list.

Time Complexity of this algorithm is O(n*n)

Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted. Normally this algorithm is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced.

Binary search can reduce the number of comparisons in normal insertion sort. We can use Binary search due to find the proper location to insert the selected item of each iteration. At normal insertion, sort takes O(i) in worst case but it will take O(log i) by using binary search.

Algorithm
insertionSort(arr, n) // Sort an arr[] of size n
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

Bellow figure shows the insertion sort process. The shaded items will represent the order of each iteration.

Here bellow is another figure will show details process of a single iteration.

Recursion

yeasir007 Algorithm , C++

What is recursion?

Sometimes a problem is too difficult or too complex to solve because it is too big. If the problem can be broken down into smaller versions of itself, we may be able to find a way to solve one of these smaller versions and then be able to build up to a solution to the entire problem. This is the idea behind recursion; recursive algorithms break down a problem into smaller pieces which you either already know the answer to, or can solve by applying the same algorithm to each piece, and then combining the results.

Identify the 3 parts of the recursive algorithm :

All recursive algorithm must have the following three stages:

Base Case: if ( actualResult() == 2 ) result = a + b;
"Work toward base case": a+b becomes the first parameter
This reduces the number of parameters to the function from 3 to 2, and 2 is the base case!
Recursive Call: add_numbers(a+b, c);

Why recursion works?

In a recursive algorithm, the computer "remembers" every previous state of the problem. This information is "held" by the computer on the "activation stack" (i.e., inside of each functions workspace).
Every function has its own workspace PER CALL of the function.

As an example we will discuss about computing Factorial of a number. What is the factorial of number X?
*** factorial(X) = X * (x-1) * (x-2) * ... * 2
But "(x-1) * (x-2) * ... * 2" is the equal of factorial(X-1)
So combine definition would be factorial(X) = X * factorial(X-1);

[Problem]
Find the factorial value of the given number, X (1 <= x <= 20) and print as shown below:
The given number is greater than or equal to 1 and less than or equal to 20.

[Input]
The first input line contains the number of test cases, T.
Then, T number of input will be given.

[Output]
For each given test case, print the factorial value.

INPUT =============
3 // number of Test cases
9 // Test case index
12 20

OUTPUT
===============================
#1 9! = 362880
#2 12! = 479001600

#3 20! = 2432902008176640000

Solution for C++:

#include
using namespace std;

long long factorial(int num);

int main(void)
{
    int test_case;
    int T;
    int num;
    long long value;

    freopen("CreateRecursion.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d", &num);
        value = factorial(num);
        printf("#%d %d! = %lld\n", test_case, num, value);
    }
}

long long factorial(int num)
{
    if (num == 0)
    {
        return 1;
    }
    else
    {
        return num * factorial(num - 1);
    }
}

Solution for Java:

Implement Graph without STL in C++/Java

yeasir007

A graph is a data structure which is a pictorial representation of a set of objects where pairs of objects are connected by links.

[problem]
Print the vertices that are adjacent to the given vertex in query.

[Input]
The first line contains the number of vertices V, the number of edges E and the number of queries Q.
From the second line on, the edge information (number of linked vertices pairs) will be given in ascending order.
On the next line, queries given as vertex numbers (asking for the adjacent vertices) will be given.
Also, edges do not overlap.
Print on each line the adjacent vertices of the given vertex. (2<=V<=100, 1<=E<=1000)

[Output] For each given vertex, print adjacent vertexes.

Implement Tree without STL in C++/JAVA

yeasir007

[problem]
Construct a tree with the given input and traverse the tree in preorder.
Then, print the visited node numbers.

[Input]
The first input line contains the number of total test cases, T.
The next line contains the number of total nodes, N and the number of edges, E.
On the following line, the edges will be given.
The edges consist of two vertices which are always given in the order “parent-child”.
For instance, 1 2 refers to the edge connecting vertex 1 and vertex 2: 1 stands for parent, 2 for child.
Parent can have two children nodes at most.
The number of nodes can be up to 10000.

[Output]
Traverse the tree in preorder, then print the visited node numbers.

Implement Link List without STL in C++/JAVA

yeasir007

Linked list is a linear collection of data elements pointing to the next node by means of a pointer.
It is a data structure consisting of a group of nodes which together represent a sequence.

[Problem]
Insert the given N integers to a linked list.
Print the remainder after
1. removing the first number pointed
2. removing next->next recursively
1 // remove the first number pointed 2 3 4 5 2 // pointer moved to 2, remove next->next 4 3 4 5 2 3 5 // pointer moved to 5, remove next->next 3 2 5 // pointer moved to 5, remove next->next 5 2 // remainder

[Input]
The first input line contains the number of test cases, T.
The second line contains the number of input, N (2 <= N <= 100).
On the next line, N data will be given.

[Output]
For each given test case, print the remainder

Implement Priority Queue without STL in C++/Java

yeasir007

A priority Queue is a data structure where each element has a "priority" associated with it.
In a priority queue, an element with high priority is served before an element with low priority.

[problem]
Store the given N (2 <= N <= 100) numbers into a priority queue, then print from the highest to the
lowest priority in order (assuming that there is no error in the input).

[Input]
The first input line contains the number of test cases, T.
The next line contains the number of data input.
Then, the integer data will be listed.
Lower number has a higher priority.

[Output]
For each given test case, print the numbers in priority order.

Implement Hash without STL in C++ and Java Language:

yeasir007

A hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values.
Hash table uses a hash function to compute an index searching into an array of buckets or slots.

[problem]
Store the given N key and data pairs into a hash table, then print each data matching to Q key inputs. * Key : Max 64 chars * Data : Max 128 chars

[Input]
The first input line contains the number of test cases, T.
The next line contains the number of keys and data pairs, N (1<= N <= 4096).
For the following N lines, key and data will be given.
Then the number of keys to search, Q (1 <= Q <= 4096) is given.

[Output]
For each given test case, print the data matching to the given keys.

Tuesday, January 30, 2018

Insertion Sort

Recursion

What is recursion?

Why recursion works?

Implement Graph without STL in C++/Java

Implement Tree without STL in C++/JAVA

Implement Link List without STL in C++/JAVA

Implement Priority Queue without STL in C++/Java

Tuesday, January 02, 2018

Implement Hash without STL in C++ and Java Language:

BLOG INFO

Contact Form

POPULAR POST

LABELS

ARCHIVE

FEATURED Post

Followers

Visitor Locations

Visitor Locations