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

learn more… | top users | synonyms

0
votes
0answers
6 views

Spin-off of Scheduling Weighted Interval Problem

I'm trying to solve a problem in which, given a + sign shaped area of land (with no width) and a list of contiguous sections of the land (segments, T-shapes, smaller + shapes, etc), each with an ...
3
votes
1answer
22 views

Proving a recursive algorithm on a set is true

If I have an algorithm that returns the entry of a set with the largest value, how do I prove the algorithm is true mathematically? (I know I could just write tests for it.) I understand how to use ...
-3
votes
6answers
74 views

How to get a Recursive Definition for $3n^2$? [on hold]

How to get a Recursive Definition for $3n^2$? Any help would be great:
0
votes
0answers
11 views

Recursive relationship for Peano Baker Series

The Peano Baker Series is a integral has the following form $$\varPhi(h,0)=I+\intop_0^h G(t_{1}) \, dt_1 + \intop_0^h G(t_1) \intop_0^{t_{1}} G(t_2) \, dt_2 \, dt_1 + \intop_0^h G(t_1) ...
0
votes
1answer
13 views

Find a shortest way between nodes in graph

I have a next structure : Each node in graph may have more than 2 links. I want to find a shortest way with node 1 and 13. ...
-4
votes
1answer
41 views

Edited-How can I solve polynomial recurrences like $f(n+1)=\frac{2f(n)}{f(n)+1}$

