58

You are conflating a number of issues here. Why does my software have all these features to begin with? Because other computers' software has those features, and network effects punish any software developer who doesn't follow the herd. Let's take an example from your question: Why does my web browser need to do anything other than basic HTML and CSS? ...


21

I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log (n^2))$, or if those are mathematically incorrect. Yes, $O(2n^2)$ or $O(\log (n^2))$ are valid variations. However, you will see them rarely if you would see them at all, especially in the end results. The reason is that $O(2n^2)$ is $O(n^2)$. Similarly, $O(\log (n^2)...


13

You are always free to not use this notation at all. That is, you can determine a function $f(n)$ as precisely as possible, and then try to improve on that. For example, you might have a sorting algorithm that makes $f(n)$ comparisons, so you could try to come up with another sorting algorithm that only does $g(n)$ comparisons. Of course, all kinds of ...


13

Since the other answers go pretty well into why companies just buy general purpose computers, I wanted to give an answer about security. In a lot of ways, it's easier to secure a system you know is insecure, than to secure a system you are pretty sure is secure but don't know in what ways it might be insecure. Windows 10 may have security vulnerabilities, ...


7

Since Vince asked me to publish my solution, I decided to write this long post. Please bear in mind that this code is really really basic and absolutely not optimized, written as fast as possible to perform some test. Credits for Hungarian algorithm code must be done to vivet. PURPOSE I need to create shifts for M workers (variable number each week) on N ...


7

While the accepted answer is quite good, it still doesn't touch at the real reason why $O(n) = O(2n)$. Big-O Notation describes scalability At its core, Big-O Notation is not a description of how long an algorithm takes to run. Nor is it a description of how many steps, lines of code, or comparisons an algorithm makes. It is most useful when used to ...


6

For the sake of completeness (since Vince has given you good help already, and it seems like you've got a program that works): This is known as the assignment problem: given some set of workers and some set of shifts, where each worker might have preferences about which shifts they take, how can you find the optimal schedule? The standard solution to it is ...


6

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not. In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that ...


5

You can write $O(f)$ for any function $f$ and it makes perfect sense. As per the definition, $g(n)=O(f(n))$ if there is some constant $c$ such that $g(n)\leq c\,f(n)$ for all large enough $n$. Nothing in that definition says that $f$ must be some sort of "nice" function. But, as other answers have pointed out, $g(n)=O(f(n))$ and $g(n)=O(2f(n))$ ...


5

The problem can be solved in time $\tilde{O}(n^{4/3})$, using several algorithms: Agarwal, Partitioning arrangements of lines II: Applications. Chazelle, Cutting hyperplanes for divide-and-conquer. Matoušek, Range searching with efficient hierarchical cuttings. There is an essentially matching lower bound due to Erickson, New lower bounds for Hopcroft's ...


5

"If I were running a company ... the employee would see only the "sections" that are relevant for them, coded by me." You are not prescient. You cannot predict the future requirements of all your employees with sufficient accuracy to know the minimum set of "section" that are relevant or suitable for any given employee. The work required to refine this ...


4

This problem, which I'll call CO for Column Ordering, is NP-hard. Here's a reduction from the NP-hard problem Vertex Cover (VC) to it: Decision problem forms of VC and CO Let the input VC instance be $(V, E, k)$. It represents the question: "Given the graph $(V, E)$, is it possible to choose a set of at most $k$ vertices from $V$ such that every edge in $...


4

Using any/all (a.k.a. or/and) gives rise to alternating Turing machines. Goldschlager and Parberry (On the construction of parallel computers from various bases of boolean functions, Theoretical Computer Science 48:43–58, 1986) consider the generalization to allowing arbitrary Boolean functions, and they call the resulting machines extended Turing ...


4

Here's an O(1) space, O(n) time algorithm with Java code. Logic: Let $P_i$ denote the price of the stock on day $i$. Calculate maximum profit for $1^{st}$ transaction by $selling$ at or before day $i$ the usual way i.e. by calculating $Max(P_i - min[P_0...P_{i-1}])$. Call this $MaxProfit1_i$. If you had sold before day $i$ you can buy again at day $i$. ...


4

Edit: See my answer to the same question on math stackexchange here. I've copy and pasted the answer again for ease of use. There has been a recent line of work investigating algorithms for submodular optimization problems when the objective may take negative values. So far, the non-negativity that we can handle is when the submodular objective decomposes ...


4

You can consider the 1D-position of the 2 runners as one 2D-position. X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100). Then all the goal points coordiantes can have a 2D-position in the same way, for instance (40, 70). Now the Travelling salesman problem has to be solved using the ...


4

Look at the definition of O(f(n)), and you see that for example O(2n^2) and O(n^2) are exactly the same. Changing an algorithm from 5n^2 to 3n^2 operations is a 40 percent improvement. Changing from O(5n^2) to O(3n^2) isn’t actually any change, they are the same. Again, read the definition of O(f(n)).


4

It may be helpful to understand that Big-O describes a set of functions. That is $O(f(n)) = \lbrace g(n) | \exists n,c>0: \forall m > n: c\times g(m) \le f(m)\rbrace$ The usage of $=$ is kind of unfortunate and using $\in$ would make that relationship a lot clearer. but the set notation symbols are a bit difficult to type so now we are stuck with the ...


4

I could do QuickSelect (j - i) times to get all the elements Overkill. Two calls to QuickSelect and one linear pass are sufficient.


4

I'd use a simple username/password system, with no password resets or two-factor auth Password resets are required somewhere because people forget passwords. 2FA is required sometimes because they leak, as it turns out that building software free of security bugs is incredibly difficult. and once logged in, the employee would see only the sections that ...


4

I would argue that the premise of the question makes a wrong assumption: There is an enormous amount of people that use computers set up to perform a single task. Behind the scenes, they're generic systems running a full OS and having all capability, but the machine has been specialized for some tasks. For example: Cashiers use machines which are commonly ...


3

As Vince observes, your problem is TSPP (traveling salesman path problem) on the plane with respect to the $L_\infty$ metric. On the plane, the $L_\infty$ and $L_1$ metrics are equivalent (the unit balls differ by a rotation of $45^\circ$), so your problem is equivalent to TSPP on the plane with respect to the $L_1$ metric. This problem has been addressed on ...


3

I believe the best algorithm known is Hopcroft and Karp, "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs", SIAM Journal of Computing 2:4 (1973), pp 225-231.


3

The problem is strongly $NP$-complete by reduction from 3-Partition. Given a set of $3n$ integers with total sum $3M$, we want to determine whether they can be partitioned into $n$ triples, each having sum $M$. Note that we can assume that no four integers have sum $\leq M$. Suppose a day is $3M+n-1$ units of time long. We want to visit $n-1$ museums $m_1,\...


3

Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.


3

1-IN-3SAT is an NP-complete variant of 3SAT in which the goal is to determine whether some assignment satisfies exactly one literal per clause. We can convert an instance of 1-IN-3SAT (even without the restriction on the number of literals per clause) to an equivalent instance of quadratic programming in which all the variables are constrained to be non-...


3

Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values). Let say we know that all integers in $A$ are 32-bit values. Use the following steps: Create an empty trie. Every node of trie may contains at most two children for 0 and 1 bits. Insert all values in $A$ into ...


3

TL;DR: Modern computers are general purpose tools. They have a huge diversity of capabilities which will never be used simultaneously. All of these capabilities integrate with each other which creates huge complexity. More specialised systems are not created because generally it is more expensive to make and sell a reduced feature system than an existing ...


3

The general $n \times m$ case is easily seen to be NP-hard by reduction from set cover. Add a column for each element; each row is the indicator function of a subset; set $t_j = 0$ for each column. A slightly more complicated reduction from subset sum shows that this is NP-hard even for $m = 2$. Suppose we are given a subset sum problem instance where we ...


3

Solve two linear programs. The first has the constraints $$ A \mathbf x = \mathbf b,\quad x_1 = x_2 \le x_3. $$ The second has the constraints $$ A \mathbf x = \mathbf b,\quad x_1 = x_3 \le x_2. $$ Choose whichever solution gives you a smaller value for $\mathbf c' \mathbf x$. This works for your particular situation. It doesn't scale to a case where you ...


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