Dynamic Programming Practise Problem Set 2

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

1. Below is a dynamic programming solution for this problem to illustrate how it can be used. There is a very straightforward O(1) time solution. It can be shown that इफ n >= 50 then any solution will include a set of coins that adds to exactly 50 cents. Hence it can be shown that an optimal solution uses 2 · [n/50 ] quarters along with un optimal solution for making n/50 − bn/50c cents which can be looked up in a table ऑफ़ size 50. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP 

Matrix chain multiplication

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Given a sequence of n matrices _M_1, _M_2, … M__n, and their dimensions _p_0, _p_1, _p_2, …, p__n, where where i = 1, 2, …, n, matrix M__i has dimension p__i − 1 × p__i, determine the order of multiplication that minimizes the the number of scalar multiplications. We wish to determine the value of the product ∏i = 1 to n Mi, where Mi has ri-1 rows and ri columns. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP  matrix-multiplication  matrix 

Dynamic Programming Practise Problem Set 1

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Suppose we want to make change for n cents, using the least number of coins of denominations 1, 10, and 25 cents. Describe an O(n) dynamic programming algorithm to find an optimal solution. (There is also an easy O(1) algorithm but the idea here is to illustrate dynamic programming.)  Here we look at a problem from computational biology. You can think of a DNAsequence as sequence of the characters “a”,”c”,”g”,”t”. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP 

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]
Graph  Algorithms  kodeknight  greedy Algo 

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]
Graph  Algorithms  kodeknight  greedy Algo  incomplete 

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]
Algorithms  kodeknight  Dynamic Programming  DP 

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]
Algorithms  kodeknight  greedy Algo 

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]
Algorithms  kodeknight  greedy Algo  distance 

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]
Algorithms  kodeknight  knapsack problem  Dynamic Programming  DP 

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]
Algorithms  kodeknight  Dynamic Programming  DP  recursion  CrackingTheCodingInterview