Important Topics of Design Analysis and Algorithm

DESIGN AND ANALYSIS OF ALGORITHM

Algrithm :- An algorithm is a set of rules for carrying out calculation either by hand or on machine.

1. ) It is a finite step-by-step procedure to achieve a required result.
2. ) It is a sequence of computational steps that transform the input into the output.
3. ) An algorithm is a sequence of operation performed on data that have to be organized in data structure.

Characteristics of algorithm are:-

1. Input and output :- These characteristics require that an algorithm produces one or more outputs have zero or more inputs that are externally supplied.
2. Definiteness:- Each operation must be perfectly clear and unambiguous.
3. Effectiveness:- this requires that each operation should be effective, i.e, each step can be done by a person using pencil and paper in a finite amount of time.
4. Termination:- This characteristics requires that an algorithm must terminate after a finite number of operation.

Complexity of an algorithm:- The complexity of an algorithm is function g(n) that gives the upper bound of the number of operation (or running time) performed by an algorithm when the input size is n.

Types of complexity:-

1. Space complexity:- The space complexity of an algorithm is the amount of memory it needs to run to completion.
2. Time complexity:- The time complexity of an algorithm is the amount of time it needs to run to completion.

Case of complexity:-

1. Worst case complexity:- The running time for any gives size input will lower than the upper bound except possibly for some value of the input where the maximum is reached.
2. Average case complexity:- the running time for any gives size input will be average number of operation over all problem instances for a given size.
3. Best case complexity:- The best case complexity of the algorithm is the function defined by the minimum number of steps taken on any  instances of size n.

Shell sort:- Shell sort is a highly efficient sorting algorithm and is bound on insertion sort algorithm and we can code it easily.

1. It roughly sorts the data first, moving large elements towards one end and small elements towards the each other.
2. In shell sort several passes over the data is performed, each finer than the last.
3. After the final pass, the data is fully sorted.
4. The shell sort down not sort the data itself, it increase the efficiency of other sorting algorithm.

Quick Sort:- Quick sort works by partitioning gives array A[p….r] into two non-empty sub array A[p-q-1] and A[q+1…r] such that every key in A[p-q-1] is less than or equal to every key in A[q+1…r]. Then the two sub array are sorted by recursive calls to quick sort.

Merge Sort: Merge sort is sorting algorithm that uses the divide and conquer.

1. This algorithm divides the array into two halves, sorts them separately and then merges them.
2. This procedure is recursive, with the base criteria that the number of elements in the array is not more than 1.

Max Sort:- heap sort finds the largest element and puts it at the of array, then the second largest item is found and this process is repeated for all other elements.

1. The general approach of heaps sort is as follows:
2. From the given array, build the initial max heap.
3. Interchange the root (maximum) element with the last element.
4. Use repetitive downward operation from root node to rebuild the heap of size one less than the sorting.
5. Repeat step a and b until there are no more elements.

Heap sort:- The heap is an array that can be viewed as a complete binary tree. The tree is filled on all levels except the lowest. Complexity : O(n log n)

Bucket Sort:- The bucket sort is used to divide the interval [0,1] into n equal-sized  sub-intervals, or bucket, and then distribute the n-input number into the bucket.

1. Since the inputs are uniformly distributed over[0,1], we do not except many number to fall into each bucket.
2. To produce the output, simply sort the number in each bucket and then go through the bucket in order, listing the element in each.

Counting Sort:- Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set.

Radix Sort:- Radix sort is a algorithm which consists of list of integer or words and each has d-digit.

1. We can start sorting on the least significant digit or on the most significant digit.
2. On the first pass entire number sort on the least significant digit (or most significant digit) and combine in a array.
3. These is the second pass, the entire number are sorted again on the second least significant digits and combine in an array and so on.

Greedy Algorithm:- Greedy algorithm are simple and straight forward.

