Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
0
votes
1answer
13 views
Fractional Knapsack Problem Linear Time
So I came across a solution to the fractional knapsack problem in linear time here:
http://algo2.iti.kit.edu/sanders/courses/algdat03/sol12.pdf
I'm not sure I understand the algorithm given. We ...
0
votes
1answer
22 views
Understanding the Master Theorem - Determining the levels of recursion
I am trying to understand the proof for the Master Theorem. I have started by unwinding the following recurrence in order to find the total running time of an algorithm whose time complexity can be ...
0
votes
0answers
7 views
Divided Differences expanded form definition.
From definition of divided differences we have that $$f[x_0,\cdots,x_n]=\sum_{j=0}^n\frac{f(x_j)}{\Pi_{{k\in\{0,\cdots,n\}-\{j\}}}(x_j-x_k)} $$
It makes completely sense to have $k\neq j$ otherwise ...
2
votes
1answer
32 views
Optimal permutation for differential storage
This is a practical problem I encountered recently. I'm convinced that it has been solved before, however I don't know where to start looking as I'm unfamiliar with all the terminology involved. Hope ...
1
vote
0answers
28 views
Why does chaotic behavior explode when $k > \pi$ for $f_{n + 1}(x) = \sin(kf_n(x))$?
Why does the recursion $f_{n + 1}(x) = \sin(kf_n(x))$ with initial conditions $f_0(x) = x$ quicly display global chaotic behavior when $k > \pi$?
I have a very limited knowledge in nonlinear ...
2
votes
2answers
91 views
is there a faster method to calculate $1/x$ ($x$ an integer) than this?
I gave this stackexchange a second go. Is there a faster way to calculate $1/x$ than the following:
Calculate $100/x$ (.or other arbitrary positive power of $10$) with remainder
Write multiplier in ...
1
vote
1answer
21 views
Mathematical Induction for a defined Fibonacci Function
I'm a bit stuck on this problem and can't figure out how to proceed. We have the following Fib. recurrence given to us:
$f(0;a,b) = a;$
$f(1;a,b) = b;$
$f(n;a,b)=f(n-1;b, a+b)$
The problem defines ...
2
votes
0answers
41 views
How to determine how fast something is going towards infinity?
Just for a little bit of information I'm more of a programmer and less a mathematician so if some of my terms seem out of place it is due to a lack for formal training in Math.
While working on my ...
0
votes
0answers
32 views
Longest Increasing Subsequence Using Divide-And-Conquer
I'm required to solve the LIS problem using Divide-and-Conquer. The hint provided is the following: For each position in the array find the
cardinality of the longest sequence that ends up with it, ...
0
votes
2answers
29 views
Sinusoidal Generation in Recursive Algorithm
I need to generate sinusoidal values for varying frequencies. I'm making a DTMF tone generator but I must generate my own values of sine using recursive algorithms. The exact wording of how I'm ...
0
votes
3answers
61 views
Solving a recurrence relation: can't figure out how to convert from summation
I am really struggling to solve this recurrence.
$$
T(n) = T(\sqrt{n}) + n.
$$
I am asked to give asymptotic upper and lower bounds for $T(n)$. I am free to use any method to arrive at my answer, ...
1
vote
1answer
28 views
$(G,\cdot)$ and $M \subseteq G$. Prove that the following algorithm computes the subgroup generated by M.
Let $(G,\cdot)$ be a finite group and $M \subseteq G$, $M\ne \emptyset$.
Prove that the following algorithm computes the subgroup generated by M :
$$S_{0}:=\{{e}\} , H_{0}:=\{{e}\}\\
S_{n+1}:=(S_{n}\...
0
votes
0answers
11 views
How can I compute recursive QR-factorization?
I wonder if it's possible to find the $Q$ and $R$ matrices from this QR-equation with only compute QR at one time only:
$$A = QR$$
if, the first column of $A$ got removed and then a new column got ...
1
vote
1answer
176 views
Variance of parameter estimate using recursive least squares
I am learning about recursive least squares estimation using a forgetting factor $\lambda$ as a tool for treating time variations of model parameters and have become stuck on the following problem.
...
-1
votes
1answer
26 views
show algorithm to compute square root converge. [closed]
Consider the calculating the square root as follow:
Let's say we want to compute square root of $x>0$, pick a number $g_1>0$, then if $|g_1^2-x| < 0.00001$ then done. Else, let $g_2=\frac{g+\...
-1
votes
2answers
117 views
Solve the operations needed for the recursive formula
$f(n) = 1+\frac{1}{n}\sum_{i = 0}^{n - 1} f(i)$
Base case: $f(0) = 0$
how can I solve the recurrence?
0
votes
3answers
37 views
sequence that adds its previous results
Let $x = 0.3$.
The first number of the sequence is $x$.
The second number is the first number + $(0.3\cdot 0.3)$.
The third number is the second number + $(0.3\cdot 0.3\cdot 0.3)$.
This is a ...
0
votes
0answers
21 views
Is there a specific search paradigm for finding pairs in a set?
I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
0
votes
2answers
30 views
What is a goal of Galileo's magnetometer recursive filter
I'm designing the basics of space magnetometer instrument for academic project and I came across a Galileo mission investigation document, with data flow described in chapter 6. As a first ...
1
vote
2answers
42 views
proof that Ackermannfunction is uniquely defined and finding algorithm without recursions to calculate its values
my question is involving the Ackermannfunction.
Let's call a function $a: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ "Ackermannfunktion", if for all $x,y \in \mathbb{N}$ the following ...
0
votes
1answer
31 views
How to prove that class of “recursive” and “recursively enumerable” languages are not equal?
I would like to formulate a formal proof for showing that the classes of recursive and recursively enumerable languages are not equal.
I know that recursive languages are accepted by Turing machines ...
0
votes
1answer
35 views
Recurrence proof by induction
I'm having a hard time to understand how am i supposed to solve this question:
$T(n) = \sqrt{n}T(\sqrt{n})+n$. Prove by induction that $T(n) = \Theta (n \log{(\log{(n)})})$.
These are all the data ...
0
votes
0answers
16 views
How many balls will be left at the end of this process?
Consider having $N$ colored balls. Each color has at least $N/2k$ and at most $N/k$ balls in the beginning, for some parameter $k\ll N$.
At each iteration, we remove $k$ balls with different colors, ...
6
votes
1answer
82 views
Why does calculating $\exp z$ using $\ln z$ via newton-raphson method fail to converge?
I am trying to calculate $\exp z$ using $\ln z$ via Newton-Raphson method $$x_{n+1} = x_n-\frac{f(x_n)}{f^{'}(x_n)}$$and got the formula $$x_{n+1}=x_n-\frac{\ln x_n-z}{\frac{1}{x_n}}$$ where $z = a + ...
0
votes
1answer
44 views
Generating function from recurrence relation of binomial distribution
Hello i have given recurrence like this :
$$p_{n,k}=(1-q)p_{n-1,k-1}+qp_{n-1,k}$$
my question is how to get (step by step) generating function from this recurrence?
we know that it's some king of ...
0
votes
1answer
55 views
Quick Sort Question
Can anybody please help me out with this sorting question? I am new to the topic of sorting algorithm and just trying to complete the same.
Ques: Sort the below using Quick sorting algorithm
15, 10, ...
0
votes
1answer
21 views
$t(\lfloor\frac{n}{2}\rfloor)+t(\lceil\frac{n}{2}\rceil)+n=n(\lfloor\log n\rfloor+3)-2^{\lfloor\log n\rfloor +1}$
Given the following recurrence relation:
$t(1) = 1$
$t(n) = t(\lfloor \frac{n}{2} \rfloor) + t(\lceil \frac{n}{2} \rceil) + n$
How would a proof for the solution $t(n) = n (\lfloor \log n \rfloor +...
0
votes
0answers
14 views
Algorithm Complexity
Given an algorithm $\mathcal{A}$ with input parameter $\theta$ with the objective of obtaining $\theta^* = \lim_{k \rightarrow \infty} \mathcal{A}_k(\theta)$.
Say we are interested in characterizing ...
2
votes
4answers
42 views
Convert Polynomial to Sum
I have to convert the polynomial: $P_4=x^4+7x^3-13x^2-103x-84$ into the form: $$P_4(x)=\sum_{i=0}^4 a_i(x-1)^i$$ using Horner's Method.
I can evaluate both of them using Horner's Method, but I can't ...
1
vote
1answer
56 views
Quick Sort worst case, why $n^2$?
I have a very hard time understanding this proof:
$$T(N) = T(N-1)+cN$$
$$T(N-1) = T(N-2)+c(N-1)$$
$$T(N-2) = T(N-3)+c(N-2)$$
$$\vdots$$
$$T(2) = T(1)+c(2)$$
$$T(N) = T(1)+c\sum_{i = 2}^{N} i = O\...
0
votes
0answers
107 views
Modified 12 coin puzzle
I was looking on to the classic 12 coin puzzle.
A slight modification to it:
If out of N coins, N-1 are genuine and 1 is fake(which may be heavier or lighter), is there a formula to calculate the ...
2
votes
1answer
46 views
Recursive algorithm probability
I'm trying to find the probability of obtaining a six on a dice roll following these rules:
You roll a dice and if you roll $6$, then you win.
However, if it is not $6$, you roll another dice....
1
vote
1answer
55 views
Can't figure out $O(n \log n)$ divide and conquer algorithm
For an $n$ that is a power of $2$, the $n × n$ Weirdo matrix $W_n$ is defined as follows. For
$n = 1, W_1 = [1]$. For $n > 1$, $W_n$ is defined inductively by
$W_n =
\left[
\begin{matrix}
W_\frac{...
0
votes
0answers
26 views
Conversion of this recursive formula to a general term of a sequence
I got puzzled trying to convert this particular recursive sequence to a general term of a sequence.
$$S_n=1+n+\sum_{j=2}^{n-1} j\times S_{n-j}\times\binom{n}{j}$$
Can somebody help me to reduce to ...
1
vote
0answers
50 views
Explicit to Recursive Formula
I've spent the day trying to figure out how to make this particular explicit formula recursive, and come up empty.
$v(t)=(0.98^t-1)\times3.92$
None of my searches helped me in converting this type ...
-1
votes
2answers
29 views
Proof of worst-case time complexity of Binary Search
I know that using the Master Theorem, one can easily arrive at the worst-case time complexity. However, how would I go about proving that it is in $O(lg(n))$ by defining upper and lower bounds? I have ...
0
votes
0answers
25 views
Recursive algorithm for planar graph
I have this pseudo-code and I need to understand what it does. It takes some planar graph as input and returns a subset of V (that are the vertexes of the graph). It is clearly recursive, but I don't ...
0
votes
1answer
69 views
Back-n-Forth or a Direct Isomorphism Between A Countable DLO Without Endpoints and $U = \{ \frac{m}{2^n} \}$
Note: I changed this question and deleted my answer, bringing it into the question for quick review. The proof now has the same brevity as the back-and-forth method found in wikipedia.
Let $P$ be a ...
1
vote
0answers
34 views
$f(n) = 2f(n/2) + n^2$ if n is even or $2f(n/2) + n^3$ if n is odd
I want to solve the following recursion to find the complexity.
$f(n)=\begin{cases}
2f(n/2) + n^2 & \textbf{if } n \text{ is even}\\
2f(\lfloor n/2\rfloor) + n^3 &...
0
votes
0answers
53 views
Number of levels in recursion tree.
See in the picture that the number of levels is clearly $1+\log_{4/3} n$.
so,the total cost should be $cn(1+\log_{4/3} n)$
However in clrs and Khan Academy article of Cormen they are doing $cn\log_{4/...
2
votes
2answers
50 views
Solution to differential equation $y'(x) = a * y(x)^2$
first of all: I am not a mathematician. I am struggling since a few hours with a simple differential equation which I would like to solve to approximate the expectation curve for computer simulations ...
1
vote
0answers
27 views
Trouble understanding a recursive summation
I'm reading an NLP paper. In section 4.2, there is the following summation:
$$\alpha[t][k] = \sum^{t-k}_{j=1}p(c^t_{t-k+1} | c^{t-k}_{t-k-j+1}) \cdot \alpha[t-k][j]$$
where $\alpha[0][0] = 1$.
...
2
votes
1answer
56 views
A little help for building the Fibonacci spiral in a particular reference system
In the following picture, the numbers represent the building steps of the Fibonacci spiral (or Golden spiral).
I would like to find the coordinates of the upper-left corner of the squares (black dots)...
1
vote
1answer
56 views
Does this recursive function have a closed-form solution?
Consider the following recursive function:
$$
z(i) = \begin{cases}
z(i + 8) + 1 & i < 0 \\
z(i - 7) & i > 2 \\
0 & 0 \leq i \leq 2
\end{cases}
$$
Does this recursive function have ...
1
vote
1answer
76 views
How can I write a recursive function having $\Theta(n^7)$?
How can I write a recursive function having $\Theta(n^7)$ cost?
I must only use if, then, else statements and a function called $G(n)$ that costs $\Theta(n)$.
For example:
...
0
votes
1answer
43 views
Principle of mathematical induction in recursive functions
"Use the principles of mathematical induction to show that the value at each positive integer of a function defined recursively is uniquely determined"
I have a problem understanding what exactly it ...
0
votes
1answer
204 views
Trying to simplify this
How do I simplify this into a formula?
Note: $z,g,o,x,p,b,c,f,y$ - are all multiplicative constants
I have:
$$n(1)=z\left(gox^0+p\left(\frac{b}c\right)-fy^0\right)$$
$$n(3)=z\left(gox^2+p\left(\...
0
votes
0answers
46 views
0
votes
1answer
55 views
Explicit form of recursive function
Given recursive function:
$$T(x)=2T(\frac{x}{2})+\frac{2}{\log (x)}$$
reach an explicit form:
We already solved it in class. However I can't seem to remember, how was it...
I Wrote it in these ...
0
votes
1answer
68 views
generating all possible k partition of an array
actually, I confronted a problem for generating all possible k partitions of an array. I tried to write the algorithm but actually, I am not able to.
can anybody please give me the idea, how to code ...
