Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [recursive-algorithms]

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

0
votes
0answers
37 views

Function-induced polynomial evaluation trees

My question relates to the Fast polynomial evaluation and composition article by Guillaume Moroz available online at https://hal.archives-ouvertes.fr/hal-00846961v3/document/. It demonstrates notions ...
0
votes
1answer
38 views

finding a recursive formula for a sequence, if possible [closed]

Hi everyone: I was looking over an NYS Algebra 2 Regents, and two training programs for a long-distance race were compared. (The answer they wanted was the recursive formula for a simple arithmetic ...
0
votes
0answers
18 views

First Order Nonlinear Recurrence Relation

I am trying to solve the closed formula for $x_n$ given the first order non-linear recurrence relation below. Unlike linear recurrences with direct solutions, I can't find any good reference for non-...
2
votes
1answer
36 views

How can i distribute the money in the fewest movements? [closed]

I am trying to evenly distribute the total amount to each person involved. For example I will use money. Example 1 Person A has $20 Person B has $40 Person C has $60 So to make everything even ...
0
votes
0answers
22 views

Multiply large numbers by dividing them into 3 (Karatsuba with n/3 size)

I was solving some problems related to Karatsuba, when I came across a problem which says, how many multiplications would you need to multiply a large number divided into 3 smaller ones like this: a =...
0
votes
3answers
43 views

How to write recursive formula as explicit (specifically, exponential)?

I recall learning in school how to convert arithmetic and geometric sequence formulas between recursive and explicit, but I don't remember learning a systematic method to approach it. For example, let ...
1
vote
2answers
33 views

find the largest square foot given an area

Given an area of n square foot, I need to be able to find the largest square foot I could make in the given area. Example: if I had a total area of 12 square foot, I would be able to make one 3x3 ...
6
votes
1answer
213 views

Common roots of recursive defined polynomial

I have a series of polynomials $P_j(x)$ given by the recursive formula $$P_{j+1}=\frac{e_j}{c_j}xP_{j}-\frac{f_j}{c_j}P_{j-1} $$ with $P_{-1} \equiv 0$, $P_0 \equiv 1$, where $$c_j = (j+1)(j+2\kappa+1)...
0
votes
1answer
48 views

Is there a rule behind why $\left \{ 1+(-1/2)^n) \right \}^{+\infty}_{n=1}$ is $a_{n+2}=1/2(a_{n+1}+a_{n}) , a_{0} = 2 , a_{1}=1/2$ in recursive form?

I understand that both expresions represent the same sequence of numbers. It starts at $a_{0}=2$ and oscilate around 1 converging to it from up and down. I have been playing around with the explicit ...
1
vote
1answer
34 views

Visualize $T(n)=2T(n/2)+O(n)=O(n\log(n))$ on a Tree

I understand the mathematical proof for $T(n)=2T(n/2)+O(n)=O(n\log(n))$, however I cannot visually wrap my head around how it works. Intuitively, it just feels like it should $O(n^2)$. Can you show me ...
0
votes
1answer
42 views

Convergence of recursive scheme

I would like to see why below recursive scheme is convergent : $x_{n+1}= \sqrt{\alpha\cdot x_n+\beta}$ Here, $\alpha>0$ and $\beta\in\mathbb{R}\setminus\left\{0\right\}$. I tried something like: ...
2
votes
1answer
49 views

Dynamic Programming problem palindrome