1. Greedy algorithm are shortsighted in their approach in the sense that they take decision on the basis of information at hand without worrying about the effect these decision may have in the future.
2. Greedy algorithm are easy to invent, easy to implement and most of the time quite efficient.
3. Many problem cannot be solved correctly by greedy approach.
4. Greedy algorithm are used to solve optimization problems.

Function included in greedy algorithm:- A function that checks whether chosen set of items provide a solution.

1. A function that checks the feasibility of a set.
2. The selection function tells which of the candidates are most promising.
3. An objective function, which does not appear explicitly, gives the value of a solution.

Spanning tree:- A spanning tree of a graph is just a subgraph that contains all the  vertices and is  a tree.

1. That is, a spanning tree of a connected graph G contains all the vertices and has as the edges which connect all the vertices. So, the number of edges will be 1 less than number of nodes.
2. If graph is not connected, i.e., a graph with n vertices has edges less than n-1 then no spanning tree is possible.
3. A graph may have many spanning trees.

String Matching:- String matching is a process of finding one or more occurrences of a pattern in a text.

Types of String Matching:-

1. Naïve string matching algorithm
2. Rabin-karp algorithm
3. KMP(Knuth-morris-pratt)algorithm

Fast Fourier Transform:- The Fast Fourier Transform is a algorithm that computes a discrete Fourier transform (DSF) of n-length vector in O(n log n) time.

In the FFT algorithm, we apply the divide and conquer approach to polynomial evaluation by observing that if n is even, we can divide a degree(n-1) polynomial.

A(x)= a₀+a₁x+a₂x²+…a_n-1x^n-1

Into two degree(n/2-1) polynomials.

A^[0](x)= a₀+a₂x+a₄x²+…a_n-2^xn/2-1

A^[1](x)= a₀+a₃x+a₅x²+…a_n-1^xn/2-1

Where A^[0] contain all the even index coefficients of A and A^[1] contains all the odd index coefficients and we can combine these two polynomials into A, using the equation,

 

A(x) = A^[0] (x²) + xA^[1] (x²).

Kruskal’s algorithm:- In this algorithm, we choose an edge of G which has smallest weight among the edges of G which are not loops.

1. This algorithm gives an acyclic sub graph T of G and the theorem given below proves that T is minimal spanning tree of G. following steps are required:-

Step1: choose e₁, an edge of G, such that weight of e₁, w(e₁) is as small as possible and e₁ is not a loop.

Step2: If edge e₁, e₂,….. e_i have been selected then choose an edge e_i+1 not already chosen such that

i. The induced sub graph

G[{e₁….e_i+1}] is acyclic and

ii. If G has n vertices, stop after n-1 edge s have been chosen. Otherwise repeat stop 2.

Step3: If G has n vertices, stop after n-1 edge have been chosen.

If G be a weighted connected graph in which the weight of the edge are all non-negative number, let T be sub graph of G obtained by kruskal’s algorithm then, T is minimal spanning tree.

Prim’s Algorithm:- First it chooses a vertex and then chooses an edge with smallest weight incident on that on that vertex. The algorithm involves following steps:-

Step 1: Choose any vertex V₁ of G.

Step 2: Choose an edge e₁ = V₁ V₂ of G such that V₂ V₁ and e₁ has smallest weight among the edge among the edge of G incident with V₁.

Step 3: if edge e₁,e₂,…..,e_i have been chosen involving end points V₁,V₂,….,Vi+1, choose an edge e_i+1= V_jV_k with V_j = (V₁……Vi+j)

