Alogrithm

1. What Is Algorithm?

Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output.

2. Why We Need To Do Algorithm Analysis?

A problem can be solved in more than one ways. So, many solution algorithms can be derived for a given problem. We analyze available algorithms to find and implement the best suitable algorithm.

3. What Are The Criteria Of Algorithm Analysis?

An algorithm are generally analyzed on two factors − time and space. That is, how much execution time and how much extra space required by the algorithm.

4. What Is Asymptotic Analysis Of An Algorithm?

Asymptotic analysis of an algorithm, refers to defining the mathematical boundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case and worst case scenario of an algorithm.

5. What Are Asymptotic Notations?

Asymptotic analysis can provide three levels of mathematical binding of execution time of an algorithm −

• Best case is represented by Ω (n) notation.
• Worst case is represented by Ο (n) notation.
• Average case is represented by Θ (n) notation.

6. Briefly Explain The Approaches To Develop Algorithms?

There are three commonly used approaches to develop algorithms:

Greedy Approach − finding solution by choosing next best option Divide and Conquer − diving the problem to a minimum possible sub-problem and solving them independently                                          Dynamic Programming − diving the problem to a minimum possible sub-problem and solving them combined.

7. Give Some Examples Greedy Algorithms?

The below given problems find their solution using greedy algorithm approach:

• Travelling Salesman Problem.
• Prim’s Minimal Spanning Tree Algorithm.
• Kruskal’s Minimal Spanning Tree Algorithm.
• Dijkstra’s Minimal Spanning Tree Algorithm.
• Graph – Map Coloring.
• Graph – Vertex Cover.
• Knapsack Problem.
• Job Scheduling Problem.

8. What Are Some Examples Of Divide And Conquer Algorithms?

The below given problems find their solution using divide and conquer algorithm approach:

• Merge Sort
• Quick Sort
• Binary Search
• Strassen’s Matrix Multiplication
• Closest pair (points)

9. What Are Some Examples Of Dynamic Programming Algorithms?

The below given problems find their solution using divide and conquer algorithm approach:

• Fibonacci number series
• Knapsack problem
• Tower of Hanoi
• All pair shortest path by Floyd-Warshall
• Shortest path by Dijkstra
• Project scheduling

10. What Is Linear Searching?

Linear search tries to find an item in a sequentially arranged data type. These sequentially arranged data items known as array or list, are accessible in incrementing memory location. Linear search compares expected data item with each of data items in list or array. The average case time complexity of linear search is Ο (n) and worst case complexity is Ο (n2). Data in target arrays/lists need not to be sorted.

11. What Is Binary Search?

A binary search works only on sorted lists or arrays. This search selects the middle which splits the entire list into two parts. First the middle is compared.

This search first compares the target value to the mid of the list. If it is not found, then it takes decision on whether.

12. What Is Bubble Sort And How Bubble Sort Works?

Bubble sort is comparison based algorithm in which each pair of adjacent elements is compared and elements are swapped if they are not in order. Because the time complexity is Ο (n2), it is not suitable for large set of data

13. Tell Me Something About ‘insertion Sort’?

Insertion sort divides the list into two sub-list, sorted and unsorted. It takes one element at time and finds it appropriate location in sorted sub-list and insert there. The output after insertion is a sorted sub-list. It iteratively works on all the elements of unsorted sub-list and inserts them to sorted sub-list in order.

14. What Is Selection Sort?

Selection sort is in-place sorting technique. It divides the data set into two sub-lists: sorted and unsorted. Then it selects the minimum element from unsorted sub-list and places it into the sorted list. This iterates unless all the elements from unsorted sub-list are consumed into sorted sub-list.

15. How Insertion Sort And Selection Sorts Are Different?

Both sorting techniques maintains two sub-lists, sorted and unsorted and both take one element at a time and places it into sorted sub-list. Insertion sort works on the current element in hand and places it in the sorted array at appropriate location maintaining the properties of insertion sort. Whereas, selection sort searches the minimum from the unsorted sub-list and replaces it with the current element in hand.

16. What Is Merge Sort And How It Works?

Merge sort is sorting algorithm based on divide and conquer programming approach. It keeps on dividing the list into smaller sub-list until all sub-list has only 1 element. And then it merges them in a sorted way until all sub-lists are consumed. It has run-time complexity of Ο (n log n) and it needs Ο (n) auxiliary space.