I am stuck with the following problem: Given a string of characters $w$, we want to know the minimum number of characters that we must add to $w$ in order to convert this string in a palindrome (note ...
0
votes
0answers
18 views

Hankel or Bessel functions of integer separated order evaluated at the same value

Let $H_\nu^{(1)}=J_\nu+iY_\nu$ be one of the Hankel function. If $\nu=\left|N-\alpha\right|$ with $N$ integer and $0<\alpha<1$, is there a fast way to get all $H_\nu^{(1)}(z)$ for all $\left|N\...
2
votes
1answer
42 views

What's the idea behind recursive least squares (RLS)?

The simply explanation of recursive Least squares (RLS) is: $$\theta(t) = \theta(t-1) -P(t)\phi(t)[y(t) - \theta ^T(t)\theta(t-1)]$$ $$P^{-1}(t) = P^{-1} + \phi(t) \phi^T(t)$$ Where $\phi$ is the ...
0
votes
1answer
40 views

what is the complexity of recursive summation

Can someone tell me the exact complexity of this recursion ? this is actually formula for below question ( solved in recursive brute force way ) There is n steps stairs and a person standing at the ...
2
votes
1answer
59 views

*Numerical* Convergence of the Babylonian Method?

I understand the sequence $x_{n+1} = \frac12\left(x_n + \frac2 {x_n}\right) $ converges to $ \sqrt2 $ algebraically. That is proved by means of fixed-point method or monotone convergence theorem and ...
0
votes
0answers
9 views

Simplification in Recursive Algorithms with tilde relationship

$f(N)\sim g(N)$ iff $|\frac{f(N)}{g(N)}|\rightarrow 1$ as $N\rightarrow \infty$. Define $C_N$ to be the number of compares to sort $N$ elements and analyze $C_N$. Given $\frac{C_N}{N+1} = (\frac{C_1}{...
1
vote
1answer
13 views

Basic Recurrence Problem in the Analysis of Algorithm

I am taking an algorithm course at Coursera. From this webpage by a Princeton Professor, Example 1.5 (Analysis of quicksort) gives the following codes. public class Quick { private static ...
11
votes
3answers
726 views

How to tell if a particular number will survive in this sieve?

I was asked this in an interview. We have people numbered from one to infinity: $$1, 2, 3, 4, 5, 6, 7, 8, \dotsc\,.$$ In first pass every 2nd person is killed, so we have $$1, 3, 5, 7, 9, 11,\...
0
votes
0answers
18 views

Graph algorithm to find the most likely ancestor of a node

I'm working on the Wikipedia Category Graph (WCG). In the WCG, each article is associated to multiple categories. For example, the article "Lists_of_Israeli_footballers" is linked to multiple ...
1
vote
0answers
37 views

How to derive a recursive version of a regularised cost function

I am to derive a recursive version of the following cost function and examine for which choice of D can we have a estimator windup $V(\theta) = \frac{1}{2}\sum_{t=1}^n(y(t)-\phi(t)^T\theta)^2 + \...
0
votes
2answers
27 views

An algorithm to make a variable the sole term of one side

Is it always possible to refactor an equation so that a desired variable appears as the sole term of one side?* If so, how? Simple example: $$xa = ya + b \\ xa - ya = b \\ a(x - y) = b \\ a = \frac{...
2
votes
2answers
40 views

Finding a recurrence for $t_n$ that holds true for a set of integers

I know the answer but I have no idea how to explain it Question A $t_3 =$ ['aaa', 'abb', 'acc', 'bba', 'cca'] ($5$ elements) $t_4 =$ ['aaaa', 'aabb', 'aacc', 'abba', 'acca', 'bbaa', '...
0
votes
2answers
44 views

Confusing symbols

I saw these symbols in the text book for a subject i'm taking next semester, and I am just curious about what they mean. What is the question asking me?
0
votes
0answers
48 views

Stuck Simplifying for a Fibonacci Series

I am attempting to solve for $n$ in the equation: $g_n=g_1F_{n-1}+g_2F_n$ where $F_n$ is the $n$th Fibonacci number. I know that $g_0$ and $g_1$ will be positive integers such that $0 < g_1 \...
1
vote
0answers
47 views

What is the difference between Kalman Filter and Recursive Least Squares? [closed]

I wish to understand the difference between Kalman Filter and Recursive Least Squares since both of them use prediction and correction approach. In Kalman filter, the value of existing state vector ...
0
votes
0answers
9 views

Particle Filters: whether current measurement depends on previous measurement

Recently I was learning basic estimation theory. I am confused that whether the measurement $z_k$ is related to previous measurements $z_{1:k-1}$. A quick recap of the estimation problem. Given ...
0
votes
0answers
13 views

Solving Recurrence to Find Asymptotic Behavior (Algorithm)

Can somebody check if I got the right answers for those recurring functions? 1)$T(n)=4T(\frac{n}{3})+nlg^2n$ - using the asters theore i got that $T(n) \: \in \: \Theta(n^{\log_{3} 4}) \approx \Theta(...
1
vote
0answers
54 views

Longest path of a matrix

Given a matrix $$ A = \begin{pmatrix} 1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7 \end{pmatrix} $$ We know that the length of the longest path that is ...
0
votes
1answer
39 views

Prove $N\cdot lg(N) = \sum_{k=1}^N(\lfloor lg(k) \rfloor + 2)$ - “Analysis of Algorithms” by R. Sedgewick

This is a problem from "Analysis of Algorithms" by R. Sedgewick. In the context of the merge sort: $C_N = N\cdot lg(N)$ Exercise 1.4 Develop a recurrence describing the quantity $C_{N+1} − C_N$ ...
0
votes
6answers
89 views

Finding a recursive formula/sum for $\pi$

I'm very much aware of the $$\pi = 4 \left(1 - \frac13 + \frac15 - \frac17 + \frac19 -\cdots \right)$$ and $$\pi = \sqrt{6\left(1 + \frac14 + \frac19 + \frac{1}{16}+ \cdots \right)}$$ and even less ...
0
votes
0answers
21 views

Find an alternative FPTAS for knapsack

There is a famous algorithm using, the recusive integer data problem on: w(j,p) = min weight set of items of profit=p when we have j items Now I was wondering if there was an alternative solution ...
0
votes
0answers
29 views

Expand recursive equation to convert it into a normal formula

The Problem: I am faced with the following recursive equation: $$V(n) =\begin{cases} 2V(n/2)+n& \text{for n > 1}\\ 0 &\text{for n = 1} \end{cases}$$ I am trying to expand the function ...
0
votes
1answer
195 views

recurrance with merge-sort

Trying to modify a merge sort by recursively splitting an array of size n into k sorted subarrays k > 2 and merging these subarrays. Time for merging is c(k-1)n. Specify the recurrence relation and ...
-1
votes
3answers
63 views

How to solve the recurrence $a_{n}=\frac{n+1}{n} a_{n-1}+3n+3$?

I tried to solve this recurrence by taking out $n+1$ as a common in the RHS, but still have $n \cdot a_n$ and $a_n$
2
votes
1answer
57 views

multiple knapsack problem?

I have a weight X. This should be distributed into multiple knapsacks w1...wY. It should be distributed to the largest knapsacks first and smallest last. Yet the optimal distribution should be found ...
1
vote
1answer
13 views

Is the function $F=\chi_{>m}$ primitive recursive for some undetermined m?

Is the function $F=\chi_{>m}$ primitive recursive for some undetermined $m$? An exercise can be seen here like the following: $F(m)=0,$ if the decimal expansion of $\pi$ has a run of at least $m$...
0
votes
0answers
28 views

How do I extract a curve in xyz from curvature/torsion using Frenet Serret equations?

Somewhat of a continuation of this, opening this scab because I have the same question but the solution was not covered in post and I have been banging my head against the wall for a week trying to ...
8
votes
0answers
84 views

Let $X$ be a random variable, $\frac{\mathbb{E}[e^{sX}-e^{tX}]}{s-t}$ for $s \approx t$. As

Question Let $X$ be a random variable for which we only have the value of its Moment Generating Function $M_X$ on a discrete set of points, I am looking for a stable method to compute: $$\frac{M_X(s) ...
0
votes
0answers
32 views

How to identify shortest and longest path, given a recursion tree?

Show that the solution to $T(n)=T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right)+n$ is $\Omega (n \log n)$ by analyzing the recursion tree. This is my recursion tree : How can I show that $T(n)=...
0
votes
1answer
29 views

Prove that a proposed algorithm gives an optimal solution of the optimization problem.

We have $N$ queues. Each of the queues contains a number of numbered ball, and the balls can be taken out in descending order. For example, the queues can be as the follows: I want to take $L$ balls ...
0
votes
3answers
30 views

How to show that this specific limit exists in this proof?

Given the sequence $T_n$ where $T_1 = 0, T_2 = 1, T_3 = 1$ and $T_n = T_{n-1} + T_{n-2} + T_{n-3}$ for $n >= 3$. Find what the ratio of consecutive terms, $\frac{T_{n+1}}{T_n}$ is converging to. I ...
1
vote
1answer
22 views

Improving the efficiency of exponential smoothing for binary digits

Let's say I'm a stock exchange, and I have an order flow for Apple shares. Let's say those numbers look like: 10,000 (buy) -3,100 (sell) 24,243 (buy) These orders come in very quickly. What I want ...
0
votes
1answer
36 views

Given two arrays A1,A2, return if for a given X , there is a pair of ai∈Ai such that a1+a2=X (𝑂(n log(𝑛)))

The question is fairly easy to understand, the problem is i need the algorithm running time to be 𝑂(n log(𝑛)), which i couldn't achieve. Given two arrays with positive integers,lets call them A1,...
-1
votes
2answers
51 views

I don't understand what this question is asking and how to show it/prove it$

Given the sequence $T_n$ where $T_1 = 0, T_2 = 1, T_3 = 1$ and $T_n = T_{n-1} + T_{n-2} + T_{n-3}$ for $n >= 3$. Find what the ratio of consecutive terms, $\frac{T_{n+1}}{T_n}$ is converging to. ...
-2
votes
2answers
48 views

Prove a recursive sequence using induction

I'm having trouble with this recursive sequence question and was wondering how to prove it. The sequence $a_n$ is defined recursively by, $a_1 = 6$, $a_2 = 8$, $a_n = 4(a_{n-1}) - 4(a_{n-2})$ for $n&...
1
vote
0answers
17 views

How many calls of the form $\det(B)$ does the algorithm create?

Let's say $A\in \mathbb{R}^{n\times n}$ and the $n^2$ components of $A$ are pairwise different. In order to calculate $\det(A)$ we can use the recursive algorithm that computes $\det(A) = \sum\limits_{...
1
vote
2answers
36 views

Evaluating a polynomial using Horner's algorithm

With Horner's algorithm, I can solve f(x$_{0}$) for a polynomial like this: $a_0 + a_1x + a_2x^2 + a_3x^3 + ... + a_nx^n$ By doing this: b$_n$ = a$_n$ b$_{n-1}$ = a$_{n-1}$ + b$_n$x$_0$ b$_{n-2}$ =...
1
vote
3answers
65 views

What are these kind of problems called?

The question is that: There are $100$ of coins, to be given to members of a family. The eldest brother is the one who decides how to distribute them After his decision, family members vote ...
0
votes
0answers
23 views

Best recursive algorithm for Auto-Convolution?

i have a question. I know a recursive algorithm that can compute convolution generally with complexity of $\theta(n^{log_2 3})\simeq \theta(n^{1.58}) $ is there any better algorithm with better ...