The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
5answers
403 views

Find value of f(2013)?

Given a function $f(x)$ such that: $f(1) + f(2) + f(3)+\cdots+f(n) = n^2f(n)$ Find the value of $f(2013)$. It is given that $f(1) = 2014$. I tried attempting the question as a bottom-up DP, but ...
0
votes
0answers
41 views

What kind of an optimisation problem am I dealing with? [on hold]

I have a connected graph made up of $x$ vertices. Each vertex has a probability $p$. I want to determine the total probability in traversing as many vertices as possible, Edges have a certain cost to ...
0
votes
2answers
37 views

Dynamic programming:Making a Change

I'm practicing problems on dynamic programming.The problem is as follows: You are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so ...
0
votes
0answers
6 views

Dinamic programming for sum of two largest values from a Uniform parent

I must find a recursion formula to find the sum of two largest values from a Uniform parent [0,1]. I need dinamic programming but I don't know how to organize it.
0
votes
0answers
44 views

Dynamic programming for optimal maximum and optimal minimum

We have a sequence of $a_i$ and a choosing rule that is take the first number $x_t\ge a_t$. The definition is = $$ min\{ t|t \in \{ 1,2,\cdots,n\}\,\,,\,\, x_t\ge a_t\}$$ The sequence $a_i$ is ...
0
votes
1answer
24 views

What is the formal name of this problem?

I'm doing an assignment and I'm having trouble with this question, could anyone give me the formal name of the problem described so I can research it better? The task is to move a player along a path ...
1
vote
2answers
121 views

Algorithm: Scheduling of Overlapping Intervals

I'm reviewing algorithms, and I've come across this problem. At first, it seemed like an interval scheduling problem to me, but now I think it is a dynamic programming problem. I'm not sure how to ...
1
vote
1answer
77 views

Three dynamic programming techniques

I've noticed three terms that come up when I look at dynamic programming exercises. Binary choice - seen it in a weighted interval scheduling problem. Multiway choice - seen in a segmented least ...
0
votes
0answers
17 views

Find an explicit expression for f(y)

Consider the function $$f(y) = \min \Bigg \{ \int_0^{\log 2}[x^\prime (t)^2 + x (t)^2]dt : x(0) = 1, x(\log 2) = y \Bigg \}.$$ Find an explicit expression for $f(y)$ and use it to determine the ...
0
votes
1answer
17 views

Finding the optimal solution

Find the optimal solution of the problem $$\min \Bigg \{ \int_0^1 [x^\prime (t)^2 + 2x(t)^2]e^t dt : x(0) = 0, x(1) = e - e^{-2}\Bigg \}$$ and the value of the minimum. Not sure how to approach this ...
2
votes
0answers
62 views

A Strange Algorithm on Processor [closed]

We have n processes, each with a predetermined start and end time. We want to use the ...
0
votes
0answers
31 views

Can every optimization problem that can be solved by a greedy algorithm be solved using dynamic programming? Why, why not?

In other terms, is the set of optimization problems solvable using greedy algorithms contained fully within the set of optimization problems solvable by dynamic programming?
0
votes
1answer
48 views

Understanding Mathematical Symbols in Algorithms

Just a quick question here. I am working on an assignment for algorithms involving dynamic programming. Don't worry, this isn't a question about my assignment, just a question about understanding a ...
1
vote
1answer
49 views

How to convert mathematical programming problem to dynamic programming problem

Do not know how to approach this problem. The task is to convert the problem of mathematical programming: $\max(\prod_{i=1}^nx_i)$ $\sum_{i=1}^na_ix_i\leq c$ $c \gt 0, a_i \gt 0$ into a problem ...
1
vote
1answer
46 views

Dynamic Programming - how to minimize sum of distances

Let's assume that we're given the num[N], an array of N positive integers in an ascending order. For instance, let's assume that N=10, and num[N] is the following: 1 2 3 6 7 9 11 22 44 50 Let ...
1
vote
0answers
16 views

Finding groups with minimum mean deviation

Is there any algorithm that groups consecutive elements in an array that gives the minimum mean deviation. For example we are given an array a=[1,2,3,4,8,2,3,5] There can be many "consecutive" ...
0
votes
0answers
26 views

