Arogya Thapa Magar: Design and Analysis Of Algorithm (DAA)

Showing posts with label Design and Analysis Of Algorithm (DAA). Show all posts

Approximation Algorithms | DAA

Arogya Thapa Magar at January 13, 2020 1

Approximation Algorithms

An approximate algorithm is a way of dealing with NP—completeness for optimization problem. This technique does not guarantee the best solution. The goal of an approximation algorithm is to come as close as possible to the optimum value in a reasonable amount of time which is at most polynomial time. If we are dealing with optimization problem {maximization or minimization}
with feasible solution having positive cost then it is worthy to look at approximate algorithm for near optimal solution.

Vertex Cover Problem

A vertex cover of an undirected graph G =(V.E) is a subset V‘ I V such that for all edges (u.v) EE either usV’ or vsV’ or u and v 2 V’. The problem here is to ﬁnd the vertex cover of minimum size in a given graph G. Optimal vertex—cover is the optimization version of an NP—complete problem but it is not too hard to find a vertex-cover that is near optimal.

Algorithm

ApproxVertexCover {G}
{
C ={ } ;
E’ = E
while E' is not empty
do Let (u, v} be an arbitrary edge of E‘
C = C U {u, v}
Remove from E' every edge incident on either u or v
return C
}

Example: (vertex cover running example for graph below)

Analysis:

If E' is represented using the adjacency lists the above algorithm takes O (V+E) since each edge is processed only once and every vertex is processed only once throughout the whole operation.

Cook’s Theorem | DAA

Arogya Thapa Magar at January 12, 2020 0

Cook’s Theorem

SAT is NP-complete
Proof
To prove that SAT is NP—complete, we have to show that

SATεNP
SAT is NP-Hard

SATεNP

Circuit satisﬁability problem (SAT) is the question “Given a Boolean combinational circuit, is it satisﬁable? i.e. does the circuit has assignment sequence of truth values that produces the output of the circuit as 1'?” Given the circuit satisﬁability problem take a circuit x and a certiﬁcate y with the set of values that produce output 1, we can verify that whether the given certiﬁcate satisﬁes the circuit in polynomial time. So we can say that circuit satisﬁability problem is NP.

SAT is N P-hard

Take a problem V E NP, let A be the algorithm that veriﬁes V in polynomial time (this rnust be true since V E NP}. We can program A on a computer and therefore there exists a (huge) logical circuit whose input wires correspond to bits of the inputs x and y of A and which outputs l precisely when A(x,y} returns yes. For any instance x of V let Ax be the circuit obtained from A by setting the x-input wire values according to the speciﬁc string x. The construction ofAx from x is our reduction function.

C Programming Design and Analysis Of Algorithm (DAA)

C Program For Prim's Algorithm To Find Shortest Path | C Programming

Arogya Thapa Magar at January 09, 2020 0

C Program For Prim's Algorithm To Find Shortest Path

#include <stdio.h>
#include <stdlib.h>

#define infinity 9999
#define MAX 20

int G[MAX][MAX], spanning[MAX][MAX], n;

int prims();

int main()
{
    int i, j, total_cost;
    printf("Enter no. of vertices:");
    scanf("%d", &n);

    printf("\nEnter the adjacency matrix:\n");

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &G[i][j]);

    total_cost = prims();
    printf("\nspanning tree matrix:\n");

    for (i = 0; i < n; i++)
    {
        printf("\n");
        for (j = 0; j < n; j++)
            printf("%d\t", spanning[i][j]);
    }

    printf("\n\nTotal cost of spanning tree=%d", total_cost);
    return 0;
}