17. What Is Shell Sort?

Shell sort can be said a variant of insertion sort. Shell sort divides the list into smaller sublist based on some gap variable and then each sub-list is sorted using insertion sort. In best cases, it can perform upto Ο(n log n).

18. How Quick Sort Works?

Quick sort uses divide and conquer approach. It divides the list in smaller ‘partitions’ using ‘pivot’. The values which are smaller than the pivot are arranged in the left partition and greater values are arranged in the right partition. Each partition is recursively sorted using quick sort.

19. What Is A Graph?

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.

20. How Depth First Traversal Works?

Depth First Search algorithm(DFS) traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration.

21. How Breadth First Traversal Works?

Breadth First Search algorithm(BFS) traverses a graph in a breadth wards motion and uses a queue to remember to get the next vertex to start a search when a dead end occurs in any iteration.

22. What Is A Tree?

A tree is a minimally connected graph having no loops and circuits.

23. What Is A Binary Tree?

A binary tree has a special condition that each node can have two children at maximum.

24. What Is Tower of Hanoi problem?

Tower of Hanoi, is a mathematical puzzle which consists of three tower (pegs) and more than one rings. All rings are of different size and stacked upon each other where the large disk is always below the small disk. The aim is to move the tower of disk from one peg to another, without breaking its properties.

25. State Recursion and Its Different Types?

Recursion is the name given to the technique of defining a set or a process in terms of itself. There are essentially two types of recursion. The first type concerns recursively defined function and the second type of recursion is the recursive use of a procedure.

26. Define String In An Algorithmic Notation And An Example To Support It?

In the algorithmic notation, a string is expressed as any sequence of characters enclosed in single quote marks.

27. How to Find Median of a Bst?

Find the no. of elements on the left side.

If it is n-1 the root is the median.

If it is more than n-1, then it has already been found in the left sub tree.

Else it should be in the right sub tree.

28. What Is The General Strategy For Markov Algorithm?

The general strategy in a Markov Algorithm is to take as input a string’ a’ and, through a number of steps in the algorithm, transform a to an output string b. this transformation process is generally performed in computers for text editing or program compilation.

29. What Is Diffie-hellman problem in algorithms?

It is noted that by which a key can be securely shared by two users without any actual exchange.

30. What Is The Goal Of The Shortest Distance Algorithm?

The goal is completely fill the distance array so that for each vertex v, the value of distance[v] is the weight of the shortest path from start to v.

31. What Is A Backtracking Algorithm? 

It is an algorithm that considers systematically all possible outcomes for each decision. Examples of backtracking algorithms are the problem generating permutations of a given sequence.

32. What Is Best-first Search Algorithm?

It is a search algorithm that considers the estimated best partial solution next. This is typically implemented with priority queues of data analysis algorithm.

33. Define a Brute-force Algorithm. Give an Example?

A brute force algorithm is a type of algorithm that proceeds in a simple and easy way, but requires a huge number of steps to complete. As an example, if you want to find out the factorial of a given number n, using this sort of algorithm will require to get all the possible number combinations one by one.

34.  Explain about the Algorithm Ord words?

Ord algorithm constructs the vectors TITLE, T_INDEX, and KEYWORDS.

35. How to find if two given rectangles overlap in problem solving?
Two rectangles do not overlap if one of the following conditions is true.
1) One rectangle is above top edge of other rectangle.
2) One rectangle is on left side of left edge of other rectangle.

36. How to count inversions in a sorted array?
Two elements arr[i] and arr[j] in an array arr [] form an inversion if a[i] > a[j] and i < j. How to count all inversions in an unsorted way. 

37. How to write an efficient method to calculate x raise to the power n?
The idea is to use divide and conquerhere to do it in O (Logn) time.  

38. Explain what is Space complexity of insertion sort algorithm?

Insertion sort is an in-place sorting algorithm which means that it requires no extra or little.  Storage. For insertion sort, it requires only single list elements to be stored out-side the initial data, making o (1) in the space-complexity.

39. Explain how encryption algorithm works?

Encryption is the process of converting plaintext into a secret code format referred as “Cipher text”. To convert the text, algorithm uses a string of bits referred as “keys” for calculations. The larger the key, the greater the number of potential patterns for creating cipher text. Most encryption algorithm use codes fixed blocks of input that have length about 64 to 128 bits, while some uses stream method.

40. Explain the code of inorder tree traversal?

