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

learn more… | top users | synonyms

-1
votes
0answers
11 views

Projection functions are representable in Axiom System Q [on hold]

Wish to prove that the projection function is represented in Q by the formula ($x_{1}$= $x_{1}$) & ($x_{2}$= $x_{2}$) & ... & ($x_{k+1}$= $x_{i}$). Basically have to show 2 conditions: If ...
0
votes
0answers
15 views

Seemingly-random algorithm for generating fictional static objects on a real-world map?

I'm a software engineer building a mobile game which uses geo-location and a real-world map. As the user moves around in the real world, the map display moves around following them, and displays ...
-4
votes
1answer
37 views

Find a recursive algorithm to find $a^{2^n}$

Edit1: Used Latex. =] Edit2: Thanks for the guidance to the users below. Really helped me out editing the post and guidance on the math problem. The question gave me a hint: $a^{2^{n+1}} = (a^{2^n}) ...
1
vote
0answers
49 views

Let A[1..n] be an array of numbers. [on hold]

Let A[1..n] be an array of numbers. To find the largest number in A, one way is to divide A into two halves, recursively find the largest number in each half, and pick the maximum between the two. ...
7
votes
6answers
567 views

Non-literal applications of “Shortest Path” algorithm?

It's obvious that it's used in stuff like Google Maps, but what are some more metaphorical applications where you're minimizing the path between nodes (which can represent anything)
-2
votes
1answer
34 views

How should I proceed to solve this recurrence relation: $T(n) = T(n - 1)^2$

I tried to solve this recurrence relation, but I was confused when I had to determine the pattern. $$ T(n) = \begin{cases} 3, & \text{if }n = 0 \\ T(n - 1)^2, & \text{if }n > 0 \end{cases} ...
3
votes
0answers
32 views

Four for loops in Matlab — optimize for speed

Let $s$ be a constant integer. I am computing a four dimensional matrix $A$ of size $(s+1)^4$ with entries in $[0,1]$. For this computation we use a three dimensional matrix $B$ of size $(s+1)^3$ with ...
1
vote
0answers
42 views

Chaining recursive functions

$T(0,r) = k$ $T(n,r) = k + T(n-1,r) + T(n-1,r+1)$ $T(n,0) = k + T(n-1,0) + T(n-1,1)$ $T(n,1) = k + T(n-1,1) + T(n-1,2)$ $T(n,2) = k + T(n-1,2)$ $T(n,3) = k$ Compact: $T(n,0) = k' + T(n-1,0) + ...
0
votes
1answer
29 views

$T(n) = 2T(n/2) +n\log n$ - Algorithms

According to this http://en.wikipedia.org/wiki/Introduction_to_Algorithms $T(n)=2T(n/2)+n\log n$ is not case 3 of Master Theorem, can someone explain me why? And which case of master theorem it is?
0
votes
0answers
27 views

How can I find the height of the Recursion Tree?

How do I determine the height of a Recursion tree? For example for the recursion $T(n) = 3T(\frac{2n}{3}) + O(1) $. Could you give me a hint?
1
vote
1answer
100 views

Solving the recurrence relation $T(n) = T(n-\sqrt n) + 1$

I have an algorithm that at each step can discard $\lceil\sqrt(n)\rceil$ possibilities at a cost $1$. The solution to the recurrence relation below is related to the question of complexity of such ...
0
votes
1answer
5 views

How to calculate rental income of an appreciating property?

I'm trying to calculate the total rental income I might receive over 25 years. The rent is 5% of the property value, which is initially £300k. If the property itself increases in value by 3% per year, ...
0
votes
1answer
17 views

how to write a recursive definition

so the question asks to define s(n) as the number of strings of a's b's and c's of length n that do not contains "aa". write a recursive definition for s(n). what is s(0),s(1),s(2),s(3). i had to ...
1
vote
1answer
59 views

Combinatorial Proof of Identity

How do I build a combinatorial proof of the following recursion: $$\binom {n}{k} = (k+1)\binom {n-1}{k}+(n-k)\binom {n-1}{k-1}$$ I'm having really big difficulties in finding the right way to ...
3
votes
1answer
35 views

$n$th term of a recursive formula

