New answers tagged

0

The reason is instead of aligning the sheep at the edge, you want to align them at that sheep. Example: *.*.* Here, instead of solution ..*** (3 moves) or ***.. (3 moves), the ideal solution is .***. (2 moves). Proof: Clearly, some sheep makes 0 moves in the optimal solution. Assume in the optimal solution, i < m is that sheep, and the solution takes less ...


2

I don't see a need for any interesting algorithm. In its essence it is equivalent to the following: given an array $A$ of integers and an integer $x$, move all instances of $x$ to the front of $A$, keeping the rest in the same order. Once you can solve that, you can apply it to each node of your tree. To move all instances to the front, one approach is to ...


3

If the algorithm terminates at all then $A[i] = i$ for $i \leq n-1$, and so $A$ is sorted. Hence it suffices to show that the algorithm terminates. Furthermore, when reaching $i = i_0$, we know that $A[j] = j$ for $j < i_0$, and so $A[i_0],\ldots,A[n]$ is a permutation of $i_0,\ldots,n$, which is a smaller instance of the same problem. Hence it suffices ...


1

If you're familiar with cycle sort, you can start to see that this algorithm also operates in a similar way (although it's super inefficient). Essentially, the inner loop doesn't terminate until the element in the current position $i$ is $i$. So when the outer loop moves on to the next element, you are guaranteed that the subarray to the left is sorted and ...


0

Short answer: Regular $\subseteq$ Context-free $\subseteq$ Decidable $\subseteq$ Turing-recognizable Long answer: take a look at the computation models. You will see that each one is an extension of the one before it.


1

Adding to @Djrocks192s answer, we can also calculate it like that: $$\sum_{i=x}^{x+n} i = \sum_{k=0}^n x+k = nx + \sum_{k=0}^n k = nx + \frac{n(n+1)}{2}$$


1

Since you strictly want $O(1)$, you can just do the math and get that $$\sum_{i\ \in \ Array}i=\sum_{i=x}^{x+n} i =\sum_{i=1}^{x+n}i\ -\sum_{i=1}^{x-1}i =\frac{(x+n)(x+n+1)}{2}-\frac{(x-1)(x)}{2}$$ I do not see any iterative way to do it as you require the runtime to be $O(1).$


-1

So expanding on what zkutch said in their answer, we can take out the $O(lgn)$ from the summation as follows: \begin{equation} \begin{split} \sum_{1}^{n-1} 1 \cdot O(lgn) &= O(lgn) \cdot \sum_{1}^{n-1} 1\\ &= O(lgn) \cdot (1 + 1 + ... +_{n-1~times})\\ &= O(lgn) \cdot (n - 1)\\ &= O(nlgn) \end{split} \end{equation} And hence arrive at the ...


-1

Summand inside sum is not depend on summation index, then pull it out and you have n−1 before log.


0

Some of those problems are decidable. Many of them are neither decidable nor undecidable. Some problems are decision problems; some are not. If you have a decision problem, you can ask whether it is decidable or not. Most decision problems that you'll see in a data structures class will have an algorithm that terminates in a finite amount of time, so they'...


0

If there is an algorithm, it is decidable. Its impossible for something to be not decidable and decidable at the same time. Take a look at the formal definition of a decidable language.


0

Depending on the problem, there might not be any difference. If the problem's goal is to answer a yes/no question, then there is no difference; accepting the input is equivalent to answering yes, and rejecting is equivalent to answering no. However, if the goal of your problem is to output something else (e.g., output a number), then it is not identical to ...


0

A common refinement to quicksort could also be used with quickselect to deal with duplicates. Instead of partitioning into two buckets, do so into three. This new partition is called the "fat partition". It holds items that are equal to the current pivot. When there are no duplicates, this adds 2% overhead to the sort, according to the following ...


2

It looks like the article was written by someone who does not understand matrix multiplication. the number of additions is equal to the number of entries in the matrix, so four for the two-by-two matrices and 16 for the four-by-four matrices. With the classic matrix multiplication algorithm (which is the one explained in the example) between two $4\times 4$...


2

This is a very simple question, I will explain steps-by-steps: First, you need to count total elements and total comparisons in your tree Second, you need to know that for each element in the tree, it takes $\frac{total \ comparisons}{total \ elements}$ average comparisons to search for an element in the tree. Third, if the problem gives you a probability to ...


1

If you consider the problem Tree traversal, then the correct answer is indeed: Traversal requires $\Omega$(n) time, since it must visit every node. We are here talking about requirement and lower bound, as in "what is necessary". If you want to talk about common algorithms for tree traversal, then it is true that they also have a complexity $O(n)$...


0

Traversal of a binary tree is $O(n)$, $\Omega(n)$, and $\Theta(n)$. All three are correct. Big-O is an upper bound, Big-Omega is a lower bound, and Big-Theta is a "tight" bound. Big-O notation is often used in a non-formal context even when a stronger claim (i.e. $\Theta(n)$) can be made. Big-Omega alone isn't the most helpful metric. We're often ...


0

No. The word "abab" is described by (1) but not (2). You can test and visualize this here. Trying to think about it inductively: (1) can only prepend "a" or "b" to a string while (2) can only prepend "a" and only append "b". Switching the order of a production does not necessarily change the language the ...


Top 50 recent answers are included