int prims()
{
    int cost[MAX][MAX];
    int u, v, min_distance, distance[MAX], from[MAX];
    int visited[MAX], no_of_edges, i, min_cost, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
        {
            if (G[i][j] == 0)
                cost[i][j] = infinity;
            else
                cost[i][j] = G[i][j];
            spanning[i][j] = 0;
        }
    distance[0] = 0;
    visited[0] = 1;

    for (i = 1; i < n; i++)
    {
        distance[i] = cost[0][i];
        from[i] = 0;
        visited[i] = 0;
    }

    min_cost = 0;
    no_of_edges = n - 1;

    while (no_of_edges > 0)
    {
        min_distance = infinity;
        for (i = 1; i < n; i++)
            if (visited[i] == 0 && distance[i] < min_distance)
            {
                v = i;
                min_distance = distance[i];
            }

        u = from[v];
        spanning[u][v] = distance[v];
        spanning[v][u] = distance[v];
        no_of_edges--;
        visited[v] = 1;
        for (i = 1; i < n; i++)
            if (visited[i] == 0 && cost[i][v] < distance[i])
            {
                distance[i] = cost[i][v];
                from[i] = v;
            }

        min_cost = min_cost + cost[u][v];
    }

    return (min_cost);
}

Output

C Program For Prim's Algorithm To Find Shortest Path | C Programming

Design and Analysis Of Algorithm (DAA)

Directed Acyclic Graph (DAG) | DAA

Arogya Thapa Magar at January 07, 2020 0

Directed Acyclic Graph (DAG)

DAG, here directed means that each edge has an arrow denoting that the edge can be traversed in only that particular direction. Acyclic means that the graph has no cycles, i.e., starting at one node, you can never end up at the same node. DAG can be used to ﬁnd shortest path from a given source node to all other nodes. To find shortest path by using DAG, ﬁrst of all sort the vertices of graph topologically and then relax the vertices in topological order.

Example:

Step 1: Sort the vertices of graph topologically

Step 2: Relax from S

Step 3: Relax from C

Step 4: Relax from A

Step5: Relax from B

Step6: Relax from D

Algorithm

DagSP(G,w,s)
{
Topologically Sort the vertices of G
for each vertex v belongs to V
do d[v] = ?
d[s] = 0
for each vertex u, taken in topologically sorted order
do for each vertex v adjacent to u
do if d[v] > d[u] + w(u,v)
then d[v] = d[u] + w(u,v)
}

Analysis:

In tlle above algorithm, the topological sort can be done in O(V+E) time (Since this is similar to DPS! see book.).The ﬁrst for loop block lakes O(V) time. In case of second for loop it executes in O(V2) Time so the total running time is O(V2). Aggregate analysis gives us the running time O(E+V).

Design and Analysis Of Algorithm (DAA)

Prim’s Algorithm | Minimum Spanning Tree | DAA

Arogya Thapa Magar at January 06, 2020 0

Prim’s Algorithm

This is another algorithm for finding MST. The idea behind this algorithm is just take any arbitrary vertex and choose the edge with minimum weight incident on the chosen vertex. Add the vertex and continue the above process taking all the vertices added. Remember the cycle must be avoided.

Algorithm:

PrimMST(G)
{
T = ?; // T is a set of edges of MST
S = {s} ; //s is randomly chosen vertex and S is set of vertices
while(S != V)
{
e = (u,v) an edge of minimum weight incident to vertices in T and not forming a
simple circuit in T if added to T i.e. u ??S and v??V-S
T = T ??{(u,v)};
S = S ??{v};
}
}

Analysis:

In the above algorithm while loop execute O(V). The edge of minimum weight incident on a vertex can be found in O(E), so the total time is O(EV). We can improve the performance of the above algorithm by choosing better data structures as priority queue and normally it will be seen that the running time of prim’s algorithm is O(ElogV)!.

Design and Analysis Of Algorithm (DAA)

Kruskal Algorithm | Minimum Spanning Tree | DAA

Arogya Thapa Magar at January 04, 2020 0

Minimum Spanning Tree

Given an undirected graph G = (V,E), a subgraph T =(V,E’) of G is a spanning tree if and only if T is a tree. The MST is a spanning tree of a connected weighted graph such that the total sum of the weights of all edges eÎE’ is minimum amongst all the sum of edges that would give a spanning tree.

Kruskal’s Algorithm:

The problem of finding MST can be solved by using Kruskal’s algorithm. The idea behind this algorithm is that you put the set of edges form the given graph G = (V,E) in nondecreasing order of their weights. The selection of each edge in sequence then guarantees that the total cost that would from will be the minimum. Note that we have G as a graph, V as a set of n vertices and E as set of edges of graph G.

Algorithm:

KruskalMST(G)

