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

learn more… | top users | synonyms

1
vote
1answer
68 views

$n$-Bit Strings Not Containing $010$

So, I am asked to consider the number of $n$-bit strings that don't contain $010$ by considering the following $m$-leading-zero cases for $m\geq 0$, where $m\in \mathbb{N}$: $1\cdots$ $01\cdots$ ...
0
votes
3answers
147 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 ...
0
votes
1answer
105 views

Paths Within a Lattice

So, I'm reading this proof: Lemma 4.2. The Schröder numbers $(r(n):n\geq0))$ satisfy $$r(n)=r(n-1)+\sum_{k=0}^{n-1}r(k)r(n-1-k)\text{ for }n\geq1,\text{ with } r(0)=1$$ Proof. The Schröder number ...
2
votes
1answer
52 views

help deriving a closed formula for this “magic function”

I'm having trouble coming up with a closed formula for $n$ from the sequence of numbers generated by this function: The following mystery function $M : N \times N \rightarrow N $ is defined by: $$ ...
1
vote
1answer
45 views

Asymptotic Equivalence of Another Recurrence: [duplicate]

So I have the following recurrence relation: $$f(n) = f(n-1) + f(\lceil n/2\rceil)+ 1$$ I already know that: If: $$g(n) = g(n-1) + 1$$ $$g(n) = O(n)$$ If: $$g(n) = g(\lceil n/2\rceil) + 1$$ ...
5
votes
1answer
152 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
-1
votes
1answer
101 views

How to know when to use Dynamic Programming? [closed]

Given any problem, how do I know whether it is solvable using Dynamic Programming? For example: consider the rod cutting problem. Now, how do I know whether dynamic programming will give me an optimal ...
3
votes
1answer
60 views

Recursively Defined Entities

So I am having some trouble understanding how one is to come up with the recursive definition to the following problem... We are given a rectangle of width $2$ and length $n$. Suppose we have ...
5
votes
0answers
96 views

Generating Functions, Recursive Polynomials

At the CMFT international conference in Turkey (2009), the following open problem was given: Show that $$p_n(x):=\sum_{k=0}^n \frac{(n-k)^k}{k!}x^{n-k}$$ has only real simple zeros for every $n$. ...
1
vote
2answers
107 views

Suppose that a recursive routine were invoked to calculate F(4). How many times would a recursive call of F(1) occur?

The definition of a Fibonacci number is as follows: $$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$ Suppose that a recursive routine were invoked to calculate $F_4$. How many times would a ...
-1
votes
3answers
258 views

Show that the limit exists and find it's value? [duplicate]

The Fibonacci series defined recursively by $x(1) = 1, x(2) = 2$ and $x(n+1) = x(n) + x(n-1)$ Find$$\lim_{n\rightarrow\infty}\frac{x(n+1)}{x(n)}$$
0
votes
0answers
45 views

Difference Sets

suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct. We calculate the differences as: $$d=p_i-p_j\mod ...
0
votes
0answers
52 views

Recurrent equations

I'm doing an exercise regarding recurrent equations, by using the Masters theorem, and I don't know how to pick the parameter $b$ from the function written below. The master theorem concerns ...
1
vote
2answers
59 views

Recursion problem help

The following are the teachers example problems. The issue is that I don't understand the exact steps they took to go from $f(0)$ to $f(1)$ to $f(2)$ to $f(3)$. What I'm asking here is if someone ...
1
vote
3answers
57 views

Recursively Defined Functions

I am taking a summer class in discrete math and have done very well up till now. I am nervous because I have reviewed the lecture slides and practice problems but I still don't really understand what ...
1
vote
1answer
220 views

numerically evaluate a continued fraction

I am looking at a continued fraction of the form $$ F_n = \cfrac{1}{1+\cfrac{p_1}{1+\cfrac{p_2}{1+\cfrac{p_3}{1+\ldots}}}} $$ where $p_n$ is a function I know. For simplicity I just take it to $p_n=n$ ...
0
votes
1answer
60 views

Finding in a string S if is possible to create a set with perfect cubes or perfect squares with elements of S.

