Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
1,377 questions
0
votes
0
answers
104
views
Minimum steps to cut a truss
Motivation
While I was looking at the method of sections to find the forces in the members of a truss in engineering mechanics, I had a question about the minimum amount of calculation required to ...
- 113
1
vote
0
answers
36
views
Unorthodox implementation for a recursive identification method
Recently I realized that I've coded a custom-made function for recursive output error method which differs a bit from the traditional algorithm and would like to know the perception of my peers. ...
- 141
2
votes
0
answers
105
views
Conjectured fast and simple recursive algorithm for Bernoulli numbers
Let
$B_n$ be the $n$-th Bernoulli number.
$T(n,k)$ be an integer coefficients such that $T(n,k) = \nu_k$ where we start with vector $\nu$ of a fixed length $n$ with elements $\nu_1=1$, $\nu_i=0$ for $...
user929945
6
votes
1
answer
234
views
Fast and simple recursive algorithm for A375540
Let
$a(n)$ be A375540, i.e., an integer sequence such that $$ a(n) = 2^n n! [x^n] (1/2 - \exp(-x))^n. $$
Start with vector $\nu$ of fixed length $m$ with elements $\nu_i = 1$ (that is, $\nu = \{1,1,\...
user929945
0
votes
0
answers
15
views
If $f$ is an autosimilar function s.t. $f(x)=\sum_{l\in A}p_l f(c_l x)$, then $f(x)=\sum_{w\in W}p_wf(c_w x)$ for cylindrical $W\subset A^*$
I think that I have a proof for the following claim, but I am looking both for a feedback and suggestions how to make it better, for example how to make it a top-down rather than a bottom-up type of ...
- 1,673
1
vote
0
answers
42
views
How to informally understand `hash reducibility`?
I was reading a paper on a certain reducibilities in Polynomial classes. And I stumbled across this definition: For sets $A,B$ computable in polynomial time, we write $A \leq^{\#} B$ via a polynomial $...
- 303
0
votes
1
answer
94
views
Trouble understanding quicksort O(nlogn) proof
I have trouble understanding this proof for quicksort: The goal is to bound the overall number of comparisons performed by the algorithm. Consider an array $A$ with elements $z_1, z_2, ..., z_n$ with $...
- 3
0
votes
0
answers
133
views
Is my proof of $T(n) = T(n - 1) + n$ being $O(n^2)$ correct?
I know that this has been posted at least once, but the accepted solution doesn't use the substitution method laid out in Introduction to Algorithms by Thomas Cormen.
What I've tried so far is this:
$...
- 1
2
votes
0
answers
58
views
The growth rate of a recursively defined function
Imagine a function where you know how to get from $f(n)$ to $f(n-1)$ and from $f(2n)$ to $f(n)$. How many steps would it take to get to $f(1)$? I am not talking about the optimal route but rather if $...
- 31
0
votes
1
answer
175
views
Finding order of time complexity for program finding the $m$-subsets of an $n$-set.
For the code here, the analysis for the order-of-time complexity is as follows:
For the purpose of finding the time-complexity of the above program; the program statements of concern are:
...
- 4,972
0
votes
1
answer
77
views
Redistributing points along a set of points (Stroke)
I'm currently facing the following problem: I want to write an algorithm that, given as input a list of points (representing a path/stroke/curve), and a target $distance$ it creates a new stroke that ...
- 405
2
votes
2
answers
106
views
Minimum distance decoding
I have been researching decoding methods for Reed–Muller codes and am currently reviewing a recursive decoding approach proposed by Ilya Dumer in his paper “Recursive Decoding and Its Performance for ...
0
votes
1
answer
81
views
Algorithm to expand arbitrary partitions
Suppose you have an expression like:
$$
(a + b + c + d)(e + f + g)(h + i)
$$
Is there a method to expand this expression that does not involve multiplying only two groups at a time? Some way to ...
- 41
0
votes
1
answer
94
views
Recursive to explicit/closed form [duplicate]
A similar question has been asked before but I haven't seen an answer to this specific one after looking for so long.
I have a recursive function where:
$P(2) = 1$
For $n ≥ 3$, $P(n) = (n-2)P(n-1) + ...
- 69
0
votes
0
answers
61
views
Solve Recurrence Relation with Master theorem Case 3
I need your help with the following problem:
I’m supposed to find a simple function $ g(n) $ for the recurrence relation
$ T(n) = 9 \cdot T\left( \lceil \frac{n}{4} \rceil \right) + 3^n $
with the ...
- 43
0
votes
0
answers
87
views
Recursive system identification initialization (continuous-time model)
I have a doubt concerning recursive system identification. I have seen that in many occasions we have a data set $u(t)=[u(1)\, u(2) \, \dots]$. When the first couple of data $y(t)$ and $u(t)$ arrives,...
- 141
0
votes
0
answers
21
views
Convergence of $ \vec{x_{n+1}} = A^{-1} f(\vec{x_{n}},\vec{y_{n}}), \:\:\: \vec{y_{n+1}} = A^{-1} g(\vec{x_{n}},\vec{y_{n}}) $
I have two systems
$$ A \vec{x} = f(\vec{x}, \vec{y}), \:\:\: A \vec{y} = g(\vec{x}, \vec{y}) $$
Both have same constant, square matrix $A$. I implemented an iterative algorithm with an initial value ...
- 5,409
3
votes
2
answers
140
views
Asymptotic equivalent of sequence defined by a recursion relation.
For the study of a termination speed of a recursive algorithm of mine, I would like to have more precise result on the following sequence:
$$0< a_0 = a< 4 \qquad \text{and} \qquad a_{k+1} = \...
- 5,691
0
votes
0
answers
48
views
Correctness of recursive sorting algorithm through induction
Hi I need help to prove the correctness of a recursive algorithm.
It works like this, it takes an input array A with the size of the array being a power of 4.
The algorithm is defined like this:
sort(...
1
vote
1
answer
200
views
Explain how to find this formula from the recursion in this paper
I am trying to understand how to find this formula, which seems straight forward, but I am missing something.
In page 20 of this paper (or thesis):
https://egrove.olemiss.edu/cgi/viewcontent.cgi?...
- 1,112
0
votes
0
answers
45
views
Strict bound for recurrence formula
Given the recurrence $$T(n) = (2k - 1)T(\frac{n}{k})+2^kn$$ I need to show (or disprove) that for every $\epsilon>0$ there exists a $k$ such that $T(n)=o(n^{1+\epsilon})$.
So far, I've been able to ...
- 459
0
votes
1
answer
61
views
solve a recursion formula using a generating function
I have the following formula for a vector $v_n= \ ^t(a_n, b_n)\in \mathbb R^2$ :
$v_n= Av_{n-1}+ Bv_{n-2}$ for two given matrices $A$ and $B$ in $M_2(\mathbb R)$, and we are given $v_1$ and $v_2$ of ...
- 1,112
1
vote
0
answers
67
views
Recursive sum of binomial random variables
In my work I've come across the following problem.
For $Y_k\sim\text{Binomial}(X_k,p)$ and $X_0=1$, compute the probability distribution for the following recursion,
$$X_k=X_{k-1}+Y_{k-1}$$
This ...
- 8,345
0
votes
1
answer
73
views
Solution to recurrence equation $T(x,y) = T(x-1,y) + T(x,y-1) + O(1)$ in terms of big-O expression
What would be the solution, expressed in big-O notation, to the recurrence equation $$T(x,y) = T(x-1,y) + T(x,y-1) + O(1)$$ with base case being either or both $$T(x,0) \text{ for any x}$$ $$T(0,y) \...
- 137
0
votes
0
answers
73
views
Prove or give a counterexample of a recursively defined function
Conjecture:
For any given $\alpha\in\mathbb{R},$
Any given bijective continuous function $f:D \rightarrow \mathbb{R_{\ge\alpha}},$
And any given $\mu_\alpha:D\rightarrow \mathbb{R}$, where $D\subset\...
- 765
1
vote
1
answer
75
views
I stumbled on a bruteforcing median algorithm. Can anyone tell me why it works and is there a name for this equation?
I recently stumbled on an algorithm while trying to write a program to estimate a median without sorting, a randomized group of non-repeating numbers with a known number of elements. Performance is ...
- 11
0
votes
1
answer
110
views
How to calculate $p_{A}+ p_{B}$ quickly?
Given $p_{A}, p_{B}, p_{C}$ so that $p_{A}+ p_{B}+ p_{C}= 1$, and the transition matrix equation $\begin{bmatrix} a+ m & -b & -s\\ -a & b+ d & 0\\ -m & -d & s\\ \end{bmatrix}\...
- 288
1
vote
2
answers
220
views
Prefix-free binary codes with costs
I came across the following problem:
We would like to generate a prefix-free binary code with $n$ codewords, such that we pay $4$ units for each 1-bit and $1$ unit ...
- 53
1
vote
4
answers
238
views
resolve recurrence $a_n=a_{n-1}+3a_{n-3}$
Hy all
I want to try to find the solution for the recurrence $a_n=a_{n-1}+3a_{n-3}$. If i take the equation associate to it, then i have $x^3-x^2+3=0$. But in this case, i have just one real root and ...
- 1,317
0
votes
1
answer
157
views
Find the chromatic polynomial of a graph using deletion and contraction
Find the chromatic polynomial of the following graph.
The graph in question is the one on top and I am doing deletion and contraction recursively as the picture shows.
This is what I get and I have ...
- 1,252
2
votes
1
answer
92
views
In how many ways can the integers $1,2, \dots ,n$ be arranged so that there is only one integer that is immediately followed by a smaller integer? [closed]
I attempted this using an recursive idea. I noticed that as long as $1$ does not appear on the first position and it appears on the $k$-th position, then there are exactly $n$ choose $k$ number of ...
- 29
0
votes
0
answers
58
views
$\mu$ recursive function exercises
Could you please explain the solutions of the exercises? The definition of $\mu$- recursive finctions is clear to me, but I want to know the way of thinking to solve the exercises.
Thank you.
- 359
0
votes
1
answer
58
views
Proving this recursive merging routine from merge sort works
I was wondering if anyone could provide a proof that the following algorithm to merge $2$ sorted arrays into a combined sorted array works:
\begin{array}{l}
\texttt{function merge($x[1 \ldots k], y[1 \...
- 3,152
0
votes
1
answer
80
views
Dynamic programming, optimization problem where decision leads to multiple overlapping subproblem. [closed]
In the matrix chain multiplication (MCM) problem each time we apply a decision of parentizing an expresion $e=(e_1)(e_2)$ we have two subproblems to solve but they are not overlapping. Indeed, solving ...
- 1,813
2
votes
1
answer
563
views
Reasoning about the Collatz conjecture, multiple infinitely growing trees that never overlap? [closed]
I have been pondering the Collatz conjecture recently as a mental exercise, and have run into a problem that has to do with proving that an iteratively growing tree of odd positive integers will ...
- 55
-2
votes
1
answer
82
views
Generate set of numbers containing 3 consecutive 1, but without the elements of the previous set [closed]
So I have this specific problem that I couldn't figure out. I want to create a set $F_n$ containing all bitstrings that has 3 consecutive 1s, but not those that are already contained in all the ...
- 723
0
votes
1
answer
78
views
Division based recurrences instead of subtraction based: $F(x)=F(x/2)+F(x/3)$
The most famous (and simplest non-trivial) recurrence is the Fibonacci recurrence $F(n)=F(n-1)+F(n-2)$ with $F(0)=0, F(1)=1$. What if we consider instead division based recurrences, the simplest non-...
- 11k
0
votes
1
answer
144
views
Why doesn't this diagonal argument work?
I have a question about the standard rules for computing p.r. terms (see below). It seems pretty clear that these rules could be used to define a p.r. operation that evaluates any p.r. term of the ...
- 27
0
votes
1
answer
155
views
How to Prove Division of One Bezier Curve into Two using de Casteljau Algorithm
$\newcommand{\brstbasis}[2]{b^{#1}_{#2}}$
$\newcommand{\posintset}{\mathbb{Z}^{+}}$
$\newcommand{\intset}{\mathbb{Z}}$
$\newcommand{\realset}{\mathbb{R}}$
$\newcommand{\domain}[1]{\operatorname{dom}\...
- 1,960
0
votes
0
answers
55
views
Recursive approximations of inverse square law
I have a toy electrostatics simulation that consists of some number of 2D point particles that each have a real-valued "charge" $q_i$, which then exert forces on each other proportional to $...
- 738
1
vote
1
answer
1k
views
Tried finding an efficient algorithm for a 4-digit number guessing game, knowing only the number of digits on correct positions..
I've been playing a game similar to Bulls and Cows, but it goes like this: one player has to pick a random $4$ digit number. Digits can repeat, any digit between $0$ to $9$ and, you only get the ...
- 13
0
votes
2
answers
47
views
Find limit of Decrementing Recursive Series
I want to find a formula to find the lower limit part of this recursive or geometric series
$$
x_{n} = \left( x_{n-1} + p \right) \times \left( 1 - \frac{t}{100} \right)
$$
I was just wondering what ...
- 13
0
votes
4
answers
127
views
Prove that $x_{n+1} = \frac{1}{3}(2x_n + \frac{a}{x_n^2})$ is decreasing
Prove that $x_{n+1} = \frac{1}{3}(2x_n + \frac{a}{x_n^2})$ is decreasing where $x_1$ $> 0$.
I have been asked the above question and the working out given to me skipped some steps in between.
It ...
- 621
0
votes
1
answer
45
views
create a recurrence relation for the number of ways of creating an n-length sequence with a, b, and c where "cab" is only at the beginning
This is similar to a problem called forbidden sequence where you must find a recurrence relation for the number of ways of creating an n-length sequence using 0, 1, and 2 without the occurrence of the ...
- 15
1
vote
1
answer
48
views
Lemma 6.2. in Scaling Algorithms for the Shortest Path Problem
I have a question regarding the proof of Lemma 6.2. in this paper: https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/scaling%20algorithm%20for%20the%20shortest.pdf.
The simplified ...
- 112
2
votes
1
answer
129
views
Let $x_0 = 3;\ x_{n+1}=3x_n\ $ if $\ \frac{x_n}{2}<1;\ x_{n+1}=\frac{x_n}{2}\ $ if $\ \frac{x_n}{2}>1.\ $ Is $\ \liminf_{n\to\infty} x_n=1?$
This is a natural follow-up question of this previous question of mine.
Let $x_0 = 3.$ Let $\ x_{n+1} = 3x_n\ $ if $\ \frac{x_n}{2}<1;\quad x_{n+1} = \frac{x_n}{2}\ $ if $\ \frac{x_n}{2}>1.\quad ...
- 25.2k
3
votes
2
answers
345
views
Guaranteed graph labyrinth solving sequence
Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
- 53
0
votes
0
answers
83
views
Finding an algorithm that goes through all the possible permutations of a set only by swapping 2 elements
I recently came across a problem when trying to deal with a set of numbers with n elements.
The problem is as follows:
Starting with a set of n distinct elements, how would one generalize a unique ...
0
votes
0
answers
61
views
Subset Product has a pseudo-polynomial algorithm?
Subset Product- Given $N$ and a list of positive divisors $S$, decide if there is a product combination equal to $N$
We will sort $S$ in numerical order from smallest to largest in order
to find out ...
- 191
7
votes
1
answer
244
views
Prove or reject my solution to "How quickly can you type this unary string?"
I had posted an answer on the Code Golf SE yesterday. Although the answer on that site remain valid if no counterexample can be find. I'm interesting in its correctness. So I want to find a prove or ...
- 182