Seam Carving - Energy functions. How do they work?

I have been taking an interesting in dynamic programming and more specifically Seam Carving. For those who are not aware what this is, please look here and for some more detailed information here. If ...
1
vote
1answer
43 views

Number of strings of size $k$ that do not have 'ab'

Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab' Find strings, of size $k$ is in $L$ ($L_k$) Consider $A_k$ (strings of size $k$ that end in $a$) ...
0
votes
1answer
37 views

What is the system equation $f$ in Hamilton equation in $H=g+p^Tf$?

I am studying the Donald Kirk's book Introduction to Dynamic Programming. Suppose some integral $\int g dt$ that must be minimised. Then you are given some constraints. Hamilton equation is $H=g+p^T ...
0
votes
1answer
75 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
1
vote
1answer
65 views

Cost of conversion of string $A$ to string $B$

We are given $2$ strings $A=[1 \dots m]$ and $B[1 \dots n]$ and the following $3$ operations are allowed: Insert a charachter,with cost $c_i$ Delete a character,with cost $c_d$ Replace a ...
1
vote
1answer
63 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
3
votes
0answers
135 views

Finding optimal velocity profile using Dynamic Programming

This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here. The main problem for me is: How to introduce the time ...
0
votes
2answers
119 views

Longest Common Subsequence

Let $X=<x_1,x_2,…,x_m>$ and $Y=<y_1,y_2,…,y_n>$ be sequences and let $Z=<z_1,z_2,…,z_k>$ a longest common subsequence (LCS) of $X$ and $Y$.Then: If $x_m=y_n$,then $z_k=x_m=y_n$ and ...
0
votes
5answers
103 views

Number of ways in which $2010$ can be formed using $2,5,10$.

We can form $10$ using $2,5,10$ in $3$ ways. In how many ways can we form $2010(201*10)$. My teacher mentioned. $202*203/2$ I cannot figure out how. I also saw a DP method for finding number of ways ...
1
vote
2answers
70 views

number of combinations of selecting 1 element each from 3 sets..

Suppose we have 3 sets A=(a1,a2,...) B=(b1,b2,....) and C=(c1,c2,...) which may contain comman elements that is element present in set A may present in set B or in Set C,element in set B may be there ...
0
votes
0answers
43 views

Total number of subsets

I am trying to solve this hackerrank problem https://www.hackerrank.com/contests/101jul14/challenges/colorful-polygon. Not able to understand the editorial. Can some explain how to solve it using ...
1
vote
0answers
67 views

Traverse resultant 2d array after integer partition

I have used the solution of integer partitioning using dynamic programming explained in this post and in this article. Following is the resultant matrix when N is equal to 6: $$\begin{bmatrix} 1 ...
0
votes
2answers
58 views

Find point in 3D plane

I have four points in a 3D space, example: $$(0,0,1),\ (1,0,1),\ (1,0,2)\ \mbox{and}\ (0,0,2).$$ Then I have a 2D position on that square plane: $$x = 0.5,\ y = 0.5.$$ I need to find out the 3D ...
2
votes
0answers
85 views

Building Minimum warehouses

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. ...
1
vote
0answers
27 views

Markov decision processes with action space only revealed at point of decision.

I have a problem which looks like a finite horizon Markov decision process, except the actions space at each time is revealed at the decision making point. There is no way to know before hand the ...
2
votes
3answers
39 views

Performing matrix chain multiplication by hand

I'm trying to gain intuition for writing a matrix chain multiplication algorithm by working through a few problems by hand. I see plenty of worked-through solutions on sets of three or four solutions, ...
2
votes
1answer
215 views

Dynamic Programming: Stock Exercise

I'm having a trouble dealing with this problem: Since future market prices, and the effect of large sales on these prices, are very hard to predict, brokerage firms use models of the market to ...
4
votes
1answer
97 views

Difference between Variation of Calculus problems and Control Theory problems?

Variation of Calculus seems to have problems without the control with variables such as state and time. Then again Control Theory problems seems to have problems with one extra variable that is ...
1
vote
0answers
32 views

