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

learn more… | top users | synonyms

1
vote
1answer
95 views

Finding previous term in sequence

I'm afraid this problem fits more to stackoverflow, but maybe it fits also here. For a given $F_n$ (but we don't know $n$) find $F_{n-1}$, knowing that $\forall_{n>1}F_n=F_{n-1}+F_{n-2}$. Also ...
1
vote
1answer
156 views

Divide and conquer - Algorithm MYST

i am trying to understand the following algorithm. It is a divide and conquer algorithm, which sorts a given array, but can someone help me to understand the idea of this algorithm. What is the ...
0
votes
6answers
298 views

Obtain the formula for the following sequence

I can't seem to figure out how to find an algebraic formula for the following sequence of numbers. $$0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0$$ Can somebody ...
0
votes
1answer
4k views

Convert Recursive to Closed Formula

I got a particular sequence defined by the following recursive function: $$T_n = T_{n-1} \times 2 - T_{n-10}$$ I need help converting it to a closed form so I can calculate very large values of n ...
0
votes
3answers
551 views

Recursive sequence - Convergency and Limit

i just started university so im pretty new to all this new math. My problem is to solve this recursive sequence: $a_{n+1} = a_{n}^3$ with: $a_{0} = \frac{1}{2}$ ...
0
votes
1answer
606 views

calculating matrix rank with gaussian elimination

[The answer to my problem has been found: it was a simple sign error. the pseudo code below is fine] I have implemented an algorithm in c++ that should calculate the matrix rank of a given n x m ...
3
votes
0answers
410 views

When do floors and ceilings matter while solving recurrences?

I came across places where floors and ceilings are neglected while solving recurrences. Example from CLRS (chapter 4, pg.83) where floor is neglected: Here (pg.2, exercise 4.1–1) is an example ...
3
votes
3answers
3k views

What is the bound of : $ T(n)=T(n-2)+\log(n)$?

Given : $T(n)=T(n-2)+\log(n)$ I need to find the bound for the above recurrence . So: $$\begin{align*} T(n-2)&=T(n-2-2)+\log(n-2)\\ &=T(n-4)+\log(n-2)\\ T(n)&=T(n-2)+\log(n)\\ ...
0
votes
1answer
205 views

How to get the recursive formula of a problem?

I am trying to understand a problem im reading and produce a recursive formula for the problem. The problem, an ice cream van can serve j^2 customers at a time, However the van needs time to make new ...
2
votes
1answer
825 views

Stepping through the Josephus problem

I'm trying to figure out how the math in the Josephus problem works exactly. I first heard of it for programming purposes so that's where my focus has been. The formula does seem to be recursive from ...
2
votes
1answer
183 views

What kind of recursion or series is this?

I am developing a language learning program, and would like to know the mathematical expression and description for what I have (perhaps incorrectly) calling a recursive series method of learning the ...
1
vote
2answers
74 views

Subsets of $\{1, 2,\ldots, n\}$ which add up to $n$

Problem: Given a number $n,$ we want to find out the subsets of $\{1,2,\ldots,n\}$ that add up to the given number $n.$ Example: If $n=6,$ then the output is: $\{1,5\}, \{2,4\}, \{1,2,3\}.$ ...
1
vote
0answers
165 views

Panjer Recursion and Expectation

Given a Panjer Recursion set up, with the usual properties, and supposing now that $N$ has a Poisson distribution with mean $\lambda$. How can we derive a recursion for $E(S^k)$ where $S$ be the ...
0
votes
0answers
75 views

Calculate pairing in a rotational system

I'm not even sure how to word this question. So I'll explain it out. I've got these values: A1, A2, B1, B2, B3, C1, C2, I need each A to be paired with each B and C each B with each A and C ...
6
votes
2answers
2k views

Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is ...
2
votes
3answers
636 views

Prove algorithm correctness

I'm wondering if there exists any rule/scheme of proceeding with proving algorithm correctness? For example we have a function $F$ defined on the natural numbers and defined below: ...
2
votes
1answer
307 views

To officially be recursion, must there be a base case?

In this Python code, the function f is defined, which then immediately calls itself: def f(): f() It's not very complicated, the first line defines the ...
7
votes
3answers
1k views

Solving a Recurrence Relation/Equation, is there more than 1 way to solve this?