/##
 # @typedef {{
 #   Val: number,
 #   left: Node,
 # Right: Node,
 #}} Node
 #/
/##
 # @param {Node} root
 # @return {Array<number>} In-order printout of the tree’s nodes.
 #/
Function inOrderTraversal (root) {
}

41. What is strassens matrix multiplication problem?

Stassen’s Matrix multiplication can be performed only on square matrices where n is a power of 2. Order of both of the matrices are n × n.

42. What is the Procedure of Strassen matrix multiplication

There are some procedures:

1. Divide a matrix of order of 2*2 recursively till we get the matrix of 2*2.
2. Use the previous set of formulas to carry out 2*2 matrix multiplication.
3. In this eight multiplication and four additions, subtraction are performed.
4. Combine the result of two matrixes to find the final product or final matrix.

43. Explain the formula of strassens matrix problem?

Strassen’s matrix multiplication there are seven multiplication and four addition, subtraction in total.

D1 =  (a11 + a22) (b11 + b22)
D2 =  (a21 + a22).b11
D3 =  (b12 – b22).a11
D4 =  (b21 – b11).a22
D5 =  (a11 + a12).b22
D6 =  (a21 – a11) . (b11 + b12)
D7 =  (a12 – a22) . (b21 + b22)
    C11 = d1 + d4 – d5 + d7
    C12 = d3 + d5
    C21 = d2 + d4
    C22 = d1 + d3 – d2 – d6

44. Write the algorithm for strassens multiplication in the form of psudocode?

Algorithm Strassen (n, a, b, d)
begin
If n = threshold then compute
C = a * b is a conventional matrix.
Else
Partition a into four sub matrices  a11, a12, a21, a22.
Partition b into four sub matrices b11, b12, b21, b22.
Strassen ( n/2, a11 + a22, b11 + b22, d1)
Strassen ( n/2, a21 + a22, b11, d2)
Strassen ( n/2, a11, b12 – b22, d3)
Strassen ( n/2, a22, b21 – b11, d4)
Strassen ( n/2, a11 + a12, b22, d5)
Strassen (n/2, a21 – a11, b11 + b22, d6)
Strassen (n/2, a12 – a22, b21 + b22, d7)
C = d1+d4-d5+d7     d3+d5
d2+d4           d1+d3-d2-d6
end if
return (C)
end.

45. What is decrease and conquer algorithm?

To exploit the relationship between the solution of a given instance of a problem and the solution of a smaller instance of the same problem. By reducing successively the problem’s dimension we eventually arrive to a particular case which can be solved directly.

46. What is the main motive of decrease and conquer algorithm?

It is such an approach could lead us to an algorithm which is more efficient than a brute force algorithm • sometimes it is easier to describe the solution of a problem by referring to the solution of a smaller problem than to describe explicitly the solution.

47. Give the syntax of decrease and conquer algorithm?

consider the problem of computing xn for n=2m, m>=1 Since x*x if m=1 x 2^m= x 2^(m-1)*x2^(m-1) if m>1 It follows that we can compute x2^m by computing: m=1 => p:=x*x=x2 m=2 => p:=p*p=x2 *x2=x4 m=3 => p:=p*p=x4 *x4=x8

48. Explain the analysis and complexity of decrease and conquer algorithm?

Power2(x,m) p ← x*x FOR i ← 1, m-1 DO p ← p*p ENDFOR RETURN p Analysis: a) Correctness Loop invariant: p=x2^i b) Complexity (i) problem size: m (ii) dominant operation: * T(m) = m Remark: m=log n

49. Explain the code of DFS in algorithm

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)
init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)

50. Explain the code of BFS in algorithm?

BFS(G,start_v):
    let Q be a queue
      label start_v as discovered
      Q.enqueue(start_v)
      while Q is not empty
          v = Q.dequeue()
          if v is the goal:
              return v
          for all edges from v to w in G.adjacentEdges(v) do
             if w is not labeled as discovered:
                 label w as discovered
                 w.parent = v
                 Q.enqueue(w) 

51. What is the Space and time complexity of BFS algorithm?

 O(|V|) = O(b^d)

52. What is the space and time complexity of DFS algorithm?

O (V+E) Say, you have a connected graph with V nodes and E edges. In DFS, you traverse each node exactly once. Therefore, the time complexity of DFS is at least O (V)

53. What is the difference between BFS and DFS algorithms?       

