Tagged Questions
1
vote
1answer
46 views
Register Machine on Fibonacci Numbers
This problem is easy to understand but I am struggling to come up with any solutions.
According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a ...
0
votes
0answers
35 views
Finding the value of an algebric expression
I have this expression $Ax+By+Cz$ where $x,y,z \geq 0$ and are integers. Suppose I am given a value $T$; I want to find the largest value which is less than $T$ and which cannot be generated by ...
1
vote
2answers
32 views
Tight asymptotic upper bounds on specific recurrences
give a tight asymptotic upper bound (() notation) on the solution to each of the following recurrences.
$T(n)=2T(n/8) + \sqrt[3]n$
$T(n)=T(n/3) + T(n/4) + 5n$
1
vote
1answer
22 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 ...
1
vote
1answer
53 views
Generalized Josephus problem
I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as
f(1) = a
f(2n) = 2f(n) + b, for n >= 1
f(2n+1) = 2f(n) + y, for n >= 1
...
2
votes
1answer
36 views
Quadratic Forms and Newton's Method
Consider the function $f(x,y) = 5x^2 + 5y^2 -xy -11x +11y +11$. Consider applying Newton's Method for minimizing $f$. How many iterations are needed to reach the global minimum point? Why should ...
1
vote
1answer
48 views
How do I determine if two of my software's representation of algebraic numbers are equal?
I have software which stores information about algebraic numbers with absolute precision. If you build it up by creating instances of a Python representation of an integer, float, Decimal, or string, ...
0
votes
0answers
19 views
When do floors ceilings matter in recursions and when can we just omit then?
The title is pretty much self explanatory.. When solving recurrences in our Algorithm Analysis class sometimes, we omit the floors and ceilings and sometimes we dont. Can you please explain what's the ...
2
votes
2answers
58 views
Convergence of a Recursive Sequence - An Example
Consider the sequence
$\displaystyle x(k+1) = \frac{1}{2}\left(x(k) + \frac{a}{x(k)}\right)$
where $x(k)$ stands for the $k$th term of the sequence. What does this process converge to, and what is ...
0
votes
0answers
44 views
Prove correctness of the algorithim
Consider the following algorithm min which takes lists x,y as parameters and returns the zth smallest element in union of x and y.
Pre conditions: X and Y are sorted lists of ints in increasing order ...
1
vote
0answers
42 views
Non overlapping areas algorithm
One of my fellow members on stackoverflow has posted a question thread which concerns how to write a mathematical equation to calculate the exposed areas of a window from a group of windows (like on ...
1
vote
1answer
39 views
Balancing two sets while items in one are unmovable
I'm working on a following problem: Given two sets containing jars, each of which is assigned a random weight (weight is a real number), find a way to balance two sets by weight, i.e. the difference ...
0
votes
4answers
121 views
Solving recurrence relations (change variable etc.) problems
I have been given
$$f(1) = 3\\
f(2) = 8\\
f(n) = 6f(n/2) - 8 f(n/4) \;,\;\; n > 0$$
How would I go about solving this? I've tried working so hard to get this to no avail. If someone can ...
1
vote
0answers
19 views
Algorithm for approaching zero delta.
I'm working on translating an old program for a gas-mixing furnace, and I have a logic problem that I believe I need help on the math with.
I have the specimen temperature ($T$), a variable called ...
0
votes
1answer
72 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 ...
4
votes
3answers
69 views
Need help about solving a recurrence relation
I have a recurrence relation which is like the following:
$$
T(n) = 2T(n/2) + \log_2 n.
$$
I am using recursion tree method to solve this. And at the end, i came up with the following equation:
$$
...
0
votes
1answer
117 views
Solving $T(n)=4T(\frac{n}{2})+n^2$
I am trying to solve a recurrence by using substitution method. The recurrence relation is:
$$T(n)=4T\left(\frac{n}{2}\right)+n^2$$
My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
5
votes
2answers
180 views
Sum of the series formula
I need to figure out the sum of the series as quickly as possible in a program given n and k: $$f(n,k)= ...
0
votes
0answers
92 views
Using Secant Method to find number of roots
I have a discrete function,
$ y=F(N) $
where $N$ is positive integer, and I don't know number of roots of this function.
Can I use Secant Method to find number of roots?
For example, If this function ...
1
vote
1answer
19 views
Square terrain recurrence derivation
You have a square terrain with area $A > 0$. You want to add information into the terrain. You want to subdivide the terrain into $4$ quadrants, process them individually, and assemble the results. ...
1
vote
0answers
30 views
Confusion related to time complexity of fast Fourier transform
I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT.
It says that lets say I have a polynomial of ...
1
vote
2answers
38 views
Θ(n) + O(n) = ? (recurrence equation)
If I have a recurrence equation like:
T(n) <= T(n/2) + Θ(n) + O(n)
Is the above expression equal to:
T(n) <= T(n/2) + Θ(n)
Or is that expression equal to:
T(n) <= T(n/2) + ...
0
votes
2answers
171 views
Solving Recurrence T(n) = T(n − 3) + 1/2;
I have to solve the following recurrence.
$$\begin{gather}
T(n) = T(n − 3) + 1/2\\
T(0) = T(1) = T(2) = 1.
\end{gather}$$
I tried solving it using the forward iteration.
$$\begin{align}
T(3) ...
0
votes
0answers
44 views
Solving the recurrences of algorithms
Im having some trouble understanding recurrences.
I have an assignment where I have to solve some recurrences, theyre generally in the form of:
$$T(n) = aT(n/b) + f(n)$$
I have 3 general formulas ...
2
votes
1answer
127 views
Recursive FFT java implementation
Given below is my java program for FFT. For the input {0,2,3,-1} its returns a false output in complex point representation.
...
2
votes
2answers
113 views
Solving recurrences with boundary conditions
I'm trying to follow CLRS ("Introduction to Algorithms") and I just hit a question in a practice assignment I found online that I just can't make any sense of.
Consider this problem:
Show that ...
0
votes
3answers
48 views
Finding an approximate diagonal in a grid
Imagine a 2 dimensional grid, with a variable size of $ x*y $. For this example of figure 1, let $ x=14; y=5 $.
Now one may position "pixels" in this gird. They can only be placed on the grid's points ...
0
votes
1answer
58 views
Is this formula for the number of nodes for a complete tree or a full and complete tree?
In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer:
$$ \sum^{h}_{i = 0}k^i $$
where h is the height and k is the max number of ...
0
votes
2answers
58 views
Explanation needed on this rather basic recurrence solution
We are studying about recurrences in our analysis of algorithms class. As an example of the substitution method (with induction) we are given the following:
$$T(n) = \lbrace 2T\left(\frac{n}{2}\right) ...
3
votes
1answer
264 views
Show that the solution to $T(n) = T(n - 1) + n$ is $O(n^2)$
Hello and thanks for taking the time to answer my question.
The question is really the title itself. We're studying about solving recurrences using the method of substitution and induction. How can I ...
0
votes
3answers
81 views
How can $n \lg n = O(n^{log_3 4 - r})$?
How can I understand this bound, for me it is not true.
$$n\lg n = O(n^{\log_3 4 - r})$$
where $\lg n = \log_2 n$ and $r > 0$
I'm trying to solve this recurrence $T(n) = 4T(n/3) + n\lg n$ using ...
0
votes
2answers
58 views
Properties of algorithms
I have 2 questions.
1.Let's have an algorithm
input a;
x ← -7;
y ← a;
while x $<$ y do
x ← x+5;
y ← 2·x+y-6;
done
Question: What is the greatest "stopping" ...
0
votes
0answers
83 views
Master Theorem $T(n)=4T(n/8)+n^(3/8)$
My try was :
$$f(n)= n^3/5=n^{0.6} g(n) = n^{\log_8}(4) =n^{0.667}$$ so $f(n)<g(n)$
So $f(n) = \Omega(n^{\log_8}(n) + \epsilon)$ but with regularity condition
$4f(n/8) \le cn^{3/5}$ ,for $c$ ...
2
votes
2answers
100 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 ...
3
votes
1answer
37 views
Is every context free language equivalent to one whose grammar has only one non-terminal symbol?
A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting ...
1
vote
1answer
327 views
Which approach to follow: greedy, divide-n-conquer or dynamic programming?
Given any problem
say we have to pick few objects out of N so that the total weight is below W considering all objects of SAME value,
A variation for this problem can be to have values assigned to ...
2
votes
2answers
76 views
Combination/Permutation Question
I'm trying to solve a programming challenge, and I have narrowed down all the challenge to a combination/permutation problem.
I ended up with 5 possible scenarios, and I need to find all possible ...
0
votes
1answer
58 views
Help in understanding search of Vantage-Point tree
This is my reference: http://stevehanov.ca/blog/index.php?id=130
A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It ...
-5
votes
1answer
94 views
What approach can be used to solve this? [closed]
The problem can be found here.
The game is simple. You initially have ‘H’ amount of health and ‘A’ amount of armor. At any instant you can live in any of the three places - fire, water and air. ...
0
votes
0answers
79 views
can we have the worst case complexity of Euclid's algorithm to be $\log\left(\min(a,b)\right)$?
What is the worst case complexity of Euclid's algorithm? Since the run time of Euclid's algorithm depends on the number of digits in the $\min(a,b)$, shall we have it as $\log\left(\min(a,b)\right)$?
1
vote
1answer
281 views
Sum of series with log in each term
I was solving recurrence relation of Introduction to Algorithms by {Cormen, Leiserson, Rivest, Stein}, 3rd. edition. Problem 4-3 (i)
$$
T(n) = T(n-2) + \frac{1}{lg \; n}
$$
I tried few ways, like ...
0
votes
0answers
78 views
On Cooley–Tukey FFT algorithm
Does anyone know why Cooley-Tukey
FFT algorithm has a complexity $O(N\log N)$ for a sequence of length
$N$?
Thanks for any helpful answers.
1
vote
0answers
68 views
A question on algorithm complexity
It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$
for a signal with bandwidth $N$. How to see or show that the fast
Fourier transform ...
0
votes
1answer
451 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
53 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.
...
3
votes
2answers
143 views
Finding the nearest integers to real numbers defined implicitly
I was trying to bound the maximum cost of top-down merge sort:
$$
f(0) = f(1) = 0,\quad f(n) = n\lceil{\lg n}\rceil - 2^{\lceil\lg n\rceil} + 1,
$$
where $\lg n$ is the binary logarithm of $n$ and ...
1
vote
0answers
89 views
Who invented the breadth-first permutation algorithm?
My initial problem was solved here. It is about enumerating all n-tuples of a permutation in a specific order.
The solution algorithm is very simple and I'm sure has been used before. However, I did ...
1
vote
0answers
65 views
Proving that an effective procedure is correct
I will start with definitions, theorems, and a few solved exercises which I am taking as theorems now. My actual question will be last, if you want to scroll ahead to see it.
Definitions:
(1) The ...
1
vote
1answer
224 views
What is the lower bound and upper bound on time for inserting n nodes into a binary search tree?
So given a $n$ array of few numbers(say $n$) we can sort them using the binary search tree (BST) as a black box . In order to that we first build a BST out of the array taking all the elements in ...
1
vote
2answers
776 views
Worst case analysis of MAX-HEAPIFY procedure .
From CLRS book for MAX-HEAPIFY procedure :
The children's subtrees each have size at most 2n/3 - the worst case
occurs when the last row of the tree is exactly half full
I fail to see this ...