1) Solve the recurrence relation $$T(n)=\begin{cases} 2T(n-1)+1,&\text{if }n>1\\ 1,&\text{if }n=1\;. \end{cases}$$ 2) Name a problem that also has such a recurrence relation. The ...
1
vote
3answers
2k views

Solving recurrence relation $T(n) = 2T(n - 1) + \Theta(n)$ using the recursion tree method

I am trying to solve this recursive relation using the recursion tree method: $T(n) = 2T(n - 1) + \Theta(n)$ with $T(0) = \Theta(1)$. The answer is $T(n) = 2^n*{\rm constant}_2 + (2^n - 1)n + ...
3
votes
2answers
99 views

recursive relation with sequences

I am not sure how to properly do this question but I am told that the solution I came up with is wrong and I dont see how...I basically used algebra and plugging of variables and rearranging ...
0
votes
2answers
143 views

recursion question

I just need a hint to solving this question or a starting point because I am totally stuck...I don't really understand how I can prove this. It doesn't seem possible to me that different applications ...
2
votes
1answer
146 views

Test machine usage

A real problem from the hospital. Suppose we have $n$ blood samples to test HIV. We don't want test them one by one, since the cost is huge and most people don't have a positive result. So we try to ...
0
votes
1answer
258 views

recursive algorithm design

A question about recursive algorithm design. Let A be a set of n items. The only operation available to you is "compare(x,y)", which returns "ture" if x = y and "false" otherwise. An item is said to ...
2
votes
1answer
421 views

Finding General Expression from recursion

I am trying to find a general expression from a recursion. Here it goes: $(x+i)P_i = (i+1)P_{i+1} + \frac{x}{2} P_{i-1}$ $i$ goes from $0$ to $S$. How can I calculate a generic $P_i$ in terms of ...
3
votes
2answers
239 views

Can this be solved by induction? (number of ways of cutting a rod into pieces)

I am reading an algorithm example. The example is about Rod cutting. The idea is that a steel rod can either be sold as it is, or be cut into integral pieces and ...
-2
votes
4answers
3k views

Factorial Function - Recursive and iterative implementation

I have the function: n! = n*(n-1)*(n-2)...* 3 * 2 * 1 Which I need to sketch an implementation recursively and iteratively. Could anyone point me in the right ...
5
votes
3answers
7k views

Worst case complexity of the quicksort algorithm

Good evening, I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm, for a given number of elements. This is part of ...
4
votes
1answer
704 views

Applying a Math Formula in a more elegant way (maybe a recursive call would do the trick)

This is my first post in Math section. I've been redirected here from StackOverflow, users from there suggested me to ask here. This could appear a little bit complex at first sight but afterall ...
2
votes
3answers
2k views

Recurrence equation $T(n)=3T(\sqrt{n}) +1$

I need to find an exact solution to the following recurrence using substitution (change of variables). $$ T(n) = 3T(\sqrt{n}) + 1, \quad \text{ when } n > 2, $$ and $$ T(2) = 1 .$$ I can't get ...
2
votes
1answer
367 views

Solving recursion with 2 parameters

How do i solve a recursion like this: $c_{i,j} = c_{i,j-1} + c_{i-1,j}$ with $c_{i,0} = c_{0,j} = 1$ After one step it can be written as: $c_{i,j} = c_{i,j-2} + 2c_{i-1,j-1} + c_{i-2,j-1}$ which ...
1
vote
2answers
546 views

The first four terms x, y, z, w of an arithmetic sequence

I have been attempting this question for the past 3 days with no luck: ...
2
votes
1answer
491 views

Balancing weights with weights

We have a collection of items of weight $d_i$, $$d_1, d_2, ..., d_k, \quad k \le 100$$ where some of the weights may be equal. Let $$ n = \sum_{i=1}^k d_i $$ I need to figure out quickly if this ...
2
votes
1answer
102 views

Recursion with non-equal exponents

This is my first question on this site... yesterday I asked this on cs.so but they downwote and told me that so.cs is a research-level site, not for students... I hope it's appropriate to ask this ...
0
votes
2answers
85 views

Finding optimal path for evaluating expressions

I am creating a program which needs to do the following: I have equations like the following and based on the input I get I should able to calculate the values of $x$, $y$ and $z$ $$x = a + b$$ $$y ...
2
votes
1answer
69 views