{

T = {V} // forest of n nodes

S = set of edges sorted in nondecreasing order of weight

while(|T| < n-1 and E !=Æ)

{

Select (u,v) from S in order DAA

Remove (u,v) from E

if((u,v) doesnot create a cycle in T))

T = T È {(u,v)}

}

Analysis:

In the above algorithm the n tree forest at the beginning takes (V) time, the creation of set S takes O(ElogE) time and while loop execute O(n) times and the steps inside the loop take almost linear time (see disjoint set operations; find and union). So the total time taken is O(ElogE) or asymptotically equivalently O(ElogV)!.

Design and Analysis Of Algorithm (DAA)

Depth First Search | Graph Traversals | DAA

Arogya Thapa Magar at January 04, 2020 0

Graph Traversals

There are a number of approaches used for solving problems on graphs. One of the most important approaches is based on the notion of systematically visiting all the vertices and edge of a graph. The reason for this is that these traversals impose a type of tree structure (or generally a forest) on the graph, and trees are usually much easier to reason about than general graphs.

Depth First Search

This is another technique that can be used to search the graph. Choose a vertex as a root and form a path by starting at a root vertex by successively adding vertices and edges. This process is continued until no possible path can be formed. If the path contains all the vertices then the tree consisting this path is DFS tree. Otherwise, we must add other edges and vertices. For this move back from the last vertex that is met in the previous path and find whether it is possible to find new path starting from the vertex just met. If there is such a path continue the process above. If this cannot be done, move back to another vertex and repeat the process. The whole process is continued until all the vertices are met. This method of search is also called backtracking.

Example: Use depth first search to find a spanning tree of the following graph.

Depth First Search | Graph Traversals | DAA

Algorithm:

  DFS(G,s)

  {

  T = {s};

  Traverse(s);

  }

  Traverse(v)

  {

  for each w adjacent to v and not yet in T

  {

  T = T U {w}; //put edge {v,w} also

  Traverse (w);

  }

  }

Analysis:

The complexity of the algorithm is greatly affected by Traverse function we can write its running time in terms of the relation T(n) = T(n-1) + O(n), here O(n) is for each vertex at most all the vertices are checked (for loop). At each recursive call a vertex is decreased. Solving this we can find that the complexity of an algorithm is O(n^2 ). Also from aggregate analysis we can write the complexity as O(E+V) because traverse function is invoked V times maximum and for loop executes O(E) times in total.

Design and Analysis Of Algorithm (DAA)

Breadth First Search | Graph Traversals | DAA

Arogya Thapa Magar at January 03, 2020 0

Graph Traversals

Breadth-first search

This is one of the simplest methods of graph searching. Choose some vertex arbitrarily as a root. Add all the vertices and edges that are incident in the root. The new vertices added will become the vertices at the level 1 of the BFS tree. Form the set of the added vertices of level 1, find other vertices, such that they are connected by edges at level 1 vertices. Follow the above step until all the vertices are added.

Algorithm:

BFS(G,s) //s is start vertex

{

T = {s}; L =Φ; //an empty queue

Enqueue(L,s);

while (L != Φ )

{

v = dequeue(L);

for each neighbor w to v

if ( w Ï L and w Ï T )

{

enqueue( L,w);

T = T U {w}; //put edge {v,w} also

}

}

}

Example: Use breadth first search to find a BFS tree of the following graph.

Breadth First Search | Graph Traversals | DAA

Analysis

From the algorithm above all the vertices are put once in the queue and they are accessed. For each accessed vertex from the queue their adjacent vertices are looked for and this can be done in O(n) time(for the worst case the graph is complete). This computation for all the possible vertices that may be in the queue i.e. n, produce complexity of an algorithm as O(n2 ). Also from aggregate analysis we can write the complexity as O(E+V) because inner loop executes E times in total

Design and Analysis Of Algorithm (DAA)

Graph Algorithm | DAA

Arogya Thapa Magar at January 01, 2020 0

Graph Algorithm

Graph is a collection of vertices or nodes, connected by a collection of edges. Graphs are extremely important because they are a very flexible mathematical model for many application problems. Basically, any time you have a set of objects, and there is some “connection” or “relationship” or “interaction” between pairs of objects, a graph is a good way to model this. Examples of graphs in application include communication and transportation networks, VLSI and other sorts of logic circuits, surface meshes used for shape description in computer-aided design and geographic information systems, precedence constraints in scheduling systems etc.

