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

learn more… | top users | synonyms

3
votes
2answers
98 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
140 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
251 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
406 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
232 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
700 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
363 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
526 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
457 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
101 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
466 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
170 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
495 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
735 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
197 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
501 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
757 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
330 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 - ...
0
votes
1answer
139 views

Can I write this series as a recursive function

I've been given the task of computing two series programmatically one is of the form: $ 1 + \frac{1}{2} +\frac{1}{3}+\frac{1}{4}...+ \frac{1}{n} $ The other one is an estimation for $\pi$ which is ...
7
votes
2answers
930 views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
1
vote
2answers
229 views

Homework question dealing with recursion

I need help with this recursion question:
0
votes
2answers
218 views

$f(x) = f(x-1)*b \to f(x) = c_1 b^{x-1}$

I'm trying to teach myself mathematics. I only started last year with a previous knowledge of basic arithmetic. I often make a detour into regions featuring problems that are a bit too deep for me. ...