# Tagged Questions

Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

36 views

### Given a set of numbers (negative or positive), and a maximum weight w, find a subset that is maximal whose sum is less than w

The aim of this problem is to find a subset (need not be consecutive) of a given set such that the sum is maximal and less than some given number $w$. (Note, we are trying to find a subset that is ...
36 views

### Getting speed difference between signal comparison using Dynamic Time Warping

I understand that Dynamic Time Warping is an algorithm to find a matching between two signals with different length and speed But is there a possible way to find the speed difference between the two ...
100 views

### Are basic CS algorithms used in machine learning?

I have read some articles which state that basic algorithms such as dynamic programming , graph algorithms etc are not required int machine learning fields such as deep learning , reinforcement ...
41 views

### can we solve dynamic knapsack problem using Memoization approach?

As we know Dynamic programming has two techniques. Bottom up dynamic programming approach. Top down memoization approach Normally dynamic knapsack problem is solved using Bottom up dynamic ...
29 views

### Find number of pairs [duplicate]

I have an array A of integers. I want to find possible number of pairs of non-intersecting sub-array which don't have any element common in them. For example A={1, 2, 1, 2} then correct subarrays(1-...
36 views

### Is there Any difference between dynamic programming vs branch-bound vs delayed column generation

I was reading about cutting stock problem https://en.wikipedia.org/wiki/Cutting_stock_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-...
53 views

### Discrete optimisation in 5 variables

I need to solve the following optimisation problem and I can't come up with any solutions. Is there any algorithm to solve this type of problem. I tried to think of a greedy algorithm or brute force, ...
227 views

### Finding all soldier wins

Consider the following game (see also this question): One day a castle is attacked at sunrise (by surprise) by n soldiers. Each soldier carries a canon and a rifle. The castle has strength s. On ...
73 views

### Understanding The Mapping Of Edges to Nodes In A Graph Theory Problem

I am really confused with this problem. Here's the problem: You have $N$ points numbered $1$ through $N$,inclusive, and $N$ arrows again numbered $1$ through $N$,inclusive. No two arrows start at ...
32 views

### Knuth Yao DP Speedup - Cutting Sticks

There's a problem called Cutting Sticks - we start with one stick and n points where it needs to be cut. Cutting a stick costs the length of that stick. Of course, we want to minimize the toal cost. ...
45 views

### Two recurrences for the change-making problem with repetition

The change-making problem with unbounded repetition is: Input: Unlimited quantities of coins with values $x_1, \ldots, x_n$; and an amount $v$. Output: Can the given $v$ amount of money be ...
39 views

### Does the Longest Common Subsequence problem reduce to its binary version?

I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by ...
42 views

### Figure out recursive function for this problem

I'm trying to solve this problem whole day. The result should be dynamic programming algorithm but the first thing I need is to find out recurrent function. There is N students (N is even) in class. ...
50 views

### With Memoization Are Time Complexity & Space Complexity Always the Same?

I am studying Dynamic Programming using both iterative and recursive functions. With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of ...
38 views

### Maximize cost in graph with variable costs

Consider the following problem. A prisoner eats once a day, he can either have a low, or a high calorie dish. In order to be allowed to eat the high calorie dish, he must not have eaten the previous ...
38 views

### Josephus Problem - A faster Solution

I came through Josephus problem a little while ago. Problem is stated as follows : "People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and ...
38 views

37 views

### What is the formal justification for the correctness of the second formulation of rod cutting DP solution

CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference. Define $r_j$ to be the optimal way to cut a rod ...
40 views

### Orderability of Belief States in a POMDP?

Consider a POMDP with integer states $1,2,\ldots,N$, where $N$ is finite. We thus have a complete order over the states. It seems reasonable to think that belief states for this POMDP may be ...
24 views

### Does Optimal Substructure implies Convexity and vice versa?

In undergraduate CS, Dynamic Programming problems are often related to Overlapping Optimal Substructure (https://en.wikipedia.org/wiki/Optimal_substructure). Dynamic Programming is also often used in ...
43 views

### Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?

At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure ...
205 views

### Cutting yarn into integer-length pieces to maximize profit based on known prices for each length

My classmates and I were working on a problem on our introduction to algorithms homework, but we are having a lot of trouble wrapping our heads around it. Below is the problem: We are given a ...
56 views

### Is it possible to solve the coin denomination problem using a 1-D array?

In an algorithm book it said that to solve the coin denomination problem via Dynamic Programming approach a 2-D array is needed: Exercises 8.4 #9 Is it not possible to do this using a 1-D array. I ...
32 views

### Shuffled Strings Dynamic Programming [closed]

So I have this question: A shuffle of two strings X and Y is formed by interspersing the characters into a new string, keeping the characters of X and Y in the same order. Example would be ...
111 views

107 views

### Dijkstra's algorithm to compute shortest paths using k edges?

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ ...
806 views

### Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
99 views

### Finding a maximal set of nonintersecting line segments in a unit circle

Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning ...
41 views

### Travelling plan between two places

There is a class of DP related problems where you have a set of consecutive steps, say $1 \ldots n$, and two places e.g. $A$ and $B$. At each step $i$ there are two choices: stay where you are or ...
79 views