1
vote
0answers
11 views

Algorithm conjecture

This is an algorithm analysis question for computer science. Let f(n) be positive functions. (Dis)prove the following conjecture? $$f(n)+o(f(n))\in\Theta(f(n))$$ o above is the Little O, defined as ...
1
vote
2answers
26 views

Asymptotic Notations in limits

Can the asymptotic notations, like Big O, be defined using limits? example:- Lim x->infi (f(n)/g(n))=c for defining f(n)=O(g(n)) If not, why??
0
votes
0answers
28 views

Produce a list of the most-similar units, given various correlations/relationships

I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...
1
vote
1answer
219 views

Solve non-linear equations of 3 variables using Newton-Raphson Method iterms of c,s and q.

The three non-linear equations are given by \begin{equation} c[(6.7 * 10^8) + (1.2 * 10^8)s+(1-q)(2.6*10^8)]-0.00114532=0 \end{equation} \begin{equation} s[2.001 *c + 835(1-q)]-2.001*c =0 ...
-1
votes
1answer
108 views

MAX-HEAPIFY - why the worst case is when the bottom level is “half full”?

In the 3rd edition of 'Introduction to Algorithms', on page 155, when analysing MAX-HEAPIFY it says: The children's subtrees each have size at most 2n/3 - the worst case occurs when the last row ...
1
vote
1answer
13 views

Defining a region as a data structure

Is there a way for one to define a curve or region (such as a closed, 2-d disk) as a data structure into the computer, and make an algorithm which detects if a point is a boundary point, limit points, ...
0
votes
0answers
18 views

Amortized Analysis Problem

I need to find the cost of the problem below but I cannot find a pattern to find the total cost. Problem: The cost of multiplication of n-bit binary number by 2. If a bit changes the cost of that ...
0
votes
1answer
29 views

asymptotic analysis

For each of the following sentences involving functions f and/or g, find a counterexample to show that it is false: What is meant by counterexamples?
2
votes
0answers
51 views

Expected error due to the tablemakers' dilemma

[note: to me, this does not seem like a question for m.se, but on mathoverflow it has been retroactively closed, with very little indication of why or what might be corrected... and waiting for ...
4
votes
1answer
90 views

Is it true that there is no algorithm to approximate the least upper bound?

I just read the following text below from Bishop's Foundations of Contructive Analysis, is it true that there is no such algorithm? The book is from 1967 - I don't know if someone managed to invent ...
1
vote
1answer
58 views

Do this algorithm terminates?

Let $x \in \mathbb{R}^p$ denote a $p$ dimensional data point (a vector). I have two sets $A = \{x_1, .., x_n\}$ and $B = \{x_{n+1}, .., x_{n+m}\}$. So $|A| = n$, and $|B| = m$. Given $k \in ...
2
votes
0answers
122 views

What is Algorithmic Graph Theory? [closed]

I'm an undergraduate and I signed up for a course next semester called Algorithmic Graph Theory. The course description doesn't give any details on the contents of the class, and there's no listing of ...
0
votes
1answer
38 views

Bounding below the difference of sums

I would like to bound below the following expression: $\lambda(m,n)=\sum\limits_{i = 1}^{m+n}\lg{i} - \sum\limits_{i = 1}^{m}\lg{i} - \sum\limits_{i = 1}^{n}\lg{i}$ by some expression that ideally ...
0
votes
2answers
289 views

Worst case analysis of a basic algorithm

I'm wondering how to perform a worst case analysis on a such algorithm. The basic operation is function. ...
0
votes
0answers
64 views

Graph analysis and runtime.

Hi this is the second last problem in my text book got to do with graphs, and i was wondering if anyone could help me with my pre-exam prep. Specifically, i was having trouble visualizing an algorithm ...
0
votes
1answer
227 views

Which one gives better constant factors between heap sort and quick sort?

Heap Sort has complexity $\mathcal{O}(n\lg(n))$ and Quick Sort with some tuning (choosing the pivot in a random order) on average also sorts in $\mathcal{O}(n\lg(n))$ and both of these are tight upper ...
1
vote
0answers
80 views

Trying to create an algorithm that takes into account multiple variables

I've hit a road block on how I can put what I have into a calculation that works. Simply I am trying to work out the "value" of each company that we have on my companies books. The information I want ...
1
vote
1answer
123 views

Strategy to maximize no. of balls from N boxes

If you have N boxes each containing distinct number of balls and you are allowed to choose at most ...
1
vote
0answers
350 views

Applications of Convergence of a series in Algorithms

We were introduced to testing the convergence of a series & calculating the point of convergence in the first maths of college curriculum. I wish to explore its usage in computer algorithms. ...
1
vote
2answers
1k views

Bellman-Ford algorithm: why V-1 number of relaxation iterations?

Why does Bellman-Ford algorithm perform V-1 number of relaxation iterations? I feel that it is correct when going through examples. But how do we explain it for the general case? I have gone through ...
2
votes
0answers
163 views

calculate the rate of change

I am trying to calculate the change frequency for a set of data. Each bit of data has the date-time it was created. I would like to say for a specific set of data the change frequency is hourly, ...
2
votes
2answers
191 views

Formula to generate a score from 1 to 100 based on 2 percentages?

I am trying to come up with a formula that will result in a score of 1 to 100 (never anything lower or higher). I have two numbers that I can use to come up with this score, a specific percent and an ...
6
votes
1answer
266 views

Algorithmic Analysis Simplified under Big O

Hi I am revising for my exams and I have the following inhomogeneous first order recurrence relation defined as follows: f(0) = 2 f(n) = 6f(n-1) - 5, n > 0 I ...
2
votes
1answer
108 views

Exp function in an averaging algorithm

I was looking at some source code that was described as 'maintaining a moving average over the previous 10 minutes', and noticed it uses the exponential function. Now its been a while since my ...
1
vote
1answer
86 views

Spread evenly $x$ black balls among a total of $2^n$ balls

Suppose you want to line up $2^n$ balls of which $x$ are black the rest are white. Find a general method to do this so that the black balls are as dispersed as possible, assuming that the pattern ...
2
votes
2answers
133 views

Development of a specific hardware architecture for a particular algorithm

How does a technical and theoretical study of a project of implementing an algorithm on a specific hardware architecture? Function example: ...