16

You can say that an algorithm is asymptotically optimal in such a case. In general, people might also say that an algorithm is optimal in some other sense, like assuming some particular complexity-theoretic conjecture like (S)ETH.


4

This is the so-called "nuts and bolts" problem, and your pivoting approach can be shown (under uniform choices of pivots) to give a randomized algorithm with expected query complexity $O(n \log n)$, using the analysis of Quicksort as a template. Fast deterministic algorithms are less obvious. The first true breakthrough paper I know of for this is that of ...


4

I have been implementing a branch and bound solver with heuristics for an NP-hard problem. It got complicated at some points and had to reimplement parts a couple of times. The problem was (I think), that I started implementing with only an intuition about the design and how it looks like. That is bad software engineering and is catastrophic in big project. ...


3

You're asking to enumerate all maximum matchings in a bipartite graph. Unfortunately that problem is #P-complete, so there is unlikely to be any efficient algorithm that works on arbitrary size graphs. There might be algorithms that work well enough for your situation, given the small numbers you're dealing with. For instance, a simple approach is to use ...


3

For your first question: O(n logn) might be 4nlogn or 13nlogn or 0.1nlogn etc. If you compare 4n^2 and 100nlogn you will see that for n < about 200 the O(n^2) is faster. Big O is an asymptotic measure. It says what happens when n approaches infinity, but does not say anything about “smaller” inputs. For your second question: You have n/k sublists. Each ...


3

Consider the following special case where for each element $i$ the table contains the constraint $\#i \geq (1/l) \cdot l$. This means we need to select the sets in such a way that each element appears at least once. This problem is called the set covering problem, where you have to output whether there is a subset of $l$ sets in the input that covers all the ...


3

There are $9592$ primes below $10^5$. You can convert each number in each array to a sparse binary vector of length $9592$, signifying the parity of the power of each prime. Using radix sort, sort each of the arrays, and then merge them. Denoting by $a_x,b_x$ the number of times that $x$ appears in each of the arrays (respectively), the answer is $\sum_x a_x ...


2

If we assume any given square can be the head or tail (but not both) of at most one snake then clearly an upper limit on the number of snakes on a $n \times n$ board is $\frac {n^2} 2$. For a $m \times n$ board we can generalise this to $\frac {mn} 2$. And we can reach this upper limit if either $m$ or $n$ is even. What happens if $m$ and $n$ are both odd ?


2

Sorry, but you can’t just count loops, the number of loops is totally irrelevant. If you count nested loops, that is slightly significant but can be very misleading. You need to count how many iterations a loop performs. In the first example, the number of iterations is up to primes.length, which is around n / log n. In the second example, the number of ...


2

Disclaimer This solution assumes that the language $\text{Acyclic}$ is the language that contains exactly all acyclic directed graphs. It is impossible to achieve this in polynomial time unless $\operatorname{P}=\operatorname{NP}$. The reason is that the problem you have to solve is NP-hard. It is called the directed feedback arc set problem. It is one of ...


2

We measure the running time as a function of the length of the input, not as a function of $n$. So, it doesn't matter whether the length of the input is $2^n$ or not. When we talk about an exponential-time function, we normally mean exponential in the length of the input, not exponential in some other parameter (like $n$). For your problem, the length of ...


2

In my opinion the problem statement seems poorly posed. It's not clear what is meant by the problem statement. Normally, if we write $a$ or $b$ the assumption is that they are a constant: they do not depend on $n$. If they are intended to be a function of $n$, then they should be written as $a(n)$ or $b(n)$. Since that wasn't done, the only assumption I ...


2

(Not enough reputation to comment, so writing here.) Unless your algorithms are secret, please post your algorithms here. Maybe someone (not me though) can find a library for you. Maybe someone can tell how long does it take to implement it. Use Git and GitHub. You can rollback bad code with this. Always write tests. This helps against regressions as you ...


1

Here is a simpler solution if points lay only on the axis running in time $O(n^2)$. scroll down for a solution for the general case for any set of points in the plane. Let us distinguish three case of triangles. the first is when the origin is a point of the triangle (and hence it must be the right angle). The second case is where two points lay on the $x$ ...


1

To be an algorithm designer, you have to do some steps. First, learn the basics of algorithmic thinking. You can learn it by using a simple programming language book. Choosing the language is not important. You can take a look at this page for finding a book. After finishing this step, you have to be able to present pseudocode (or code written in a specific ...


1

If your shapes are not too elongated, you could calculate their axis-aligned bounding boxes (BBs) and store these bounding boxes in an index, such as R-Tree, quadtree or one of their more modern variants. Then: Define a distance function that gives the closest BB to the BB of your search-object. Find the BB in the index that is closest to the BB of you ...


1

Compute sums for the first two halves of the arrays, if they agree, the difference (if any) is in the second halves. If they don't agree, check first quarters, and so on.


1

As Jeff Erickson says in his book, "greedy algorithms never work". (Except in the --rare-- cases where they do, and they offer simple, efficient approximations to many NP-hard search problems, see for instance Kun's "When Greedy Algorithms are Good Enough: Submodularity and the (1 – 1/e)-Approximation", check also Krause and Golovin's survey for more in-...


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