You have a sequence $S[1...n]$ with $n$ digits(0 to 9) and you wanna know if its possible break then in perfect square or perfect cube. For example, if $S = 1252714481644$, then the answer is $YES$ ...
6
votes
4answers
173 views

Recursive Sequence Tree Problem (Original Research in the Field of Comp. Sci)

This question appears also in http://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. I was told that cross-posting in this ...
0
votes
0answers
148 views

random sample algorithm with m subsets

Suppose we want to create a random sample of the set {1, 2, 3, ... n}, that is, an m-element subset S, where $0 \leq m \leq n$, such that each m-subset is equally likely to be created. One way ...
3
votes
3answers
88 views

Recurrence relation not working as expected

I was dealing with the following recursive formula which had three constants ($k_1, k_2, k_3$) where $x$ would always be an integer: $$ f(x) = \begin{cases} 0 & if x = 1\\ k_1f(x-1) + k_2x + k_3 ...
0
votes
4answers
76 views

Solving a simple ${\cal O}(N\log N)$ recursive equation.

A recursive divide and conquer algorithm runs for input size $N$ in $T(N)$ time where $$ \begin{align} T(1)&={\cal O}(1) \\ T(N)&={\cal O}(1)+2T(N/2)+{\cal O}(N) \\ ...
1
vote
1answer
41 views

Sum count algorithm name

I want to find out what this algorithm is called ...
0
votes
2answers
77 views

Recursive function into non-recursive

I have to express $a_n$ in terms of $n$. How do I convert this recursive function into a non-recursive one? Is there any methodology to follow in order to do the same with any recursively defined ...
2
votes
0answers
125 views

Subtrees of a tree

I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K. for example: If ...
2
votes
3answers
122 views

What does 'i-th' mean?

I have seen a problem set for the tower of hanoi algorithm that states: Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is ...
0
votes
1answer
284 views

Master Theorem change of variables with root other than 2

I'm working on this: $$T(n) = 12T(n^{1/3}) + \log(n)^{2}$$ Using change of variables, and substituting $m = \log n$, I get as far as: $$S(m) = 12S(m/3) + m^{2}$$ I see how a square root would work ...
0
votes
1answer
152 views

Recursive Function for Pyramid-Scheme

consider a group which has 1 user. each month, every user can bring another user to join the group. the user that has been joined for 3 months, should leave the group. calculate the total membership ...
0
votes
1answer
65 views

recurrence relation using master method

I know that the Master theorem is used for the recurrence relations of the form: $$T(n)=aT(n/b)+f(n)$$ In my question, I am supposed to solve the following recurrence relation by using Master theorem: ...
2
votes
1answer
92 views

Application Church-Turing thesis

I would like to give examples of problems which are solvable with an algorithm, for example the function $f$ which maps the tuple $(n,m)$ to the greatest common divisor. This map is recursive. I would ...
6
votes
2answers
152 views

Has anything useful come from Ackermann's Function?

Here is the function: if (m == 0) return n + 1; else if (n == 0) return A(m-1, 1); else return A(m-1, A(m, n-1)); This seems like an interesting ...
1
vote
1answer
114 views

Register Machine on Fibonacci Numbers

This problem is easy to understand but I am struggling to come up with any solutions. According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a ...
0
votes
0answers
45 views

Finding the value of an algebric expression

I have this expression $Ax+By+Cz$ where $x,y,z \geq 0$ and are integers. Suppose I am given a value $T$; I want to find the largest value which is less than $T$ and which cannot be generated by ...
0
votes
1answer
112 views

Recursive Definitions with Converse

I think I know how to solve i. and ii., but not iii: Base Case: $(0,0) \in S$ Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$. (For i and ii): Prove that if $(a,b) \in ...
1
vote
3answers
96 views

HOW TO: Recurrence Relation $T(n) = 2T(n^\frac{1}{2}) + c$

I've been trying to do this for hours. I just don't know how. I'm familiar with recurrence relations in the form of $T(\frac{n}{2})$, but what do you need to do to solve $T(n^\frac{1}{2})$? I've ...
2
votes
2answers
226 views

