# Tagged Questions

Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

59 views

### A long strip of paper

A strip of paper has $1024$ units in length and one unit wide, divided into 1,024 unit square. The strip is folded repeatedly. The first fold is done such that the right edge coincides with the left. ...
56 views

### Pile of $2000$ cards

A pile of cards $2000$ is labeled with integers from $1$ to $2000$, with different integers of different cards. The cards in the pile are not in numerical order. The top card is removed from the pile ...
342 views

### Recursive number digits power n sum => is there a limit of unique result numbers found?

Say you have a number xyz and you choose to split it to digits, take a power of each digit to three and summarize them. Some numbers gives same result than the original number, for example: 153 = 1^3 ...
310 views

59 views

152 views

### Recursive fibonacci algorithm correctnes? [proof by induction]

im studying for the computer science GRE, as an exercise i need to provide a recursive fibonacci algorithm and show its correctness by mathematical induction. here is my recursive version of ...
117 views

### Filling the plane with a sequence

I am not sure if this is the right stack to ask this question, but since there is a definite fractal dimension to it, I thought I'd give it a go. The problem I am facing is one of calculating an ...
420 views

### Solving recursive relations using matrix method.

I am looking to solve the recursive relation $P_n=2P_{(n-2)}+3P_{(n-3)}+7P_{(n-7)}$ using the matrix method. The matrix method solves the recursive relation in ...
84 views

### After $n$ iterations of the continued fraction algorithm, what kind of rational numbers will have terminated?

For a positive real number $r_0$, we have the continued fraction recursive algorithm: \begin{align} &r_n\in\mathbb{Z}\implies\text{terminate the algorithm}\\ &\text{else } r_{n+1} = \frac{1}{...
507 views

### Recursive formula for subset sum?

Wikipedia describes an algorithm for the subset sum problem which runs in time $O(2^{\frac{n}{2}})$. It works by dividing the set in half once, computing all the sums in each half (cleverly presorted)...
158 views

### Algorithm analysis

Consider a recursive Mergesort implementation that calls Insertion Sort on sublists smaller than some threshold. If there are n calls to Mergesort, how many calls will there be to Insertion Sort? ...
236 views

323 views

### (CHECK) $n$-bit Strings Containing a Pattern

$$\text{\bf{PLEASE~~~CHECK~~~AUTHOR'S~~~ANSWER}}$$ If $S_n$ denotes the number of $n$-bit strings that do not contain the pattern $00$, then what is the underlying recurrence relation and initial ...