And V_k  {V₁……V_i+1} such that e_i+1 has smallest weight among the edges of {G with precisely one end in {V₁………..V_i+1}.

Step 4: Stop after n-1 edges have been chosen. Otherwise gets step 3.

Dijkstra’s Algorithm:- is a greedy algorithm that solves the single source shortest path problem for a directed graph G=(V,E) with non-negative edge weights, i.e., we assume that ω(u, v) ≥ 0 each edge (u, v)  E.

1. Dijkstra’s algorithm maintain a set S of vertices whose final shortest path weights from the source s have already been determined.
2. That is, for all vertices v S, we have d[v] = (s, v)
3. The algorithm repeatedly selects the vertex u = V-S with the minimum shortest path estimate, insert u into S, and relaxes all edges leaving u.
4. We maintain a priority queue Q that contain all the vertices in v-s, keyed by their of values.
5. Dijkstra’s always chooses the “lightest or closest” vertex in V-S to insert set S that it uses as a greedy strategy.

Bellman-ford algorithm:- Bellman-ford algorithm finds all shortest path length from a source s belongs to all v belongs to V or determines that negative-weight cycle exists.

1. Bellman-ford algorithm solves that single source shortest path problem in the general case in which edges of a given digraph G can have negative weight as long as G contains no negative cycles.
2. This algorithm, uses the notation of edge relaxation but does not use with greedy method.
3. The algorithm returns boolean TRUE if the given digraph contains no negative cycles that are reachable from source vertex otherwise it return boolean FALSE.

Hamiltonian Cycle:- Given a graph G=(V, E), we have to find the Hamiltonian circuit using backtracking approach.

1. We start our search from any arbitrary vertex, say ’a’. this vertex ‘a’ becomes the root of our implicit tree.
2. The first element of our partial solution in the first intermediate vertex of the Hamiltonian cycle that is to be constructed.
3. The next adjacent vertex is selected on the basis of alphabetical ( or numerical) order.
4. If at any stage any arbitrary vertex makes a cycle with any vertex other than vertex ‘a’ then we say that dead end is reached.
5. In this case we backtrack one step an again search begins by selecting another vertex and backtrack the element from the partial solution must be removed.
6. The search using backtracking is successful if a Hamiltonian cycle is obtained.

Floyd’s and warshall’s Algorithm:- Floyd-warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted, directed graph.

1. A single execution of the algorithm will find the shortest path between all pair of vertices.
2. It does so in (V³) time, where V is the number of vertices in the graph.
3. Negative weight edges may be “intermediate” vertices of the shortest path, where an intermediate vertex of a simple path p = (v₁, v₂,…..v_m) is any vertex of p other than v₁ or v_m, that is, any vertex in the set (v₂,v₃,….v_m-1)
4. Let the vertices of G be V = (1,2,….n) and consider a subset (1,2,….k) of vertices for some k.
5. For any pair of vertices I,jV, consider all paths from i to j whose intermediate vertices are all drawn from (1,2,….k) and let p be a minimum weight path from among them.

Red and Black Tree:- A red-black tree is a binary tree where each node has node as an extra attribute, either red or black. Its is self-balancing binary search tree (BST) where every node follows following properties:

1. Every node is either red or black.
2. the root is black.
3. Every leaf (NIL) is black.
4. If a node is red. Then both its children are black.
5. For each node, all paths from the node to descendent leave contain the same number of black nodes.

B Tree:- B-tree of order m is an m-array search tree with the following properties:

1. The root is either leaf or has atleast two children.
2. Each node, except for the root and the leave, has between m/2 and m children.
3. Each path from the root to a leaf has the same length.
4. The root, each internal node and each leaf is typically a disk block.
5. Each node internal node has upto (m-1) key values and upto m children.

Binomial heap:- is a type of  data structure which keeps data sorted and allows insertion and deletion in amortized time.

1. A binomial heap is implemented as a collection of binomial tree.
2. The total number of node at order k are 2^k
3. The height of the tree is k.
4. There are exactly (k/i) i.e., ^kC, nodes at depth i for i = 0, 1,…..k(this is why tree is called a “binomial” tree).
5. Root has degree k (children) and its children are B_k-1, B_k-2,….B₀ from left to right.

Fibonacci heap:- A Fibonacci heap is a set of min-heap ordered tree.

1. Trees are not ordered binomial trees, because
   a. Children of a node are unordered.
   b. Deleting node may destroy binomial construction.
2. Fibonacci heap H is accessed by a pointer min(H) to the root of a tree containing a minimum key. This node is called the minimum node.
3. If Fibonacci heap H I empty, then min(H) = NIL.