A directed graph (or digraph) G = (V,E) consists of a finite set V , called the vertices or nodes, and E, a set of ordered pairs, called the edges of G.

An undirected graph (or graph) G = (V,E) consists of a finite set V of vertices, and a set E of unordered pairs of distinct vertices, called the edges.

We say that vertex v is adjacent to vertex u if there is an edge (u; v). In a directed graph, given the edge e = (u; v), we say that u is the origin of e and v is the destination of e. In undirected graphs u and v are the endpoints of the edge. The edge e is incident (meaning that it touches) both u and v.

In a digraph, the number of edges coming out of a vertex is called the out-degree of that vertex, and the number of edges coming in is called the in-degree. In an undirected graph we just talk about the degree of a vertex as the number of incident edges. By the degree of a graph, we usually mean the maximum degree of its vertices.

Notice that generally the number of edges in a graph may be as large as quadratic in the number of vertices. However, the large graphs that arise in practice typically have much fewer edges. A graph is said to be sparse if E = Θ(V ), and dense, otherwise. When giving the running times of algorithms, we will usually express it as a function of both V and E, so that the performance on sparse and dense graphs will be apparent.

Design and Analysis Of Algorithm (DAA)

Job Sequencing with Deadline | DAA

Arogya Thapa Magar at December 30, 2019 1

Job Sequencing with Deadline

We are given a set of n jobs. Associated with each job I, di>=0 is an integer deadline and pi>=O is proﬁt. For any job i proﬁt is earned iff job is completed by deadline. To complete a job one has to process a job for one unit of time. Our aim is to ﬁnd feasible subset of jobs such that proﬁt is maximum.

Example

n=4, (p1,p2,p3,p4)=(100,10,15,27),(d1,d2,d3,d4)=(2,1,2,1)

n=4, (p1,p4,p3,p2)=(100,27,15,10),(d1,d4,d3,d2)=(2,1,2,1)

We have to try all the possibilities, complexity is O(n!). Greedy strategy using total profit as optimization function to above example. Begin with J=

Job 1 considered, and added to J ->J={1}
Job 4 considered, and added to J -> J={1,4}
Job 3 considered, but discarded because not feasible ->J={1,4}
Job 2 considered, but discarded because not feasible -> J={1,4}

Final solution is J={1,4} with total profit 127 and it is optimal

Algorithm:

Assume the jobs are ordered such that p[1]>=p[2] >=…>=p[n] d[i]>=1, 1<=i<=n are the deadlines, n>=1. The jobs n are ordered such that p[1]>=p[2]>=... >=p[n]. J[i] is the ith job in the optimal solution, 1<=i<=k. Also, at termination d[J[i]]<=d[J[i+1]], 1<=i


JobSequencing(int d[], int j[], int n)


{


d[0] = J[0] = 0; // Initialize.


J[1] = 1; // Include job 1.


int k=1;


for (int i=2; i<=n; i++)


{//Consider jobs in nonincreasing order of p[i]. Find position for i and check feasibility of insertion.


int r = k;


while ((d[J[r]] > d[i]) && (d[J[r]] != r))


r--;


if ((d[J[r]] <= d[i]) && (d[i] > r))


{                // Insert i into J[].


for (int q=k; q>=(r+1); q--)


J[q+1] = J[q];


J[r+1] = i;


k++;


}


}


return (k);


}

Analysis

For loop executes O(n) line. While loop inside the for loop executes at most times and if the condition given inside if statement is true inner for loop executes O(k-r) times. Hence total time for each iteration of outer for loop is O(k). Thus time complexity is O(n^2) .

Design and Analysis Of Algorithm (DAA)

Huffman Coding | DAA

Arogya Thapa Magar at December 29, 2019 0

Huffman coding

Huffman coding is an algorithm for the lossless compression of ﬁles based on the frequency of occurrence of a symbol in the ﬁle that is being compressed. In any ﬁle, certain characters are used more than others. Using binary representation, the number of bits required to represent each character depends upon the number of characters that have to be represented. Using one bit we

