New answers tagged

0

You are correct about the running time: nums.sort((a, b) => a - b); Depends on sorting algorithm, $n \cdot \lg(n)$ assuming merge-sort. for (let i = 0; i < nums.length; i++) $n$ (worst case assuming no duplicates) while (left < right) $n - i$ (worst case, also assuming no duplicates) Running time therefore is: $$O(n \cdot \lg(n) + \sum_{i=0}...


1

If c < 0.5 then this can't be done faster than O(n). Assume the array is all zeroes, with a single 1 somewhere in the middle. You have to examine array elements at least until you find the 1, or until you are left with an unexamined subarray of size 2cn. Since you have no clue where the 1 is, it might take n attempts to find a 1, and n - 2cn attempts ...


2

You problem is solved trivially in order statistic trees, where each node has an additional size attribute, and many answers have already mentioned this situation. So what to do first is to calculate and memorize size for each node ($O(|V|)$), and then do a BST search to find the node with rank $|V|/2$, which is $O(\log(|V|))$ for balanced trees. This ...


-1

i was thinking quicksort. you select as pivot the element that just happens to be the middle element. compare the pivot to the remaining 4 items resulting in two piles to be sorted. each of those piles can be sorted in 1 comparison. unless i have made a terrible mistake, the 5 items were fully sorted in just 6 comparisons and i think that is the absolute ...


0

I wrote the description below thinking that you were asking for all combinations of elements. However, at second glance it is unclear. I'll describe both cases. Combinations So let's talk about the number of combinations. If you're trying to pick $k$ numbers from $1,2,...,n$, there's $2^n$ ways. $$\sum_{k=0}^n{n\choose k} = 2^n$$ This is a subtle hint ...


0

I see two ways of doing it / thinking about it, which are essentially equivalent. Method 1: Use recursion to implement your DFS. When at a node of your tree, you just need to recursively call the DFS on every child node, then output/store the current node (or the other way around). The backtracking will take care of itself. If you don't want to use ...


0

If the numbers are all integers at most $k$, then you can apply a fast algorithm for substring matching with don't-care symbols (see below) to solve the problem in $O(kn(\log m + \log k))$ time by applying the following transformation: Map each text character $t$ to $t-1$ zeros followed by a 1. Map each pattern character $p$ to $p-1$ don't-care symbols ...


1

Use binary search to find the smallest factor, divide and repeat.


1

Simulated annealing, like gradient descent, needs a metric that identifies partial correctness. Unlike gradient descent, simulated annealing tries to escape local minima by randomly allowing state transitions that are not improvements. Instead of randomly generating a new permutation each iteration, you should only generate a full random permutation at the ...


1

To improve your brute force, you would only need to look at the substrings of minimum length, as longer substrings will occur at most as many times as their own substrings. This should take linear time to create the dictionary, and O(nlog(n)) to sort. If this is too memory intensive, you could do pruning by first brute-forcing this for say, substrings of ...


2

I'm assuming we're given an ordered list $(y_0,y_1,...,y_{n-1})$ of initial point positions together with a list $(s_0,s_1,...,s_{n-1})$ of their speeds. You can visualize moving points on a Cartesian plane with "position" and "time" coordinate axes - so the point $P_i$ trace will be a ray $R_i$, beginning at the point $(0,y_i)$ and consisting of points $(t,...


0

Consider a string of 100 million characters with say 100 z’s in between plus a huge number of the characters a to y (and no character lexicographically after z). Find an algorithm that would often give you the correct result in O(n), actually with at most 2n comparisons. Find out why this algorithm doesn’t always run in O(n), then figure out what you can do ...


2

As with most things involving trees, it's easiest to analyse recursively. Given a one-element set $\{a\}$, the only parenthesisation is $(a)$. Given a larger set $S$, we choose an arbitrary element $x \in S$. Then for each proper subset $T \subset (S \setminus \{x\}) $ we have parenthesisations $(p)(q)$ where $p$ is a parenthesisation of $\{x\} \cup T$ and ...


0

Let us start with the subroutine PARTITION. The loop maintains the following invariant: $A[k] \geq x$ for all $k \geq j$, and $A[k] \leq x$ for all $k \leq i$. If the loop ever terminates, then the two ranges "$k \geq j$" and "$k \leq i$" cover the entire array, and in particular, $A[k] \leq x$ for all $k \leq j$, and $A[k] \geq x$ for all $k \geq i \geq ...


0

If you want to reduce Clique directly to 3SAT, you can design a boolean circuit, where the input is a graph and a subset of vertices, and the output is TRUE if that subset is a clique and FALSE otherwise. If the graph has N vertices, you need: N variables, one for each vertex, which is TRUE if it is part of the subset and FALSE otherwise. N * (N - 1) ...


0

In computation, time consume depends deeply on the algorithm we choose. Since the search time consumes log2(N) and insertion time consumes N/2, the insertion time increases sharply as compared to the search time. The only thing is that they depend on size of the symbol table, not the initial size because insertion and search time depend on the actual size ...


1

I think instead of performing merge at the beginning. We can add a node which has the similar edges as the two merged vertices. Having the following DAG. If we want to merge node A and B. We add a new node which has the similar attributes as A + B. Then trasverse from new node AB (should be Depth-first): If it find Node A or B, then the merge should ...


2

Are every problems in EXP karp reducible to any EXP-Complete? Yes. That's the definition of $\mathrm{EXP}$-completeness. My question is: where is my mistake? Your mistake is in believing that $L''\notin\mathrm{EXP}$. You've demonstrated a Turing machine that decides $L$ in time $O(n^{\log n}) = O(2^{(\log n)^2})\subset O(2^n)$. I'm not sure what you ...


3

The term for the problem you seem most focused on is a Sybil attack whose typical solution is some form of identity. Another mitigation is a proof of work system that makes account creation expensive. The goal is to have the cost of creating multiple accounts not be worth the gains. This is more effective when one needs many Sybil accounts to really benefit....


0

Usually dictionaries are not sorted. There are no provisions for accessing items in sorted order, and finding the predecessor and successor of a key take O (n) and are not really useful. What you do however is iterating through a dictionary, that is you have a loop that will visit each key, or each value, or each key-value pair in the dictionary exactly ...


1

It's true that on page 73, the author defines the abstract functions $Predecessor(D, k)$ and $Successor(D, k)$, which find the predecessor and successor of a given key. But the chart on page 74 lists the interfaces as $Predecessor(L, x)$ and $Successor(L, x)$, which find the predecessor and successor of a given entry index. Clearly this is O(1) for a ...


0

This seems reminiscent of design of experiments problem. (link) Rather than check every possible subset, it would be much more feasible do a sample which emphasizes maximizing change. The whole subject was pioneered by R.A. Fisher, who was hired to improve the yield of farmer's crops. Since each experiment required considerable time and land to execute, he ...


-1

I have built a new algorithm to find the minimal set M but I can't check whether the algorithm is correct or not. The algorithm is as follows: 1. Consider the new array formed by multiplying the abssica array and the corresponding ordinate array and arrange it in ascending order. Next we arrange the abssica array and the ordinate array ...


0

Check if this is discussed in the encyclopaedic D. Grune, C. J. H. Jacobs, "Parsing Techniques: a Practical Guide" (Spinger, 2008). If not, perhaps it is similar enough to a technique discussed.


-1

An algorithm that always works is: Put the left hand on the wall, and continue that way to the exit. Can't guarantee shortest path (to do so, you need to know the maze, at least partially, and be able to look forward. Check out the $A^*$ (A-star) algorithm, it was originally designed for just such tasks).


0

By Rice's theorem, to see if the language accepted by a Turing machine has any non-trivial property (here: being context free) is not decidable. So you would have to restrict the power of your recognizing machinery (or description) to make it not Turing complete to hope for an answer. For some language descriptions the answer is trivial: If it is by regular ...


0

Suppose that the array $A$ is chosen in the following way: Sample $n$ real numbers uniformly from the interval $[0,1]$. Sort the $n$ samples. Suppose that you choose a further uniform random variable $x$ from the interval $[0,1]$. The expected running time of interpolation search on $A$ and $x$ is $O(\log\log n)$, where the expectation is over the choices ...


1

The statement $f = O(h)$ just states that there exists a constant $C>0$ such that $f(N) \leq Ch(N)$ for all $N$ (some variants have this hold only for large enough $N$, but in most cases there is no difference). In your case, $f(N) \leq CN^{\log_b a-\epsilon}$ for all $N$. This holds for $N = n/b^j$ in particular, and implies that $$ g(n) \leq C \sum_{j=0}...


2

A clear explicit relationship is that Big Oh is defined via limits which of course are central to calculus.


3

an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step I don't think that's really true. It seems to me that all you're doing here is observing that a discrete linear function changes by a constant amount at each step and wondering if that's connected to the fact that the derivative of a continuous ...


0

I come from a database / transaction background which will influence this answer. My take would be to serialize the downvotes and handle one at a time. The banned function will be handled this way. Unbanning (is this a Word? ) will need to be handle separately: imagine that a troll is banned, a while later the total weight has increased enough for that ...


1

An arbitrary algorithm can't be preemptive or non-preemptive. Preemption is a mode of multitasking, used by an operating system to control user processes. From the Preemption Wiki page: In computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of ...


0

You could do ternary search by splitting into three parts, use one comparison to see if the key has to be in the first third, and another one to distinguish between second and third stretch if it isn't in the first one. Assuming uniformly distributed searches, this would reduce the range to a third with $1/3 + 2 \cdot 2/3 = 5/3$ comparisons. This idea leads ...


1

Timetabling is known to be NP-complete. Your more complex variant is too. Don't expect "nice" or "efficient" solutions. Either settle for an approximate solution (good luck in deriving one) or some sort of randomized heuristic. I'd try some variant of genetic algorithms (look around for it's application to time tabling, they use special mutation and ...


5

The solution outline: Step 1. Verify, that all the initial (at the moment $t=0$) wave circles don't contain your starting point $(0,0)$. If yes, then continue - otherwise exit, no escape. Step 2. For each wave circle $W_i$ you need to find an escape sector - the range of directions, where the escape is guaranteed. Imagine a circle of your possible ...


1

Yes, you can. Kadanes's algorithm keeps the value of the best subarray in a variable, let's call it best_sum. Notice the invariant in the algorithm. best_sum will always (after each iteration) contain the value of the maxium subarray of the prefix of the array that you already visited. Additionally you know the best suffix sum of the current prefix, let's ...


3

You're mistaken. The analysis of the Karatsuba algorithm takes addition and subtraction into account. If you analyze your pseudo-code, you can see that you have exactly 3 recursive function calls with arguments of size $n/2$, and all other operations like addition, subtraction, extracting the higher and lower bits, ..., run in $O(n)$. Therefore you get ...


3

$n! = n \cdot (n-1) \cdot ... \cdot 1 \ge n \cdot (n-1) \cdot ... \cdot (n/2) \ge (n/2)^{(n/2)}$ so $\log(n!)≥c\cdot n\cdot\log n$ for $c \ge 1/2$


2

... further simplify $(n/2)\log(n/2)$ --> $(n/2)\log(n^{-2})$, ... This is wrong. In fact, for $n\ge 3$, $n^{\log_3 2}\ge 2$, so \begin{align} (n/2)\log(n/2)&=(n/2)(\log n-\log2)\\ &\ge (n/2)\cdot\left(1-\log_3 2\right)\log n\\ &=\left(1-\log_3 2\right)/2\cdot n\cdot \log n, \end{align} and $\log(n!)\ge \left(1-\log_3 2\right)/2\cdot n\cdot \...


0

As others have noted, it depends. Generally speaking, a polygon is non-degenerate if it has no anomalous points, but this just pushes the problem back one step; what is "anomalous"? The real answer is that a polygon is degenerate if it violates the specification. The slightly rude answer is that a polygon is degenerate if it is an edge case which your ...


0

A degenerate polygon is one that has zero area.


2

Each summing approach can be represented by a binary tree: the leaves represent the original elements and each internal node (including the root) represents the result element of the addition of the elements represented by its two children. For example, Input: [1, 5, 3, 7] Adding 1 and 3 together (Cost 1+3 = 4) State: [5, 7, 4] Adding 4 and 5 together (...


0

Any algorithm which follows the cycles of the permutation will do. They move an element out of the way, place the element that has to take it's place, fill in it's position, until exhausting a cycle; go for the next cycle. Time is $n$ + number of cycles (clearly $O(n)$); extra space is one element worth.


4

First note that $\text{increase-key}$ must be $O(\log n)$ if we wish for $\text{insert}$ and $\text{find-min}$ to stay $O(1)$ as they are in a Fibonacci heap. If it weren't you'd be able to sort in $O(n)$ time by doing $n$ $\text{insert}$s, followed by repeatedly using $\text{find-min}$ to get the minimum and then $\text{increase-key}$ on the head by $\...


0

My original post regarding a variant of the 3SUMx3 problem was in error. However, I believe I was in the right path and have edited the post with a new algorithm. Let's say we have a set S which needs to be split into 3 sets such that we can then run the 3SUMx3 algorithm on it. Also let's assume that the entries in S form an alphabet of range (0, M] such ...


1

Bellman-Ford simply returns there exists at least one negative-weight cycle, it doesn't actually find all edges part of all such cycles. At best, without extending the algorithm too much, you find at most one edge per negative-weight cycle as cycles may intersect. There are ways to recover a negative weight cycle, see the link you provided, but this is ...


0

I don't know the name of the problem, but I do know the solution - this is the same problem that I had to solve for my algorithms course, just different terminology. The problem allows for a greedy choice. If you merely wanted a hint, then stop reading here because below is the solution. Greedy choice: you schedule the job with maximum profit on its ...


1

In the field of Denotational semantics they have developed a (very) formal definition of iteration in terms of recursive functions that you might like to look into. https://en.wikipedia.org/wiki/Denotational_semantics


1

So first of all lets consider the techniques. Nearest neighbour is a heuristic that directs the search. That means that it informs how the search should proceed. It can be seen as preemptive. The 2-opt is not a search heuristic but is a technique used to attempt to improve a solution(partial solution). You can think of it as massaging the solution into a ...


1

This would fall under something called black box optimization. In general, there are several methods you could try in practice such as (stochastic) hill climbing or say a genetic algorithm. Such methods might seem "random", but they take some care in moving in a smart way but also use some "randomness" to escape local optimums.


Top 50 recent answers are included