Tag Info

New answers tagged

0

Let me Google that for you ... http://en.wikipedia.org/wiki/Merge_sort#Analysis


1

Intuitive Algorithm assuming matrix is completely monotonic: Search along diagonal starting from (1,1). 1 worst case: exactly N comparisons number will be between two kitty corner numbers on the diagonal (i,i) and (i+1, i+1). So, start from (i,i+1) and search moving right until you hit (i,N) or you find what you're looking for. start from (i+1,1) and ...


1

Always be aware of the logical structure of what you want to prove. The theorem that Dijkstra works for arbitrary weighted graphs is of the form: For any weighted graph $G$ and source $S$ and destination $T$, Dijkstra finds some shortest path from $S$ to $T$ in $G$. Thus if you want to prove that Dijkstra does not work, you want to prove the negation ...


0

The density of villages goes up as $O(n)$, so the distance to the nearest one must go down as $O(1/\sqrt{n})$. (Imagine a perfectly regular grid. If there are $n^2$ villages in the grid, the grid would be a square $n$ villages on a side, so their separation would be about $1/n$.) The total distance would therefore be (with a slight abuse of notation) ...


1

Your proof seems fine to me, and as Konrad noted, part 2 implies part 1. No matter what values are in the array, the algorithm executes the $\Theta(1)$ statement if A[i] = A[j] then b = TRUE the same number of times: once for every pair of integers $(i,j)$ where $0\le i < j < n$. As you found out, there are exactly $\frac{n(n-1)}{2}$ such pairs. What’s ...


0

First part it unnecessary. If you prove this algorithm runs $\Theta(n^2)$ than you have $O(n^2)$.


0

Assuming the variables are the same type, we need 3 variables, the $x$ and $y$ and a third $temp$ variable. We can see that writing straight to $x$ destroys the information we have in it, so first we must store that information elsewhere, i.e. in a third temporary variable, say $temp$: temp=x; Now we are free to continue. $x$ can be assigned the value ...


1

Using the Strassen algorithm for matrix multiplication, we define seven new matrices, $M_1, \dots, M_7$, where each $M_k$ does one multiplication. This is why the run-time will be $O(n^{\log_2 7})$ all the time using Strassen's algorithm. However, if we know our matrices are identical, then we can instead define the matrices $N_1,\dots, N_5$, where $$N_1 = ...


0

