amusement park scheduling rides using dynamic programming
You arrive at Waldo's World Amusement Park with T minutes remaining until the park closes. The park has n rides and your objective is to complete as many rides as possible before the park closes. (For this problem, taking the same ride twice counts as 2 rides.) You are given a table W such that W(i, t) gives you the waiting time for ride i at time t. For convenience, assume that t is expressed as minutes before the park closes. Ride i itself takes ri minutes and all times are measured in integer minutes.
I tried solving it using a method similar to 0 1 knapsack problem. But the Table W which contains the waiting time for ride i varies wrt to time t. Is it exactly a knapsack plus activity selection combined problem?
1 answer

Would this make any sense? Let
f(t)
represent the most achievable rides at timet
. Then:// Higher t is back in time // since t is how many minutes // before the park closes f(t) = max( // Not taking any ride f(t  1), // Take ride i 1 + f(t  W(i, t)  r_i) ) for all i
See also questions close to this topic

Efficient algorithm for grouping variablelength tuples
I am trying to devise an efficient algorithm for grouping a sequence of tuples of integers of any length, such as:
[(), (1,), (1,1), (1,2), (2,), (2,1,1), (2,1,2), (2,2)]
The grouping rule, in Python for example, is the following:
def tupleSameGroup(tuple1, tuple2): sameGroup = True for index in range(min(len(tuple1), len(tuple2))): if tuple1[index] != tuple2[index]: sameGroup = False return sameGroup
In rough words, if one tuple is a "subset" of another matching from the beginning, they are the same group. An empty tuple is in the same group as any tuple.
Based on this rule, I want my algorithm to produce as output a list of all unique groups of tuples; so a list of list of tuples, where within the inner list the tuples are all in the same group, but between there is a pair that is not. For the above example, the desired output is:
[[(), (1,), (1,1)], [(), (1,), (1,2)], [(), (2,), (2,1,1)], [(), (2,), (2,1,2)], [(), (2,), (2,2)]]
Any help would be much appreciated! Thank you.

Algorithm question: finding next non overlapping interval
Lets say we have a list of interval sorted by start point in ascending order. we want an algorithm to find for each interval, the next nonoverlapping interval with smallest start point.
For example we have list of interval as {(1,5), (2,4), (4, 6),(6, 10)}, for 0th interval (1, 5), the nearest nonoverlapping interval is 3rd interval which is (6, 10), for 1st (2,4) it should be 2nd (4,6). Therefore the desired output is [3, 2, 3, 1].
I can come up with an brute force O(N^2) algorithm which is to do linear scan for each interval. But I think there might exist an O(N) algorithm, anyone know the is there a better solution for this problem?

Datastructure to store database record
I want to store employees record. I don't want to use any external libraries or framework. I am trying to build the data structure from scratch.
There will be three fields,
EmployeeName Age Salary
We also want to query like,
Get all the salary where EmployeeName = "Bill" Get all the EmployeeName where salary > 2000 Get all the Salary where age='50'
I am open to use any language but not any builtin package. What is the recommended datastructure to achieve it ?