How are Hamilton function and Hamilton-Jacobian-Bellman function related to each other?

I am trying to understand the solution to the problem 2 here that uses the Hamilton conditions for the HJB. I don't understand how the Hamilton conditions can be used with the ...
0
votes
1answer
75 views

hint to approach this question

2 teams play in total During the course of the game, each team gets points, and thus increases its score by 1. The initial score is 0 for both teams. The game ends when One of the teams gets 25 ...
0
votes
1answer
49 views

Count how many arrays of a specific type exist - O(N) Dynamic Programming

Consider an array of N + 2 binary digits (1 and 0), which contains at least one '1' and three '0'. The last and first digit of the array is 0. Given two numbers, let's say p and q, determine how many ...
0
votes
0answers
66 views

Recurrence Relation for the checkerboard problem

Im trying to come up with an accurate recurrence relation for the checkerboard problem given here (http://www.8bitavenue.com/2011/12/dynamic-programming-moving-on-a-checkerboard/). A recursive ...
2
votes
0answers
50 views

A Dynamic Programming Question

$\underline{\text{Household Sector:}}$ The household comprises of a single agent whose objective function is to maximize the expected value of his lifetime utility which is a function of ...
0
votes
0answers
99 views

Dynamic programming: optimal stopping problem

I am studying the optimal stopping problem. The probability setup is as follows: Assume space $\Omega=\{\omega\in C([0,T];R)|\ \omega_0 =0\}$. Denote $B$ as the canonical process and ...
0
votes
0answers
22 views

If the state variable retains all the history, is it still dynamic programming?

Let $X$ be a stochastic process observed over 100 periods. At each period, I seek the optimal control $u_t$ so as to minimize the total cost $$ V= \sum_{t=0}^{100} f\left(X_t,u_t\left(X_t, ...
1
vote
0answers
67 views

Dynamic Programming Question

A train is given to two children as a gift. A train consists of a sequence of cars connected in a single line. There is an even number of cars, and the two children wish to divide them up. They do ...
0
votes
0answers
158 views

The difference between Dynamic Optimization, Stochastic Programming, Optimal control and Markov Decision Processes

I've seen the following terms thrown around somewhat interchangeably, and I'm confused. What are the distinctions between them, and what are some representative problems that each deals with? ...
0
votes
0answers
77 views

Inventory Control using Dynamic Programming

I am trying to solve a traditional inventory control stochastic dynamic programming problem where \begin{align} x_{k+1} &= x_k + u_k - w_k\\ w_{N-1} &= \begin{cases} 0 &\text{w.p. } ...
1
vote
2answers
42 views

Another Grid Problem

There is a maze of size N*M, consisting of unit blocks. At the start Alice has K percentage of energy. Now Alice start from 1 st row and move towards N th row. From the present block she can move to a ...
1
vote
1answer
249 views

Reducing the maximum euclidean distance

This question comes from the HackerRank's "20/20 Hack February" contest which has now ended (problem link). There are N bikers present in a city (shaped as a grid) having M bikes. All the bikers ...
0
votes
0answers
34 views

Problems with understanding a few first order conditions in a Bellman Equation

I apologize for linking rather than posting the reference for my question, but it would take too long to write it in Latex here. Here it is a paper that I've been reading -- I did not understand the ...
3
votes
2answers
133 views

Flip the bulbs in minimum number of moves

We are given a $n \times m$ rectangular matrix in which every cell there is a light bulb, together with the information whether the bulb is ON or OFF. Now i am required to switch OFF all the bulbs ...
2
votes
1answer
73 views

Please explain why the below algorithm has n*m subproblems rather than 2(n+m-1) subprobems.

I am providing the solution as well which I found on the web. I don't understand why it says at the end that there are n*m subproblems. Question: For bit strings X = x1 . . . xm, Y = y1 . . . yn ...
0
votes
3answers
105 views

A dynamic dice game

I learned the following dice game from another forum. It was not solved there. The dice game is as follows. Toss 6 dice. Each toss you can keep one or more up to the total number of dice tossed. You ...