Recurrence Relation for Strassen

I'm trying to solve the following recurrence relation (Strassen's):- $$ T(n) =\begin{cases} 7T(n/2) + 18n^2 & \text{if } n > 2\\ 1 & \text{if } n \leq 2 \end{cases} ...
7
votes
1answer
93 views

Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$

I'm trying to solve the following recurrence : $$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$ I've tried substituting $n$ for some other variables to transform the above to something easier without ...
1
vote
1answer
62 views

Solving recurrenc using recurrence tree method.

I got this recurrence to solve: $T(n) = 2.1 T(n/2) + n$. I know the answer (got it using the plug and chug method and using the master method too), but I'm trying to solve using recurrence tree and ...
2
votes
0answers
96 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: $g(1) = \alpha;$ $g(2n+j) = 3g(n) + γn + β_j$ : j = 0,1 and n >= 1 I have assumed the closed form to ...
0
votes
2answers
55 views

Equation of a curve whose difference in ordinate values form an arithmetic sequence

I have the following recurrence equation that I have obtained while trying to solve a problem:- $$T(0) = 1$$ $$T(n) = T(n-1) + 9n - 8: n \ge 1$$ The values of $T(n)$ for $n = 0,1,2,... $ are as ...
1
vote
1answer
127 views

Generalized Josephus problem

I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as f(1) = a f(2n) = 2f(n) + b, for n >= 1 f(2n+1) = 2f(n) + y, for n >= 1 ...
2
votes
2answers
114 views

Recursive algorithm correctness: problem.

Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
0
votes
0answers
344 views

How to find integer solutions of an equation using approximation methods?

If I have a function called $f(x)$ that have several roots, integers and not integers. How can I find just the integer ones by approximations methods? A simple example would be ...
2
votes
1answer
75 views

Quadratic Forms and Newton's Method

Consider the function $f(x,y) = 5x^2 + 5y^2 -xy -11x +11y +11$. Consider applying Newton's Method for minimizing $f$. How many iterations are needed to reach the global minimum point? Why should ...
1
vote
1answer
77 views

How do I determine if two of my software's representation of algebraic numbers are equal?

I have software which stores information about algebraic numbers with absolute precision. If you build it up by creating instances of a Python representation of an integer, float, Decimal, or string, ...
1
vote
0answers
62 views

How to deduce the results of response time by this trajectory approach?

First, we denote this: And And we get this right property( $last_i$ means the last node on $τ_i$): And: $Smin_i^h$ = $\sum_{h'=first_i}^{h-1} ({C_i^{h'} + L_{max})}$ $Smax_i^h$ = ...
2
votes
3answers
70 views

Divide et impera recurrence, why induction does not work?

$$ T(n) = T\left(\frac n2\right) + 2^n $$ where $n \ge 1$ and $T(1) = 1$. If I understand the substitution method and the induction, I can guess that $T(n) = O(2^n)$. I must prove that $T(n) = ...
0
votes
1answer
40 views

Identify Type of Recursive Sequence?

I would love to learn techniques for solving the following, but I can't seem to identify this type of sequence: let $N > 0$ and let $k$ be an arbitrary positive integer between $0$ and $N-1$ ...
0
votes
0answers
117 views

how to solve the following recurrence $T(n) \leq 2c (\lfloor \frac{n}{2} \rfloor + 17) \log (\lfloor \frac{n}{2} \rfloor + 17) + n$.

The title is pretty much self-explanatory. I don't think I have the necessary math skills to solve the recurrence. Thanks in advance. Edit: My question is how to simplify $ ... \log (\lfloor ...
2
votes
2answers
304 views

Convergence of a Recursive Sequence - An Example

Consider the sequence $\displaystyle x(k+1) = \frac{1}{2}\left(x(k) + \frac{a}{x(k)}\right)$ where $x(k)$ stands for the $k$th term of the sequence. What does this process converge to, and what is ...
2
votes
0answers
94 views

Recursive Sequence from Finite Sequences

I'm searching for the name of these kind of sequences: Suppose you start off with a finite sequence containing one term: S0 = {3} To get the next sequence you ...