Tag Info

1

NP-Completeness deals with decision problems. So if you have the problem: INSTANCE: Let $G$ be a graph and let $x \leq |G|$ be an integer. DECISION: Does $G$ contain a subgraph isomorphic to $K_{x}$? This is NP-Complete. The optimization variant (finding the largest $x$) is NP-Hard.

0

This is correct, but it does not satisfy the requirements. You are asked to write a "logarithmic iterative algorithm". This means that the number of operations is of order $\log(n)$. Your routine takes $\Omega(n)$ operations. A hint: Since you are given that $n = 3^m$ for some $m$, use $3(3^{m-1}) =3^m$ and look at $x^3$.

0

n represents the number of digits of the factors that are being multiplied. For example: 1234 x 5678 = 7006652 So 1234 as 4 digits, as for 5678. Then we say n = 4 because each factor as 4 digits. Now apply the equation and see for yourself: 1234*5678 = 10^4(12*56) + 10^2(12*78 + 34*56) + 34*78 = 7006652

1

Let $M=(Q,\Sigma, \delta, q_0, F)$ where the set of states is $$Q=\{q_0, q_1, q_{11}, q_{10}, q_f\},$$ the input alphabet is $$\Sigma = \{0,1\},$$ the transition function $\delta: Q\times \Sigma\to\ Q$ is defined by \begin{array}{c|c|c|c|c|c} \delta(q,b)& q_0 & q_1 & q_{11} & q_{10} & q_f\\\hline 0 & q_0 & q_{10} & q_f ...

1

Here is a NFA accepting your language, where I the an initial state, and F is a final state. It reads the word, and, in a non-deterministic way, choses to read one of the subword you want. Then, you "just" have to determinise it (be careful, it can have up to $2^8$ states… you may want to rewrite the NFA with less states)

1

Possible solution: Build a DFA $A_1$ that accepts strings with $100$. Build a DFA $A_2$ that accepts strings with $110$. Build DFA $A$ that accepts strings with $100$ or $110$. The latter is the union of DFA's $A_1$ and $A_2$ (the union accepts a string iff it is accepted by $A_1$ or $A_2$). Here [ link ] (pp.3-5) you can find some example how to perform ...

0