Can anybody tell me the systematic way of solving this recurrence. $$f(n+1)=\frac{2f(n)}{f(n)+1}$$ I looked over the internet, but could not find the answer. Thanks {Edit- I am sorry, previously I ...
-1
votes
0answers
17 views

Moving part of the sequence to fit a function. [closed]

The sequence $s(k)$ where $k=1,2,3....$ satisfies the recursion $s(n)=s(n-2)+s(n-3)$ for $n\geq 4$. If $s(n)$ is rewritten in the form $$s(n)=s(n-1)+S(n_0,n_1,\dots)$$ where $S(n_0,n_1,\dots)$ is ...
1
vote
1answer
18 views

Uniqueness of abelian group structure on a given set and recursive algorithms

If we have some function $f$ under $\mathbb{Z}$ and $$f(a, f(b, c)) = f(f(a, b), c)$$ $$f(a, b) = f(b, a)$$ $$f(a, 0) = a$$ $$f(a, -a) = 0$$ meaning $f$ is an abelian group with an identity element of ...
1
vote
1answer
23 views

How page rank relates to the power iteration method

I do not see how pageRank relates to the power method. Since for the pageRank we are looking for the steady stable state (vector) for a Markov (transition) matrix and the matrix has already an ...
0
votes
0answers
23 views

Round robin match location algorithm

Although this is a software engineering problem, I feel like this is a mathematical question so wanted to ask it here. I'm trying to figure out an algorithm for setting a matches location for a round ...
0
votes
2answers
34 views

Help with creating Recursive Algorithms

Prove your algorithms correct. Write an (efficient) recursive algorithm Pow (a,n) than computes $ (a \in \mathbb R)(n \in \mathbb Z):n\geq 0, a^n $. Write a recursive algorithm that computes ...
1
vote
0answers
18 views

Runtime of recursive algorithm - Master's Theorem

I wrote a computer program that solves a question, and I am interested in knowing what is the runtime. My aim is for $O(\log n)$, and I'd like someone more experienced (and smarter?) to review my ...
0
votes
0answers
12 views

Complexity of recurrence containing geometic series.

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$? So far I have: $ O(n) \le cn$ for some constant $c$ Hence: $$T(n) \le 3T(\frac{n}{2}) + cn$$ After a recursion: $$T(n) \le ...
0
votes
0answers
21 views

Closest pair points algorithm with Manhattan Distance

According to the solution of closet pair (euclid distance) with divide and conquer algorithm during merge algorithm we prove that for each point at distance d (minimum distance of two different sub ...
0
votes
0answers
39 views

Greek cross fractal

I need some code to generate a Greek cross fractal. Example: http://commons.wikimedia.org/wiki/File:Greek_cross_3D_1_through_4.png It must be made of increasingly smaller panels, but the panels may ...
2
votes
1answer
35 views

How to remove fields from sudoku puzzle in such way to assure there's still only 1 solution?

I'm trying to create a Sudoku puzzle (programatically, if that matters). Here's how I do it. STEP 1: Creating an initial set, with unique solution: 123456789 456789123 789123456 ...etc... STEP 2: ...
0
votes
1answer
58 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 ...
1
vote
0answers
16 views
2
votes
1answer
38 views

Counting Inversions - Recursive Algorithm

Now in my lecture notes in a course I'm taking I was given the following pseudo-code to Count Inversions (Using a Recursive Algorithm). ...
0
votes
2answers
31 views

Calculating Running Time of Recurrence Relations

I had to calculate the Running Time of the following Algorithm. ...
0
votes
0answers
7 views

Function to increase entropy for a specific number and seed and reduce it for the rest

Hello I think I am wording the title correctly. I am looking for a function / algorithm that can increase the variability or entropy of a specific number and reducing it for the rest. The function can ...
0
votes
1answer
37 views

Recursive Relations

I've been doing recursive relations and found a question I wasn't able to solve. I'm given a recursive algorithm that finds the $\gcd$ of two numbers $p$ and $q$. Algorithm: ...
3
votes
2answers
42 views

Is there a way to rewrite this recursive function so that it can be calculated in linear time?

I have this recursive function: $$ f(0)=f(1)=1 \\ f(x)=\sum_{i=0}^{x} f(i)×f(x-1-i) $$ The sequence turns out to be $1,1,2,5,14,42, \dotsc$ I want to be able to calculate the nth element ...
2
votes
1answer
38 views

Limit maze to region

I have created a random hexagonal maze using an algorithm. But how do I limit the maze to just the green hexagonal region in the following picture? Note that the size of the maze and the green region ...
2
votes
0answers
30 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
2answers
65 views

Find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidian algorithm.

I need to find the gcd of two polynomials: $f(x) = x^4+1$ and $g(x)=x^2-1$ using the Euclidian algorithm. Wolfram shows that the gcd is equal to $1$, but for some reason I don't get the same answer. ...
2
votes
1answer
44 views

Hexagon “maze” algorithm

Can anyone suggest a good algorithm to create structures like this? Note that what I what I am asking for is not a true maze with one start and one solution. Rather, it's for a video game, so like ...
-2
votes
1answer
76 views

2010 local contest questions on recurrence relation?

How we can solve this recurrence relation: $T(n)= 2^{log_{2}3} T(n/2)+ n \sqrt {n} $ anyone could help me this difficult question, that mentioned in 2010 local contest?
1
vote
1answer
35 views

Probability to iteratively and independently remove $n$ elements until all gone

The problem is as follows: Let S be a set of n elements. At the first stage each element in S is in- dependently removed with probability p. Those elements not removed constitute the set S1. ...
0
votes
2answers
58 views

recurrence formula for number of decimal numbers with some restrictions

I ran into a Olympiad Question that so difficult, if $a_n$ be the number of decimal numbers with length $n$ that has no $0$ in the digits and also has not any combinations $11,12,21$, I want to find ...
0
votes
0answers
33 views

Finding Explicit Function from a reclusive formula

I have been working on a project that will move much faster if I can write a recursive formula as an explicit formula. Let, $f(m-1,i)=i*f(m,i)-f(m,i+1)$ $i \in \mathbb{N}$ Thus, ...
0
votes
0answers
12 views

What to do when RHS of inhomgenous equation is to the nth power?

This is from an algorithm analysis course. I'm trying to analyse the time complexity of a recurrence relation. I have a inhomogneous equation for which I need to derive the characteristic equation. ...
0
votes
1answer
37 views

How to solve this recurrence, $T(n) = T(\sqrt{n}) + n$ using recursive tree method?

How to solve this recurrence, $ T(n) = T(\sqrt{n}) + n $ using recursive tree method? I draw the tree and got a sum, $ T(n) = T(1) + ( n + n^{\frac 12} +n^{\frac 14}+n^{\frac 18}+\ldots +1) $ I need ...
0
votes
0answers
46 views

Can linear execution time be achieved [duplicate]

The SELECT algorithm determines the $i$th smallest of an input array of $n>1$ distinct elements by executing the following steps. Divide the $n$ elements of the input array into $\lfloor ...
3
votes
1answer
45 views

How to find an explicit formula for a recursive function?

Define $$ S_{n+1} = \frac{S_n^2+x}{2S_n}$$ and $S_1 = k$, where x,k > 0. find an explicit formula for $S_n$ in terms of n. I don't even know where to begin. I tried using algebraic ...
2
votes
1answer
78 views

Why does Archimedes Method to calculate Pi decrease in precision after a certain time?

i`m using the following recursive formula to calculate Pi based on Archimedes ideas. $$ S' = \sqrt{2-\sqrt{4-S^2}} $$ The formula gives back the edge length of a Polygon B based on the edge length of ...
2
votes
1answer
45 views

Understanding the Power Iterative Method to find eigenvalues

I'm slightly confused about how to use the power method and the steps to calculate an eigenvalue. - I understand that the power method is defined as U(x+1) = AU(x)/a(x) where "a" is the first ...
0
votes
1answer
33 views

Iterative Logarithm in Recurrence Relation?

Anyone Could describe me How we can solve this recurrence relation? $T(n) = T(\log n) + O(1)$ $T(1) = 1$ a) $O(\log n)$ b) $ O (\log^* n) $ c) $ O (\log^2 n) $ d) $ O (n / \log n) $ Our TA ...
2
votes
1answer
103 views

Relax function on Bellman Ford Algorithms

In a Weighted Directed Graph $G$ (with positive weights), with $n$ vertex and $m$ edges, we want to calculate the shortest path from vertex $1$ to other vertexes. we use $1$-dimensional array $D = ...
3
votes
2answers
60 views

n bag of sand and one algorithms

We have $n$ bags of sand, with volume $$v_1,...,v_n, \forall i: \space 0 < v_i < 1$$ but not essentially sorted. we want to place all bag to boxes with volumes 1. We propose one algorithm: ...
0
votes
3answers
50 views

Order of Natural Numbers in Algorithms

Could anyone describe, why this is a True statements? if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then $\Sigma_{i=1}^{n} f_i(n)=O(n^2) $
0
votes
1answer
23 views

Why $T(n) = 2t(n/2) + \log n$ is in $ O(n)$?

My professor said that $T(n) = 2t(n/2) + \log n$ is in $O(n)$ I checked with Master Theorem and I did not really understood why. By Case1 (which would give us exactly $O(n)$) we have $a = 2, b = 2, ...
3
votes
2answers
90 views

$ T(n)= T(\log n)+ \mathcal O(1) $ Recurrence Relation

what is the solution of following recurrence relation? $$\begin{align} T(1) &= 1\\ T(n) &= T(\log n) + \mathcal O(1) \end{align}$$ a) $O(log n)$ b) $ O (log^* n) $ c) $ O (log^2 n) $ d) $ ...
0
votes
1answer
59 views

How to prove a recurrence with multiple terms?

I have to prove that the recursion: $$T(n) = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + n $$ is $$ T(n) = Θ(n*\log n)$$ As you can see, the reccurence has two different terms that ...
0
votes
1answer
22 views

Computation Operation in one Recurrence Relation

We want to calculate $T(n)$ from recurrence relation $ T(n)= \Sigma_{i=1}^{n-1} T(i) \times T(i-1)$` and we know $T(0)=T(1)=2$. How many computation operation, an Efficient Algorithm needs for ...
0
votes
0answers
39 views

recursive-algorithm problem

I am not to sure were to begin Thanks
0
votes
0answers
38 views

Best strategy for this archery-based probability game

This is with reference to the comments posted by @Trenin on my answer to this question. He says that since 2 players strategies depend on each other, we can't get the best strategy so easily. My ...
0
votes
1answer
57 views

Fan speed algorithm

I'm a programmer an I think my problem related to mathematics! I want when CPU have a static percentage of load (for example $10\%$) fan also have static rpm (Rotations per minute). But for now I have ...
0
votes
1answer
26 views

Recursive function with p=2/3 to call itself and 1/3 to return always ends?

So I was reading Godel, Escher, Bach and this problem came up: Let f(t) { 1)Generate random number k 2) if( k mod 3 = 0 or k mod 3 = 1 ) call f(t) //so 2/3's of the time, a new recursion level ...
0
votes
1answer
55 views

When drawing a recursion tree, how does b effect the tree if it is given?

So the problem I have is T(n) = T(n/8) + T(7n/8) +5n. I need to draw a recursion tree to prove that T(n) = Ө (n log 8 n ). I also need to show that T(n) = O (n log 8 n ) and T(n) = Ω (n log 8 n ). ...