Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
0
votes
0answers
37 views
Function-induced polynomial evaluation trees
My question relates to the Fast polynomial evaluation and composition article by Guillaume Moroz available online at https://hal.archives-ouvertes.fr/hal-00846961v3/document/. It demonstrates notions ...
0
votes
1answer
38 views
finding a recursive formula for a sequence, if possible [closed]
Hi everyone: I was looking over an NYS Algebra 2 Regents, and two training programs for a long-distance race were compared. (The answer they wanted was the recursive formula for a simple arithmetic ...
0
votes
0answers
18 views
First Order Nonlinear Recurrence Relation
I am trying to solve the closed formula for $x_n$ given the first order non-linear recurrence relation below. Unlike linear recurrences with direct solutions, I can't find any good reference for non-...
2
votes
1answer
36 views
How can i distribute the money in the fewest movements? [closed]
I am trying to evenly distribute the total amount to each person involved.
For example I will use money.
Example 1
Person A has $20
Person B has $40
Person C has $60
So to make everything even ...
0
votes
0answers
22 views
Multiply large numbers by dividing them into 3 (Karatsuba with n/3 size)
I was solving some problems related to Karatsuba, when I came across a problem which says, how many multiplications would you need to multiply a large number divided into 3 smaller ones like this:
a =...
0
votes
3answers
43 views
How to write recursive formula as explicit (specifically, exponential)?
I recall learning in school how to convert arithmetic and geometric sequence formulas between recursive and explicit, but I don't remember learning a systematic method to approach it. For example, let ...
1
vote
2answers
33 views
find the largest square foot given an area
Given an area of n square foot, I need to be able to find the largest square foot I could make in the given area.
Example: if I had a total area of 12 square foot, I would be able to make one 3x3 ...
6
votes
1answer
213 views
Common roots of recursive defined polynomial
I have a series of polynomials $P_j(x)$ given by the recursive formula
$$P_{j+1}=\frac{e_j}{c_j}xP_{j}-\frac{f_j}{c_j}P_{j-1}
$$
with $P_{-1} \equiv 0$, $P_0 \equiv 1$, where
$$c_j = (j+1)(j+2\kappa+1)...
0
votes
1answer
48 views
Is there a rule behind why $\left \{ 1+(-1/2)^n) \right \}^{+\infty}_{n=1}$ is $a_{n+2}=1/2(a_{n+1}+a_{n}) , a_{0} = 2 , a_{1}=1/2$ in recursive form?
I understand that both expresions represent the same sequence of numbers. It starts at $a_{0}=2$ and oscilate around 1 converging to it from up and down.
I have been playing around with the explicit ...
1
vote
1answer
34 views
Visualize $T(n)=2T(n/2)+O(n)=O(n\log(n))$ on a Tree
I understand the mathematical proof for $T(n)=2T(n/2)+O(n)=O(n\log(n))$, however I cannot visually wrap my head around how it works. Intuitively, it just feels like it should $O(n^2)$. Can you show me ...
0
votes
1answer
42 views
Convergence of recursive scheme
I would like to see why below recursive scheme is convergent :
$x_{n+1}= \sqrt{\alpha\cdot x_n+\beta}$
Here, $\alpha>0$ and $\beta\in\mathbb{R}\setminus\left\{0\right\}$.
I tried something like:
...
2
votes
1answer
49 views
Dynamic Programming problem palindrome
I am stuck with the following problem:
Given a string of characters $w$, we want to know the minimum number of characters that we must add to $w$ in order to convert this string in a palindrome (note ...
0
votes
0answers
18 views
Hankel or Bessel functions of integer separated order evaluated at the same value
Let $H_\nu^{(1)}=J_\nu+iY_\nu$ be one of the Hankel function. If $\nu=\left|N-\alpha\right|$ with $N$ integer and $0<\alpha<1$, is there a fast way to get all $H_\nu^{(1)}(z)$ for all $\left|N\...
2
votes
1answer
42 views
What's the idea behind recursive least squares (RLS)?
The simply explanation of recursive Least squares (RLS) is:
$$\theta(t) = \theta(t-1) -P(t)\phi(t)[y(t) - \theta ^T(t)\theta(t-1)]$$
$$P^{-1}(t) = P^{-1} + \phi(t) \phi^T(t)$$
Where $\phi$ is the ...
0
votes
1answer
40 views
what is the complexity of recursive summation
Can someone tell me the exact complexity of this recursion ? this is actually formula for below question ( solved in recursive brute force way )
There is n steps stairs and a person standing at the ...
2
votes
1answer
59 views
*Numerical* Convergence of the Babylonian Method?
I understand the sequence $x_{n+1} = \frac12\left(x_n + \frac2 {x_n}\right) $ converges to $ \sqrt2 $ algebraically.
That is proved by means of fixed-point method or monotone convergence theorem and ...
0
votes
0answers
9 views
Simplification in Recursive Algorithms with tilde relationship
$f(N)\sim g(N)$ iff $|\frac{f(N)}{g(N)}|\rightarrow 1$ as $N\rightarrow \infty$.
Define $C_N$ to be the number of compares to sort $N$ elements and analyze $C_N$.
Given $\frac{C_N}{N+1} = (\frac{C_1}{...
1
vote
1answer
13 views
Basic Recurrence Problem in the Analysis of Algorithm
I am taking an algorithm course at Coursera. From this webpage by a Princeton Professor, Example 1.5 (Analysis of quicksort) gives the following codes.
public class Quick
{
private static ...
11
votes
3answers
726 views
How to tell if a particular number will survive in this sieve?
I was asked this in an interview.
We have people numbered from one to infinity: $$1, 2, 3, 4, 5, 6, 7, 8, \dotsc\,.$$ In first pass every 2nd person is killed, so we have $$1, 3, 5, 7, 9, 11,\...
0
votes
0answers
18 views
Graph algorithm to find the most likely ancestor of a node
I'm working on the Wikipedia Category Graph (WCG). In the WCG, each article is associated to multiple categories.
For example, the article "Lists_of_Israeli_footballers" is linked to multiple ...
1
vote
0answers
37 views
How to derive a recursive version of a regularised cost function
I am to derive a recursive version of the following cost function and examine for which choice of D can we have a estimator windup
$V(\theta) = \frac{1}{2}\sum_{t=1}^n(y(t)-\phi(t)^T\theta)^2 + \...
0
votes
2answers
27 views
An algorithm to make a variable the sole term of one side
Is it always possible to refactor an equation so that a desired variable appears as the sole term of one side?* If so, how?
Simple example:
$$xa = ya + b \\ xa - ya = b \\
a(x - y) = b \\
a = \frac{...
2
votes
2answers
40 views
Finding a recurrence for $t_n$ that holds true for a set of integers
I know the answer but I have no idea how to explain it
Question A
$t_3 =$ ['aaa', 'abb', 'acc', 'bba', 'cca'] ($5$ elements)
$t_4 =$ ['aaaa', 'aabb', 'aacc', 'abba', 'acca', 'bbaa', '...
0
votes
2answers
44 views
Confusing symbols
I saw these symbols in the text book for a subject i'm taking next semester, and I am just curious about what they mean. What is the question asking me?
0
votes
0answers
48 views
Stuck Simplifying for a Fibonacci Series
I am attempting to solve for $n$ in the equation:
$g_n=g_1F_{n-1}+g_2F_n$
where $F_n$ is the $n$th Fibonacci number. I know that $g_0$ and $g_1$ will be positive integers such that $0 < g_1 \...
1
vote
0answers
47 views
What is the difference between Kalman Filter and Recursive Least Squares? [closed]
I wish to understand the difference between Kalman Filter and Recursive Least Squares since both of them use prediction and correction approach.
In Kalman filter, the value of existing state vector ...
0
votes
0answers
9 views
Particle Filters: whether current measurement depends on previous measurement
Recently I was learning basic estimation theory. I am confused that whether the measurement $z_k$ is related to previous measurements $z_{1:k-1}$.
A quick recap of the estimation problem.
Given ...
0
votes
0answers
13 views
Solving Recurrence to Find Asymptotic Behavior (Algorithm)
Can somebody check if I got the right answers for those recurring functions?
1)$T(n)=4T(\frac{n}{3})+nlg^2n$ - using the asters theore i got that $T(n) \: \in \: \Theta(n^{\log_{3} 4}) \approx \Theta(...
1
vote
0answers
54 views
Longest path of a matrix
Given a matrix
$$
A = \begin{pmatrix}
1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7
\end{pmatrix}
$$
We know that the length of the longest path that is ...
0
votes
1answer
39 views
Prove $N\cdot lg(N) = \sum_{k=1}^N(\lfloor lg(k) \rfloor + 2)$ - “Analysis of Algorithms” by R. Sedgewick
This is a problem from "Analysis of Algorithms" by R. Sedgewick. In the context of the merge sort:
$C_N = N\cdot lg(N)$
Exercise 1.4
Develop a recurrence describing the quantity $C_{N+1} − C_N$ ...
0
votes
6answers
89 views
Finding a recursive formula/sum for $\pi$
I'm very much aware of the
$$\pi = 4 \left(1 - \frac13 + \frac15 - \frac17 + \frac19 -\cdots \right)$$ and
$$\pi = \sqrt{6\left(1 + \frac14 + \frac19 + \frac{1}{16}+ \cdots \right)}$$
and even less ...
0
votes
0answers
21 views
Find an alternative FPTAS for knapsack
There is a famous algorithm using, the recusive integer data problem on:
w(j,p) = min weight set of items of profit=p when we have j items
Now I was wondering if there was an alternative solution ...
0
votes
0answers
29 views
Expand recursive equation to convert it into a normal formula
The Problem:
I am faced with the following recursive equation:
$$V(n) =\begin{cases}
2V(n/2)+n& \text{for n > 1}\\
0 &\text{for n = 1}
\end{cases}$$
I am trying to expand the function ...
0
votes
1answer
195 views
recurrance with merge-sort
Trying to modify a merge sort by recursively splitting an array of size n into k sorted subarrays k > 2 and merging these subarrays. Time for merging is c(k-1)n. Specify the recurrence relation and ...
-1
votes
3answers
63 views
How to solve the recurrence $a_{n}=\frac{n+1}{n} a_{n-1}+3n+3$?
I tried to solve this recurrence by taking out $n+1$ as a common in the RHS, but still have $n \cdot a_n$ and $a_n$
2
votes
1answer
57 views
multiple knapsack problem?
I have a weight X. This should be distributed into multiple knapsacks w1...wY.
It should be distributed to the largest knapsacks first and smallest last.
Yet the optimal distribution should be found ...
1
vote
1answer
13 views
Is the function $F=\chi_{>m}$ primitive recursive for some undetermined m?
Is the function $F=\chi_{>m}$ primitive recursive for some undetermined $m$?
An exercise can be seen here like the following:
$F(m)=0,$ if the decimal expansion of $\pi$ has a run of at least $m$...
0
votes
0answers
28 views
How do I extract a curve in xyz from curvature/torsion using Frenet Serret equations?
Somewhat of a continuation of this, opening this scab because I have the same question but the solution was not covered in post and I have been banging my head against the wall for a week trying to ...
8
votes
0answers
84 views
Let $X$ be a random variable, $\frac{\mathbb{E}[e^{sX}-e^{tX}]}{s-t}$ for $s \approx t$. As
Question
Let $X$ be a random variable for which we only have the value of its Moment Generating Function $M_X$ on a discrete set of points, I am looking for a stable method to compute:
$$\frac{M_X(s) ...
0
votes
0answers
32 views
How to identify shortest and longest path, given a recursion tree?
Show that the solution to $T(n)=T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right)+n$ is $\Omega (n \log n)$ by analyzing the recursion tree.
This is my recursion tree :
How can I show that $T(n)=...
0
votes
1answer
29 views
Prove that a proposed algorithm gives an optimal solution of the optimization problem.
We have $N$ queues.
Each of the queues contains a number of numbered ball, and the balls can be taken out in descending order.
For example, the queues can be as the follows:
I want to take $L$ balls ...
0
votes
3answers
30 views
How to show that this specific limit exists in this proof?
Given the sequence $T_n$ where $T_1 = 0, T_2 = 1, T_3 = 1$ and $T_n = T_{n-1} + T_{n-2} + T_{n-3}$ for $n >= 3$. Find what the ratio of consecutive terms, $\frac{T_{n+1}}{T_n}$ is converging to.
I ...
1
vote
1answer
22 views
Improving the efficiency of exponential smoothing for binary digits
Let's say I'm a stock exchange, and I have an order flow for Apple shares. Let's say those numbers look like:
10,000 (buy)
-3,100 (sell)
24,243 (buy)
These orders come in very quickly. What I want ...
0
votes
1answer
36 views
Given two arrays A1,A2, return if for a given X , there is a pair of ai∈Ai such that a1+a2=X (𝑂(n log(𝑛)))
The question is fairly easy to understand, the problem is i need the algorithm running time to be 𝑂(n log(𝑛)), which i couldn't achieve.
Given two arrays with positive integers,lets call them A1,...
-1
votes
2answers
51 views
I don't understand what this question is asking and how to show it/prove it$
Given the sequence $T_n$ where $T_1 = 0, T_2 = 1, T_3 = 1$ and $T_n = T_{n-1} + T_{n-2} + T_{n-3}$ for $n >= 3$. Find what the ratio of consecutive terms, $\frac{T_{n+1}}{T_n}$ is converging to.
...
-2
votes
2answers
48 views
Prove a recursive sequence using induction
I'm having trouble with this recursive sequence question and was wondering how to prove it.
The sequence $a_n$ is defined recursively by, $a_1 = 6$, $a_2 = 8$, $a_n = 4(a_{n-1}) - 4(a_{n-2})$ for $n&...
1
vote
0answers
17 views
How many calls of the form $\det(B)$ does the algorithm create?
Let's say $A\in \mathbb{R}^{n\times n}$ and the $n^2$ components of $A$ are pairwise different. In order to calculate $\det(A)$ we can use the recursive algorithm that computes $\det(A) = \sum\limits_{...
1
vote
2answers
36 views
Evaluating a polynomial using Horner's algorithm
With Horner's algorithm, I can solve f(x$_{0}$) for a polynomial like this:
$a_0 + a_1x + a_2x^2 + a_3x^3 + ... + a_nx^n$
By doing this:
b$_n$ = a$_n$
b$_{n-1}$ = a$_{n-1}$ + b$_n$x$_0$
b$_{n-2}$ =...
1
vote
3answers
65 views
What are these kind of problems called?
The question is that:
There are $100$ of coins, to be given to members of a family.
The eldest brother is the one who decides how to distribute them
After his decision, family members vote ...
0
votes
0answers
23 views
Best recursive algorithm for Auto-Convolution?
i have a question.
I know a recursive algorithm that can compute convolution generally with complexity of $\theta(n^{log_2 3})\simeq \theta(n^{1.58}) $ is there any better algorithm with better ...