COMPARISON	BFS	DFS
Basic	Vertex-based algorithm	Edge-based algorithm
Data structure used to store the nodes	Queue	Stack
Memory consumption	Inefficient	Efficient
Structure of the constructed tree	Wide and short	Narrow and long
Traversing fashion	Oldest unvisited vertices are explored at first.	Vertices along the edge are explored in the beginning.
Optimality	Optimal for finding the shortest distance, not in cost.	Not optimal
Applications	Examines bipartite graph, connected component and shortest path present in a graph.	Examines two-edge connected graph, strongly connected graph, acyclic graph and topological order.

54.What is topological sorting? 

Topological Sort: A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge UV from vertex u to vertex v, u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph.

55. Explain topological sorting with example?

As in the image above, the topological order is 7 6 5 4 3 2 1 0. There can be one or more topological order in any graph. Like in the example above 7 5 6 4 2 3 1 0 is also a topological order.

56. Explain the psudocode of topological sorting?

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is non-empty do
  remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
    remove edge e from the graph
  if m has no other incoming edges then
      insert m into S
if graph has edges then
    return error   (graph has at least one cycle)
else
   return L 

57. Explain the technique of transform and conquer?

Either the problem or algorithm can be transformed in one of three ways

• Instance simplification: the instances of the problem can be transformed into an easier instance to solve.
• Representation change: the data structure can be transformed so that it is more efficient.
• Problem reduction: the problem can be transformed to an easier problem to solve.

58. What is presorting technique explain? Tell the cost of calculation?

“Presorting” is a common example of “instance simplification.” Presorting is sorting ahead of time, to make repetitive solutions faster.  If you wish to find many kth statistics in an array then it might make sense to sort the array ahead of time for so that the cost for determining each statistics is constant time.

Presorting is a form of preconditioning. Preconditioning is manipulating the data to make the algorithm faster.

Another example is the problem to determine the uniqueness of array elements. The brute force algorithm would compare each array element with the rest of the array. The cost would be Θ(n2). If we presort the array then the algorithm only needs to compare adjacent elements for uniqueness. The cost for determining uniqueness (without the sorting cost) is Θ(n).

 The total cost is

T (n) = Tsort (n) + Tscan (n) ε Θ (n log n) + Θ (n) = Θ (n log n)

59. Write the psudocode on presorting?

Algorithm PresortMode (A[0…n-1])
// assumes that A is sorted
i ← 0
Modefrequency ← 0
While i < n do
Runlength ← 1
Runvalue ← A[i]
while i+runlength < n and A[i+runlength] = runvalue do
runlength++
if runlength > modefequency then
modefrequency ← runlength
modevalue ← runvalue
return modevalue

60. What is heap Sort?

A heap is a priority queue that is a complete tree

61. What are the properties of heap sort?

   Properties of Heaps

1. The height of a heap is floor (log n).
2. The root contains the highest priority item.
3. A node and all the descendants is a heap
4. A heap can be implemented using an array and all operations are in-place.
5. If index of the root = 1 then index of left child = 2iand right child = 2i+1
6. Level iof the heap has 2 power i elements
7. heap order, the parent value is larger than the children value.

62. Explain the psudocode of heap sorting?

HeapBottomUp (H[1…n])
for i ← floor (n/2) down to 1 do
k ← i // parent index
v ← H[k] // proposed parent value
heap ← false
while not heap and 2*k ≤ n do
J ← 2*k
if j < n then // there are children
if H[j] < H[j+1] then j++ // find the larger child value
if v ≥ H[j] then heap ← true  // check heap ordering mode
else // correct the heap ordering
H[k] ← H[j] // bubble down
k ← j // move down the heap
H[k] ← v // insert the value

 63. What is warshall algorithm?

 Floyd-Warshall algorithm will tell the optimal distance between each pair of friends. It will clearly tell you that the quickest path from one home to another house or from source to destination is the connecting edge that has a weight of 1. 

64. Explain the psudocode of warshall algorithm?

Create a |V| x |V| matrix, M, that will describe the distances between vertices
For each cell (i, j) in M:
    if i == j:
        M[i][j] = 0
    if (i, j) is an edge in E:
        M[i][j] = weight(i, j)
    else:
        M[i][j] = infinity