Incomplete “round trip” of taking a minimum, then a maximum, from a positively skewed distribution

Let's say you have a distribution that is either symmetric or positively skewed (and defined over 0-1). Call it F. Then, you find the distribution of the minimum of n>1 draws from F. Call it Fmin. ...
2
votes
1answer
69 views

How to prove that all the $a_i$ will be the same after inf operations?

Given some real number :$$a_1,a_2,...,a_n$$Every time I chose two of them $a_i$ and $a_j$ and set both of them to $\frac{a_i+a_j}{2}$. Now I have operated $T$ times,when $T$ is infinite,I guess that ...
1
vote
1answer
53 views

Finding a recursive function for a problem

I have a homework assignment to find a recursive function for $k(n)$ where $k(n)$ is the number of ways to split the set $\{1,2,3,4....n\}$ while not having any subset contain more than two elements. ...
1
vote
1answer
3k views

Is it possible to make the Breadth First Search Algorithm recursive?

I'm a student an I see the BFS Algorithm for graph exploration. I see the DFS algorithm too and this one is easily thinkable in a recursive mode. But is it possible for the BFS? Thanks.
2
votes
1answer
142 views

Cooley-Tukey FFT with arbitrary radices

The radix-2 FFT using Cooley-Tukey utilises two interleaved transforms of length $N/2$, and you can see near the bottom of that section that we can find the second half of the original transform by ...
2
votes
3answers
87 views

how many times will a function print to the console?

I have the following snippet: public Foo(int n) { for (int i=0; i<n; i++) { new Foo(i) } console.writeln("?") } For a given $n$, how ...
1
vote
3answers
478 views

How do I find the inductive definition of the set defined as $\{2n+3m+1|n,m\in\mathbb N\}$?

$\lbrace 2n+3m+1:n,m\in N\rbrace$ is the set of all positive integers except for $0$ and $2$. I need to know how to write its inductive definition. This is part of the introduction on learning how to ...
4
votes
0answers
174 views

Fractional iteration of the Newton-approximation-formula: how to resolve one unknown parameter?

For my own exercising I tried to find a closed form expression for the Newton-approximation algorithm, beginning with the simple example for getting the squareroot of some given $ \small z^2 $ by ...
2
votes
2answers
501 views

Analysis of algorithms and recurrence relations

Suppose that the function of the time of execution of some recursive algorithm is given by a recurrence relation of order $n$. Let $$p(x)=0,$$ with $p(x)$ a polynomial of degree $n$, the corresponding ...
8
votes
3answers
746 views

Karatsuba vs. Schönhage-Strassen for multiplication of polynomials

I am wondering how to most effectively multiply two polynomials with several 100's of coefficients, each coefficient having 1000-2000 decimal digits. I know Schönhage-Strassen begins to outperform ...
3
votes
4answers
2k views

Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed

Update: This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution. http://www.youtube.com/watch?v=VbSwwos4R2E Hi, I ...
3
votes
1answer
202 views

Nesting functions to understand nesting series

So I am working on a problem that involves an expression that has a "nested" sigma notation. Maybe "nested" isn't the correct word, because you start with an input (of your choosing) and the output ...
1
vote
1answer
505 views

Adding and Multiplying Polynomials Recursively

What theorem can be used to recursively multiply two polynomials together? Is there another theorem that uses recursion to add together two polynomials recursively? I'm looking for something that ...
6
votes
3answers
5k views

Using Horner's Method

I'm trying to evaluate a polynomial recursively using Horner's method. It's rather simple when I have every value of $x$ (like: $x+x^2+x^3...$), but what if I'm missing some of those? Example: ...
1
vote
2answers
784 views

Recursive method to evaluate a polynomial

I want to find a recursive way of evaluating any polynomial (I'm given the polynomial, and a value for x, and I need to replace the x in the polynomial with the value). The polynomial can be anything, ...
1
vote
1answer
331 views

Recursive coefficient of determination (R2)

Is there a way to compute the coefficient of determination $R^2$ in a recursive way? $R^2$ is defined as following: $$R^2 \equiv 1 - \frac{SS_{\rm err} }{ SS_{\rm tot}} = 1 - \frac{\sum_i (y_i - ...