With finite doors and keys, it is possible to enumerate all paths. Traverse the graph breadth first tracking which nodes have been visited. Upon entering a room with a key, compute the transitive closure of that node with the new door unlocked. Add each member of the transitive closure as an edge to the current node (following this edge should add the ...


1

If you set $a_0=2$, then in general $$a_n=2+4n+\frac12\Big((-1)^{n+1}+1\Big)\;.$$ The terms are increasing by $4$, except that the odd-numbered terms are larger by $1$ than they 'should' be. A positive integer $n$ belongs to the sequence if and only if either $n-2$ is divisible by $8$, or $n+1$ is divisible by $8$.


0

$$2 \rightarrow 7 (+5)\\7 \rightarrow 10 (+3)\\10 \rightarrow 15 (+5)\\15 \rightarrow 18 (+3)\\18 \rightarrow 23 (+5)\\...$$ we can say $$a_1=2 \\a_{n+1}=a_{n} + 4+ (-1)^{n+1}\\a_2=a_1+4+(-1)^2=2+4+1=7\\a_3=a_2+4+(-1)^3=7+4-1=10\\...$$


0

Combinatorially The program prints three numbers in each line, so if we consider an urn containing $n$ enumerated bools form $1$ to $n$ the program consists of printing the corresponding numbers to every possible triple bools $B_i,B_j,B_k$ ($i< j< k$) this means that the number of printed lines is the number of different three bools in the urn so this ...


0

I think doing some research into breadth-first graph traversal will help you quite a bit. In essence, you are going to use a queue Q and you are going to push pairs onto Q of the form (Node key, distance from Node 1). A basic algorithm to accomplish what you are after will look like this: pushback (1,0) onto Q while Q is nonempty pop the pair (m,n) off ...


1

Algorithmically, I would generate the list $$1^k\pmod{d}, 2^k\pmod{d}, 3^k\pmod{d},\ldots, (d-1)^k\pmod{d}$$ Then, I would calculate the $d^2$ differences of two elements from this list, and check which of them happen to be $c^k\pmod{d}$. There are various ways to optimize this process for speed, but they depend on which of the unknowns (if any) are large. ...


1

The differentials listed are indeed correct (as stated by @Jean-ClaudeArbaut - thank you).


1

relax the edges once in increasing order and once in decreasing order.


0

If $n$ numbers $a_1,a_2,\cdots,a_n$ are given, I think that the answer is $$\sum_{i=0}^{n-1}(-1)^i\binom{n-1}{i}a_i.$$ For 5 numbers $a,b,c,d,e$, one has $$a,b,c,d,e$$ $$a-b,b-c,c-d,d-e$$ $$a-2b+c,b-2c+d,c-2d+e$$ $$a-3b+3c-d,b-3c+3d-e$$ $$a-4b+6c-4d+e$$ This can be written as $$\binom{4}{0}a-\binom{4}{1}b+\binom{4}{2}c-\binom{4}{3}d+\binom{4}{4}e.$$


1

Given two Boolean formulae $\phi$ and $\phi'$, the problem of determining whether there is some $\bar a$ such that $\phi(\bar a)\ne \phi'(\bar a)$ is in $NP$, since you can nondeterministically guess such an $\bar a$ and then verify in polynomial time that it satisfies $\phi(\bar a)\ne \phi'(\bar a)$. So, assuming $P=NP$, there's a polynomial-time algorithm ...


4

There are a number of things you could optimize on, runtime, your own work time implementing code, or memory use. Most likely memory use will become the first obstacle when looking at larger examples (as you can't wait to hope for more memory). Thus in the end an algorithm like your #2 will get you further. (If you want a quick hack for small examples use ...


5

If I really wanted to do this I would try programming a variety of different algorithms and thoroughly test them all on a range examples. It also provides a good sanity test of their correctness by comparing the results returned by the different methods tried. But, from the way you have described Algorithm 1, it looks as though you would have to start by ...


1

$$\sum_{i=0}^\infty x^i=\frac1{1-x}$$ Differentiate that with respect to $x$: $$\sum_{i=0}^\infty ix^{i-1}=\sum_{j=0}^\infty(j+1)x^j=\frac1{(1-x)^2}$$ Rearrange it a little, and you can find $\sum i/2^i$. Differentiate again, rearrange it again, and you can find $\sum i^2/2^i$. This is a finite number, as you guessed. $$T(n)=n\log ...


-1

Write down the quotients backwards 8 32 1 1 4, leaving out the last quotient 8. Then write 8 32 1 1 4 1 8 Then multiply the first 32 in the top row by the 8 in the bottom row and add the 1 in the second row, getting 257, and write 8 32 1 1 4 1 8 257 Then multiply the first 1 in the first row by the 257 in the second row and add ...


0

One thing you may consider to be a problem with the algorithm is that will be forced towards 50% cash, 50% investments over time. Clarification: Say you start with 100 gold pieces, none invested, if a buy decision takes place then 10 gold will be invested. Then next time either 1 gold from investment to purse or 9 gold from purse into investment. You would ...


0

In short, your problem is \begin{align} \max ~&~ \lambda_1 x_1 + \ldots + \lambda_n x_n \\ \mathrm{s.t.} ~&~ c_1 x_1 + \ldots + c_n x_n \geq \gamma \\ &~ x_i \in \{-1, 1\} \end{align} Let $y_i = \frac{x_i + 1}{2}$. Then you can rewrite the problem as \begin{align} \max ~&~ 2 \left(\lambda_1 y_1 + \ldots + \lambda_n y_n\right) - ...


2

If doSomething(k) takes ck operations for some constant c>0, then it takes c(n-j) operations to do doSomething(n-j), where j is given by the previous loop. That is, doSomething(n-j) has complexity $O\left(\sum_{k=1}^{n-j}c\right)$, since $\sum_{k=1}^{n-j}c =c(n-j).$ Now, the entire algorithm has complexity $$O\left( \sum_{i=1}^n \sum_{j=i}^n ...


2

You can, instead of $doSomething(n-j)$, write $c\cdot (n-j)$ since that is how many operations will be performed. So the total number of operations is $$\sum_{i=1}^n\sum_{j=i}^nc\cdot (n-j)=c\cdot \left(\sum_{i=1}^n\sum_{j=i}^n(n-j)\right)$$ Now, first evaluate the inner sum: $$\sum_{j=i}^n (n - j)$$ This is a sum of all numbers between $0$ and $n-i$, ...


1

For general $n$ we can define $T_k$ in the same way as for $n = 2$ as those jobs that are processed on one machine while at least one other machine is idle. Thus, while a job $T_k$ is running the idle time of the other machines is at most $(n - 1) \mu * T_k$. Therefore, you have to adapt your first inequality to \begin{align} w &= \frac{1}{n} ...


0

If the MST is unique then the answer of user3440448 is correct. Since your notes say "the MST" this seems to be the case. However, note, that if the MST is not unique then statement (1) does no longer hold: Consider a cycle of four nodes $v_1$, $v_2$, $v_3$, and $v_4$ with length 1 for all edges $(v_1, v_2)$, $(v_2, v_3)$, $(v_3, v_4)$, and $(v_4, v_1)$. ...


1

You may observe that $$ \sum_{i=1}^n i=\sum_{i=1}^n (n+1-i), \qquad (i \to n+1-i) \tag1 $$ giving $$ \sum_{i=1}^n i=\sum_{i=1}^n (n+1)-\sum_{i=1}^n i $$ or $$ \begin{align} 2 \times\sum_{i=1}^n i&=(n+1)\sum_{i=1}^n 1=(n+1)n \end{align} $$ to obtain $$ \sum_{i=1}^n i=\frac{n(n+1)}2, $$ you conclude using $(1)$.


0

Let G be an undirected, weighted, connected graph G. Let $u$ and $v$ be two non-adjacent vertices, and let d$(u,v) = k$. Also, let $P_1 = (u,u_1,...u_{k-1},v)$. Now, assume to the contrary that $\exists$ a path, distinct from $P_1$, from $u$ to $v$ of length $k$. That is, $P_2 = (u,w_1,w_2,...w_{k-1},v)$. Then, by assumption, $P_1$ is contained in the ...


0

I think the paper by Takeaki Uno, An algorithm for enumerating all directed spanning trees in a directed graph, should help you solve your problem.


0

This is a somewhat complex problem. You want to minimize the number of circles while still having the overlap. If you settle for good, but not perfect solutions, you can write algorithms to find good solutions. For instance genetic algorithms will "evolve" solutions as your shape evolves. However, if you want to do any of this, you need at least some ...


1

We all agree that the procedure consists in comparing the smallest element in $A$ with the smallest element in $B$ and removing the smallest of the two. We do this until one of the lists empties. As there are $2n$ elements in total, we can't do more than $2n-1$ deletions (when a single element is left, one of the lists is empty). This bound can be achieved ...


1

Look at the algorithm. Every time you made a comparison, you immediately added an element to the output list. And then you added one more element to the output list without making a comparison. If both input lists have $n$ elements each, the output list has $2n$ elements. Size of output $\geq$ number of comparisons, so it is easy to show $2n$ is an upper ...


1

The best thing is to explicitly write down a corresponding algorithm, such as Given sorted input lists $L_1$, $L_2$ of lengths $n,m$, produce a merged (sorted) list $O$. [Init] Set $O$ to the empty list. [Done?] If $L_1$ or $L_2$ is empty, append $L_1$ to $O$ and append $L_2$ to $O$ and terminate. [Compare; note that both lists are nonempty] If the head ...


0

Take an arbitrary vertex $v$, then $|\delta_G(v)|+|\delta_{\bar{G}}(v)|=|V(G)|-1$. By definition, $\delta(G)\leq|\delta_G(v)|$ for all $v\in V(G)$, hence, $\delta(G)+\delta(\bar{G})\leq n-1$, where $n=|V(G)|$.


1

Assuming that $c \geq 0$, you can reformulate your problem as a convex optimization problem, introducing a dummy variable $t$. It is equivalent to $$\min_{x \in \Delta_n,t \in \mathbb{R}} \langle g , x - y \rangle + \frac{c}{2} t^2 $$ subject to the convex constraint $$ \lVert x - y\rVert_1 \leq t. $$ Note that we do not need an equality constraint as $t$ ...


1

The number of possible sets in your example should be $\dbinom{7}3 = 35$. Hence, have functions which checks if there are $35$, $3$ element sets and any two such sets are pairwise distinct. In general, if you have $n$ elements and you are looking for $k$ element subsets, the number of such subsets is $\dbinom{n}k = \dfrac{n!}{k!(n-k)!}$.


1

You need to know that all the outputs are distinct; this might be a consequence of generating them in increasing lexicographic order as appears to be the case here. You need to know how many of them are generated. If you generated $\binom{n}{k}$ subsets of size $k$ from an input set of size $n$, then you generated all of them.


1

See http://en.wikipedia.org/wiki/Longest_path_problem for a discussion of the longest path problem. In general it is NP-hard unless your graph is directed acyclic. Thus there are probably no fast solutions. If you want a somewhat brute force solution, then for each starting node do a depth first search (look up on wikipedia if you're not familiar with it) ...


0

If you want a concrete example that in theory should be computable but not by any fixed finite length algorithm, consider the "busy beaver" function $B(n)$. This is the maximum number of steps a computer program of size $n$ can run on empty input and terminate without running forever. It is possible to compute $B(n)$ for small $n$, and some believe that ...


2

There are uncountably many such real numbers. Any algorithm can be described as a sequence of 0's and 1's that encode its operations. Thus, we can identify any algorithm with a natural number, so it makes sense to speak of the $k^{th}$ algorithm. Let $\alpha$ be the real number such that the $k^{th}$ digit is 1 if the $k^{th}$ algorithm halts after a ...


1

Look up "recursive set", also "Chaitin's constant".


1

It is natural to consider (and analyze) the Collatz map not as an operation on numbers but on strings. Most obvious candidates are the strings representing the numbers in bases $2$, $3$, and $6$. In base $6$ the Collatz map is "shift invariant" and works like a cellular automaton; the reason being that $:2$ and $\times3$ are the same in base $6$; ...


3

There is a trivial algorithm. All twin primes produce composites of the form X^2-1. An interesting property of even perfect squares minus 1 (which are always composite) is the triviality of their smallest prime factor unless they are twin-prime composites. This makes it extremely fast to factor them and easy to determine the instances of twin primes (simply ...


1

Let $q$ denote a prime, and let $$ s(n) = \sum_{q\le n} q = \frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right) $$ as discussed on MathOverflow. Clearly $ s(n) = \sum_{q\le n} p(q) \le A(n) $. Define the sets $$ S_q(n) = \{1<k\le n, p(k)=q \} $$ If $\sqrt{n}<q\le n$ then $\left\vert S_q(n)\right\vert = 1$, and for every $q$ $$ \left\vert ...


3

Less words, more facts. Let $$ f(z) = \sum_{n\geq 1} T(n)\,z^n.\tag{1}$$ The recurrence relation hence gives: $$\begin{eqnarray*} f(z) &=& 2\sum_{n\geq 4} T(n-1)\,z^{n} + (z+z^2+z^3)+\sum_{n\geq 4}n^2 z^n\\&=&2z\sum_{n\geq 3}T(n)\,z^n+(z+z^2+z^3)+\frac{z^4 (16 - 23 z + 9 ...


2

This is a non-homogeneous linear recurrence relation. There is a standard procedure for solving these when the non-homogeneous term has a particular form, namely a polynomial, an exponential, or the product of a polynomial and an exponential. In your equation, the non-homogeneous term is $F(n)=n^2$. The first step is to find the general solution to the ...


0

As @SBareS mentioned in the comments the worst case analysis is looking at literally that. For algorithm complexity an algorithm may on average run at a different asymptotic rate compared to artificial input which is designed to require more steps or if randomization is involved a run of the algorithm could randomly choose the worst choice every step which ...


0

There is a standard way to do this, though it is unlikely to give you the most efficient result. First create a non-deterministic finite automaton to recognise the finite language you want. This could consist of one "piece" like the one you have shown for each word - so, for your first question, three pieces: the states in the second would be labelled ...



Top 50 recent answers are included