Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
0
votes
0answers
20 views
Recursive algorithm for planar graph
I have this pseudo-code and I need to understand what it does. It takes some planar graph as input and returns a subset of V (that are the vertexes of the graph). It is clearly recursive, but I don't ...
0
votes
1answer
46 views
Divide and conquer: Why $F(0) = 0$? [on hold]
Reading algorithms. Fibonacci example.
I saw an example where it said $F(1) = 1$ and $F(0) = 0$. (Fibonacci)
Why $F(1) = 1$ and $F(0) = 0$? From where does it originate?
Thanks.
0
votes
1answer
61 views
Back-n-Forth or a Direct Isomorphism Between A Countable DLO Without Endpoints and $U = \{ \frac{m}{2^n} \}$
Note: I changed this question and deleted my answer, bringing it into the question for quick review. The proof now has the same brevity as the back-and-forth method found in wikipedia.
Let $P$ be a ...
-1
votes
0answers
23 views
Multiple equations dependent on each other
I am trying to process the trade data of 1,000+ cryptocurrencies across 25+ different crypto exchanges.
I cannot figure out how to calculate the average price for each coin.
First, the formula to ...
1
vote
0answers
26 views
$f(n) = 2f(n/2) + n^2$ if n is even or $2f(n/2) + n^3$ if n is odd
I want to solve the following recursion to find the complexity.
$f(n)=\begin{cases}
2f(n/2) + n^2 & \textbf{if } n \text{ is even}\\
2f(\lfloor n/2\rfloor) + n^3 &...
0
votes
0answers
24 views
Number of levels in recursion tree.
See in the picture that the number of levels is clearly $1+\log_{4/3} n$.
so,the total cost should be $cn(1+\log_{4/3} n)$
However in clrs and Khan Academy article of Cormen they are doing $cn\log_{4/...
2
votes
2answers
47 views
Solution to differential equation $y'(x) = a * y(x)^2$
first of all: I am not a mathematician. I am struggling since a few hours with a simple differential equation which I would like to solve to approximate the expectation curve for computer simulations ...
1
vote
0answers
23 views
Trouble understanding a recursive summation
I'm reading an NLP paper. In section 4.2, there is the following summation:
$$\alpha[t][k] = \sum^{t-k}_{j=1}p(c^t_{t-k+1} | c^{t-k}_{t-k-j+1}) \cdot \alpha[t-k][j]$$
where $\alpha[0][0] = 1$.
...
2
votes
1answer
42 views
A little help for building the Fibonacci spiral in a particular reference system
In the following picture, the numbers represent the building steps of the Fibonacci spiral (or Golden spiral).
I would like to find the coordinates of the upper-left corner of the squares (black dots)...
0
votes
0answers
12 views
Prove that the time it takes to run the merge sort algorithm on a list of n numbers is less than an equation
Problem
Can someone help me with this. I use strong deduction and then I have $T_{k} = 2^kT_{\dfrac{n}{2^k}}+kn$ but I don't know what to do next.
1
vote
1answer
50 views
Does this recursive function have a closed-form solution?
Consider the following recursive function:
$$
z(i) = \begin{cases}
z(i + 8) + 1 & i < 0 \\
z(i - 7) & i > 2 \\
0 & 0 \leq i \leq 2
\end{cases}
$$
Does this recursive function have ...
1
vote
1answer
71 views
How can I write a recursive function having $\Theta(n^7)$?
How can I write a recursive function having $\Theta(n^7)$ cost?
I must only use if, then, else statements and a function called $G(n)$ that costs $\Theta(n)$.
For example:
...
0
votes
1answer
40 views
Principle of mathematical induction in recursive functions
"Use the principles of mathematical induction to show that the value at each positive integer of a function defined recursively is uniquely determined"
I have a problem understanding what exactly it ...
0
votes
1answer
198 views
Trying to simplify this
How do I simplify this into a formula?
Note: $z,g,o,x,p,b,c,f,y$ - are all multiplicative constants
I have:
$$n(1)=z\left(gox^0+p\left(\frac{b}c\right)-fy^0\right)$$
$$n(3)=z\left(gox^2+p\left(\...
0
votes
0answers
46 views
0
votes
1answer
53 views
Explicit form of recursive function
Given recursive function:
$$T(x)=2T(\frac{x}{2})+\frac{2}{\log (x)}$$
reach an explicit form:
We already solved it in class. However I can't seem to remember, how was it...
I Wrote it in these ...
0
votes
1answer
25 views
generating all possible k partition of an array
actually, I confronted a problem for generating all possible k partitions of an array. I tried to write the algorithm but actually, I am not able to.
can anybody please give me the idea, how to code ...
0
votes
1answer
39 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
21 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
39 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
23 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
49 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
41 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
227 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
49 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
40 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
59 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
48 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
44 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
66 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
11 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
727 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
39 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
51 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
49 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
74 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
15 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
98 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
41 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
154 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
45 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
274 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 ...
