Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
0
votes
0answers
45 views
What is the dynamic programming pseudo code solution for a binary Markovian sequence?
The Problem
I wrote up my own pseudo code and implemented it in Python and got only 70% accuracy for N = 300 and p = 60%. The lecture notes implied I should get near perfect accuracy for similar $N$ ...
0
votes
2answers
33 views
Understanding algorithm for maximum sum of non-consecutive elements
There is a well-known problem in CS of finding the maximum sum of non-consecutive integers in a list. There is even an SO post about how to solve it:
https://stackoverflow.com/questions/4487438/...
2
votes
0answers
38 views
Sequence matching
Let $T$ and $P$ be respectively two sequences $t_1, · · · , t_n$ and $p_1, · · · , p_k$ of characters such that $k ≤ n$. The characters range over a finite alphabet Σ. With each position of $T$, we ...
0
votes
1answer
34 views
Divide an array into two sub arrays such that their sums are equal and possibly maximum
Given an array A, we should partition A into two subarrays whose sums are equal, and that maximizes this sum. We are free to omit items from the subarrays.
For example, ...
3
votes
1answer
32 views
Length of longest arithmetic progression in an array
I was reading an article on Longest Arithmetic Progression. The solution given has S(n)=$O(n^2)$. Can't I solve it in $O(1)$ space? To find the three elements, we first fix an element as middle ...
0
votes
0answers
22 views
Extended stars and bars approach using dynamic programming
If we have an equation with N variables of the form x1 + x2 + x3 +...+ xN with sum S, and upper and lower bounds for each of the N variables, is it possible to find the number of integer solutions (...
0
votes
1answer
26 views
Is deep learning appropriate to approximate dynamic programming problems?
I have a problem which can be completely solved using dynamic programming, but in a very intractable way (On^4, where n is around 1000). I won't get into the details of the problem since it's a bit ...
1
vote
1answer
26 views
what is the significance of the word “Sub-problems” in Greedy Method?
With respect to Dynamic Programming we make a statement that :
Greedy algorithm have a local choice of the sub-problems whereas
Dynamic programming would solve the all sub-problems and then ...
0
votes
1answer
29 views
Can Tug of war problem be solved by DP or greedy approach?
For problem explanation: https://www.geeksforgeeks.org/tug-of-war/
I know the exponential solution to the problem, but can it be improved by greedy or DP approach. If yes then please explain the ...
0
votes
0answers
15 views
How can I solve it (modification of famous robot travelling problem)?
Imagine you have to solve this question (+ you have obstacles, i.e. walls), but you're allowed to move in any of 4 directions (not just 2: down and right). How can you solve it? I'm struggling to ...
1
vote
1answer
17 views
Marginalise edge weights on graph
I have a directed acyclic graph with a score on each edge. The score of a path is defined to be the sum of the scores on the edges along this path. The probability of a path is the score of such a ...
0
votes
0answers
15 views
How can I find worst time complexity for a Regular Expression problem?
I am not looking for the complexity of following algorithm but rather how to think about the problem and calculate complexity of a given solution?
One way is to perhaps use The Master Method for ...
0
votes
1answer
35 views
Solve longest common subsequence in a non dynamic programming way? [closed]
I am working on the longest common subsequence (LCS) problem while learning dynamic programming. Below is the Java code I created to solve the problem, which is not dynamic programming as far as I ...
0
votes
0answers
41 views
How to understand the Bellman Equation in plain English terms?
So on my course we're dealing with a more basic, simple varition of the Bellman Equation.
V(S) = max a(R(s,a)+yV(s'))
As far as I can tell...
V(S) = Value of a state
max a = Maximum over all ...
0
votes
1answer
33 views
Egg dropping puzzle - clarification of problem statement
I was trying to understand the egg dropping puzzle. The problem objective is:
What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst ...
0
votes
0answers
13 views
Correctness of Memoized 0-1 Knapsack solution with item limit
I came across this question and its solution: Variant of the knapsack problem
The reason I'm asking this separately is I have understood their solution, however, being new to Dynamic Programming, I ...
0
votes
0answers
15 views
How to determine whether a set can be divided into two subsets of same sum?
I was trying to solve the problem mentioned above. I went through some resources of the problem and they all say that if the sum of the set is odd, then we cannot partition the set into two subsets. ...
3
votes
1answer
173 views
What is the complexity of comparing point sequences?
Given two sorted arrays of floating point numbers $X$ and $Y$, we can define the S-distance as follows. The S-distance is defined as the minimum cost associated with the transformation of one point ...
0
votes
0answers
18 views
Get count of longest zigzag sub-sequences
I know how to get longest zigzag sub-sequence and length of it. There are several methods available for that. But some times there are many sub-sequences available which have same length. How to ...
0
votes
1answer
21 views
Minimise given size using dynamic programming
Given numbers $0<x_1<x_2< \dots<x_{n^2}<1,$ for every subset of $n$ of them $x_{i_1}<x_{i_2}< \dots<x_{i_n},$ let us consider the size: $$\max\{x_{i_1}, x_{i_2}-x_{i_1}, x_{i_3}...
0
votes
0answers
15 views
Relation between Q-learning and value iteration
Assume that Q-learning algorithm has already converged. Then can I say
$$
Q(s,a)=\mathbb{E}^{(s,a)}[R(s,a)] +\mathbb{E}^{\mathit{Pol}^*} [\sum\limits_{n=1}^{\infty} \gamma^n~ R(S_n,Pol^*(S_n))|S_1=s']
...
0
votes
2answers
93 views
Calculate the number of trailing zeros in equation f(n) = f(n-1) * f(n-2) where f(0) and f(1) are any given arbitary numbers
This question is doable if you can calculate the number by multiplying f(n-1) and f(n-2).
Is it possible to do this question if we entirely want to skip ...
0
votes
0answers
34 views
stabilizing Q-Learning
I have this issue with Q-Learning that whenever I run it, it returns a different Q value for a certain state-action pair. Although, I am using decaying learning rate (e.g. 1/(time+1)) and gamma=0.99. ...
0
votes
1answer
20 views
Print (not count) all possible path classic climbing stair problem)
I came across this classic question and found may many solution to it. for loop and DP/ reclusive + memorization.
Also found a twisted version of the questions asking to print all possible path ...
3
votes
1answer
67 views
Time Complexity: Intuition for Recursive Algorithm
I decide to learn more about dynamic programming, so I started reading the Dynamic Programming chapter from the CLSR book.
The first example problem presented there is Rod Cutting (15.1). Given a rod ...
0
votes
1answer
35 views
Build all valid parenthesis in polynomial time
Given some binary operator $\otimes : X\times X\to X,$ and list $x_1,\dots,x_n$ where $x_i\in X,$ can all possible expressions in $\otimes$ be computed within a number of operator applications ...
0
votes
1answer
59 views
Prove Recursive formula (Dynamic programming) N(C,i)
I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following ...
0
votes
0answers
24 views
Q-Learning Error Bounds
I have searched a lot for this, but apparently there is no result on calculating any bound on the error $||Q-Q^*||$ when I stop Q-learning after say $N$ iterations ($Q$ is the vector of Q-values at ...
1
vote
0answers
103 views
k-way set partition problem--dynamic programming solution
I was reading up on the set partition problem on this site of Wikipedia: https://en.m.wikipedia.org/wiki/Partition_problem
Among other things, they present a DP approach to solving the equal subset ...
0
votes
3answers
48 views
Fibonacci Series with Dynamic Programming
We can compute Fibonacci numbers by means of dynamic programming approach. If we do not store intermediate solutions, we cannot use them for future necessities. In this case, asymptotic complexity ...
0
votes
0answers
18 views
Determining epsilon for knapsack problem solved with FPTAS
I want to solve the knapsack problem with FPTAS and two parameters $\varepsilon_1 <\varepsilon_2$ .
I know that as long as we choose smaller epsilon we get more tight approximation but we pay with ...
0
votes
0answers
85 views
Longest increasing subsequence (Dynamic Programming)
I have written the following recursive structure for finding length of longest increasing subsequence.
...
0
votes
0answers
54 views
How to correctly count subsets using dynamic programming
I'm trying to solve this problem: UVa 1734 - Numbered Cards.
You have $N$ cards and each has an unique number between $1$ and $N$ written on it. In how many ways can you select a non-empty subset ...
1
vote
1answer
18 views
A “packing” optimisation problem with application in dynamic programming
I'm interested in the following problem :
Input : an integer $n$, and $k$ increasing functions $f_i:\mathbb{N}\rightarrow\mathbb{R}$, such that $f_i(0)=0$ for all $1\le i \le k$
Output : $k$ ...
2
votes
1answer
47 views
Understanding Bellman-Ford and Floyd-Warshall Algorithms as Dynamic Programming Algorithms
From my understanding, a problem amenable to a dynamic programming solution has these two properties:
Overlapping Subproblems — The same subcase (a subsection of the overall problem) keeps ...
1
vote
0answers
20 views
Comparison of time-dependent traveling salesman heuristics
I'm looking into implementing a heuristic for the time-dependent traveling traveling salesman problem (TDTSP) that completes in a certain amount of time.
There are a wide range of possible ways to ...
0
votes
0answers
31 views
Maximize picks from a list when you can only choose 2 items from every 7 items
What would be an O(n) algorithm to maximize picks from a list when you can only choose 2 items from every 7 items. I've been thinking about this problem for a few days and I can't figure out an answer....
3
votes
1answer
71 views
Finding the length of the longest increasing path in a matrix
Problem:
Given a matrix, find the length of the longest increasing path. We can move up, down, left, or right.
Example:
$$
\begin{pmatrix}
1&2&3&4\\2&2&3&4\\3&2&3&...
1
vote
1answer
69 views
Variant of the knapsack problem and box stacking
I'm facing a problem described as follows:
You are given a set of $n$ types of rectangular 3-D boxes, where the i-th box has height $h_i$, width $w_i$, depth $d_i$ and value $v_i$. You want to create ...
0
votes
0answers
21 views
Dynamic programming - Find shortest sequence of moves in a grid of letters to type a sentence
We have a keyboard-like grid containing letters or other symbols.
We also have a sentence that we would like to write with the grid.
At the beginning the cursor points at the symbol in the top letf ...
0
votes
0answers
31 views
Gas Station Problem Variation
My friend challenged me with this question. I've enjoyed two weeks with ocassional problem-solving sessions but it became such bug in my head that I needed to sign up :)
We have:
car with fuel ...
1
vote
0answers
73 views
A knapsack problem with variable knapsack size
I've come across this problem and I can't find a decent DP solution for it.
Given an initial amount of money and a bunch of items to buy (where each item has a 'value' and 'price' assigned to it), ...
2
votes
1answer
29 views
Online set cover variant? Routing of requests
We have a set of $k$ path requests from $src$ to $dst$ that arrive sequentially.
Each request may have multiple paths, but can choose only one of them. For example, in the Figure shown, there are ...
0
votes
1answer
27 views
Transform 2D range query matrix into segment tree to make memory usage lower
Let's say we have given matrix $N\cdot N$, with zeros and ones only at $P$ position at it. We want to implement queries $q(x_1, y_1, x_2, y_2)$ which will return the number of ones in the sub-...
0
votes
0answers
28 views
Algorithm to check if exists a valid streaming sequence in O(n)?
Given n packets, each packet has b(i) bits and takes t(i) seconds to stream. We cannot send 2 packets at the same time. Given r > 0 and for each t > 0, the total number of bits we send from second 0 ...
0
votes
0answers
50 views
Activity planning problem
Given a sequence of N activity durations, the time P of pause between activities, and D, the length of a day (there are no breaks between days, only between activities in a day), what is the minimum ...
1
vote
1answer
355 views
Number of possible sequence partitioning
Given a sequence of 1 and 0 elements, what is the number of possible partitioning of the sequence in sub-sequences (not necessarily consecutive elements, and any number of sub-sequences are allowed) ...
1
vote
0answers
56 views
Are there Dynamic programming speedups for $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$
I am wondering if there are dynamic programming speedups for the minimization problem $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$. Now I understand that its highly unlikely that such thing would exist for ...
1
vote
1answer
79 views
Understanding tables in Dynamic programming
I came across this problem that asks you to implement a regular expression matcher with support for '.' and '*', where
'.' Matches any single character.
'*' Matches zero or more of the preceding ...
-1
votes
1answer
119 views
Knapsack progblem with two conditions
I want to create an algorighm (with dynamic programing) similar to 1/0 knapsack problem but, I have one extra condition isVegetable or isFruit.
Assume we have N food items where we know ...
