__DESIGN AND ANALYSIS OF ALGORITHM __

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

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

__Characteristics of algorithm are__**:- **

**Input and output :-**These characteristics require that an algorithm produces one or more outputs have zero or more inputs that are externally supplied.**Definiteness:-**Each operation must be perfectly clear and unambiguous.**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.**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__**:-**

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

__Case of complexity__**:- **

**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.**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.**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.

- It roughly sorts the data first, moving large elements towards one end and small elements towards the each other.
- In shell sort several passes over the data is performed, each finer than the last.
- After the final pass, the data is fully sorted.
- 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.

- This algorithm divides the array into two halves, sorts them separately and then merges them.
- 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.

- The general approach of heaps sort is as follows:
- From the given array, build the initial max heap.
- Interchange the root (maximum) element with the last element.
- Use repetitive downward operation from root node to rebuild the heap of size one less than the sorting.
- 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.

- Since the inputs are uniformly distributed over[0,1], we do not except many number to fall into each bucket.
- 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.

- We can start sorting on the least significant digit or on the most significant digit.
- On the first pass entire number sort on the least significant digit (or most significant digit) and combine in a array.
- 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.

- 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.
- Greedy algorithm are easy to invent, easy to implement and most of the time quite efficient.
- Many problem cannot be solved correctly by greedy approach.
- 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.

- A function that checks the feasibility of a set.
- The selection function tells which of the candidates are most promising.
- 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.

- 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.
- If graph is not connected, i.e., a graph with n vertices has edges less than n-1 then no spanning tree is possible.
- 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__**:- **

- Naïve string matching algorithm
- Rabin-karp algorithm
- 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_{0}+a_{1}x+a_{2}x^{2}+…a_{n-1}x^{n-1}

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

A^{[0]}(x)= a_{0}+a_{2}x+a_{4}x^{2}+…a_{n-}2^{xn/2-1}

A^{[1]}(x)= a_{0}+a_{3}x+a_{5}x^{2}+…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^{2}) + xA^{[1]} (x^{2}).

** 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.

- 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_{1}, an edge of G, such that weight of e_{1}, w(e_{1}) is as small as possible and e_{1} is not a loop.

Step2: If edge e_{1}, e_{2},….. e_{i} have been selected then choose an edge e_{i+1} not already chosen such that

i. The induced sub graph

G[{e_{1}….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_{1} of G.

**Step 2: **Choose an edge e_{1} = V_{1 }V_{2} of G such that V_{2} V_{1} and e_{1} has smallest weight among the edge among the edge of G incident with V_{1}.

**Step 3:** if edge e_{1},e_{2},…..,e_{i} have been chosen involving end points V_{1},V_{2},….,Vi+1, choose an edge e_{i+1}= V_{j}V_{k} with V_{j} = (V_{1}……Vi+j)

And V_{k } {V_{1}……V_{i+1}} such that e_{i+1} has smallest weight among the edges of {G with precisely one end in {V_{1}………..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.

- Dijkstra’s algorithm maintain a set S of vertices whose final shortest path weights from the source s have already been determined.
- That is, for all vertices v S, we have d[v] = (s, v)
- 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.
- We maintain a priority queue Q that contain all the vertices in v-s, keyed by their of values.
- 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.

- 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.
- This algorithm, uses the notation of edge relaxation but does not use with greedy method.
- 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.

- We start our search from any arbitrary vertex, say ’a’. this vertex ‘a’ becomes the root of our implicit tree.
- The first element of our partial solution in the first intermediate vertex of the Hamiltonian cycle that is to be constructed.
- The next adjacent vertex is selected on the basis of alphabetical ( or numerical) order.
- 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.
- 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.
- 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.

- A single execution of the algorithm will find the shortest path between all pair of vertices.
- It does so in (V
^{3}) time, where V is the number of vertices in the graph. - Negative weight edges may be “intermediate” vertices of the shortest path, where an intermediate vertex of a simple path p = (v
_{1}, v_{2},…..v_{m}) is any vertex of p other than v_{1}or v_{m}, that is, any vertex in the set (v_{2},v_{3},….v_{m-1}) - Let the vertices of G be V = (1,2,….n) and consider a subset (1,2,….k) of vertices for some k.
- 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:

- Every node is either
**red**or**black.** - the root is black.
- Every leaf (NIL) is black.
- If a node is red. Then both its children are black.
- 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:

- The root is either leaf or has atleast two children.
- Each node, except for the root and the leave, has between m/2 and m children.
- Each path from the root to a leaf has the same length.
- The root, each internal node and each leaf is typically a disk block.
- 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.

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

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

- Trees are not ordered binomial trees, because

a. Children of a node are unordered.

b. Deleting node may destroy binomial construction. - 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.
- If Fibonacci heap H I empty, then min(H) = NIL.

Category: