Tag Info

New answers tagged

0

One way I can think of is to use Boolean algebra. For example, given $A=10, B=5, C=4, D=1, E=1, F=2, G=7$ with $AB, DG,$ and $AG$ disallowed: We can say that our disallowed combinations look like $(AB + DG + AG)'$. ($XY$ means $X \text{ and } Y$. $X + Y$ means $X \text{ or } Y$. $X'$ means $\text{not } X$.) Applying de Morgan's Law and distributing when ...


0

I think I found a solution... If we discretize the values, the problem does indeed become easier: Now, we know that there is always at least one perfect fit ($\Sigma\Delta=0$), namely $C_s=1$. Therefore, we do not really need to optimize for $\Sigma\Delta$, just find a better $C_s$ that is also a perfect fit. This implies the following conditions: (1) ...


0

If you intend the chain lengths to averaged over all slots, including the empty slots, then the answer is just the average number of elements per hash slot. This is obviously $\dfrac{n}{m}$ no matter what the probability distribution is. If you intend the chain lengths to be averaged over only the non-empty slots, then we want the expected number of ...


3

This is $O(n)$. First, define the deviation of a vertex $p_r$ to be the (signed) angle by which the direction of $p_rp_{r+1}$ differs from the direction of $p_{r-1}p_r$. This can be calculated as $\arcsin z$, where $z$ is the $z$-coordinate of: $\dfrac{(p_{r+1}-p_r)}{|p_{r+1}-p_r|} \times \dfrac{(p_r - p_{r-1})}{|p_r - p_{r-1}|}$ Now, we get a convex set ...


2

Alternatively to checking oriented area as in Yves Daoust's answer, one could check that the polygon is locally convex at each vertex as follows. Let $p_i$ be a fixed vertex. For each other vertex $w$, show that the angles $\angle p_{i-1}p_i w$ and $\angle wp_ip_{i+1}$ are accute. This can be done arithmetically by using the distances between the points ...


2

It can all be done easily in $O(n)$ operations: for safety, first check that the given polygon can be split in two monotone chains (find the leftmost and rightmost of them and check monotonicity in between, i.e. increasing abscissas); if that fails, the polygon is not convex. Then check that all angles are convex in these chains. This is a simplified ...


0

The distribution in each bin is binomial. You have $n$ "trials", which are the $n$ elements. For any given bin, you have a probability $p = \frac{1}{m}$ of any given element winding up in the bin. The mean of the binomial distribution is given by $\mu = np$, which in your case is $$\mu = \frac{n}{m}$$


0

Fitting any empirical model on so little data is indeed a random guesswork. (Anyway, I would certainly not think of a logarithmic or exponential model, as the first data point is $(0,0)$). To get any sensible answer, it is better that you explain how this data is generated. With no better information, natural cubic spline interpolation should be ...


0

I don't know of a particular algorithm, but you can try fitting the points to different curves. You basically want to find $y(x)$, where you have: $$y(0)=0,\ y(5)=62,\ y(15)=87,\ y(40)=108$$ By looking at the curve you can see that the slope decreases sharply though the function is increasing. Thus, assuming the function is monotonic, either $y(x)=Ax^b, ...


0

If there exists limit $$ \lim_{n\to+\infty} \dfrac{f(n)}{g(n)}=C,\qquad |C|<\infty, $$ then we will assume that functions have the same order, if $0<|C|<\infty$, function $f(n)$ has lower order than $g(n)$, if $C=0$. Use these well known limits: $$ \lim_{n\to+\infty}\dfrac{\ln n}{n^a}=0, \qquad a>0; $$ $$ ...


0

You are quite correct - your answer is wrong. I assume that you are talking about Big O notation. To answer the question: Read the article, your notes and the textbook Classify the functions by the notation the fall into - to help you have some linear, polynomial, exponential, logarithmic and quasilinier. Within each classification decide which will grow ...


0

Not true. Consider $f(n) = 2^n,\ \ f(cn) = 2^{cn} \neq c_1 \cdot 2^n$ for arbitrary $c$. Therefore $f(cn) \notin \Theta(f(n))$


0

The function $f(a) = x^a$ is increasing so we immediately know that $x^a = O(x^b)$ whenever $a < b$. To prove that $x^b \neq O(x^a)$ we'll suppose that it is. Then there is some constant $C$ such that, for $x$ sufficiently large \begin{equation} x^b \leq C x^a. \end{equation} Then \begin{align} C \geq x^{b - a} \geq x^{\epsilon} \end{align} for some ...


0

I like this kind of problems. Here we go: If $k=1$ the result follows immediately. Let's assume the result is also true for all $k-1\geq 1$. Then, if we have $k$ boxes of size $n$ (and $k$ different colors). Put all the cups of one color (choosing a color for which you have $n$ or less cups) in a box and set it aside even if you don't fill the box ...


0

Here are my initial thoughts on making a countable sequence of all univariate polynomials. First, if you have a degree $k$ polynomial and any of the coefficients to an $x^j$ term for $j < k$ is zero, let's represent its coefficient as $\frac{0}{1}$. Also represent any integer coefficients $a$ as $\frac{a}{1}. $Now we can separate all polynomials into a ...


1

There is no winning strategy. Even for just the $2$-long boat alone, you would need 50 bombs to be sure. Optimal strategies are also not possible here. You can make optimal strategies for when the opponen't boats are 'randomly' positioned (although even that is only a minor improvement), but a well-playing opponent will compensate that by putting their ...


0

Here is just part (a). You should be able to extend it to the other parts. $$ d|a \quad \Rightarrow \quad dm = a \quad \text{for some $m \in \mathbb{Z}$} \quad \Rightarrow \quad d(-m) = -a \quad \text{where $-m \in \mathbb{Z}$} \quad \Rightarrow \quad d|(-a) $$


0

In general, you can reduce the problem for $n$ to the problem for $n-2$ in two steps: $$\begin{align} n-(n-1)&=1\\ (n-2)\times1&=n-2\\ \end{align}$$ Thus if $n\gt2$ is even, you can reduce it to the case $n=4$ in $n-4$ steps, at which point three multiplications finishes things off. If $n\gt3$ is odd, then you can reduce it to the case $n=5$ in ...


0

First suppose that $n$ is even (for example, $12$). Then you can have 12 - 11 = 1 10 - 9 = 1 -------------Your steps-------------- 8 * 7 = 56 6 * 5 = 30 3 - 4 = -1 1 - 2 = -1 30 - -1 = 31 56 - 31 = 25 25 + -1 = 24 ----------------------------------------- 24 * 1 = 24 24 * 1 = 24 Hence any even number over $8$ would work. I couldn't think of a general ...


3

There is no simple closed formula for such a sum, but it is not too difficult to guess that it behaves like: $$\sum_{n=1}^{N}\sqrt{4n+1}\approx \frac{1}{6}(4N+1)^{3/2}.$$ As a matter of fact, the inequality: $$ \sum_{n=1}^{N}\sqrt{4n+1}= \frac{1}{6}(4N+1)^{3/2}+\frac{1}{2}(4N+1)^{1/2}+\theta$$ where $\theta\in(-0.82,-0.745)$ holds by induction.


6

There is an answer which is not simple at all since $$\sum_{i=1}^n \sqrt{4i+1}=2 \left(\zeta \left(-\frac{1}{2},\frac{5}{4}\right)-\zeta \left(-\frac{1}{2},n+\frac{5}{4}\right)\right)$$ in which appears Hurwitz $\zeta$ function. However, you could notice that $$2\sqrt{i}<\sqrt{4i+1}<2\sqrt{i+1}$$ and so ...


0

"Spigot algorithm" appears to be somewhat vague, possibly referring to any of three different classes of algorithms: Any algorithm which can compute successive digits, storing only a constant amount of state information. The possibly first spigot algorithm for π from Rabinowitz and Wagon is in this class; it seems that they coined the term "spigot ...


0

I have implemented an solution based on this formula. OF course in dynamic programming MaxSale(P, X, N) = max{yi*pi - sigma(f(yj))*pi + MaxSale(P, X-yi, N-1)} OR = yn*X - sigma(f(yj))*X, when come to the last day - have to sell all no matter what price it is to maximize the revenue , where yi ...


0

I found this out, and will edit with a more complete response as I figure it out: Let $f(x) = \sqrt{x + \sqrt{x + ...}}$. Then $f(x) = \sqrt{x + f(x)} \Rightarrow f(x)^2 - f(x) - x = 0 \Rightarrow f(x) = \frac{1}{2}\left(1 \pm \sqrt{1 + 4x}\right)$. We can, however, eliminate the minus from the $\pm$ since we want $f(x)$ to be positive. Thus: $f(x) ...


0

Hints: You might start by by finding a simple expression for $g(x)= \sqrt{x+\sqrt{x+\sqrt{x+\cdots}}}$, ensuring you have a sensible answer for non-negative integer $x$, especially when $x=0$ Take the average of $g(x)$ across integer $x$ for $0 \le x \lt N$. I doubt there is a closed form for the expected value. For example ...


2

$\Sigma_{i=0}^{log n} (n/2^i) = n*\Sigma_{i=0}^{log n} (1/2^i)$ is equivalent to $2n$ when $n$ is huge, so this is $O(n)$. For n big enough, $\Sigma_{i=1}^{n} (i log i) > \Sigma_{i=1}^{n} i = \frac{n(n+1)}{2}$ which is $O(n^2)$. So unless I'm missing something, I think the statement is wrong.


2

Note first of all that X and Y do not hold their normal meaning in your expressions. X denotes the row and Y denotes the column. It's leveraging that you could assign the elements of a matrix an index in a linear manner row-wise: \begin{array}{cccc} 0&1&2&3\\ 4&5&6&7\\ \end{array} Given the width $W$, row $r$ and column $c$, the ...


1

If the prime factorizations of the Carmichael function $\lambda(n)\;$ or the Euler totient function $\varphi(n)\;$ are known, there are effective algorithms, see e.g. Algorithm 1.4.3 in H. Cohen's book A Course in Computational Algebraic Number Theory or Algorithm 4.79: Determining the order of a group element from Applied Cryptography by A.J. Menezes et ...


0

Greedy means locally optimal. The local optimal has been simplified by the fact that each lecture begins as soon as the other ends and that no two can occur at the same time. This means that at each step, the algorithm, not knowing how many future lectures there are going to be, will fit the shortest duration ones first in order maximize the total number of ...


0

You need to show the whole problem-we don't have access to Example 7. What is the criterion for "optimum"? Is it the most talks scheduled without overlap, the highest utilization of the hall, or what? You are probably expected to show a list of talks, show what the greedy algorithm produces, and show a better solution (according to the criterion for ...


2

Finding the order of $a \in \mathbb{Z}/n\mathbb{Z}^\times$ is not so easy even when $n = p$ is prime. We know that the order of $a$ must divide $p-1$, but if $p$ is large this may be incredibly hard to factor. The primitive root theorem says that there exists an element of order $p-1$ in $\mathbb{Z}/p\mathbb{Z}$, but there are not really any great algorithms ...


0

If you do row reduction on $A^T$ (transpose of $A$), the columns with (row) leading $1$s will give you a maximal set of linearly independent columns of $A^T$. The corresponding rows of $A$ would give you a maximal set of linearly independent rows of $A$. (The reason for the transposing is that row reduction preserves column dependencies, but not row ...


1

You are correct that the outer loop "keeps dividing $i$ in two". So if $i$ starts at $N^2,$ the next two values are $\frac{N^2}{2}$ and $\frac{N^2}{4},$ just as you wrote--but the next value after $\frac{N^2}{4}$ is $\frac{N^2}{8},$ not $\frac{N^2}{6}.$ You should be summing a geometric series rather than a harmonic series. Also, there is that factor of ...


2

The statementsum++; shall run following number of times: \begin{align*} &= N^2 + \frac{N^2}{2} + \frac{N^2}{4} + ... + \frac{N^2}{2^k}\\ &= N^2 * \left( 1 + \frac{1}{2} + \frac{1}{4} + ... + \frac{1}{2^k} \right) \end{align*} If the number of terms in this series is $k$, then we have: $2^k = N^2$. (because the terms are halved till we reach ...


3

If you make $k$ of $n$ cuts horizontally and $n-k$ cuts vertically, the result will be $(k+1)(n-k+1) = -k^2 + n k + (n+1)$ pieces. Maximizing this is equivalent to finding $$\max_{k\in\{0, \ldots, n\}} -k^2+nk+(n+1)$$ The derivative is $-2k+n$ and the function is concave, thus $k=\frac n2$ is the unique maximum in $\mathbb R$. If $n$ is even, we are done and ...


1

The ratios are simply computed as the name suggest (provided the time values are non-zero): 0.009/0.002 = 4.5000 log2(0.009/0.002) = 2.1699 0.042/0.009 = 4.6667 log2(0.042/0.009) = 2.2224 0.175/0.042 = 4.1667 log2(0.175/0.042) = 2.0588 ... ... 290.449/65.873 = 4.4092 log2(...) ...


0

Note: This turned out to be incorrect, I left it here so nobody else makes the same mistake Here is the algorithm I believe is correct: Assume M is larger than N for simplicity. We want to make the squares as large as possible, since total area is given (M times N), the larger the area of any particular square, less will be the number of squares required ...


1

The article you linked to deals with the asymmetric travelling salesman problem. The authors have a subsequent paper which deals with the more usual symmetric TSP: Gutin and Yeo, "The Greedy Algorithm for the Symmetric TSP" (2007). An explicit construction of a graph on which "the greedy algorithm produces the unique worst tour" is given in the proof of ...


0

We could try to compute $$L_1=\lim_{n\to \infty} \frac{a^{b^n}}{b^{a^n}}\text{,}$$ but it is harder than computing the limit $$L_2=\lim_{n\to \infty} \log \left(\frac{a^{b^n}}{b^{a^n}} \right) = \lim_{n\to \infty} \left(\log (a^{b^n}) - \log (b^{a^n})\right)\text{.}$$ Since $\log x^y = y\log x$ for all $x,y>0$, it holds that $$L_2=\lim_{n\to \infty} ...


1

If I've understood the problem correctly, you have a set of numbers, say n, and you want the average of that, then your set grows to n+1, and you'd like the new average. One thing you could do is always hold the accumulator (sum) of your set of variables. That way, you'd only need to divide by n to return the mean. This doesn't really make sense for a small ...


0

What you are describing is a subset of automated planning. You would typically describe your problem in an action language like STRIPS and then run a planner to determine whether the goal state or states can be reached. Determining whether a successful plan exists for a given problem is PSPACE-complete, but constraints such as limiting the number of steps ...


0

Perhaps I'm overinterpreting the example and its presentation in the Question, but if the problem is determining all simple (no retracing edges) paths in an undirected cycle-free connected graph, i.e. a tree, there is a simple Answer. Given there are $n$ nodes in the tree, any pair of (not necessarily distinct) nodes uniquely determines a simple path ...


0

This is a partial answer. Let's look only for matrices that are similar to matrices with positive entries (not necessariy symmetric). Some simple sufficent conditions can be obtained. For example, let $A$ be a matrix of order $n$ with integer entries. Let us assume that the eigenvalues of $A$ are $\lambda_1,\ldots,\lambda_n$. Notice that the trace of $A$ ...


0

This is called a minimum path cover, optimal path cover, or path partition. The number of paths in a minimum path cover is the path covering number. This paper gives quite an extensive list of references on the problem: http://arxiv.org/pdf/1204.2306.pdf


0

The formula in the last answer (of Yuval Filmus) seems to be wrong: for m=4,n=9,S=6 one gets a nonzero result while it's impossible to have a sum of 6 with 9 dices! The wanted formula i guess is the one corresponding to the coefficient "c" at http://mathworld.wolfram.com/Dice.html


1

For a loop like this, for (int i = 5; i < N; i++) one way to count the number of iterations is to make a list of the number of different values of $i$ that will occur; each one results in one iteration of the loop. Those values are $$ 5, 6, 7, 8, \ldots, N - 1. $$ In case you still don't recognize how many numbers are in that list, it's almost the same ...


0

It helps to draw a graph: to show that $f$ is $\Theta(g)$, you want to show that (1) if you multiply $g$ by a large enough number, then its graph will be above the graph of $f$ (2) if you multiple $f$ by a large enough number it's graph will be above the graph of $g$, or equivalently, if you multiply g by a 8small enough* number, it's graph'll be below ...


0

Intuitively, the first is saying that as $n$ gets large, you don't care about adding or subtracting a constant to the base in $n^b$. You don't plug in something random, you have to think about what you can prove. For the first, if you knew that $a$ is positive, you could use $c_1=1$ and argue that as $n \lt n+a, 1\cdot n^b \lt (n+a)^b$ This fails if $a ...


1

The intuition is to make $\frac{\left|b\right|}{n} \le \frac{a}{2}$ and to make $\frac{|c|}{n^2} \le \frac{a}{4}$. That way, you can show the following inequality: $$ \frac{a}{4} = a - \frac{a}{2} - \frac{a}{4} \le a+\frac{b}{n}+\frac{c}{n^2} \le a + \frac{a}{2} + \frac{a}{4} = \frac{7a}{4}$$ Therefore, let $c_1 = \frac{a}{4}$ and $c_2 = \frac{7a}{4}$. It ...


0

MINIMAX PRINCIPLE Minimax is a method in decision theory for minimizing the xpected maximum loss. It is applied in two players games such as tic-tac-toe, or chess where the two players take alternate moves. It has also been extended to more complex games whic require general decision making in the presence of increased uncertainty. All these games have a ...



Top 50 recent answers are included