Dynamic Programming Practise Problem Set 3

Calculate M = M1 × M2 × M3 × M4, where the dimensions of the matrices are M1: 10,20       M2: 20,50       M3: 50,1       M4: 1,100 a) Calculating M = M1 × ( M2 × ( M3 × M4 ) ) b) Calculating M = ( M1 × ( M2 × M3 ) ) × M4 2 Calculate the length of longest sub string in Hello and Aloha 3. Calculate longest sub sequence in  houseboat and computer. Answers 1 a) 125000    b)  2200 2        A L O H A    ...

Read More

Longest common substring problem

Given two sequences of letters, such as A = HELLO and B = ALOHA, find the longest contiguous sequence appearing in both. One solution:   (assume strings have lengths m and n) For each of the m starting points of A, check for the longest common string starting at each of the n starting points of B. The checks could average Θ(m) time → a total of Θ(m^2*n) time. Dynamic programming solution: Let Li, j = maximum length of common strings that end at A[i] & B[j].   Then, Li, j  =  0 if i = 0 or j = 0        ...

Read More

Dynamic Programming Practise Problem Set 2

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. Here’s the dynamic programming solution for this problem. (It does not use the फक्त that an optimal solution...

Read More

Matrix chain multiplication

Problem Given a sequence of n matrices M1, M2, ... Mn, and their dimensions p0, p1, p2, ..., pn, where where i = 1, 2, ..., n, matrix Mi has dimension pi − 1 × pi, 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. The order of which matrices are multiplied together first can significantly affect the time required. To multiply M×N, where matrix M is p×q and matrix N is q×r, takes pqr operations...

Read More

Dynamic Programming Practise Problem Set 1

 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”. Suppose you are given DNA sequences D1 of n1 characters and DNA sequence D2 of n2 characters. You might want to know...

Read More

Prim's Algorithm

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...

Read More

Kruskal's Algorithm

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...

Read More

Dynamic-Programming Algorithm for the Activity-Selection Problem

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. LECTURE-HALL-ASSIGNMENT (s,f) n = length [s) FOR i = 1 to n        ...

Read More

An Activity Selection Problem ( Greedy Approach)

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 Greedy Algorithm for Selection Problem I. Sort the input activities by increasing finishing time. f1 ≤ ...

Read More

Dijkstra's Algorithm (Shortest Path)

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. Hence we have the invariant property V=S U C. When algorithm starts Delta contains only the source vertex and when the algorithm...

Read More

Dynamic-Programming Solution to the 0-1 Knapsack Problem

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...

Read More

Find the nth Fibonacci number

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. Solution 1 - Using Recursion If we translate...

Read More

Solve the Rat In A Maze problem using backtracking.

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. For the sake of simplifying the implementation, have a boundary around your matrix and fill it up with all ones. This is so that you know when the rat is trying to go...

Read More

Representing the Solution Space

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...

Read More

Balancing Scales

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...

Read More