can represent two characters, i.e., 0 represents the first character and l represents the second character. Using two bits we can represent four characters, and so on. Unlike ASCII code, which is a fixed-length code using seven bits per character, Huffman compression is a variable-length coding system that assigns smaller codes for more frequently used characters and larger codes

for less frequently used characters in order to reduce the size of ﬁles being compressed and transferred.

For example, in a ﬁle with the following data: ‘XXXXXXYYYYZZ. The frequency of "X" is 6, the frequency of "Y" is 4, and the frequency of "Z" is 2. If each character is represented using a fixed-length code of two bits, then the number of bits required to store this ﬁle would be 24, i.e., (2 x 6) + (2): 4) + (2): 2] = 24. If the above data were compressed using Huffman compression, the more frequently occurring numbers would be represented by smaller bits, such as: X by the code 0 (1 bit),Y by the code 10 (2 bits) and Z by the code 11 (2 bits}, the size of the ﬁle becomes 18, i.e., (h 6) + [2 x 4] + (2 x 2) = 18. In this example, more frequently occurring characters are

assigned smaller codes, resulting in a smaller number of bits in the final compressed file.

Huffman compression was named after its discoverer, David Huffman.

To generate Huffman codes, we should create a binary tree of nodes. Initially, all nodes are leaf nodes, which contain the symbol itself, the weight (frequency of appearance) of the symbol. As a common convention, bit '0' represents following the left child and bit '1' represents following the right child. A ﬁnished tree has up to n leaf nodes and n — l. internal nodes. A Huffman tree that omits unused symbols produces the most optimal code lengths. The process essentially begins with the leaf nodes containing the probabilities of the symbol they represent, then a new node whose children are the 2 nodes with smallest probability is created, such that the new node's probability is equal to the sum of the children's probability. With the previous 2 nodes merged into one node and with the new 11ode being now considered, the procedure is repeated until only one node remains, the Huffman tree. The simplest construction algorithm uses a priority queue where the 11ode with lowest probability is given highest priority:

Example

The following example bases on a data source using a set of ﬁve different symbols The

symbol's frequencies are:

Symbol Frequency

A 24

B 12

C 10

D 5

E 8

----> total 186 bit (with 3 bit per code word)

Algorithm

A greedy algorithm can construct Huffman code that is optimal preﬁx codes. A tree corresponding to optimal codes is constructed in a bottom up manner starting from the |C| leaves and |C|-1 merging operations. Use priority queue Q to keep nodes ordered by frequency. Here the priority queue we considered is binary heap.


HuffmanAlgo(C)


{


n = |C|; Q = C1


For(i=1; i<=n-1; i++)


{


2 = Allocate-Node();


x = Extract-Min(Q);


y = Extract-Min(Q);


left(z) = x; right(z) = y;


f(z) = f(x) + (y);


Insert(Q,2);


}


}

Analysis

We can use BuildHeap(C] to create a priority queue that takes O(11) time. Inside the for loop the expensive operations can be done in Oﬂogn) time. Since operations inside for loop executes for n-1 time total running time of Huffrnan algorithm is O(11logn).

Design and Analysis Of Algorithm (DAA)

Fractional Knapsack Problem | DAA

Arogya Thapa Magar at December 26, 2019 0

Fractional Knapsack Problem

Statement:

A thief has a bag or knapsack that can contain maximum weight W of his loot. There are n items and the weight of ith item is wi and it worth vi. Any amount of item can be put into the bag i.e. xi fraction of item can be collected, where 0<=xi<=1. Here the objective is to collect the items that maximize the total profit earned.

Algorithm:

Take as much of the item with the highest value per weight (vi/wi) as you can. If the item is finished then move on to next item that has highest (vi/wi), continue this until the knapsack is full. v[1 … n] and w[1 … n] contain the values and weights respectively of the n objects sorted in non increasing ordered of v[i]/w[i] . W is the capacity of the knapsack, x[1 … n] is the solution vector that includes fractional amount of items and n is the number of items.

GreedyFracKnapsack(W,n)
{
for(i=1; i<=n; i++)
{
x[i] = 0.0;
}
tempW = W;
for(i=1; i<=n; i++)
{
if(w[i] > tempW) then break;
x[i] = 1.0; tempW -= w[i];
}
if(i<=n)
x[i] = tempW/w[i];
}

