• Explain asymptotic notations in detail?
    Asymptotic Notation is a way of comparing function that ignores constant factors and small input sizes. Three notations are used to calculate the running time complexity of an algorithm:
    Big-oh notation:
    Big-oh is the formal method of expressing the upper bound of an algorithm's running time. It is the measure of the longest amount of time. The function f (n) = O (g (n)) [read as "f of n is big-oh of g of n"] if and only if exist positive constant c and such that.
    Omega () Notation:
    The function f (n) = Ω (g (n)) [read as "f of n is omega of g of n"] if and only if there exists positive constant c and n0 such that.
    Theta Notation
    The function f (n) = ΞΈ (g (n)) [read as "f is the theta of g of n"] if and only if there exists positive constant k1, k2 and k0 such that
  • What is Divide and conquer method?
    Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design is to take a dispute on a huge input, break the input into minor pieces, decide the problem on each of the small pieces, and then merge the piecewise solutions into a global solution.
    Divide and Conquer algorithm consists of a dispute using the following three steps.
    Divide the original problem into a set of subproblems.
    Conquer: Solve every subproblem individually, recursively.
    Combine: Put together the solutions of the subproblems to get the solution to the whole problem.
    sample image
    Fundamentals of this method:
    There are two fundamental of Divide & Conquer Strategy:
    Relational Formula
    Stopping Condition 1. Relational Formula:
    It is the formula that we generate from the given technique. After generation of Formula we apply D&C Strategy, i.e. we break the problem recursively & solve the broken subproblems.
    2. Stopping Condition:
    When we break the problem using Divide & Conquer Strategy, then we need to know that for how much time, we need to apply divide & Conquer. So the condition where the need to stop our recursion steps of D&C is called as Stopping Condition.
  • What is maxium and minimum?
    Max-Min problem is to find a maximum and minimum element from the given array. We can effectively solve it using divide and conquer approach.
    In the traditional approach, the maximum and minimum element can be found by comparing each element and updating Max and Min values as and when required. This approach is simple but it does (n – 1) comparisons for finding max and the same number of comparisons for finding the min. It results in a total of 2(n – 1) comparisons. Using a divide and conquer approach, we can reduce the number of comparisons.
    Divide and conquer approach for Max. Min problem works in three stages.
    If a1 is the only element in the array, a1 is the maximum and minimum.
    If the array contains only two elements a1 and a2, then the single comparison between two elements can decide the minimum and maximum of them.
    If there are more than two elements, the algorithm divides the array from the middle and creates two subproblems. Both subproblems are treated as an independent problem and the same recursive process is applied to them. This division continues until subproblem size becomes one or two.
    After solving two subproblems, their minimum and maximum numbers are compared to build the solution of the large problem. This process continues in a bottom-up fashion to build the solution of a parent problem.
  • Define Dijkstra algorithm?
    Dijkstra algorithm is a single-source shortest path algorithm. Here, single-source means that only one source is given, and we have to find the shortest path from the source to all the nodes.
    Example Image
    First, we have to consider any vertex as a source vertex. Suppose we consider vertex 0 as a source vertex.
    Here we assume that 0 as a source vertex, and distance to all the other vertices is infinity. Initially, we do not know the distances. First, we will find out the vertices which are directly connected to the vertex 0. As we can observe in the above graph that two vertices are directly connected to vertex 0.
    Initially all the vertices are marked unvisited.
    The path to A is 0 and for all the other vertices it is set to infinity.
    Now the source vertex A is marked as visited.Then its neighbours are accessed(only accessed and not visited).
    The path to B is updated to 4 using relaxation as the path to A is 0 and path from A to B is 4, so min((0+4),∞) is 4.
    The path to C is updated to 5 using relaxation as the path to A is 0 and path from A to C is 5, so min((0+5),∞) is 5.Both the neighbours of A are relaxed so we move ahead.
    Then the next unvisited vertex with least path is picked and visited. So vertex B is visited and its unvisited neighbours are relaxed.After relaxing path to C remains 5, path to E becomes 11 and path to D becomes 13.
    Then vertex C is visited and its unvisited neighbour E is relaxed. While relaxing E, we find that the path to E via is smaller than its current path, so the path to E is updated to 8.All neighbours of C are now relaxed.
    Vertex E is visited and its neighbours B,D and F are relaxed. As only vertex F is unvisited only, F is relaxed. Path of B remains 4, path to D remains 13 and path to F becomes 14(8+6).
    Then vertex D is visited and only F is relaxed. .The path to vertex F remains 14.
    Now only vertex F is remaining so it is visited but no relaxations are performed as all of its neighbours are already visited.
    As soon as all the vertices become visited the program stops.
  • What is All pair shortest Path?
    All Pairs Shortest Path Algorithm is also known as the Floyd-Warshall algorithm. And this is an optimization problem that can be solved using dynamic programming.
    Let G = be a directed graph, where V is a set of vertices and E is a set of edges with nonnegative length. Find the shortest path between each pair of nodes.
    L = Matrix, which gives the length of each edge
    L[i, j] = 0, if i == j // Distance of node from itself is zero
    L[i, j] = ∞ , if i β‰  j and (i, j) βˆ‰ E
    L[i, j] = w (i, j), if i β‰  j and (i, j) ∈ E // w(i, j) is the weight of the edge (i, j)
    Principle of optimality :
    If k is the node on the shortest path from i to j, then the path from i to k and k to j, must also be shortest.
    In the following figure, the optimal path from i to j is either p or summation of p1 and p2.
  • What is Knapsack Problem?
    We are given N items where each item has some weight and profit associated with it. We are also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The target is to put the items into the bag such that the sum of profits associated with them is the maximum possible.
    Follow the below steps to solve the problem:
    The maximum value obtained from β€˜N’ items is the max of the following two values.
    Maximum value obtained by N-1 items and W weight (excluding nth item)
    Value of nth item plus maximum value obtained by N-1 items and (W – weight of the Nth item) [including Nth item].
    If the weight of the β€˜Nthβ€˜ item is greater than β€˜W’, then the Nth item cannot be included and Case 1 is the only possibility.
  • What are Hamilton Cycles?
    Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in the graph) from the last vertex to the first vertex of the Hamiltonian Path. Determine whether a given graph contains Hamiltonian Cycle or not. If it contains, then prints the path. Following are the input and output of the required function.
    Example Image
    pseudo Code
    Begin
    if all nodes are included, then
    if there is an edge between nodes k and 0, then
    return true
    else
    return false;

    for all vertex v except starting point, do
    if isValid(v, k), then //when v is a valid edge
    add v into the path
    if cycleFound(k+1) is true, then
    return true
    otherwise remove v from the path
    done
    return false
    End
  • What is a N-queens problem?
    The N Queen is the problem of placing N chess queens on an NΓ—N chessboard so that no two queens attack each other. For example, the following is a solution for the 4 Queen problem.
    Example Image
    Algorithm for n queens Problem
    Initialize an empty chessboard of size NxN.
    Start with the leftmost column and place a queen in the first row of that column.
    Move to the next column and place a queen in the first row of that column.
    Repeat step 3 until either all N queens have been placed or it is impossible to place a queen in the current column without violating the rules of the problem.
    If all N queens have been placed, print the solution.
    If it is not possible to place a queen in the current column without violating the rules of the problem, backtrack to the previous column.
    Remove the queen from the previous column and move it down one row.
    Repeat steps 4-7 until all possible configurations have been tried