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

learn more… | top users | synonyms

1
vote
0answers
32 views

Most efficient algorithm to distribute n n-bit strings among n people

If there are N people, and a corresponding set of subsets K, what is the most efficient algorithmic approach I can use to give everyone a (not necessarily unique) N-bit string (leading zeroes ...
4
votes
4answers
494 views

A 3rd grade math problem: fill in blanks with numbers to obtain a valid equation

Even though this is a 3rd-grade math problem, people found it extremely hard. Any people have a solution, or algorithm is welcome. I'll try make a program base on the algorithm and see if it's ...
6
votes
1answer
115 views

What are the solutions for $a(n)$ and $b(n)$ when $a(n+1)=a(n)b(n)$ and $b(n+1)=a(n)+b(n)$?

If you have the following recurrence relations : $a(n+1)= a(n) b(n)$ $b(n+1)= a(n) + b(n) $ How do you find the form of $a(n)$ and $b(n)$ ? I suspect there isn't a closed form , but a infinit sum ...
2
votes
1answer
27 views

Is this the correct minimum number of coins needed to make change?

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
-1
votes
0answers
30 views

How to prove $T(n) = 2*T(\lfloor n/2 \rfloor) + n \quad \text{is}\quad \Omega(n \log n)$?

In CLRS edition 3, this is the question in chapter 4. They have proved that the inequality is $O(n \log n)$ and wants learners to prove that it is also $\Omega(n \log n)$ and thus establish that it is ...
0
votes
1answer
19 views

How would you apply the Greedy technique in this situation/why wouldn't it work?

I am going over the Rod Cutting Problem The author states "Selling a rod of length $i$ units earns $P$[i] dollars." Here is the table $P$ for this problem I'am currently going over this question ...
1
vote
1answer
32 views

Where does 13 come from?

I am going over the Rod Cutting Problem Everything makes sense to me until For example, $L$ = {9} has the total cost Cost($L$) = $P$[9] = 13, whereas $L$' = {1,1,1,1,1,1,1,1,1} has the total cost ...
0
votes
1answer
32 views

Sequence who converges to $\sqrt{a}$ for every $a\geq0$

If we have: $$x_n=\left\lbrace \begin{matrix} b\in\mathbb{R}\setminus \{0\} & ,n=1 \\ \dfrac{a+x_{n-1}^2}{2x_{n-1}} & , n>1\end{matrix} \right.$$ Then, is easy to prove that $(x_n)\to ...
2
votes
1answer
59 views

Solving $T(n) = 3T(n-1)$

How is the constant before the $T$ important to the result from $T(n)$ I know that \begin{equation*} T(n) = T(n-1) + 3 \Rightarrow \theta(n)~\text{and}~T(n) = T(n-1) + n \Rightarrow \theta(n^2) ...
1
vote
1answer
61 views

Struggling with difference between greedy and naive but optimal algorithms? (Graph theory)

I've been thinking about the following problem for quite a while and tried multiple solutions, but I'm having difficulty telling the difference between a greedy algorithm and an inefficient naive ...
0
votes
1answer
28 views

Where does the root of this tree come from?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
2
votes
1answer
40 views

Wouldn't this Greedy Algorithm achieve the highest possible of money in this situation?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
0
votes
0answers
9 views

recurrence tree final step - binary search

Starting with the base case and recursive case run times as follows: 􏰀 t(N) = 1 , if N = 1 t(N)= 1+t(N/2) ,ifN > 1 At the end of my tree I have ...
1
vote
3answers
43 views

How to apply Master theorem to this relation?

This is the definition of master theorem I am using(from Master Theorem) I am trying to use that master theorem to find the tight bound for this relation $T(n) = 9T(\frac{n}{3}) + n^3*log_2(n)$ ...
1
vote
0answers
35 views

Coppersmith-Winograd algorithm

I'm interested in algorithms to compute matrix multiplications. Is the Coppersmith-Winograd algorithm similar to the Strassen algorithm ? I have two other questions: 1) Are the multiplications done ...
0
votes
0answers
11 views

Formula for a recursive function

Given the recursive function $T: \mathbb{N}_0 \to \mathbb{R}_+$ $$T(n) ≤ max_{1 ≤ k ≤ n - 1}\{T(k-1) + T(n - k) + c n^2\}$$ with c > 0 constant, I want to determine an absolute formula to quickly ...
0
votes
1answer
23 views

Recursive solution to “Number of subsets of a set without 3 following numbers”

so I got the following problem: For a given natural n number, let A be the set A={1,2,...,n} I need to provide a recursive solution that will return the number of possible subsets that doesn't ...
0
votes
1answer
22 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
0
votes
2answers
26 views

Getting rid of $2^n$ when solving $a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ by characteristic roots

$a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ For $n\ge3$, With initial conditions $a_2=1$, $a_1=1$, and $a_0=1$ I'd like the find the particular solution with characteristic roots. However when generating ...
1
vote
0answers
16 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
2
votes
1answer
38 views

How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?

This is recurrence $T(n)$ $ T(n) = \begin{cases} c, & \text{if $n$ is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ...
0
votes
2answers
23 views

Does this recurrence relation run in $ \Theta(n) $?

This is the recurrence relation I am trying to solve: \begin{align} T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\ T(1) & = c. \end{align} I broke this down (i.e., solved this ...
2
votes
0answers
48 views

How to find a enclosed envelope with maximum points among a cloud of spheres? [ Concave Hull ]

I have a questions regarding the selection of the outer points (i.e. sphere center), among a collection of many spheres in 2D/3D space. The outer points is that when all of these points are ...
0
votes
0answers
11 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
29 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 ...
0
votes
0answers
14 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
20 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
42 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
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
43 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
36 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
35 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
23 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
13 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
39 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
41 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
36 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
78 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
17 views
2
votes
1answer
47 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
34 views

Calculating Running Time of Recurrence Relations

I had to calculate the Running Time of the following Algorithm. ...
0
votes
0answers
9 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
43 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
41 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
36 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
70 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
48 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 ...
1
vote
1answer
36 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
60 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 ...