All Questions
91
questions
3
votes
1
answer
88
views
Why would solving #MATCHING(bipartite) problem efficiently solve #MATCHING efficiently?
Im gathering information about the matching counting problem for a graph $G$ (#MATCHING($G$)). I found that for the specific case of $G$ being a bipartite graph then the problem has a simple (not ...
- 541
0
votes
0
answers
39
views
What is the asymptotically best algorithm for the euclidean Steiner tree problem?
So I would like to know what the fastest (asymptotically, worst case runtime) exact algorithm for the Euclidean Steiner tree problem is. (More precisely, I would like to know the best known algorithm ...
- 131
1
vote
1
answer
217
views
Complexity of a list problem
I have two lists $L_1$ and $L_2$ of real numbers which are of equal length $n$ and I would like to analyze the complexity of the following problem:
Select an index set $I\subseteq \{1,...,n\}$ with ...
- 19
4
votes
1
answer
285
views
Printing neatly
I'm working on the following problem (which is not my actual question)
Consider the problem of neatly printing a paragraph with a monospaced font (all
characters having the same width). The input ...
- 910
0
votes
1
answer
40
views
Is the stable marriage problem defined for $0$ people?
When proving properties of algorithms which are supposed to solve the stable marriage problem, I find myself unable to prove them sometimes in the case of there being $0$ things to pair with each ...
- 3,019
0
votes
1
answer
31
views
How to find the location of an object moving through a graph with inputs of arcs?
I have a bidirected graph which represents rooms in a building. I have scanners set up on doorways which can detect an object moving through them (but not direction). Based on this information what ...
1
vote
2
answers
71
views
Marching cubes generates surface triangles. How to adapt it to generate tetrahedra throughout the volume of a 3D model?
Background
There is a source code that generates surface triangles. The isosurface is generated for the iso-value of 0. The source code uses a table for ...
- 271
0
votes
1
answer
24
views
What is the best-case number of array item comparisons in this algorithm, in terms of n?
The Smart Bubble Sort.
Preconditions: x1, x2, ... , xn is in U, a set that is totally ordered by <, and n ≥ 2.
Postconditions: x1 ≤ x2 ⋯ ≤ xn.
...
- 3
1
vote
1
answer
304
views
Time Complexity of Modular Multiplication
I was reading a paper about the Miller-Rabin primality test and I came across the statement that the time-complexity of a modular multiplication is equivalent to $\mathcal{O}((logN)^2)$ using the ...
- 33
1
vote
3
answers
372
views
finding and proving a greedy algorithm to maximize total energy
Find a function $f:\mathbb{R}^2\to \mathbb{Z}$ that satisfies the following properties, or show that no such function exists:
$f$ is increasing with respect to its first coordinate (i.e. $f(x, a) \...
- 1,166
1
vote
0
answers
54
views
Time Complexity Calculation - Is my approach correct?
Give the running time in terms of n.
...
8
votes
0
answers
314
views
Harmonic Numbers' Numerators Divisible by a Prime $p$
For a prime $p$, I am trying to determine the set of all $n$ for which the numerator of $H_n$ is divisible by $p$, with $H_n$ being the $n$'th harmonic number.
After going through a lot of literature, ...
- 1,022
0
votes
2
answers
65
views
one doubt on big oh notation
I see an example that $f(n)=O(n)$ and $\sum_{i=1}^nf_i(n)=O(n^2) $ in which $f_i$ is a function from natural to natural number.
I ran into a challenge, that above notation is differ from the
...
- 1
1
vote
2
answers
7k
views
How many comparisons does the insertion sort use to sort the lists in question
I have two lists to sort using insertion sort:
How many comparisons does the insertion sort use to sort the list
$n, n − 1, . . . , 2, 1$?
How many comparisons does the insertion sort use to sort ...
- 1,189
1
vote
4
answers
459
views
$ \sqrt n \log \sqrt n$ is lower than $n$ ?!
I see an example in asymptotic notation that not very sensible for me.
what is the intuitive idea to understand $ \sqrt n \log \sqrt n$ is lower than $n$ in concept of asymptotic view?
- 27