for k from 1 to |V|:
 for i from 1 to |V|:
  for j from 1 to |V|:
  if M[i][j] > M[i][k] + M[k][j]:
  M[i][j] = M[i][k] + M[k][j]

65. What is the time and space complexity of warshall algorithm?

The Floyd-Warshall algorithm runs in O\big (|V|^ {3}\big) O (∣V∣ to the power 3) time.

66. What is a ford’s Algorithm?

Bellman Ford’s algorithm is used to find the shortest paths from the source vertex to all other vertices in a weighted graph. It depends on the concept of Shortest path contains at most n−1 edges, because the shortest path couldn’t have a cycle. 

67. Explain the psudocode of fords algorithm?

vector <int> v [2000 + 10];
    int dis [1000 + 10];
    for(int i = 0; i < m + 2; i++){
        v[i].clear();
        dis[i] = 2e9;
    }
   for(int i = 0; i < m; i++){
        scanf(“%d%d%d”, &from , &next , &weight);
        v[i].push_back(from);
        v[i].push_back(next);
        v[i].push_back(weight);
   }
    dis[0] = 0;
    for(int i = 0; i < n – 1; i++){
     int j = 0;
     while(v[j].size() != 0){
            if(dis[ v[j][0]  ] + v[j][2] < dis[ v[j][1] ] ){
                dis[ v[j][1] ] = dis[ v[j][0]  ] + v[j][2];
            }
            j++;
        }
    }

68. What is the time complexity of fords algorithm?

Time Complexity of Bellman Ford algorithm is relatively high O (v, E), in case E=V square, O (E cube).

69. What is knapsack problem in algorithm?

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

70. Explain the algorithm psudocode of knapsack problem?

• List item Total number of items
• List item Weight
• List item Value
• List item If item is fragile or not (true/false)

Constrains:

• List item Maximal weight of knapsack
• List item Maximum number of fragile items knapsack can contain.

It looks like a modification to knapsack would solve it.

Let’s say we have N items, maximum knapsack weight is W, and max amount of fragile items is F
let’s define our dp table as 3-dimensional array dp[N+1][W+1][F+1]
p[N+1][W+1][F+1] // memo table, initially filled with -1
 int solve(n,w,f)
{
    if(n > N)return 0;
    if(dp[n][w][f] != -1) return dp[n][w][f];
    dp[n][w][f] = solve(n+1,w,f); //skip item
    if(w + weight(n) <= W && f + isFragile(n) <=F)
    dp[n][w][f] = max(dp[n][w][f], value(n) + solve(n+1, w + weight(n), f + isFragile(n)));
    return dp[n][w][f]
}
print(solve(1,0,0))
for getting the sub set
vector<int> getSolution(n,w,f)
{
    int optimalValue = solve(n,w,f);
    vector<int>answer; //just some dynamic array / arrayList
    while(n <= N)
    {
        if(solve(n+1,w,f) == optimalValue)n++; //if after skipping item we can still get optimal answer we just skip it
        else //otherwise we cant so current item must be taken
        {
            int new_w = w + weight(n);
            int new_f = f + isFragile(n);
            answer.push_back(n); //so we just save its index, and update all values
            optimalValue -= value(n);
            n++;
            w = new_w;
            f = new_f;
        }
    }
    return answer;
}

71. What is the time complexity of knapsack problem?

Time complexity of 0 1 Knapsack problem is O (nW) where, n is the number of items and W is the capacity of knapsack.

72. What is greedy technique in algorithm?

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. … A candidate set, from which a solution is created. A selection function, which chooses the best candidate to be added to the solution.

73. Which algorithms of complexity belongs to greedy technique?

Examples of such greedy algorithms are Kruskal’s algorithm and Prim’s algorithm for finding minimum spanning trees, and the algorithm for finding optimum Huffman trees

74. Who invented greedy algorithm?

Huffman invented a greedy algorithm that constructs an optimal prefix code called a Huffman code. 

75. What is prims algorithm?

A minimum-cost spanning tree (MST) is one which has the smallest possible total weight. A graph might have more than one MST, but in the Prim’s algorithm the approach used by Prim’s algorithm to select a “starting” vertex, then “grow” the tree out from that point

76. Explain the psudocode for prims algorithm?

(G, w, r)
for each u  V [G]
 do key[u] ← ∞
 π[u] ← NIL
 key[r] ← 0
 Q ← V [G]
 while Q ≠ Ø
 do u ← EXTRACT-MIN(Q)
  for each v  Adj[u]
 do if v  Q and w(u, v) < key[v]
 then π[v] ← u
 key[v] ← w(u, v)