Since $Q(x)$ is defined as $(x+\lfloor \sqrt{n} \rfloor)^2 -n$, that follows directly from this definition. The comments below show that I jumped too soon. However, looking more closely at the paper, I am inclined to agree with Thomas Andrews that this is indeed a typo. I've looked at $(x+\lfloor \sqrt{n} \rfloor)^2 -(x-\lfloor \sqrt{n} \rfloor)^2 ... 0 If your input is small enough, integer programming will give you the optimal solution. However if you have millions of rows, this will not work, as integer programming algorithms do not run in polynomial time. Indeed, heuristics, or metaheuristics are the way to go in this case. 1 Optimizing a boolean function is NP-Hard in general, so I wouldn't say that there is one popular approach that would work every time. There are exact methods and heuristics. The exacts methods might not be quick enough depending on the complexity of the boolean function and there are no guarantees that the heuristics will ever find the optimal solution. A ... 0 The algorithm for this turned out to be quite simple. Divide(int a, int b){ if (a <10*b) return divSubRoutine(a, b); int q = Divide (divbyConst(a,10), b); int r = a - 10*b*q; return Divide(r, b) + 10*q; } 1 Understanding numerical algorithms necessarily involves some arithmetic and algebra as well as just logic. I would strongly recommend you dip into Knuth's wonderful Art of Computer Programming. This is an encyclopaedic work but quite easy to use as a a very readable reference once you read the introductory sections. Volume 2 includes a discussion of the ... 0 Hint:The general formula for dearrangements is$n![1-\frac{1}{1!}+\frac{1}{2!}...\frac{(-1)^n}{n!}]$. now you can plug in your values and get the required answer. Note sometimes we actuallly need to do some mental stuff even if if the formula is available 1 Suppose person 1 wears hat 2 and person 2 wears hat 1. People 3 up to$n$have hats 3 up to$n$remaining to them. The assignment of hats to the first to people can be completed to a derangement by any derangement of people 3 and up. Since there are$n-2$people 3 and up, the problem reduces to$n-2$people (people 3 and up) and$n-2hats (hats 3 and up). -1 No, there's not a limit definition for Big O. $$f(n) \in O(g(n)) := \exists\, C>0 \; \exists\, n_0 \; \forall\, n>n_0 \;(\,|f(n)|< C|g(n)|\,)$$ But we do have \begin{align} \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0 &\Rightarrow f(n) \in O(g(n)) \\[1ex] \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0 &\not\Leftarrow f(n) \in O(g(n)) . \end{align} ... 1 To show that one of the statements is not true it suffices to give an example for which the statement is false. In the following example graphs the DFS is always started at nodes$and the orientation of the edges indicates the search direction. Edges that are not oriented are not traversed during the search. For statements 1. and 3. consider the following ... 0 The time complexity of the third loop can be bounded more tight. You already observed that the outer loop is executed exactly$m$times. For each$j$the inner loop is executed$b[j]times. Thus, the time complexity for the third loop can be expressed as \begin{align*} \sum_{j=0}^{m-1} c \cdot b[j] = c \cdot \sum_{j=0}^{m-1} b[j]. \end{align*} Since the ... 2 I assume the second line should have brackets around the(3i+1)$. Then: $$\sum_{i=0}^k(3i+1)=\sum_{i=0}^k3i+\sum_{i=0}^k1$$ As summation is linear, we can apply your prof's formula to the first term. 1 You have an error in the sum :$\sum_0^k 1 =k+1$and not$1$1 $$$$\sum_{i=0}^{k}1 = k+1$$$$ 1 I think we can get an improvement to linear time if only$\frac{n}{\log{n}}$items are out of place. First, pick out the misplaced items (they will occur in runs where the endpoints do not compare correctly with a neighbor), this takes linear time. Then use binary search on the remaining correctly-sorted items to find the correct positions for each ... 7$O(n)$is not possible as your initial position might be$\frac n2$small items in correct order followed by$\frac n2$items in random order. Sorting the latter takes$O(n\ln n)$. 1 Choose$h$from $$H = S \times N \times (M \cup \{ \epsilon, \text{null} \})$$ where$S$is the set of streets,$N$the set of house numbers,$M$the set of mailboxes,$\epsilon$is an empty optional (whatever that is) and$\text{null}$is your null value, the latter both distinct from all elements in$M. Or define $$H = S \times N \cup S \times N ... 0 As already stated in comments, it might be better to think about this in terms of planes. Suppose A,B\in\mathbb R^3 are cartesian coordinates. Then x=A\times B is a vector orthogonal to the plane through A, B and the center. y=A+B on the other hand is a vector pointing in the direction of O. Now take \hat x=\frac{x}{\lVert x\rVert} and \hat ... 1 Let \phi=(d/R)(180°/\pi) be the angular size of arc OE and \gamma=(OA/R)(180°/\pi) the angular size of arc OA (see picture below). If S is the center of the sphere and C is the center of circle AEB, then SC is perpendicular plane AEB. Let now H be the point where chord AB intersects radius SO. By applying the sine rule to triangle ... 0 In general APX-hardness of A will not immediately imply APX-hardness of B. Nevertheless, the implication holds if you strengthen the conditions of the reduction. If the reduction is approximation reserving, i.e. an approximation solution to B corresponds to an approximation solution to A when the reduction is applied, the implication still holds. The ... 1 Model: Let \mathbb{N}_0 = \mathbb{N} \cup \{ 0 \} and let n=x \in \mathbb{N}_0 be the largest exponent for the coins, so we can use x for the vector of unknown coin numbers further on. The integer linear program of the problem is$$ \begin{array}{ll} \min & c^\top x \\ \text{w.r.t.} & A x = b \\ & x \ge 0 \end{array} with V = ... 0 The flood fill algorithm is a typical application of depth-first search in graphs, though it can be implemented using breadth-first search. The graph is the one induced by the grid of pixels. 0 Looking at the wikipedia article, some mathematical concepts that show up are a finite number of picture elements (pixels) that have a colour assigned each these form a grid of square cells (but the idea should work for e.g hexagonal cells too, see graph for the general case) which is the picture each pixel can be addressed by coordinates or a number, they ... 1 As Henning Makholm pointed out, you can handle the x's and y's separately. The optimal value for x is attained at the median of the x_is if n is odd and in the interval between the two median points if n is even. Finding the median is in O(n) time. 0 Another: only some letters appear as double-ups. "XX" is much more likely to be "EE" than it is "QQ". 3 Just start substituting, we have \begin{align*} T(n) &= T(n-1) + C \end{align*} Now, we use this again, but for n-1 instead of n, that is \begin{align*} T(n-1) &= T(n-2) + C \end{align*} Combining both, we get \begin{align*} T(n) &= T(n-1) + C\\ &= T(n-2) + C + C\\ &= T(n-2) + 2C \end{align*} Now, apply the ... 3 By using the fact that \def\l{\operatorname{lcm}}\l(a_1, \ldots, a_n) = \l\bigl(\l(a_1, \ldots, a_{n-1}), a_n\bigr) $$1 I think a third heuristic could be using the trigram frequency and the most frequent trigram is "the". The good thing about this trigram is that it covers both the most frequent letter and bigram in English language. 1 If a and b are very large numbers, then you can use the following. I will assume that the a_i's are relatively prime (to simplify). Let c=\prod_{i=1}^Na_i. Then, the number of integers less than c which are divisible by a_1 is \prod_{i=2}^Na_i, the number of integers less than c which are divisible by a_1 and a_2 is \prod_{i=3}^Na_i. ... 0 I am wondering if there isn't a simpler solution to this problem. Suppose you have n items. For every path p of length l_p, create n-1 other paths p_2,\cdots,p_n with lengths 2l_p, 3l_p, … , nl_p, and identical capacities as path p. Here is how to interpret these extra arcs. If an item takes path p_2 for example, this means that other ... 1 If my understanding is correct, this is like minimizing the total completion time of n tasks (packets) on m machines (paths)…You can solve this with integer programming. Create the following variables: z\ge 0: completion time t_{ip}\ge 0: time at which item i (fills c_i capacities) takes path p (of length l_p and capacity C_p) y_{ip}=1 ... 0 The Miller-Rabin test doesn't need a perfect power test. See Crandall and Pomerance pages 135-136 for example. On the other hand, tests for the input being a perfect square are not uncommon in some Lucas and Frobenius tests. The former generally when searching for parameters where (P|n)=-1 which won't ever happen. But typically the test is put off ... 2 Divide your marbles into three groups. Compare group 1 vs group 2. If they are the same then you know the heavier marble is in group 3. If group 1 is heavier then the heavier marble is in group 1. If group 2 is heavier then the heavier marble is in group 2. Repeat this process until you are comparing individual marbles. If you have a situation where you can ... 4 Each weighing can reduce the number of possibilities to 1/3 of that from before, using the same argument as in the example you linked. If you have 3^n marbles, then you need at least n weighings to find the heavier marble. If you have 3^n < N \leq 3^{n+1} marbles you should need n+1 weighings--since N is not a power of three, some weighings ... 0 Why not using eigenvalue decomposition? If the matrix A is diagonalizable then A=P^{-1}DP and A^k=P^{-1}D^kP. If A cannot be diagonalized, then you can use the Jordan form A^k=P^{-1}J^kP where there is a closed form formula for J^k (see https://en.wikipedia.org/wiki/Jordan_normal_form#Powers). 0 This is a rather late answer, but hopefully still helpful. For bandit problems with infinitely many arms, there is some work. A good starting point might be \chi-Armed Bandits by Bubeck et al. You can find more references therein. Specifically, they deal with a variant where the bandit arms are in a generic measurable space, and the reward function has ... 1 You could use parametric equations similar to the following ones:$$ \left\{ \begin{array}{l} x=r(z)cos(\theta)\\ y=r(z)sin(\theta)\\ z=z \end{array} \right. $$where z and \theta are the two parameters that generate the surface with 0\le\theta\le 2\pi and 1\le z \le 6 (if I am reading your graph correctly). r(z) is the way the radius varies ... 0 An O(n\log n) algorithm exists. Sort array A, and reorder B such that the original pair A[i] and B[i] are located at A[\sigma(i)], B[\sigma(i)], where \sigma is a permutation of i which sorts A. The number of pairs (i,j) is preserved as these get mapped to the pairs (\sigma(i),\sigma(j)). Hence, we can assume A is sorted in ... 1 Use the binary decomposition of k. The complexity of the calculation of A^k is at most \sim 2\log_2(k)n^3. For A^{25}, calculate and store: A^2,A^4,A^8,A^{16},A^{24},A^{25}. 0 You can't check if a matrix has all zeroes or all ones in less than N^2 tests in the worst case. This is because whatever the order in which you test the elements, the one that makes the difference can be the last one you try. Anyway, if a matrix has N^2p zeroes and N^2q ones and you try elements at random, the average number of elements to try before ... -1 The following algorithm still has complexity N^2, but in practice should be much faster because you do not create any new matrix, so you do not have any memory allocation: traverse the whole matrix and add up its entries, i.e. compute \sum \limits _{i,j = 1} ^N a_{ij}; if you get 0, then all the entries are 0, if you get N^2 then all the entries ... 1 The Big-O time complexity is not affected if accessing a single entry is O(1) (which would not be the case for array stored in one-dimensional singly-linked lists, for example). Regarding the constant hidden in the big O, opton 1 might be best because it improves cache performance on typical CPUs of today. So you are right if you consider 4 as correct ... 4 Bisection is a good choice for part a. It is simple to use and converges linearely. I will here show how to use the bisection-method to find a root, i.e. a point x satisfying f(x) = 0, of any given (continuous) function. {\bf Setup}: Given a function f, first find a point x_{\rm high} where f(x_{\rm high}) > 0 and then a point x_{\rm low} ... 1 This obviously highly depends on the underlying graph. If the graph is a line graph consisting of nodes s = v_1, \ldots, v_n = t and edges (v_1, v_2), \ldots, (v_{n-1}, v_n) then there are n-1 (possible) cuts (\{v_1\}\{v_2, \ldots, v_n\}), (\{v_1, v_2\}\{v_3, \ldots, v_n\}), \ldots, (\{v_1, \ldots, v_{n-1}\}\{v_n\}). If the graph is a complete ... 0 In your first question let d=j-i; then$$\sum_{i=1}^{k-1}\sum_{j=i+1}^k\frac2{j-i+1}=\sum_{i=1}^{k-1}\sum_{d=1}^{k-i}\frac2{d+1}\;.$$Now let \ell=k-i, and note that as i runs from 1 up to k-1, \ell runs from k-1 down to i. Thus,$$\sum_{i=1}^{k-1}\sum_{d=1}^{k-i}\frac2{d+1}=\sum_{\ell=1}^{k-1}\sum_{d=1}^\ell\frac2{d+1}\;.\$ This last ...

Top 50 recent answers are included