Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
1,239
questions
1
vote
0
answers
15
views
Non-recursive algorithm with exponential running time
It is well-known, that there are many recursive algorithms running in exponential time, e.g. branching algorithm, backtracking etc. . My question is, is it possible to construct a non-recursive ...
- 91
0
votes
0
answers
30
views
Getting rid of asymptotic notation in Recurrence Relations
Let's suppose I want to resolve the following Recurrence Relation:
$$ T(n) = \begin{cases}
1 & n=1 \\
T(n-1) + \Theta(n) & \text{otherwise}
\end{cases}
$$
I want to prove that ...
- 101
0
votes
1
answer
25
views
Is it possible to obtain rotation or transposition with following rules?
I have been trying to solve a problem in which I faced this question which I need to answer to solve my problem. Any help or suggestions or references would be helpful ?
Given a sequence of length ...
- 62
0
votes
2
answers
69
views
Quite challenge: how to solve this functional equation?
I have asked This question before, but I forget to add some term and factors. When adding those, the difficulties increased significantly.
Consider the following equation:
$$\omega(t) = 1 + \frac{2}{t^...
- 65
2
votes
0
answers
58
views
What is the general techique to solve the following type of recursive integrals?
Consider the recursive definition of the following function:
\begin{equation}
\omega(t, a) = 1 + \frac{1}{t} \cdot \biggl( \int_{0}^{t-a}\! \omega(t-x, a) \, dx \biggr)
\end{equation}
We can assume ...
- 65
0
votes
0
answers
9
views
Randomness in iterative algorithm
Let $(H, \langle, \rangle)$ be a Hilbert space. take a closed and convex set $K \subset H$ and $f: K\times K \longrightarrow \mathbb{R}$. The equilibrium problem $EP(f,K)$ consists of finding $\...
- 1
2
votes
0
answers
23
views
Is there an algorithm that can compute finite presentations for finitely presentable subgroups in a FP group with solvable word problem?
Given a group and its finite presentation $G=\langle A\mid R\rangle$, I want the following algorithm:
Input: a finite set $W$ of words in $A\cup A^{-1}$ that generates a finitely presentable subgroup ...
- 51
0
votes
0
answers
19
views
Converting recursive equation into matrices by using matrix exponentiation
This is an example of converting fibonacci function into matrices called matrix exponentiation method.
Fibonacci sequence defines
$$
f(1)=1
$$
$$
f(2)=1
$$
$$
f(x) = f(x-1) + f(x-2)
$$
This recursive ...
0
votes
1
answer
74
views
Find a simple path in given tree with minimum number of edges
Suppose given a Tree $T=(V,E)$. Each nodes in $T$ has a degree at most two. Also, edges in $T$ has weight distinct and positive natural. Suppose $|V|=n$, our goal is find a simple path with length ...
- 1
2
votes
1
answer
31
views
Recursive algorithm complexity: Pedantic / Comprehensive proof
I'm trying to do a formal comprehensive proof of a certain recursive algorithm (Divide-and-conquer). My problem is that all resources I know always do some simplifications, and I don't manage to find ...
- 57
0
votes
1
answer
39
views
Inductive proof for recursive function
Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists over the alphabet.
I've encountered the following function:
$f([])=[]$
$f([x])=[x]$, for $x \in \Sigma$
$f(x:L)=f(L)$, for $x \in \Sigma$ ...
- 11
0
votes
0
answers
31
views
An algorithm to compute the eigenvalues of $A + B$ recursively
Is it posible to express a function
$$ Eig_n(A, B) := \{ \text{The } n\text{ eigenvalues of the } n \times n \text{ matrix } A + B \}$$
The input of $Eig$ can be either described as the eigenvalues of ...
- 637
0
votes
1
answer
44
views
How to write the general solution for the recurrence relation: $x_{n+1} = x_n e ^ {\frac{1}{x_n}}$?
Consider the sequence $(x_n)_{n\geq0}$, with $x_0>0$ and satisfying the recurrence relation: $$x_{n+1} = x_n e ^ {\frac{1}{x_n}},$$ how you go about writing $x_n$ in terms of $x_0$, and the ...
0
votes
1
answer
49
views
matlab coding - finding shortest path problem
Lately I've been trying to learn MATLAB and there's this project that have been assigned to me which I'm trying to do. the description of the project is as follows:
we have a set of 100 points: $${(0,...
- 154
4
votes
1
answer
61
views
How many multiples of 7 contain a 7 in their decimal representation?
The first few multiples of $7$ that contain a $7$ in their decimal representation are $7, 70, 77, 147, 175, 217 ..$ (OEIS A121027).
My question is how many such numbers exist below $n$:
$$
f(n) = \...
1
vote
2
answers
76
views
Solving recursive equation without Master's Theorem
Cheers, I am asked to find the time complexity of a recursive algorithm, which splits the starting problem on $\sqrt{n}$ subproblems, of size $\sqrt{n}$ each, and then combines the solution in linear ...
0
votes
0
answers
38
views
Householder QR with column pivoting
In numerical linear algebra, we know how Householder QR can handle rank deficient matrices with column pivoting: which is essentially to choose the left-over columns with the maximum norm and use ...
- 53
0
votes
0
answers
21
views
Is it possible to use a chunk of observations instead of one observation in Recursive Least Squares (RLS) at once?
Recursive Least Squares (RLS) by its structure reestimates coefficients iteratively utilizing one new observation in each iteration. Is it possible to use $n$ new observations in one iteration to ...
1
vote
2
answers
30
views
Calculating the number of possible paths from an arbitrary starting point
I have a grid of size $n\times n$, where the origin is set at $(0,0)$ and the coordinates of the points on this grid, can only be positive.
Let's say that we start at the point $(i,j)$. We can only go ...
- 532
1
vote
3
answers
93
views
solve the recurrence relation $a_n = 7a_{n-1} - 16a_{n-2} +12a_{n-3} + n4^n $
Solve the recurrence relation
$$a_n = 7a_{n-1} - 16a_{n-2} +12a_{n-3} + n4^n $$
With initial conditions:
$a_0 = −2$
$a_1 = 0$
$a_2 = 5$
I solve the homogenous part like that:
$$a_n - 7a_{n-1} + 16a_{...
- 11
0
votes
1
answer
53
views
variant of tower of hanoi
I am having a really hard time coming up with the answer for the variants of tower of hanoi.
So the puzzle goes like this:
there are $n$ disks and $n+1$ pegs. There is also an adjacency restriction ...
0
votes
1
answer
96
views
Finding the number of pairs in an array such that all the numbers between the pair are strictly less than either number in pair
Question:
Suppose we have an array $A$ of size $n$ all with distinct values. We define a pair $(a,b)$ with $a < b$ if for each $a < i < b$ we have that $A[i] < \min{\{A[a], A[b]\}}$. That ...
1
vote
0
answers
14
views
Proof that a multiple recursive function generates an infinite set [closed]
if I have an example multiple recursive function like the following:
$$f(x)\begin{cases}4x\ always\\\frac{x+1}{3}\ if\ mod(x+1, 3)=0\end{cases} $$
How can I proof that it generates (or it does not) a ...
- 11
0
votes
1
answer
34
views
In how many ways can they be coloured so that two successive strips have different colours?
$n$ strips are to be coloured using three colours viz. red, blue and green. In how many ways can they be coloured so that no two consecutive strips are of same colour?
My Attempt:
Let $a_n$ be the ...
- 7,062
1
vote
1
answer
43
views
Proof for number of comparisons needed to find max two elements in an array
I am reading this post which explains the algorithm to compute the two maximum numbers in an array.
In the second algorithm, we need to compute the number of comparisons that the algorithm makes.
The ...
- 235
1
vote
1
answer
47
views
Trying to Resolve One Recursion with Two Solutions
Background: I recently answered a question about the sequence of minimum Ford circles on each successive iteration here. I then asked myself the related question about the maximum circles on each ...
- 6,203
0
votes
0
answers
35
views
How to proof a greedy algorithm for return loans to bank
This problem was in my homework, now I'm preparing for exam but still couldn't understand it.
We have $n$ loans, each loan has initial amount $R[i]$ and interest $a[i]$, and Monthly income $S.$
each ...
- 1
1
vote
2
answers
69
views
Looking for an algorithm
I have a very long "list" of numbers ( maybe thousands ) which may be grouped, by sum into "n" groups. The number of groups and values are given. For example:
List of numbers: [1, ...
0
votes
1
answer
21
views
Is the height of this recursive tree $\lceil \log _{2} n \rceil$?
I adapted the following code for a recursive binary cumulative sum function in Python:
...
- 97
2
votes
1
answer
39
views
Recursively determine cubic spline coefficients
I am looking for a way to fit a cubic spline on previously recorded points without using matrices. The software is running on an embedded microcontroller which is low on RAM, so calculating my ...
- 123
0
votes
0
answers
16
views
Divide and Conquer: Statement Explanation
I have started reading Introduction to Algorithms by Thomas H Cormen. In Chapter 4, There is sentence that says
Subproblems are not necessarily constrained to being a constant fraction of the original ...
- 11
0
votes
0
answers
27
views
Proposition of fast algorithm for graph with weights
If ever your Djkstra algorithms are in a situation where the max weight is much smaller than the number of vertices in your graph, try transforming each weight of size "x" into "x" ...
1
vote
0
answers
101
views
Algorithm to find maximum sum over weighted overlapping intervals
Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $...
- 163
1
vote
2
answers
102
views
how can prove $n^n$ is primitive recursive
I try to prove $n^n$ is primitive recursive,first i try to releationate this proof with the proof of $x^y$, but in this case is different, because the base is not the same.
So my attempt was to see ...
- 39
1
vote
0
answers
167
views
Calculate all possible paths in graph
I have a number of graphs that look similar to this:
Graph
In this image, there are 4 levels and 4 node per level: Green is level 1, Blue is level 2, Pink is level 3 and Yellow is level 4.
Graph - ...
0
votes
0
answers
35
views
Find path between x pairs of vertices in undirected graph $G$
I am looking for the most efficient algorithm to find a path between every $x$ pair of nodes assuming $n$ total number of nodes in an undirected graph $G$ where $x$ is approx 1% of $n$. What are the ...
- 85
3
votes
1
answer
113
views
What is the time complexity of $\sum_{i = 1}^n \mathcal{O}(n!)$?
Consider the following recurrence:
\begin{equation*}
T(n) = \begin{cases}
\Theta(1) & \mbox{if $n = 1$}\\
n \cdot T(n - 1) + \Theta(n) & \mbox{otherwise} \\
\end{...
3
votes
1
answer
66
views
Solve using substitution method solve $T(n) = T(n-1) + n$ by guessing $O(n)$
I'm still learning the substitution method and I'm a bit confused on how to find out whether my guess in fact correct or not
Here's what I did so far:
Induction goal: $T(n) ≤ cn$
Induction hypothesis:...
- 35
2
votes
1
answer
89
views
Can't understand a recursive definition of reverse
reverse (x): get the reverse of a string x.
For instance; reverse (aaabc) = cbaaa
Ok, so I made this.
$W_1 ∈ Σ$* and $W_2 ∈ Σ$* and $x ∈ Σ$
I guessed that $W_1$.$(W_2x)$ is a concatenation then $(W_2x)...
- 92
0
votes
3
answers
62
views
Methods and knowledge needed for the conversion of $\sum$ and $\prod$ into non-iterative expressions
I think this might be a very broad question, but here it goes.
I have made a formula, using a sigma function, to give the $n$th number in a recursive sequence. I'm trying to make it into a non-...
- 826
1
vote
1
answer
42
views
prove $T(n)=max_{1\leq q\leq n-1}(T(q)+T(n-q))+\theta(n) \\~\\ \Longrightarrow T(n)=O(n^{2})$
let $T(i)$ denote the worst-case running time of QuickSort algorithm on an input of size $i$.
Then, the recurrence for the worst-case running time is given by:
$$T(n)=max_{1\leq q\leq n-1}(T(q)+T(n-q))...
- 329
1
vote
1
answer
56
views
Converting recursive equation into matrices
Here is example of converting fibonacci function into matrices.
Fibonacci sequence defines
$$
f(1)=1
$$
$$
f(2)=1
$$
$$
f(x) = f(x-1) + f(x-2)
$$
It can be converted into matrix
$$
\begin{bmatrix}
1 &...
0
votes
0
answers
32
views
Proof of monotonicty of power functions
For all $x\in\mathbb R$ and $n\in\mathbb Z,$ we define the “nth power $x^n$” recursively by $x^0=1,$ $x^{n+1}=x^n \cdot x.$
a) prove that $f(x) = x^n$ is monotonic on $(-\infty, 0]$ and $[0, \infty).$
...
1
vote
1
answer
401
views
Why is "Turing machine makes no left move" decidable?
We know that every RE language is accepted by Turing machine. And emptiness, finiteness of every RE language is undecidable. My question is how I check decidability "the Turing machine makes move ...
- 1
1
vote
2
answers
161
views
Decidability of DCFL and Undecidability of CFL with respect to regularity
I synced with this Hendrik Jan's answer that to prove undecidability of regularity for CFL is usually obtained from two properties of the context-free languages: (1) they are closed under union, and ...
user976798
0
votes
0
answers
21
views
Prove that divide and conquer for max sub array problem is O(n) if logs and exp are considered elementary(take one unit of time each)
I want to show that if logarithms and exponentials are considered as elementary that the divide and conquer algorithm is O(n) instead of O(n*log(n)) for the max sub array problem. I think it has ...
- 1
0
votes
0
answers
23
views
Divide and Conquer Algorithm comparison operator recursion
given a divide and conquer recursion
\begin{equation}
T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + N
\end{equation}
for $n \geq 2$ and $C_1 = 0$. I want to show that the explicit solution is ...
- 639
0
votes
1
answer
174
views
Divide and Conquer Algorithm for a Grouping Problem
I am trying to understand Divide and Conquer algorithm, I learnt it through the Skyline problem and I was able to understand that quite well, however the below problem is giving me troubles.
I was ...
- 1
0
votes
0
answers
12
views
Find a function 𝑓(𝑛) such that $𝑡_𝑛 ∈ Θ(𝑓(𝑛))$
I have a recurrence equation which is $t_n = -\frac{21}{2} 7^n + \frac{21}{2} 5^n + 10 n \cdot 5^n$.
I need to find a function $f(n)$ such that $t_n \subset \Theta(f(n)) $.
The problem here is ...
- 163
2
votes
0
answers
176
views
Dijkstra's through certain sets of vertices in certain order
I'm stuck on coming up with an algorithm for the following scenario:
Say you run a set of k errands in an area represented by a directed weighted graph G. Each vertex v is a place, and there is an ...
- 75