Confused about Memoization performance  SICP exercise 3.27
From SICP
Exercise 3.27: Memoization (also called tabulation) is a technique that enables a procedure to record, in a local table, values that have previously been computed. This technique can make a vast difference in the performance of a program. A memoized procedure maintains a table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure is asked to compute a value, it first checks the table to see if the value is already there and, if so, just returns that value. Otherwise, it computes the new value in the ordinary way and stores this in the table. As an example of memoization, recall from 1.2.2 the exponential process for computing Fibonacci numbers:
(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib ( n 1)) (fib ( n 2))))))
The memoized version of the same procedure is
(define memofib (memoize (lambda (n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (memofib ( n 1)) (memofib ( n 2))))))))
where the memoizer is defined as
(define (memoize f) (let ((table (maketable))) (lambda (x) (let ((previouslycomputedresult (lookup x table))) (or previouslycomputedresult (let ((result (f x))) (insert! x result table) result))))))
...
Explain why memofib computes the nth Fibonacci number in a number of steps proportional to N.
The insert! and lookup procedures are defined in the book as follows:
(define (lookup key table) (let ((record (assoc key (cdr table)))) (if record (cdr record) false))) (define (assoc key records) (cond ((null? records) false) ((equal? key (caar records)) (car records)) (else (assoc key (cdr records))))) (define (insert! key value table) (let ((record (assoc key (cdr table)))) (if record (setcdr! record value) (setcdr! table (cons (cons key value) (cdr table))))) 'ok)
Now, assoc has number of steps proportional to n. And since lookup and insert! uses assoc, they both have number of steps proportional to N.
I do not understand how memofib has a number of steps proportional to N. My observations are:
 Due to the definition of the argument to memofib (the lambda which has n as the formal parameter), the table would have mostly ordered keys, And the keys would be looked up in an ordered way. So it is safe to assume any call to lookup would be close to a constant time operation.
 Insert! on the other hand will not be aware that the keys would be added in some order. If a value does not exist in the table, insert! will always scan the whole list, so it would have number of steps proportional to n every time.
 If we have n1 elements in the table and we wish to compute (memofib n), it would have number of steps proportional to n due to insert!
 If we have no keys, then (memofib n) would have number of steps proportional to n^2 due to insert! being called every recursive call to memofib.
If lookup and insert! are constant then it would make sense for memofib to have number of steps proportional to n. But the real number of steps looks like n*(nk) where k are number of keys already in the table.
Am I doing it wrong? What am I missing?

Dynamic programming applied on a recursive algorithm
so bellow is my code for an algorithm using recursive calls. I will not explain what the algorithms exactly does, because i do not think that it is important to know for this question. It basically just calculates the amount of valid paths for a given input n. The algorithm has exponential complexity, so it is really slow for bigger n.
With the current algorithm i am only able to calculate n up to 10 in realistic time, but other people working on the same problem told me that it is possible to get up to 200 with the same recursive approach i took by adding in dynamic programming. So i read into dynamic programming a bit and i think i understood what it is supposed to do. It memorizes previous calculations so you do not have to calculate them again, instead you can just take them out of a list or so.
But i do not understand how i am able to apply that for my code, could anyone help me out or atleast give me a hint?
public class CalculatePaths { static private int n; static private int remainingSteps; // calculates how many steps are left static private int paths = 0; // calculates how many valid paths there are public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("Enter a value for n: "); n = scanner.nextInt(); remainingSteps = 2 * n; move(0, 0, 0, 0, remainingSteps); System.out.println("There are " + paths + " valid paths for n = " + n); } /** * Goes through all paths and calculates the amount of valid paths * Stops if x or y or negative * Stops when all steps were used * A valid path has to meet the following conditions: * 1. There arent any remaning steps left * 2. The xcoordinate has to be 0 * 3. The ycoordinate has to be equal to n */ public static void move(int xDirection, int yDirection, int parentx, int parenty, int remainingSteps) { // calculates the current coorindates with the parent coordinates and the direction coordinates parentx = parentx + xDirection; parenty = parenty + yDirection; if (parentx == 0 && parenty == n && remainingSteps == 0) { paths++; } // recursive call as long as the coordinates arent negative and there are still remaining steps if (remainingSteps > 0 && parentx >= 0 && parenty >= 0) { move(1, 0, parentx, parenty, remainingSteps  1); // goes to the right... move(0, 1, parentx, parenty, remainingSteps  1); // goes up... move(0, 1, parentx, parenty, remainingSteps  1); // goes down... move(1, 1, parentx, parenty, remainingSteps  1); // diagonal top left... } } }

Porting an example from QuantEcon.jl to POMDPs.jl
I asked this in the Julia discourse website but got no response. I'm asking over here to see if I have better luck.
Just for fun (and to learn about POMDP) I am porting an example of dynamic programming from QuantEcon.jl to POMDPs.jl. The example is available here.
My code for the implementation is:
using POMDPs using POMDPModels using POMDPModelTools using DiscreteValueIteration struct SimpleOG{TI <: Integer, T <: Real, TR <: AbstractArray{T}, TQ <: AbstractArray{T}} <: MDP{T, T} B :: TI M :: TI α :: T β :: T R :: TR Q :: TQ end function SimpleOG(; B::Integer = 10, M::Integer = 5, α::T = 0.5, β::T = 0.90) where {T <: Real} u(c) = c^α # utility function n = B + M + 1 m = M + 1 R = Matrix{T}(undef, n, m) Q = zeros(Float64, n, m, n) for a in 0:M Q[:, a + 1, (a:(a + B)) .+ 1] .= 1 / (B + 1) for s in 0:(B + M) R[s + 1, a + 1] = a <= s ? u(s  a) : Inf end end return SimpleOG(B, M, α, β, R, Q) end POMDPs.states(simpleog::SimpleOG) = collect(0:(simpleog.M + simpleog.B)) POMDPs.n_states(simpleog::SimpleOG) = simpleog.B + simpleog.M + 1 POMDPs.stateindex(simpleog::SimpleOG, s) = Int(s) + 1 POMDPs.actions(simpleog::SimpleOG) = collect(0:simpleog.M) POMDPs.n_actions(simpleog::SimpleOG) = simpleog.M + 1 POMDPs.actionindex(simpleog::SimpleOG, a) = Int(a) + 1 POMDPs.transition(simpleog::SimpleOG, s, a) = simpleog.Q[Int(a) + 1, Int(s) + 1, :] POMDPs.reward(simpleog::SimpleOG, s, a) = simpleog.R[Int(s), Int(a)] POMDPs.reward(simpleog::SimpleOG, s, a, sp) = reward(simpleog, s, a) POMDPs.discount(simpleog::SimpleOG) = simpleog.β g = SimpleOG()
When I try to solve the model I get:
julia> POMDPs.solve(g) MethodError: no method matching solve(::SimpleOG{Int64,Float64,Array{Float64,2},Array{Float64,3}}) Closest candidates are: solve(!Matched::POMDPPolicies.FunctionSolver, !Matched::Union{MDP, POMDP}) at /Users/amrods/.julia/packages/POMDPPolicies/oW6ud/src/function.jl:23 solve(!Matched::POMDPPolicies.RandomSolver, !Matched::Union{MDP, POMDP}) at /Users/amrods/.julia/packages/POMDPPolicies/oW6ud/src/random.jl:36 solve(!Matched::POMDPPolicies.VectorSolver{A}, !Matched::MDP{S,A}) where {S, A} at /Users/amrods/.julia/packages/POMDPPolicies/oW6ud/src/vector.jl:23 ... Stacktrace: [1] toplevel scope at In[14]:1
Can you help me figure out what is going on?

Analysis and design algorithms
Problem Statement:
Given:
n
# of points are distributed uniformly at random on a circle with circumference of 1.Show that the expected number of pairs of points that are within distance Θ(1/n2) of each other greater than 1.
Note: This implies that the smallest distance between two points is likely O(1/n2).
(Hint: Partition the circle into n2/k regions each of which has a size of k/n2 for some constant k.)
Question: Please help me develop an algorithm to solve this

Matlab code on how to make global stiffness matrix from element stiffness matrix for a beam/truss
How to calculate global stiffness matrix from element stiffness matrix for a beam/truss in Matlab?

Does any one know what tools are used to create this video or chart?
Does any one know what tools are used to create this animated bar charts?