The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
10 views

The following code uses the __interrupt as the interrupt service routine. How to comment on the below code. [on hold]

include define PI 3.14 __interrupt double compute_area(double radius) { double area=PI*radius*radius; printf("\narea=%f",area); return area; }
0
votes
0answers
40 views

Number of Subsets in the given list

We have a list of N elements, and a number S, how many possible number of subsets that the sum of elements in the subset is equal to S? Ex : List = [1 2 -1 4 5] S = 9 Possible subsets are : 2 ([5, ...
0
votes
1answer
39 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
26 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
29 views

A Dynamic Programming Question

Hi I'm trying to solve an economic problem but I haven' learned dynamic programming before. Need to derive the first order conditions. I'd really appreciate if you could lend me your brain for a ...
0
votes
0answers
29 views

Coin-change problems; c++ [migrated]

I'm working on a coin change program. Make change using fewest number of coins. I'm attempting dynamic programming and i may be misunderstanding the algorithm. When i compile, the debug assertion ...
0
votes
0answers
140 views

Query Preprocessing

Moderator Note: This is a current contest question on codechef.com. I have array of x integers and i need to answer y queries. Each query have 3 integers ( Number, Left index, Right Index). I ...
0
votes
0answers
19 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 ...
-1
votes
0answers
13 views

Discret DP formulation of train ticket

How can we solve by dp a train tickets selling in a finite horizon $i$ ? we have T tickets to sell, D days, and p $i$ : day $a_i$ : ticket to sell $c_i$ : tickets sold $k_i$ : price ...
0
votes
0answers
16 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
46 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
46 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
48 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
38 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
194 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
18 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
98 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
31 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
65 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 ...
2
votes
2answers
101 views

Internet problem solving contest question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion. ...
0
votes
0answers
20 views

Discrete Optimal Control and Monotone Policies

Let $x=(x1,x2) \in \mathbb{N}^2$ be the state, $u$ be the control, and the dynamics be given by $x^{(k+1)} = f(x^{(k)},u^{(k)},w^{(k)})$ where $w^{(k)}$ is an IID noise source. For some stage cost ...
2
votes
0answers
27 views

Dynamic programming and Lagrange multipliers

The problem is to solve dynamic programming problem $$\sum_{t=1}^T\left(\frac{t^3}{3}+\frac{t^2}{2}\right)a_t^2 \to \max$$ where $\sum_{t=1}^T a_t =c$, and $a_t$ is assumed to be $\geq 0$. It is ...
2
votes
0answers
153 views

Maximum subarray problem

Given a 2d array N*M made of only 1's and 0's . I need to find a maximum subarray(square or rectangle) between two rows of the given 2d array which has all ones inside it. I need to find count of ones ...
2
votes
0answers
162 views

Maximum Area of rectangle without any monsters

Moderator's note: the lock on this question from Jan 6, 2013 until Jan 13, 2013 is due to its being an active contest question on CodeChef. The question will be unlocked automatically after the end ...
0
votes
0answers
38 views

Open loop minimization for a inventory control system

I have read in a book (dynamic programming and optimal control by Bertsekas) that in case of inventory control system, with open loop minimization of the cost, we select all orders $u_0, \dots, ...
0
votes
1answer
125 views

Compute how to subdivide an n m marble slab to maximize your profit

You have mined a large slab of marble from your quarry. For simplicity, suppose the marble slab is a rectangle measuring n inches in height and m inches in width. You want to cut the slab into smaller ...
0
votes
0answers
40 views

A basic doubt on dynamic programming

In a book on dynamic programming the first paragraph of the introductory chapter says that "this book deals with situations where decisions are made in stages. The outcome of each decision is not ...
0
votes
0answers
12 views

How to optimize consumption and investment stream?

An individual with wealth W (but no labor income) can invest in a risk-free bond with rate of return R and a risky stock portfolio with a random rate of return $\hat Z$ that is IID with a lognormal ...
0
votes
1answer
69 views

Shortest path problem-minimal cost

Given a set of m things (1,2,...,m), we want to group them in clusters that contain adjacent things. For each cluster there is a cost $c_{ij}$. We are looking for the grouping in clusters so that the ...
0
votes
1answer
41 views

Help with probability formula in programming problem

I am trying to solve this dynamic programming problem using probabilities. I know how the recurrence for it should look but I have problems using a probability formula. I have the next case: In a ...
0
votes
0answers
75 views

Dynamic programming algorithm for GCD?

I can't seem to find a clear answer on this. I'm inclined to believe that there is not a DP solution for GCD, given the lack of information so far in my searches on the subject. I suppose that in ...
0
votes
0answers
321 views

Splitting an array into two subarrays with minimal sum

My question is if given an array,we have to split that into two sub-arrays such that the absolute difference between the sum of the two arrays is minimum with a condition that the difference between ...
0
votes
0answers
64 views

Minimum cost problem

I have been given $n$ points on a $2d$ plane. In terms of their $(x,y)$ coordinates. Now suppose I have to set, say firms, at these positions and the cost for building the first one is zero. For every ...
1
vote
1answer
98 views

Finding an optimal schedule [Dynamic Programming]

I'm reading through an algorithm textbook and I've come across yet another problem that I'm stuck on. I'm looking for some help solving it and if anyone could provide some similar, already-existing, ...
0
votes
1answer
174 views

Finding the longest path in a tree

Give a linear time algorithm that, given an undirected tree T = (V,E) with edges weights w, returns the weight of the heaviest path in T. This is basically asking to do the exact opposite of what the ...
2
votes
0answers
35 views

Minimize $\sum_{k=0}^3(x_k^2 + u_k^2)$

Together with some friend we are making exercises containing the Bellman equation and we faced a pretty difficult one: $x_{k+1} = x_k + u_k$ for $k = 0,1,2,3$, with starting state $x_0 = 5$ and ...
4
votes
0answers
26 views

Nonlinear optimisation of Expectation

I am preparing for my exams and I can't get my head around the following question. I know there exists a general method for solving these problems but I don't know where to start. I would greatly ...
2
votes
2answers
56 views

$\sum\limits_{k=0}^{19} \sqrt{1+u_k^2} \rightarrow \min$

Solve $\sum\limits_{k=0}^{19} \sqrt{1+u_k^2} \rightarrow \min$, such that $x_0 = 0, x_{20} = 5$ and $x_{k+1} - x_k = u_k$. I think I know how to solve problems like these recursively, but I ...
2
votes
1answer
104 views

Stochastic dynamic programming

I am making some homework exercises at the moment and I was wondering if what I did in the following exercise was correct. PROBLEM Solve $E(\sum_{k=0}^{N-1}(1-u_k)X_k + X_N) \rightarrow \max$, ...
0
votes
0answers
64 views

Bellman equation problem

I am making a exercise set about the Bellman Equation and I encountered a question I couldn't understand: Given is the problem $\sum_{k = 0}^{N-1}f(k,x_k,u_k) + \kappa(N,x_N) \rightarrow\min$ ...
0
votes
1answer
64 views

Recurrence Relation for Optimal Card Game Score

I have the following problem where Alice and Bob decide to play a simple card game. At the beginning of the game, $n$ cards are dealt face up in a long row. Each card is worth a different number of ...
1
vote
2answers
44 views

Thief, exponential reward, optimal strategy

A thief robs a house every night. His profit each night is independent of others, and is a random variable with $Exp(1/\lambda)$ distribution. Every night, there is a probability $0<q<1$ that he ...
2
votes
3answers
172 views

Dynamic programming problem

A man is in a room, with $n$ passages leading out. For passage $i$, $i = 1,...,n$, there is probability $p_i$ of escaping, $q_i$ of being killed and $r_i$ of returning to the room, where $p_i + q_i + ...
0
votes
0answers
34 views

How many number of ways are there for getting a special prime?

Definition of special prime : Any integer (+ve, -ve or 0) that is divisible by at least one of the single digit primes (2, 3, 5, 7) is a special prime. Thus -21, -30, 0, 5, 14 etc are special ...
1
vote
0answers
53 views

Find Markov policy that minimizes(maximizes) the expected discounted cost(reward)

It's an exam problem I found online.Here's a link to the pastpaper. The problem is stated as follows. A repairman who services Q facilities moves between location s and location j according to the ...
2
votes
1answer
114 views

Matrix Chain Multiplication Dynamic Equation

I am thinking about the derivation of the following dynamic equation: $$F(n_1,...,n_{k+1};k)=\min_{1<i<k+1}\{n_{i-1}n_i n_{i+1}+F(n_1,...,n_{i-1},n_{i+1},...,n_{k+1};k-1)\}, k=1,...,h$$ Let me ...
2
votes
0answers
64 views

Solving Hamilton-Jacobi-Bellman equations numerically?

I've been told that HJB equations can be solved numerically. I know very little about the subject, could someone provide a couple of comments or a reference (ideally, one that is accessible for a ...
1
vote
1answer
77 views

finding a equation to fit a curve

If I have a set of known values, i.e X Y 0.81300, 4.9900 0.84500, 3.6900 0.86400, 3.0700 0.94000, 1.5000 0.94300, 1.4600 How would I make as accurate a ...
2
votes
2answers
98 views

Why does DP solve a problem in polynomial time whereas brute force is exponential?

I am just learning DP, so maybe this is a noob doubt. I've read (while trying to understand the difference between DP and greedy approach - and I am still not fully clear) that DP goes through all ...
-1
votes
1answer
101 views

How to know when to use Dynamic Programming? [closed]

Given any problem, how do I know whether it is solvable using Dynamic Programming? For example: consider the rod cutting problem. Now, how do I know whether dynamic programming will give me an optimal ...