77. Explain the steps for prims algorithm?

make the all vertex distance infinity from source and zero for the vertex from where you are starting.

Then make a min-heap with these values.

While (i<n-1)
u=Extract-min
For (all vertex adjacent to u)
If (distance (adjacent vertex)>edge weight)
Then update the heap of the location v with edge weight other wise do not do anything.
This will generate the MST.

78. Define kruskal’s algorithm?

Kruskal’s algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which. Form a tree that includes every vertex.  

79. Explain the steps in kruskal’s algorithm?

• create a forest F (a set of trees), where each vertex in the graph is a separate tree
• create a set S containing all the edges in the graph
• while S is not empty  and F is not yet spanning tree 
  • remove an edge with minimum weight from S
  • if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree

At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, the forest has a single component and forms a minimum spanning tree.

80. Explain the psudocode of kruskal’s algorithm?

KRUSKAL (G):
1 A = ∅
2 foreach v ∈ G.V:
3    MAKE-SET(v)
4 foreach (u, v) in G.E ordered by weight (u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION (FIND-SET (u), FIND-SET(v))
8 return A

81. What is Dijkastra’s algorithm who invented this?

Dijkastra’s algorithm (or Dijkstra’s Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

82. What is the time complexity of dijkastra’s algorithm?

The time complexity for the matrix representation is O (V^2). In this post, O (ELogV) algorithm for adjacency list representation is discussed

83. Explain the psudocode of Dijkastra’s algorithm?

t v1 be the origin vertex,
//   and initialize W and ShortDist[u] as
   X: = {v1}
   ShortDist[v1] :=0
   FOR each u in V – {v1}
      ShortDist[u]:= T [v1, u]
// Now repeatedly enlarge X
//   until W includes all verticies in V
   WHILE X <> V
      // Find the vertex w in V – X at the minimum distance
      //   from v1
      MinDist: = INFINITE
      FOR each v in V – W
         IF ShortDist[v] < MinDist
            MinDist = ShortDist[v]
            x: = v
         END {if}
      END {for}
      // Add x to X
      X: = W U {w}
      // Update the shortest distance to vertices in V – X
      FOR each u in V – X
         ShortDist[u]:= Min (ShorDist[u], ShortDist[w] + T [w, u])
   END {while}

84. Explain Huffman trees?

Huffman coding is a lossless data compression algorithm. In this algorithm, a variable-length code is assigned to input different characters. The code length is related to how frequently characters are used. … First one to create a Huffman tree, and another one to traverse the tree to find codes.

85. Explain the logical steps in Huffman tree construction?

1. n=|C|
2. Q=C
3. for i=1 to n-1
4. do
5. z=allocate Node()
6. x=left[z] =Extract_Min (Q)
7. y=right[z] =Extract_Min (Q)
8. f[z] =f[x] +f[y]
9. Insert (Q,z)
10. Return Extract_Min(Q)
 Analysis
The Q is initialized as a priority queue with the character C.
Q=C can be performed by using Build Heap in O (n) time.
For loop takes (|n|-1) times because each heap operation requires O (log n) time.
Hence the total running time of Huffman code on the set of n characters is O (n log n).

86. What is lower bound argument in algorithm?

Lower bound is the best case running time. Lower bound is determined by the easiest input. It provides a goal for all inputs. 

87. What is upper bound in an algorithm?

Upper bound is the worst case and is determined by the most difficult input for a given algorithm.

88. What is branch and bound in an algorithm?

Branch and bound is a systematic method for solving optimization problems. B&B is a rather general optimization technique that applies where the greedy method and dynamic programming fail.

89. What is computational model in algorithm?

The computational complexity of a problem is the minimum of the complexities of all possible algorithms for this problem (including the unknown algorithms). … Clearly, both areas are strongly related, as the complexity of an algorithm is always an upper bound of the complexity of the problem solved by this algorithm.

90. What is list ranking in algorithms?

Ranking Algorithm Definition. An algorithm is a set of mathematical systems of calculations designed to create a result. Search Engines use algorithms to weigh varied elements to determine which webpage is most relevant to a search query.

91. What is page ranking in algorithm?

PageRank is a link analysis algorithm and it assigns a numerical weighting to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of “measuring” its relative importance within the set.