I have a formula $$ 1 + px + \dfrac{p(p-1)}{1*2}x^2 + \dfrac{p(p-1)(p-2)}{1*2*3} x^3 $$ can someone please tell me what the formula is for the $n$th term of this recursive definition ? Do I have to do ...
2
votes
0answers
42 views

Proof relating to Euclidian Algorithm

The question is as follows: (1): Let m and n be positive integers with n < m and let r be the remainder when m is divided by n. Prove that $$r < \frac m2$$ (2): The Euclidean Algorithm for ...
-1
votes
0answers
34 views

Checking if integer solutions exist

I have a linear equation $\alpha_1a_1+\alpha_2a_2+\dots=\beta$. I only need to check is there exists α1,α2... such that all are greater than or equal to zero. I am a computer science student , i got ...
1
vote
0answers
58 views

Solving a Recurrence Relation With Summation and Tau Function

How can I solve the following: $$ T(n) = \sum_{i = 1}^{d(n) - 2}T(v_i) + \sum_{i = d(n) - 1}^{n - 1}c + c' $$ Where $d(n)$ is the Tau function, and v is the set of values dividing n. e.g. $d(18) = ...
2
votes
0answers
20 views

Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
1
vote
2answers
42 views

Solving this recurrence relation

Hi all I'm preparing for a midterm and the following appeared as a practice problem that I'm not quite sure how to solve. It asks to find a tight bound on the recurrence using induction $$ {\rm ...
3
votes
0answers
80 views

What is this method of dividing a plane called?

I have an idea of a method for recursively dividing a plane, and as I'd like to do more research about this algorithm and the set of points that it produces, I'd like to know what it's formally known ...
0
votes
0answers
23 views

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
1
vote
1answer
47 views

Cyclic tower of hanoi problem [duplicate]

If I have 3 rods in a circle and it is allowed to move the disks only in the clockwise direction. How many moves is necessary to move n disks from first rod to the third rod?
1
vote
2answers
43 views

Calculate a recursive equation in terms of theta

I am struggling with the following equation for one week! Please help me solve it. $$T(n)=T(\frac{n}{2})+\frac{n}{logn}$$ So far, I have come to the equation $T(n)=\Sigma \frac{2^x}{x}$
0
votes
1answer
58 views

Quadratic Map Solution

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence ...
0
votes
0answers
5 views

How to formally describe indirect partial derivatives with two paths

Assume I have two functions like this: $y = \frac{1}{2}(o-x)^2\\o = kx$ Now, I want to calculate $\frac{\partial y}{\partial x}$ using the chain rule, i.e. like this: $\frac{\partial y}{\partial x} ...
2
votes
1answer
116 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
1
vote
1answer
39 views

Transfer a program into a logarithm formula

I have been thinking what is the math formula for the piece of code I wrote below. Assume there are B, D and F three positive integers, and D is smaller than F. Given D and F, the value of B would be ...
2
votes
0answers
21 views

Recursive and Recusively enumerable

{1^n | n finite integer and >1}, is this language recursive? I'm not sure how to prove that a language is recursive, I only know that there should be a TM that accepts any finite input and then ...
0
votes
1answer
19 views

Recursive Algorithm Analysis

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$ I have been trying to solve this question but I could not find anything. My approach: $n = 2^k$ $S(k) = T(2^n)$ and $S(k/2) = ...
0
votes
0answers
51 views

Inventory Control using Dynamic Programming

I am trying to solve a traditional inventory control stochastic dynamic programming problem where \begin{align} x_{k+1} &= x_k + u_k - w_k\\ w_{N-1} &= \begin{cases} 0 &\text{w.p. } ...
1
vote
1answer
20 views

What is the link between the quotient and the Bézout coefficients in the Extended Euclidean Algorithm?

Here is an image from the wikipedia page of the EEA for working out the Bézout coefficients for 240·sk + 46·tk = rk where rk = GCD(240,183): What I am trying to work out is what si and ti ...
0
votes
0answers
27 views

How to define this f(n) (something about recursion)?

Consider this: $$best(n)=\begin{cases}1 & \text n=1,\\2*best(n-i)+2^i-1 & \text otherwise,1<=i<n\end{cases}$$ That is, when $n>1$, for each $i$ among $[1,n)$, there must be at least ...
2
votes
1answer
59 views

The Matrix Inversion Lemma: the General Case

I find it is hard to understand the application senario of the Matrix Inversion Lemma in non-special cases. Suppose I already computed $A^{-1}$ and want to find $\left(A+UCV \right)^{-1}$. The Matrix ...
0
votes
0answers
44 views

Why can I not generalize O(n^log5) for squaring matrice of size n

I have a question that is bugging me for around a 3 days, I first asked this question in stackoverflow but no one could answer it reasonably though they tried to help, so finally I found here as a ...
0
votes
1answer
14 views

Recursively calculate grand total

Starting January, I have a value of 2.5. Each month I add 2.5. I believe that I = Prt will tell me the final value in December, but I need the running total. Ex: ...
1
vote
1answer
29 views

Multiplication cannot be obtained from zero, successor, and identity by composition without recursion

The task is to show that multiplication cannot be obtained by zero, successor, or identity functions by composition without using recursion at least twice. I'm primarily confused because it doesn't ...
0
votes
1answer
61 views

Show that $gcd(x,y)$ and $z = lcm(x,y)$ is primitive recursive

For the $gcd(x,y)$ we note: $gcd(x,0) = x$ $gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y)))$ $succ(x)$ and $mod(x,y)$ are both primitive recursive, so $gcd(x,y)$ must be as well. $z = lcm(x,y)$ if ...
1
vote
1answer
48 views

