7

Here is the fastest algorithm. I bet. The idea of the algorithm can be seen from the one-line explanation between step 4 and step 5 below. Input: $e_1,\cdots,e_n\in E$, where $n\ge 3$. Output: $p_1, \cdots, p_n$, where $p_j=e_1\cdots e_{j-1}e_{j+1}\cdots e_n$, the product of all input elements except $e_j$. Procedure: Allocate array $p_1, p_2,\cdots, p_n$ ...


3

There is no one true answer. It depends on context. The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time". Polylogarithmic time is used only in very narrow contexts. In general, if you think your audience might not be sure about ...


3

What you might have heard could have been a formulation of a No Free Lunch Theorem. Loosely, those results say that you can either have an optimization algorithm that does fairly well on many problems, or really well on some problems, but not both. Genetic Algorithms are rather broad classes of optimizers, so you can typically apply them to many types of ...


2

Swift does the same thing (having both value types and reference types). I'm sure there are efficiency studies, performed by the people implementing the Swift compiler. But the difference between reference types and value types goes a lot deeper. What you need to look at is things like mutability, semantics when passing parameters, and so on. I don't ...


2

There is a faster way than Dmitri's method. You can hash a length-$k$ sequence $f$ to $\sum_{i=1}^k h(i,f(i))$, where $h$ is any two-input hash function. This way, you can update the hash of a file even if you only know the part of the file that has been changed. Such a hashing technique is good enough in the sense that changing or rearranging terms in the ...


2

@Tassle algorithm works great but needs more explaining for vectors ordering. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ties by putting end-times before start-times. Set a counter = 0 and an empty unordered set S. Now go through your vector of times in order. The priority for the first ...


2

I suppose you want to delete as little EmptyEvents as possible. In that case, you can achieve what you want in O(nlog(n)) time, where n is the number of events. Proceed as follows: First, get rid of the EmptyEvents which overlap with a NormalEvent. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ...


2

You can have a look on DFS-B in http://web.cs.unlv.edu/larmore/Courses/CSC477/bfsDfs.pdf DFS-A can have multiple copies on the stack at the same time. However, the total number of iterations of the innermost loop of DFS-A cannot exceed the number of edges of G, and thus the size of S cannot exceed m. The running time of DFS-A is O(n + m). It is ...


1

Optidad’s answer is almost perfect, but only if you ignore week numbers. If the first four days of a year or more fall into the same week, then they are in the first calendar week of the year. But if only one, two, or three of the first days fall into the same week, then they are in the last calendar week of the previous year. The last calendar week of ...


1

Basically, the "configuration" of a year, if I understand well can be described as a state $Y_i = (D_i, L_i)$ with $D_i$ the weekday of January the $1^{st}$ (0 to 6 for monday to sunday) and $L_i$ which is 1 if $Y_i$ is a leap year and 0 else. So, comparing the state of 2 years, you can decide wether they have the same configuration. As a year has 365 days ...


1

Algorithm A contains an instruction that is executed $size * 10000$ times. Algorithm B contains an instruction that is executed $size * size$ times. It is obvious that the comparison between A and B depends on the variable size. You can see that if $size < 10000$ then B performs better, and if $size > 10000$ then A performs better. If $size = 10000$ ...


1

Algorithms don't care whether you find out what edges lead from a vertex by looking them up in an array, by calling a function called get() or by waiting for divine revelation. The only problem with Dijkstra's algorithm is that, as it is usually described, it starts by setting the distance estimate of every node to infinity and adding every node to a queue. ...


1

Obviously you can't say it's $O(N^3)$ because X might grow a lot faster than N. But you can't even say it's O (N x M x X), because you don't know how often the "list.append(count)" is executed and what the time complexity of that operation is.


1

I think an even better approach is the solution on C# which I developed for similar problem - https://github.com/kostadinmarinov/scc dfs(verticies, getNeighbours): visited <- {} return recursiveSelect( filter(verticies, (vertex): visited does not contain vertex), (vertex): dfsNext(vertex, visited, getNeighbours)) dfsNext(vertex, ...


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