Skip to main content
7 votes
Accepted

Arrays. Find row with most 1's, in O(n)

Below is an algorithm which runs in $\mathcal{O}(1)$ memory and $\mathcal{O}(n)$ time. It accepts a $n \times n$ matrix $A$ which is $1$-indexed, follows the constraint described in the problem, and ...
EnEm's user avatar
  • 391
5 votes

Arrays. Find row with most 1's, in O(n)

Hint: If the first row has k 1s, and the second row has k’ 1s, then there is no need to determine k’ at all if k’ <= k. How do you find in O(1) that k’ <= k? And if k’ > k, which you checked ...
gnasher729's user avatar
  • 30.7k
4 votes
Accepted

Approximation algorithm for binary (linear) programs

As pointed out here (Are there practical methods for solving ILP?), there are some usefullness to form your problem as an ILP and directly give that to a solver. There are multiple ways to tackle an ...
codeR's user avatar
  • 1,467
3 votes
Accepted

Minimum Cell Changes to Ensure Unique Numbers in Each Row and Column of an $ n \times n $ Table

Hint 1 If we have a cell $a_{i,j}$ which is duplicate to some other cell $a_{i, j_1}$ in its row, and some other cell $a_{i_1, j}$ in its column; we can always remove this duplicacy by only changing $...
EnEm's user avatar
  • 391
3 votes

What does "computer steps" mean in this runtime definition?

In runtime analysis, we usually define something called a basic operation that can be executed in constant time under the assumed computation model. Since we are going to do an asymptotic analysis, ...
codeR's user avatar
  • 1,467
2 votes

Deducing upper bound for Boolean Circuit size from well-known algorithms

A Turing machine running in time $t(n)$ can be simulated by circuits of size $O(t(n)\log t(n))$; see e.g. https://cseweb.ucsd.edu/classes/sp11/cse201A-a/ln412.pdf .
Emil Jeřábek's user avatar
2 votes
Accepted

How to create a tree of height $lg(n)$ using Union-Find data structure

Use the below recursive construction: constructLogHeightTree($A$) Let $n$ be size of $A$, then: If $n=1$ return Otherwise: Split $A$ into $2$ sets $A_1$ and $A_2$ with $\lceil \frac{n}{2} \rceil$ ...
EnEm's user avatar
  • 391
2 votes

What does "computer steps" mean in this runtime definition?

“Computer steps” has intentionally no precise definition. This is usually about execution time, and we assume that every computer has a constant time T, which is different for every computer, and each ...
gnasher729's user avatar
  • 30.7k
2 votes

How is the prefix function (for KMP) time complexity O(N)?

I figured it out. j never goes negative and it increases by at most n times. Thus the while loop (which always decreases j) will run a lifetime total of not more than n times.
JobHunter69's user avatar
1 vote

Mapping spherical coordinates onto faces of an icosahedron

I have done quite a bit in this area - and will share the repo when I am finished. But for the specific question above, I think a good approach is to use a KDTree. Here is the set of face-centres of ...
Konchog's user avatar
  • 33
1 vote
Accepted

MSOL for a vertex-cover enlargement problem

You can use CMSOL which allows cardinality predicates. See 5.2.6 in this report. This is authored by Courcelle himself. You can refer the original paper by Courcelle too, but it is a bit more terse. ...
Sriram's user avatar
  • 402

Only top scored, non community-wiki answers of a minimum length are eligible