Longest common substring problem

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

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: [Read More]
Algorithms  kodeknight  String  Dynamic Programming  DP 

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 

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 

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 

Optimal Substructure

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

A problem is said to have optimal substructure if the globally optimal solution can be constructed from locally optimal solutions to subproblems. The general form of problems in which optimal substructure plays a roll goes something like this. Let’s say we have a collection of objects called A. For each object o in A we have a “cost,” c(o). Now find the subset of A with the maximum (or minimum) cost, perhaps subject to certain constraints. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP 

Overlapping subproblems in Dynamic programming

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

A problem is said to have overlapping subproblems if it can be broken down into subproblems which are reused multiple times. This is closely related to recursion. To see the difference consider the factorial function, defined as follows (in Python): def factorial(n): if n == 0: return 1 return n*factorial(n-1) Thus the problem of calculating factorial(n) depends on calculating the subproblem factorial(n-1). This problem does not exhibit overlapping subproblems since factorial is called exactly once for each positive integer less than n. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP 

Common characterstics in dynamic programming

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

Dynamic Programming is an algorithm design technique for optimization problems: often minimizing or maximizing. Like divide and conquer, DP solves problems by combining solutions to subproblems. Unlike divide and conquer, subproblems are not independent. Subproblems may share subsubproblems, However, solution to one subproblem may not affect the solutions to other subproblems of the same problem. (More on this later.) DP reduces computation by: Solving subproblems in a bottom-up fashion. [Read More]
kodeknight  Dynamic Programming  DP