Analysis:

We can see that the above algorithm just contain a single loop i.e. no nested loops the running time for above algorithm is O(n). However our requirement is that v[1 … n] and w[1 … n] are sorted, so we can use sorting method to sort it in O(nlogn) time such that the complexity of the algorithm above including sorting becomes O(nlogn).

Dynamic Programming | DAA

Arogya Thapa Magar at December 23, 2019 0

Dynamic Programming:

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map,etc). Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup. So the next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time. This technique of storing solutions to subproblems instead of recomputing them is called memoization.

Technique is among the most powerful for designing algorithms for optimization problems. Dynamic programming problems are typically optimization problems (find the minimum or maximum cost solution, subject to various constraints). The technique is related to divide-and-conquer, in the sense that it breaks problems down into smaller problems that it solves recursively. However, because of the somewhat different nature of dynamic programming problems, standard divide-and-conquer solutions are not usually efficient. The basic elements that characterize a dynamic programming algorithm are:

· Substructure:

Decompose your problem into smaller (and hopefully simpler) subproblems. Express the solution of the original problem in terms of solutions for smaller problems.

· Table-structure:

Store the answers to the sub-problems in a table. This is done because subproblem solutions are reused many times.

· Bottom-up computation:

Combine solutions on smaller subproblems to solve larger subproblems. (We also discuss a top-down alternative, called memorization)

The most important question in designing a DP solution to a problem is how to set up the subproblem structure. This is called the formulation of the problem. Dynamic programming is not applicable to all optimization problems. There are two important elements that a problem must have in order for DP to be applicable.

Optimal substructure:

(Sometimes called the principle of optimality.) It states that for the global problem to be solved optimally, each subproblem should be solved optimally. (Not all optimization problems satisfy this. Sometimes it is better to lose a little on one subproblem in order to make a big gain on another.)

Polynomially many subproblems:

An important aspect to the efficiency of DP is that the total number of subproblems to be solved should be at most a polynomial number.

C Programming Design and Analysis Of Algorithm (DAA) Searching

C Program For Mini-Max Search | C Programming

Arogya Thapa Magar at December 22, 2019 0

Max and Min Finding

Here our problem is to find the minimum and maximum items in a set of n elements. We will see two methods here ﬁrst one is iterative version and the next one uses divide and conquer strategy to solve the problem.

Iterative Algorithm:


MinMax(A,n)

{

max = min = A[0];

for(i = 1; i <n; i++}

{

if(A[i] > max)

max = A[i];

if(A[i] < min}

min = A[i];

}

}

The above algorithm requires 2(n-1) comparison in worst, best, and average cases. The comparison A[i] < min is needed only when A[i] > max is not true. If We replace the content inside the for loop by

if(A[i] >1nax)

max = A[i];

else if(A[i] < min)

m.i_n = A[i];

Then the best case occurs when the elements are in increasing order with (n-1) comparisons and worst case occurs when elements are in decreasing order with 2(n-1) comparisons. For the average case A[i] > max is about half of the time so number of comparisons is 3n/2 — 1.

We can clearly conclude that the time complexity is O[n].

C Program For Mini Max Search


#include <stdio.h>


#include <stdlib.h>


#include <time.h>


#define SIZE 1000


void MinMax(int *arr, int l, int h, int *max, int *min)


{


    int max1, min1;


    if (l == h) { // case I - only one item


        *max = *min = arr[0];


    }


     else if (l == h - 1) { // case II - when there are two elements


        if (arr[l] > arr[h])


        {


            *max = arr[l];


            *min = arr[h];


        }


        else {


            *max = arr[h];


            *min = arr[l];


        }


    }


     else { // case - III


        int mid = (l + h) / 2; // Divide


        MinMax(arr, l, mid, max , min); // conquer


        MinMax(arr, mid+1, h, &max1 , &min1); //conquer


        if(*max < max1) *max = max1; //combine


        if(*min > min1) *min = min1;  //combine


    }


}


int main(int argc, char const *argv[])


