0
votes
0answers
15 views
Algorithm for topological sorting without explicit edge list
Suppose I have a set of vertices $V$ and a function $f(V_1, V_2)$ which given two vertices returns +1 if there is an edge from $V_1$ to $V_2$, -1 if there is an edge from $V_2$ to $V_1$, and 0 ...
0
votes
1answer
31 views
Doubts related to set cover NP complete problem
I have some doubts related to the set cover NP complete problem. I am trying to show that a problem is NP complete so I am trying to transform the Set Cover problem to it. However, I have some doubts
...
1
vote
1answer
26 views
Computing the running time of the Fermat primality test
I have a question concerning the Fermat primality test and its running time. According to Wikipedia: "Using fast algorithms for modular exponentiation, the running time of this algorithm is $$O(k ...
1
vote
1answer
48 views
How to get the bounds of exponential function
I have this function $(\frac{d}{d+1})^d$. How can I get the lower and upper bound of this function
0
votes
0answers
23 views
Greedy Optimized Subset-Sum Problem
Given positive integers $a_1,...,a_n,b$, find $x_1,...,x_n \in \{0,1\}$ such that $a_1x_1 + ... + a_nx_n \lt b$ but is as large as possible.
How do I show that there is a greedy algorithm to this ...
4
votes
2answers
70 views
Minimum distance of a binary linear code
I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix.
How can I find parameter $d$ efficiently?
I know the method that compute all the codewords and take ...
2
votes
1answer
24 views
knapsack with only odd elements
Is it feasible to solve the subset sum problem if all the elements are odd and we also know that whether odd or even no. of elements are used to form the sum
for example -
If i have the set -{ 9, 13 , ...
2
votes
0answers
48 views
Solving recurrence relation of algorithm complexity?
Supposing I write an algorithm that results into this kind of recurrence relation
$$\left\{ \begin{array}{ll}
T(0)=T(1)=1 \\
T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 ...
0
votes
1answer
80 views
understing Cook theorem and input length
Following is my understanding of Cook theorem.
Let P be a $\mathcal{NP}$ problem.
And let M be a polynomial NDTM for P,
$$
M(x) = \left\{
\begin{array}{ll}
1\text{ if x∈ P}\\
0\text{ ...
1
vote
1answer
41 views
Restricted partitions?
Suppose I have an integer N and i want to partition it, it must only involve numbers in set $S$ and the number should appear only once.
For example if $N = 12$ and $S = \{3, 5, 7\}$ the answer should ...
5
votes
1answer
51 views
Maximal Zero Sums Partition
You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
0
votes
1answer
67 views
algorithm and Cook theorem
Let $A$ be a set of decision algorithms which are running in polynomial time and which takes natural numbers as inputs.
$x\in A$ if and only if
for $i\in N$
$x(i)=0$ or $x(i)=1$
...
1
vote
1answer
45 views
What does it mean for a function to be polynomially bounded
There is a definition in my notes and says,
When functions are polynomially bounded, the initial conditions (the value on
small inputs) do not make a difference for the solution in ...
0
votes
0answers
37 views
Potential function in amortized analysis
I am trying to calculate the amortized cost of a dynamic array, that's size becomes 4 times the size when the array is filled. (when you re-size, you create a new one and copy the elements there).
...
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 ...
1
vote
1answer
43 views
Time complexity of a modulo operation
I am trying to prove that if $p$ is a decimal number having $m$ digits, then $p \bmod q$ can be performed in time $O(m)$ (at least theoretically), if $q$ is a prime number. How do I go about this?
A ...
0
votes
1answer
116 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 ...
2
votes
1answer
100 views
How to show that Eratosthenes sieve algorithm has a complexity of $O(n\log n)$
I know this is a loose upper bound, but I am in an entry level CS course that is just trying to get us used to evaluating algorithms. Any pointers on how to move forward on this problem?
0
votes
2answers
35 views
How can we denote the following function in terms of big-O notation?
I have got a function and want to denote it in terms of bigO notation.
f(n) = log4n+n*(1/3). Is this function O(n)? (* here is the multiplication) Thanks for your help
1
vote
1answer
36 views
Complexity analysis of logarithms
I have two functions, f(n)=log(base 2)n and g(n)=log(base 10)n. I am trying to decide whether f(n) is O(g(n)), or Ω(g(n)) or Θ(g(n)). I thinks i should take the limit f(n)/g(n) as n goes to infinity, ...
1
vote
2answers
32 views
The growth rate of the functions with respect to each other
There are two functions , for example $f(n)=3\sqrt{n}$, and $g(n)=\log n$. Which one dominates, in other words, is $f(n)=O(g(n))$ or $f(n)= \Omega(g(n))$?
Thank you.
1
vote
0answers
42 views
Asymptotic notation of the following function
I have two functions, $f(n)$ and $g(n)$, and I am trying to determine whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$. I am not sure about my answers. Help will be appreciated.
a) ...
3
votes
1answer
22 views
Indicating the complexity of functions
I am not sure about my answer about the following question. Can anyone help?
I try to express whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$, where $f(n)=n^{0,1234}$ and ...
1
vote
0answers
29 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 ...
2
votes
1answer
59 views
The Two Clique problem is in P or NP? P != NP for hypothesis.
I need to find a solution to the following question:
The problem of the "Two Clique" is in P or NP-complete (assuming P != NP)?
The "Two Clique" problem is the following:
Given a graph G = (V, E), ...
4
votes
1answer
95 views
Issue while applying Master Theorem
I've read about the master theorem for solving recurrences in Introduction to Algorithms, but have a problem (probably, due to misunderstanding) while applying it in some cases. For example, having ...
0
votes
0answers
41 views
Maximum Independent Set by Distributed Algorithm
Maximum independent set on the ring could be found by distributed algorithm like following (unique UID's is required).
...
1
vote
1answer
56 views
Help finding Complexity in Big-O notation
I have found the complexity of an algorithm as the expression below. How can I find the complexity in big O notation for such expression? Or prove that it's bounded by $n^3$ or $n^4$. Can I use triple ...
2
votes
1answer
46 views
A way to codify (pre-calculatate) if a one Tree Node is a descendant of another
I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing):
What I need is a ...
1
vote
0answers
51 views
Maximum Independent Set on Path and Ring
I known this question is more appropriate to cs.stackexchange.com, nevertheless I want to ask it in Mathematics part because for solving the following problem strong understanding of probabilistic ...
1
vote
1answer
36 views
Construct intractable instance of set cover
Choose an integer n and construct the set S with n elements. Then construct a set, s, of subsets of S such that finding the minimum subset of s (that minimises the sum of the orders of all chosen sets ...
2
votes
1answer
83 views
Does $\Theta(m \log n)$ and $0 < m < n^2$ imply $\Theta(n^2 \log n)$?
If we have an algorithm with complexity $\Theta(m + n^2)$ and we know that $0 < m < n^2$ then its complexity becomes $\Theta(n^2)$. But if we had an algorithm with complexity $\Theta(m\log{n})$ ...
5
votes
0answers
86 views
What's the most efficient algorithm for Divisibility?
What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
6
votes
1answer
735 views
What is the time complexity of Euclid's Algorithm (Upper bound,Lower Bound and Average)?
I looked it up online in many sites but none give a clear answer. They all give a lot of complicated mathematical stuff which is not only hard for me to grasp but also irrelevant as I simply want to ...
1
vote
1answer
112 views
How to prove CYK algorithm has $O(n^3)$ running time
I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final.
I'm trying to find out how to prove the algorithm has worst case running time ...
1
vote
1answer
451 views
Algorithm to check whether a graph has no cycles
Let $G=(V,E)$ be an undirected graph. Design an algorithm which decides whether the graph contains a cycle and proove its correctness and determine its complexity in terms of ...
0
votes
0answers
118 views
Solve recursion formula using Recursion Tree concept
I'm trying to figure out an important idea regarding solving Regression formulas / Recurrsion formulas using the Recursion Tree idea.
I will first write down the exercise and then I'll try to explain ...
0
votes
2answers
55 views
what is the complexity and how to start
Every year, Prof Gupta assigns the instructors to various faculty committees. There
are n faculty members and c committees. Each committee member has submitted a list of
their prices for serving on ...
3
votes
1answer
170 views
contiguous sublists of a list with positive sum
Does anyone know of an algorithm that finds contiguous sublists of a list with positive sum? Preferably in O(n). I'm more interesting in the max length of those lists.
Thank you in advance.
1
vote
3answers
90 views
Order of magnitudes comparasions
I have a list of order of magnitudes I want to compare.
My only idea is using calculus methods (limits , integral, etc...) to assert the functions relation.
I need your help with the following.
I ...
0
votes
3answers
58 views
Big-O compared to a new Operator
I'm trying to figure out a new operator compared to the Big O.
Suppose we have two positive functions, $f(n)$ and $g(n)$ then we say that $f(n) = O^*(g(n))$ if there exists a constant $ c > 0 $ ...
0
votes
1answer
78 views
Difficulty proving / finding witnesses for the following Functions (Big O and Big Ω and $\Theta)
I have left with some functions I can't find witenesses for proving Big O and Big Ω and Big $\Theta$ relations.
Notice that I should prove the following using the defintion and not any complex ...
1
vote
1answer
87 views
Polynomial complexity algorithm of partition problem with sets of equal size
Partition problem is well known ( http://en.wikipedia.org/wiki/Partition_problem ).
Let's add an additional condition: sizes of both sets should be equal. Is there a pseudo-polynomial solution to ...
1
vote
2answers
89 views
Sorting Algorithm analysis on a list of 0 and 1 element.
I'm trying to understand the difference would it make if following sorting algorithms are given a set of binary inputs i.e. collection of 0 and 1's only.
a) Heapsort
b) Quicksort
c) MergeSort
d) ...
0
votes
2answers
108 views
Inverse of matrix with QR method
What is the complexity of finding the inverse of matrix by QR decomposition? A is a $n×n$ with full rank.
1
vote
2answers
102 views
Algorithmic Complexity of $i^2$
I am new to the Big O notation in regards to algorithm design. I have had some exposure to it but I am not sure how to find the algorithmic complexity of a given function for a summation. If someone ...
0
votes
2answers
48 views
Triples algorithm complexity
This not optimal algorithm count the number of distinct triples $(i, j, k)$ such that $a[i] + a[j] + a[k] = 0$.
...
4
votes
1answer
245 views
Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?
I have been reading Introduction to Algorithms by Cormen et al. Before explaining Strassen algorithm the book says this:
Strassen’s algorithm is not at all obvious. (This might be the biggest ...
4
votes
2answers
200 views
Time complexity to calculate a digit in a decimal
As we know, it is quiet fast to calculate any digit in a rational number. For example, if I'm given 1/7 (0.142857 142857 ...) and any integer K, I could easily return the Kth digit of 1/7, by doing a ...
1
vote
1answer
222 views
Worst case of Heapify is $\Omega(n \lg n)$
Worst case of Heapify is $\Omega(n \lg n)$
I know that Heapify is $\Theta(\lg n)$, but I don't know if $\Omega(n \lg n)$ is equivalent.
Thanks.