Find coefficients of polynomial that has zeros at certain points

Given a list of values z0, z1, ..., zn-1 (possibly with repetitions), show how to find the coefficients of a polynomial P(x) of degree-bound n + 1 that has zeros only at z0, z1, ..., zn-1 (possibly ...
1
vote
0answers
16 views

Determining the optimally scoring move on a probabilistically represented 2D grid in real time

I'm posting this to StackOverflow, cstheory.stackexchange.com, and math.stackexchange.com because I'm not really sure where it fits best. I hope that's OK. I have a 2D grid (size varies per map, ...
1
vote
3answers
92 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
4
votes
5answers
564 views

Where do the first two numbers of Fibonacci Sequence come from? [duplicate]

I'm trying to code a simple algorithm that prints out the $n^{th}$ Fibonacci number. However, my program requires the initial seed values $F_0 = 0$ and $F_1 = 1$, when I'm hopeful I can figure ...
0
votes
3answers
31 views

A closed form for the recursion?

Let $x$ and $y$ be real numbers and $x < y$ Given the recursion: $m_0 = \frac{x+y}{2}$ and $m_1 =\frac{m_0+ y}{2}$, so in general, $$m_i = \frac{m_{i-1} + y}{2}$$.. What is $m_{\infty}$? thanks ...
0
votes
1answer
24 views

Time complexity of indirect recursion

How to find the complexity of an the given algorithm: Algorithm f(int n) { if(n==1)return(1); else { f(n-1)+g(n-1); } } Algorithm g(int n) { ...
0
votes
0answers
71 views

Find all possible paths in a Matrix

I'm looking for algorithms to find all paths in a 4 x 4 matrix. The rules are as follows You can move in any direction (up, down, left, right, and diagonally) The next square in the path must be a ...
2
votes
1answer
69 views

Solve the recurrence relation:$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\sqrt{n}$ [closed]

I have doubt in solving the following questions: $T(n)=2T(\sqrt{n})+n$ $T(n)=\sqrt{n}T(\sqrt{n})+c$ $T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$ T(2)=1 for all the problems Atleast give the final answer.
1
vote
1answer
65 views

How to show this algorithm on positive semidefinite matrices converges to a global maximum determinant

I'm dealing with an algorithm which is supposed to converge to the maximum determinant of certain positive semidefinite matrices. The problem is that we have such a matrix, and we vary certain ...
4
votes
3answers
157 views

How does $\tbinom{4n}{2n}$ relate to $\tbinom{2n}{n}$?

I got this question in my mind when I was working on a solution to factorial recurrence and came up with this recurrence relation: $$(2n)!=\binom{2n}{n}(n!)^2$$ which made me wonder: is there also a ...
1
vote
1answer
73 views

Help with Recursive Algorithm

We are to determine a recurrence relation for a recursive algorithm. Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person ...
1
vote
1answer
75 views

What's a useful recurrence relation for $(2n)!$ in terms of $n!$?

I want to make an algorithm for $n!$ which will divide the number in half and call the algorithm again until n is so close to $0$ that a value of $1$ can be safely returned, and use the value of each ...