DIFFERENCE BETWEEN PRIM’S and KRUSKAL’S ALGORITHM
Prim’s Algorithm Kruskal’s Algorithm
It starts to build the Minimum Spanning
It starts to build the Minimum Spanning
Tree from the vertex carrying minimum
Tree from any vertex in the graph.
weight in the graph.
It traverses one node more than one time
It traverses one node only once.
to get the minimum distance.
Prim’s algorithm has a time complexity
of O(V2), V being the number of vertices Kruskal’s algorithm’s time complexity is
and can be improved up to O(E log V) O(E log V), V being the number of vertices.
using Fibonacci heaps.
Kruskal’s algorithm can generate
Prim’s algorithm gives connected
forest(disconnected components) at any
component as well as it works only on
instant as well as it can work on
connected graph.
disconnected components
Prim’s algorithm runs faster in dense Kruskal’s algorithm runs faster in sparse
graphs. graphs.
It generates the minimum spanning tree It generates the minimum spanning tree
starting from the root vertex. starting from the least weighted edge.
Applications of prim’s algorithm are
Travelling Salesman Problem, Network Applications of Kruskal algorithm are LAN
for roads and Rail tracks connecting all connection, TV Network etc.
the cities etc.
Prim’s algorithm prefer list data Kruskal’s algorithm prefer heap data
structures. structures.
DIFFERENCE BETWEEN BACKTRACKING AND BRANCH & BOUND
Parameter Backtracking Branch and Bound
Backtracking is used to find all Branch-and-Bound is used to solve
possible solutions available to a optimisation problems. When it
Approach problem. When it realises that it realises that it already has a better
has made a bad choice, it undoes optimal solution that the pre-solution
the last choice by backing it up. leads to, it abandons that pre-solution.
It searches the state space tree It completely searches the state space
until it has found a solution for tree to get optimal solution.
the problem.
Backtracking traverses the state
Branch-and-Bound traverse the tree in
Traversal space tree by DFS(Depth First
any manner, DFS or BFS.
Search)manner.
Backtracking involves Branch-and-Bound involves a
Function
feasibility function. bounding function.
Backtracking is used for solving Branch-and-Bound is used for solving
Problems
Decision Problem. Optimisation Problem.
In Branch-and-Bound as the optimum
In backtracking, the state space
solution may be present any where in
Searching tree is searched until the
the state space tree, so the tree need to
solution is obtained.
be searched completely.
Efficiency Backtracking is more efficient. Branch-and-Bound is less efficient.
Useful in solving N-Queen
Useful in solving Knapsack
Problem, Sum of subset,
Applications Problem, Travelling Salesman
Hamilton cycle problem, graph
Problem.
coloring problem
Backtracking can solve almost
Branch-and-Bound can not solve
Solve any problem. (chess, sudoku, etc
almost any problem.
).
Typically backtracking is used Branch and bound is used to solve
Used for
to solve decision problems. optimization problems.
Nodes in stat space tree are Nodes in tree may be explored in
Nodes
explored in depth first tree. depth-first or breadth-first order.
Next move from current state Next move is always towards better
Next move
can lead to bad choice. solution.
On successful search
Entire state space tree is search in
Solution of solution in state space tree,
order to find optimal solution.
search stops.
DIFFERENCE BETWEEN GREEDY APPROACH AND DYNAMIC
PROGRAMMING
Feature Greedy method Dynamic programming
In Dynamic Programming we make
In a greedy Algorithm, we make
decision at each step considering
whatever choice seems best at the
Feasibility current problem and solution to
moment in the hope that it will
previously solved sub problem to
lead to global optimal solution.
calculate optimal solution .
It is guaranteed that Dynamic
In Greedy Method, sometimes Programming will generate an
Optimality there is no such guarantee of optimal solution as it generally
getting Optimal Solution. considers all possible cases and
then choose the best.
A Dynamic programming is an
A greedy method follows the
algorithmic technique which is
problem solving heuristic of
Recursion usually based on a recurrent
making the locally optimal choice
formula that uses some previously
at each stage.
calculated states.
It is more efficient in terms of It requires Dynamic Programming
Memoization memory as it never look back or table for Memoization and it
revise previous choices increases it’s memory complexity.
Greedy methods are generally
Dynamic Programming is generally
Time faster. For example, Dijkstra’s
slower. For example, Bellman Ford
complexity shortest path algorithm takes
algorithm takes O(VE) time.
O(ELogV + VLogV) time.
The greedy method computes its
Dynamic programming computes
solution by making its choices in
its solution bottom up or top down
Fashion a serial forward fashion, never
by synthesizing them from smaller
looking back or revising previous
optimal sub solutions.
choices.
Fractional knapsack . 0/1 knapsack problem
Example
DIFFERENCE BETWEEN DAC AND DYNAMIC PROGRAMMING
Divide and Conquer Method Dynamic Programming
[Link] deals (involves) three steps at each level [Link] involves the sequence of four steps:
of recursion: o Characterize the structure of
Divide the problem into a number of optimal solutions.
subproblems. o Recursively defines the values of
Conquer the subproblems by solving them optimal solutions.
recursively. o Compute the value of optimal
Combine the solution to the subproblems solutions in a Bottom-up minimum.
into the solution for original subproblems. o Construct an Optimal Solution from
computed information.
2. It is Recursive. 2. It is non Recursive.
3. It does more work on subproblems and 3. It solves subproblems only once and then
hence has more time consumption. stores in the table.
4. It is a top-down approach. 4. It is a Bottom-up approach.
5. In this subproblems are independent of 5. In this subproblems are interdependent.
each other.
6. For example: Merge Sort & Binary Search 6. For example: Matrix Multiplication.
etc.
DIFFERENCE BETWEEN DAC AND GREEDY APPROACH
[Link] Divide and conquer Greedy Algorithm
Divide and conquer is used to obtain a The greedy method is used to obtain
1 solution to the given problem, it does not an optimal solution to the given
aim for the optimal solution. problem.
In this technique, the problem is divided
into small subproblems. These In Greedy Method, a set of feasible
subproblems are solved independently. solutions are generated and pick up
2
Finally, all the solutions to subproblems one feasible solution is the optimal
are collected together to get the solution to solution.
the given problem.
A greedy method is comparatively
Divide and conquer is less efficient and
3 efficient and faster as it is iterative
slower because it is recursive in nature.
in nature.
In the Greedy method, the optimal
Divide and conquer may generate duplicate
4 solution is generated without
solutions.
revisiting previously generated
[Link] Divide and conquer Greedy Algorithm
solutions, thus it avoids the re-
computation
Greedy algorithms also run in
Divide and conquer algorithms mostly run
5 polynomial time but take less time
in polynomial time.
than Divide and conquer
Examples: Fractional Knapsack
Examples: Merge sort,
problem,
6 Quick sort,
Activity selection problem,
Strassen’s matrix multiplication.
Job sequencing problem.
DIFFERENCE BETWEEN DYNAMIC PROGRAMMING AND BRUTE FORCE
APPROACH
Parameters of
Comparison Brute Force Dynamic Programming
It also finds all the possible
It finds all the
outcomes, but avoids recomputation
Methodology possible outcomes of
by storing
a given problem.
solutions of the subproblems.
It helps us optimize the brute force
It could be anything,
approach, sometimes exponential
Time Complexity sometimes even in
terms are improved to polynomial
exponential terms.
terms(ex. factorial program).
The number of The number of iterations is less(in
Iterations
iterations is more terms of n)
Efficiency It is less efficient It is more efficient
Generally requires no
It requires extra space for storing the
extra space for storing
Storage solutions to the sub-problems, which
results of sub-
could be further used when required.
problems.