Prim's Algorithm
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
This algorithm was first propsed by Jarnik, but typically attributed to Prim. It starts from an arbitrary vertex (root) and at each stage, add a new branch (edge) to the tree already constructed, much like a mould. The algorithm halts when all the vertices in the graph have been reached.
To understand the problem statement refer here.
This is similar to djikstra’s algorithm where we were clear where to begin with as we were given the source vertex, but here we have to choose arbitrarily.
[Read More]Kruskal's Algorithm
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
In kruskal’s algorithm the selection function chooses edges in increasing order of length without worrying too much about their connection to previously chosen edges, except that never to form a cycle. The result is a forest of trees that grows until all the trees in a forest (all the components) merge in a single tree. graph
Example
In Kruskal’s algorithm, we sort the edges according to their edge weights and start counting them and including them in MST, if they are not forming any cycle.
[Read More]Dynamic-Programming Algorithm for the Activity-Selection Problem
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem: Given a set of activities to among lecture halls. Schedule all the activities using minimal lecture halls.
In order to determine which activity should use which lecture hall, the algorithm uses the GREEDY-ACTIVITY-SELECTOR to calculate the activities in the first lecture hall. If there are some activities yet to be scheduled, a new lecture hall is selected and GREEDY-ACTIVITY-SELECTOR is called again. This continues until all activities have been scheduled.
[Read More]An Activity Selection Problem ( Greedy Approach)
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
An activity-selection is the problem of scheduling a resource among several competing activity.
Statement: Given a set S of n activities with and start time, Si and fi, finish time of an ith activity. Find the maximum size set of mutually compatible activities.
Compatible Activities
Activities i and j are compatible if the half-open internal [si, fi) and [sj, fj) do not overlap, that is, i and j are compatible if si ≥ fj and sj ≥ fi
[Read More]Dijkstra's Algorithm (Shortest Path)
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Consider a directed graph G = (V, E).
Problem Determine the length of the shortest path from the source to each of the other nodes of the graph. This problem can be solved by a greedy algorithm often called Dijkstra’s algorithm.
The algorithm maintains two sets of vertices, S and C. At every stage the set S contains those vertices that have already been selected and set C contains all the other vertices.
[Read More]Dynamic-Programming Solution to the 0-1 Knapsack Problem
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Problem Statement 0-1 Knapsack problem
Input :
There are n items, and each item has a value:
value vi (non negative) size or weight wi (non negative and integral ) Capicity W (non negative and integer) Output:
Select a subset S ⊆ {1,2,3,….n}
that maximizes ∑ vi subject to max value&sum wi ≤ W Sometimes you may hear a cheesy problem a thief robbing a store and can carry a maximal weight of W into their knapsack.
[Read More]Find the nth Fibonacci number
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Problem: Write the code for nth Fibonacci number.
Solution: There are basically two approaches to solving the Fibonacci problem. Lets looks at the definition of Fibonacci series first.
The Fibonacci series is defined as follows
F(n) = 0 for n = 0 1 for n = 1 F(n-1) + F(n-2) for n > 1 So, F(n) = F(n-1)+F(n-2) for n≥2and 1 otherwise.
There are couple of approach to solve this.
[Read More]Solve the Rat In A Maze problem using backtracking.
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
This is one of the classical problems of computer science. There is a rat trapped in a maze. There are multiple paths in the maze from the starting point to the ending point. There is some cheese at the exit. The rat starts from the entrance of the maze and wants to get to the cheese.
This problem can be attacked as follows.
Have a m*m matrix which represents the maze.
[Read More]Representing the Solution Space
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
This section presents an interface for the nodes of a solution space. By using an interface, we hide the details of the specific problem to be solved from the backtracking algorithm. In so doing, it is possible to implement completely generic backtracking problem solvers.
Although a backtracking algorithm behaves as if it is traversing a solution tree, it is important to realize that it is not necessary to have the entire solution tree constructed at once.
[Read More]Balancing Scales
Posted on July 5, 2010
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Consider the set of scales shown in Figure . Suppose we are given a collection of n weights, , and we are required to place all of the weights onto the scales so that they are balanced.
Figure: A set of scales.
The problem can be expressed mathematically as follows: Let represent the pan in which weight is placed such that
The scales are balanced when the sum of the weights in the left pan equals the sum of the weights in the right pan,
[Read More]