Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
1,354
questions
0
votes
0
answers
27
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
36
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
213
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
6
votes
2
answers
222
views
What is the set generate by ${1}$ and a function $1/(a+b)$?
If I'm given a starting set, and an operation, what would the generated set looks like?
Here we take $S_0=\{1\}$ and $f(a,b) = \dfrac{1}{a+b}$ as an example, the following Mathematica codes shows the ...
- 465
1
vote
1
answer
24
views
Does my proof that the recurrence $T(n) = T(\frac{n}{2}) + d = \Theta(lgn)$work?
Suppose we have the recurrence
$T(n) = T(\frac{n}{2}) + d$ if $n = 2^j$ and where is some integer greater than $0$ (i.e n is even). I know that this recurrence is $\Theta(lg(n))$, and I want to prove ...
- 496
-1
votes
1
answer
62
views
Division algorithm proof intuitive [closed]
The following algorithm can be used for division. Can someone intuitively explain or offer proof that quotient returned from recursive call (say q') is such that ...
- 81
0
votes
0
answers
28
views
Understanding base cases of inductive proofs in algorithm analysis Cormen et al
I am currently working through Cormen et al's classic book on algorithms and data structures. I am trying to follow an inductive substitution proof that the following time complexity function is $O(n\...
- 496
0
votes
1
answer
52
views
Telescoping recursive term ${D(h) = D(h-2)+1}$
In the context of Computer Science, I am trying to calculate the maximum depth difference between leaf nodes in any existing AVL-Trees of height $h$. I don't think any knowledge of AVL trees is needed,...
- 342
0
votes
1
answer
28
views
Fast algorithms for computing $AGA^T$ with $G$ PSD symmetric.
Problem:
In the context of decision making in some optimization problems, I found that it is meaningful to compute $AGA^T$ with $A\in\mathbb R^{m\times n}$ and $G\in\mathbb R^{n\times n}$ a PSD ...
- 6,076
2
votes
2
answers
94
views
3d fractal helix modeling
I'm trying to build a 3d visual to illustrate a concept. Imagine a circular helix. We could define a cylinder that contains that helix. But now imagine this cylinder takes the helicoïd shape too ! We ...
- 23
1
vote
0
answers
128
views
How do I convert my recursive algorithm to an explicit formula? [closed]
I have the recursive formula:
\begin{align}
x_1&=1-\frac{1}{e} \\
x_{n+1}&=1-(1-x_n)^{1/x_n}
\end{align}
Is there any way to write this as an explicit formula? I've tried writing the exact ...
- 11
-1
votes
1
answer
61
views
Divide and conquer algorithm problem applied to an n x n-matrix of n players competing in a chess tournament [closed]
A total of n players have competed in a chess tournament. In particular every pair of players i and j played one single game. All results of the tournament are encoded in a n × n-matrix A, where for ...
- 27
1
vote
1
answer
52
views
What is the pattern and the solution to this system of equations?
I would like to find the general solution to the following system of equations:
$$ x_1 + k_1 + \sum_{i=1}^N A_{1,i}x_i=0 $$
$$ x_2 + k_2 + \sum_{i=1}^N A_{2,i}x_i=0 $$
$$\vdots$$
$$ x_N + k_N + \sum_{...
0
votes
1
answer
104
views
Expressing a Recursive Sequence in a Non-Recursive Form
I am working on a recursive sequence and wondering if it's possible to convert it into a non-recursive form. The sequence is defined as follows:
$$ a_n = a_{n-1} \times (n + 1) + n! $$
with the ...
- 81
0
votes
0
answers
26
views
Recursive function with a one integer parameter
I am trying to come up with a recursive function which takes a single integer as a starting value. Just a single example is provided and initial value is 9. Example is as follows:
Input:
9
Output:
...
- 1