{


    int arr[SIZE], n;


    clock_t start, end;


    double total_time = 0.00;


    int min, max;


    printf("Enter number of elements : ");


    scanf("%d", &n);


    for (int i = 0; i < n; i++)


    {


        arr[i] = rand() % 1000;


    }


    start = clock();


    MinMax(arr, 0, n-1, &max, &min);


    end = clock();


    printf("Min element :  %d\nMax element : %d\n", min, max);


    total_time += (double)(end - start) / CLOCKS_PER_SEC;


    printf("Execution time : %f seconds", total_time);


    return 0;


}

Output

Design and Analysis Of Algorithm (DAA) Sorting

Heap Sort

Arogya Thapa Magar at December 21, 2019 0

Heap Sort

A heap is a nearly complete binary tree with the following two properties:

Structural property: all levels are full, except possibly the last one, which is filled from left to right
Order (heap) property: for any node x, Parent(x) ≥ x

Array Representation of Heaps

A heap can be stored as an array A.
Root of tree is A[1]
Left child of A[i] = A[2i]
Right child of A[i] = A[2i + 1]
Parent of A[i] = A[ i/2 ]
Heapsize[A] ≤ length[A]

The elements in the subarray A[(⌊n/2⌋+1) .. n] are leaves

Max-heaps (largest element at root), have the max-heap property:

for all nodes i, excluding the root:

A[PARENT(i)] ≥ A[i]

Min-heaps (smallest element at root), have the min-heap property:

for all nodes i, excluding the root:

A[PARENT(i)] ≤ A[i]

Adding/Deleting Nodes

New nodes are always inserted at the bottom level (left to right) and nodes are removed from the bottom level (right to left).

Operations on Heaps

Maintain/Restore the max-heap property
1. MAX-HEAPIFY
Create a max-heap from an unordered array
1. BUILD-MAX-HEAP
Sort an array in place
1. HEAPSORT
Priority queues

Heapify Property

Suppose a node is smaller than a child and Left and Right subtrees of i are max-heaps. To eliminate the violation:

Exchange with larger child
Move down the tree
Continue until node is not smaller than children

Algorithm


Max-Heapify(A, i, n)

{


            l = Left(i)


            r = Right(i)


            largest=i;


            if l ≤ n and A[l] > A[largest]



largest = l


if r ≤ n and A[r] > A[largest]


largest = r


if largest≠i  


exchange (A[i] , A[largest])             


Max-Heapify(A, largest, n)


}

Analysis:

In the worst case Max-Heapify is called recursively h times, where h is height of the heap and since each call to the heapify takes constant time

Time complexity = O(h) = O(logn)

Building a Heap

Convert an array A[1 … n] into a max-heap (n = length[A]). The elements in the sub-array A[(⌊n/2⌋+1) .. n] are leaves. Apply MAX-HEAPIFY on elements between 1 and ⌊n/2⌋.

Algorithm:


Build-Max-Heap(A)


n = length[A]  


for i ← ⌊n/2⌋ down to 1        


do MAX-HEAPIFY(A, i, n)

Time Complexity:

Running time: Loop executes O(n) times and complexity of Heapify is O(lgn), therefore complexity of Build-Max-Heap is O(nlogn).

This is not an asymptotically tight upper bound

Pages

Approximation Algorithms

Vertex Cover Problem

Algorithm

Analysis:

Cook’s Theorem

SATεNP

SAT is N P-hard

C Program For Prim's Algorithm To Find Shortest Path

Output

Directed Acyclic Graph (DAG)

Example:

Algorithm

Analysis:

Prim’s Algorithm

Algorithm:

Analysis:

Minimum Spanning Tree

Kruskal’s Algorithm:

Algorithm:

Analysis:

Graph Traversals

Depth First Search

Algorithm:

Analysis:

Graph Traversals

Breadth-first search

Algorithm:

Analysis

Graph Algorithm

Job Sequencing with Deadline

Example

Algorithm:

Analysis

Huffman coding

Example

Algorithm

Analysis

Fractional Knapsack Problem

Dynamic Programming:

Max and Min Finding

Iterative Algorithm:

C Program For Mini Max Search

Output

Heap Sort

Array Representation of Heaps

Adding/Deleting Nodes

Operations on Heaps

Heapify Property

Algorithm

Analysis:

Building a Heap

Algorithm:

Time Complexity: