Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
2
votes
0answers
21 views
Weighted Sorting Algorithm
Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation.
Is there any ...
1
vote
1answer
27 views
Can the compiler convert recursive algorithm into a dynamic programming
So I was going through the idea behind dynamic programming (memoization), and thought of this question.
Can a compiler convert any recursion into a table filling DP solution, of course given the ...
0
votes
1answer
23 views
Optimizing the problem
I have a recurrence relation:
f(a,b) = f(a-1,b)+f(a-2,b-1)+f(a-1,b-1)
with conditions:
f(0,0)=1, f(a,0)=1, f(0,a)=0, f(x,1)=2*x
where the constraints: 1<=a<...
0
votes
0answers
13 views
Reach the nth stair using step a-b while some stairs are broken
Description
A person is standing below at a staircase having $N$ steps. Considering he can take a leap of between $a\geq1$ and $b\leq N$ steps at a time. In the meanwhile, some of the stairs are ...
0
votes
1answer
13 views
Finding recurrence relations for dynamic programming algorithms
Consider a function $f(n)$ whose definition requires one to compute $f(1),f(2),..f(n-1)$ in order to evaluate $f(n)$. Suppose that some algorithm to compute $f(n)$ has time complexity that is given by ...
0
votes
0answers
26 views
Modifying this Geeksforgeeks code help
I came across this article on Geeksforgeeks - https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/
I then thought of implementing this with some other constraints. ...
1
vote
1answer
24 views
FInding the combination with the least number of elements from and array of integers, given an integer sum
I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
1
vote
1answer
51 views
Minimum Number of Integers From a List that Add up to N (Dynamic Programming)
A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically:
Given a list $L$ of $K$ integers, $[a_1, a_2, ... , a_k$], where ...
0
votes
1answer
14 views
Maximum trailing zeros of the path
Problems:
A table with $n$ rows and $m$ columns is filled with number from $1$ to $100$ (duplication allowed). The player starts at $(1, 1)$. He can only move right or down. The goal is to reach $(n, ...
1
vote
1answer
49 views
How does the problem of “Scheduling to Minimize Lateness” exhibit optimal substructure?
The problem of "Scheduling to Minimize Lateness" is as follows (Section 4.2 of the book "Algorithm Design" by Jon Kleinberg and Eva Tardos):
Input: A finite set $J = {J_1, J_2, \ldots, J_n}$ of $n$ ...
1
vote
1answer
17 views
Graph Traversal Solutions for “Find all unique paths” Problem
I was studying the grid problem where a robot is at the top left position and wants to go to the bottom right position and you need to return the number of unique paths it can take to get there with ...
1
vote
1answer
28 views
Optimal substructure and dynamic programming for a variant of the rod cutting problem
The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.
Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the ...
2
votes
1answer
33 views
No. of subsets whose element multiply to give a square number
I have been given an array whose elements lie between [1,70] and the size of array [1,10^5].
I have to find the total number of subsets whose all elements multiply to give a perfect square number.
...
2
votes
1answer
26 views
Count number of the ways to fill a N-lengthed binary string
From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more ...
2
votes
1answer
71 views
Maximum Equal Sum K Subsequences
Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum.
Example:
...
1
vote
1answer
19 views
How to implement recursive solution with large number or parameterized possible next steps
I was looking at a recursive solution for the robot on a grid problem which basically states that there is a robot on the top left corner on a grid and you are supposed to find a path to the bottom ...
1
vote
1answer
35 views
Request for examples to show various types of subproblems in dynamic programming
Chapter 6 of "Algorithms" by Dasgupta, Papadimitriou, and Vazirani summarizes four types of subproblems that are quite common in dynamic programming. They are
prefix/postfix of a string/sequence/...
0
votes
0answers
26 views
Text alignment algorithm for word misspelling and rearrangement
I'm working on a project involving OCR, and I'm writing a post-processor using which the user corrects the OCR output using a text editor.
The OCR algorithm returns a list of "Detected Words", each ...
1
vote
1answer
21 views
Recursive DP vs Graph Traversal solutions to path-based problems
I am studying some algorithms interview questions and I am seeing many path-based questions like "if a robot is at the top left of a grid and can only move down or to the right, how many paths can ...
1
vote
1answer
164 views
Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value
GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T.
This question is a simplification of ...
0
votes
0answers
78 views
Which dynamic programming algorithm can be used to solve this variation of TSP problem?
A company has been appointed to look at building floating roads
connecting all cities of the Kingdom. The adjacent cities of the
kingdom are connected by a perimeter road (P) and the other cities
...
0
votes
0answers
51 views
Number of ways to form a wooden square with 6 wooden bars from a given set?
Given a set of N unbreakable wooden bars, the ith wooden bar has side-length of Ai.
How many ways are there to form a square by using exactly 6 bars from the given set? Two ways are considered ...
1
vote
0answers
55 views
Parenthesizing a product using dynamic programming
Here is a problem that I've been given to solve in time $O(n^2|\Sigma|)$.
Given an alphabet $\Sigma$ and the product of every two elements in this alphabet (i.e., an arbitrary mapping $\cdot\colon ...
0
votes
0answers
48 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
38 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/...
3
votes
0answers
44 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
49 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
50 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
24 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 (...
1
vote
1answer
28 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
31 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
46 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 ...
2
votes
1answer
20 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
33 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
50 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
43 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
50 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 ...
3
votes
1answer
174 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 ...
1
vote
1answer
32 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
23 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
144 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
37 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
91 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
36 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
89 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
25 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
288 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 ...
