0
votes
1answer
35 views

Find a linear-time algorithm for finding if element occurs n/4 times

Give a linear-time algorithm that determines whether an unsorted sequence of n real numbers contains a number that occurs at least n/4 times in the sequence. You algorithm should report “no” if ...
0
votes
0answers
24 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 ...
0
votes
0answers
61 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. } ...
4
votes
3answers
157 views

Recursion with Random number?

function foo(n) if n = 1 then return 1 else return foo(rand(1, n)) end if end function If ...
2
votes
1answer
88 views

What is the bound of: $T(n) = T(n-2) + (n)log(n)$?

I am given the following recurrence relationship: $\ T(n) = T(n-2) + nlog(n)\\ T(1) = T(0) = constant$, I need to find the order for the recurrence. So, using the iterative methodology, what I ...
2
votes
2answers
317 views

Using Master's Theorem with $f(n) = \lg^2 (n)$

This is a homework question about using Master's theorem, and I can't seem to wrap my head around this question: $$T(n)=2T\left(\frac{n}{3}\right)+\lg^2(n)$$ I've tried to apply the Master's ...
0
votes
1answer
62 views

Finding in a string S if is possible to create a set with perfect cubes or perfect squares with elements of S.

You have a sequence $S[1...n]$ with $n$ digits(0 to 9) and you wanna know if its possible break then in perfect square or perfect cube. For example, if $S = 1252714481644$, then the answer is $YES$ ...
1
vote
1answer
66 views

Solving recurrenc using recurrence tree method.

I got this recurrence to solve: $T(n) = 2.1 T(n/2) + n$. I know the answer (got it using the plug and chug method and using the master method too), but I'm trying to solve using recurrence tree and ...
2
votes
3answers
78 views

Divide et impera recurrence, why induction does not work?

$$ T(n) = T\left(\frac n2\right) + 2^n $$ where $n \ge 1$ and $T(1) = 1$. If I understand the substitution method and the induction, I can guess that $T(n) = O(2^n)$. I must prove that $T(n) = ...
1
vote
1answer
206 views

Dynamic Programming— Variable Width Bin (Equi-Depth) Histogram

Given some data, and a fixed number of bins (k)-- How can I design a Dynamic Programming algorithm that minimizes the largest difference between bin sizes? In other words, with a set number of bins ...
0
votes
1answer
146 views

Solving the following recurrence relation

I have a recurrence relation, it is like the following: $$ T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where $e$ is the natural logarithm} $$ To solve this and find a Θ bound, i tried the following: I ...
2
votes
1answer
278 views

recurrence-relation via master theorem

This is homework assignment on proving algorithm time complexity using Master Theorem. I have been trying to solve it for several hours by now with no luck. Can someone please at least explain, what ...
0
votes
2answers
599 views

What does “give a recursive definition of the set of polynomials with integer coefficients”, mean?

What is the set of polynomials with integer coefficients look like? Help! Thanks!
0
votes
1answer
51 views

Recursive Definitions - Should I use logic notation (i.e. arrows or “for n =…”)

[b.] $a_n = 1 + (-1)^n $ \begin{align*} a_1 = 1 + (-1)^1 = 0\\ a_2 = 1 + (-1)^2 = 2\\ a_3 = 1 + (-1)^3 = 0\\ a_4 = 1 + (-1)^4 = 2\\ \vdots \\ \\ \text{Recurisve Definition: }\\ a_1 = 0 \\ a_n = 2 ...
2
votes
2answers
90 views

Recursive Series

Am I doing this right? What's a good way to think about the different f(n)'s. f(n + 1) is the "next" element in the series? f(n) is the current element? The previous element? Find $f(1), f(3), ...
2
votes
2answers
179 views

Theta bound about $\sum \lfloor {\sqrt{n}}\rfloor$

$$S_k=\sum_{n=1}^{k^2-1}\lfloor\sqrt{n}\rfloor $$ Can somebody give me an idea about the steps I should follow? Initially I thought $$n^{1/2}\log(n) \leq n^{1/2}\leq n^{3/2}$$ so $\Theta(f(n))=S_k ...
2
votes
2answers
280 views

How to define divisibility recursively?

Let $d(x,y)=1$ if $x$ is divisible by $y$, and $=0$ otherwise. How can I define $d(x,y)$ in terms of just the basic primitive recursive functions (zero, successor, identity, projection) and the ...
4
votes
1answer
649 views

Karatsuba multiplication with integers of size 3

I understand how to apply Katarsuba multiplication in 2 digit integers. $$\begin{array} \quad & \quad & x & y \\ \times & \quad & z & w \\ \hline \quad ...
1
vote
2answers
115 views

implicit equation for covering a $3\times{n}$ face with $2\times{1}$ mosaics with recursion solution?

This is my university homework. I was on it for a day but I couldn't solve the problem. I found a implicitness solution for this problem: $f(2)=3$ $f(4)=11$ $f(n)=3f(n-2)+2f(n-4)$ I thought that ...
0
votes
1answer
672 views

How to solve the recurrence $T(n)=3T(n/2)+n$

The exercise stated that i have to solve the recurrence using the Recursion-Tree Method. I have already finished the base part, which is $\Theta(n^{\lg3})$ But for the recursive part I'm having ...
0
votes
0answers
63 views

Is this a correct translation from recursive function to math notation?

I have this recursive function, written in Java. Assignment is to translate it to mathematical notation. ...
0
votes
3answers
2k views

Recurrence telescoping $T(n) = T(n-1) + 1/n$ and $T(n) = T(n-1) + \log n$

I am trying to solve the following recurrence relations using telescoping. How would I go about doing it? $T(n) = T(n-1) + 1/n$ $T(n) = T(n-1) + \log n$ thanks
4
votes
2answers
300 views

Determining a recurrence relation (Homework)

Let ${d_n}$ be the number of DNA strings of length n that contain a pair of consecutive nucleotides of the same type. There are four symbols used in strings of DNA: A, C, G, T. The nucleotides are ...
3
votes
3answers
2k views

What is the bound of : $ T(n)=T(n-2)+\log(n)$?

Given : $T(n)=T(n-2)+\log(n)$ I need to find the bound for the above recurrence . So: $$\begin{align*} T(n-2)&=T(n-2-2)+\log(n-2)\\ &=T(n-4)+\log(n-2)\\ T(n)&=T(n-2)+\log(n)\\ ...
0
votes
1answer
194 views

How to get the recursive formula of a problem?

I am trying to understand a problem im reading and produce a recursive formula for the problem. The problem, an ice cream van can serve j^2 customers at a time, However the van needs time to make new ...
5
votes
2answers
1k views

Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is ...
2
votes
1answer
99 views

Recursion with non-equal exponents

This is my first question on this site... yesterday I asked this on cs.so but they downwote and told me that so.cs is a research-level site, not for students... I hope it's appropriate to ask this ...
1
vote
1answer
53 views

Finding a recursive function for a problem

I have a homework assignment to find a recursive function for $k(n)$ where $k(n)$ is the number of ways to split the set $\{1,2,3,4....n\}$ while not having any subset contain more than two elements. ...
1
vote
3answers
388 views

How do I find the inductive definition of the set defined as $\{2n+3m+1|n,m\in\mathbb N\}$?

$\lbrace 2n+3m+1:n,m\in N\rbrace$ is the set of all positive integers except for $0$ and $2$. I need to know how to write its inductive definition. This is part of the introduction on learning how to ...
1
vote
2answers
223 views

Homework question dealing with recursion

I need help with this recursion question: