Tag Info

New answers tagged

0

As far as I can see you are trying to test each $$k^{\phi(n)/p_i}$$ where $\{p_i\}$ are the prime factors of $\phi(n)$) and $\{k\}$ is each number less than $n$. I think you need a flag to capture whether that hits $1$ for any $\{p_i\}$ and make your output decision only after you have run through all $\{p_i\}$ for any $k$. You can also accelerate your ...


1

$$\lim_{n \to +\infty} \frac{g(n)}{f(n)}=c$$ means that $\forall \epsilon>0, \exists n_0 \in \mathbb{N}$ such that $\forall n \geq n_0:$ $$\left |\frac{g(n)}{f(n)}-c \right | < \epsilon \Rightarrow - \epsilon< \frac{g(n)}{f(n)}-c< \epsilon \Rightarrow c- \epsilon< \frac{g(n)}{f(n)}<c+\epsilon \\ \Rightarrow (c-\epsilon)f(n)< ...


0

Let's say we started with: 8 7 5 6 3 2 1 4 and mergesort got all the way up to two halves of the list: 5 6 7 8, 1 2 3 4 Now we want to merge. When we choose from the right half, we add the number of remaining elements on the left half to the inversion count. For example: We choose 1 and add 4 We choose 2 and add 4 We choose 3 and add 4 We choose 4 and ...


1

You have to evaluate the sum $a_0+a_1+\cdots+a_n$, where the terms satisfy $$ a_0=1, \qquad a_{k+1}=(-1)^k \dfrac{x^2}{2k(2k-1)} a_k $$


2

A divide an conquer algorithm works as follows (it is $O(n)$ though): For an array $A[1,\dots,n]$, we compute the following three things instead (kind of like having a stronger induction hypothesis): 1) A $p$ such that $A[1] + A[2] + \dots + A[p]$ is maximum. 2) An $s$ such that $A[s] + A[s+1] + \dots + A[n]$ is maximum. 3) $i \le j$, such ...


0

Firstly, the diagram you drew is a valid example of such a tree. Secondly, the problem statement says "pseudocode;" everyone has a different understanding of what this means. I'd ask your instructor about how particular s/he is if this is for a class. Since I'm not too familiar with C++, your pseudocode is a bit too code-like for me (but that's personal ...


0

A linear programming formulation should do nicely, the Integrality Theorem guaranteeing that basic feasible solutions are in integers.


2

This might be an extension of the marriage theorem, except that any group of n passengers needs to be friends with at least $\left \lceil \frac{n}{4}\right \rceil$ drivers.


0

You can model this with the Bond evaluation formula. It states the following: $$B = \frac{P}{(1+i)} + \frac{P}{(1+i)^2} +...+ \frac{P}{(1+i)^n} = P\sum_{j=1}^n(1+i)^{-j}$$ Where $n$ is the duration of the Bond/loan, $P$ is the value of the payments and $B$ is the value of the Bond/loan. In your example of the 20,000 with an APR of 20%, if we a consider an ...


2

Here is a sketch of a common algorithm. While basic, there are some obvious ways to improve it. For concreteness sake, suppose we wish to plot the contour $f(x,y)=0$, where $$f(x,y) = x^3 - x y + y^4.$$ Let us start with a rectangular grid in the plane. Something like so: This particular grid is $10\times10$ and lives in the square ...


2

In general no, because you can extend your language with oracles which may perform some weird operations (like solving the halting problem). However, Turing machines (or any Turing-complete concept, like λ-calculus, certain cellular automata, etc.) will get you anything you would want in an ordinary setting. Be aware, that on different computation models ...


1

Consider the function:$$ f(x)=\sum_{k=1}^n x^k=\frac{1-x^{n+1}}{1-x} $$ Then: $$f'(x)=\sum_{k=1}^n kx^{k-1}=\frac{1}{x}\sum_{k=1}^n kx^{k}=\frac{{x}^{n}\,\left( n\,x-n-1\right) +1}{{x}^{2}-2\,x+1} $$ So: $$\sum_{k=1}^n kx^{k}=\frac{{x}^{n+1}\,\left( n\,x-n-1\right) +x}{{x}^{2}-2\,x+1} $$ (you could obtain something equivalent to the above just by asking ...


0

Your algorithm is correct, and so is the algorithm that ml0105 gave. But whichever algorithm you use, you will certainly need two nested inductions. I will prove your algorithm but exactly the same structure can be used to prove the other algorithm. Firstly I would encourage you to write down the invariances embedded into the code itself as it is most ...


2

$\begin{matrix} & & & & & 1&1&0&1\\ & & & &\times & \color{red}{\rm 1} & \color{purple}{\rm 0} & \color{blue}{\rm 1} & \color{green}{\rm 1} \end{matrix}$ $\begin{matrix} & & & & 1 & 1 & 0 & 1 & (1101 \times \color{green}{\rm 1}) \\ ~ & & & 1 & 1 ...


0

Adding the condition: if s=t then a:=0 seemed to fix my issue!


1

If you use Matlab, that's already been done for you with the randsample function. You can call it to pick c values from 1 to n^2, without replacement. Those values serve as linear indices of the matrix entries that should be set to 1: n = 5; c = 8; M = zeros(n,n); M(randsample(n^2,c)) = 1; If you want to do it more manually: generate a random permutation ...


1

You basically want to identify the set of positions where the entry will be $1$. So you are looking to choose a random set of size $c$ from a set of size $n^2$. There are $\binom{n^2}{c}$ such possibilities, and you want to choose one of them uniformly randomly. Look at algorithms for choosing a random subset. A simple idea would be to randomly choose a ...


1

Only $1$ input is needed to determine the polynomial: $\pi$. Since $\pi$ is transcendental, in principle we can figure out the polynomial from $f(\pi)$ (in a loose sense, none of the powers of $\pi$ can run into each other). Note that this also works if we get rid of the positivity constraint.


1

In your particular case, I can't say very much, but notice this looks very much like Bezout's identity for the greatest common divisor. $$ \mathrm{gcd}(a,b) = 1 \longleftrightarrow \exists \; x,y \in \mathbb{Z} : ax + by =1$$ We can clear denominators: $$ \frac{234}{24621} - x^{\frac{1}{3456}- \frac{1}{12345}} = \frac{1}{24621 \times ...


0

In general an equality constraint can be handled by using it to eliminate one of the variables (using ordinary linear algebra) before any of the clever optimization algorithms is let loose on the problem. This works well for a general optimization algorithm, but if one wants to allow your method to be specialized to a particular sparse shape of the goal ...


1

Some clarifications: when speaking of the(??) feasible set being a matroid, your lecturer was probably talking about greedoids in general. The statement about the feasible set being a matroid doesn't make a lot of sense to me, but saying that the greedoid (whose feasible set(s) we're talking about) is a matroid does make sense. Furthermore the matroid in ...


0

From your, proof, if we consider an edge with weight $w$ in $M*$. It has to be adjacent to another edge in $M$ with weight $w'$ such that $w' > w$. In addition, every edge in $M$ can be adjacent to at most two edges in $M*$ (one edge in each endpoint). This mean that for any edge $e' \in M$, there exists at most two $e \in M*$ such that $f(e) = e')$. For ...


1

In parametrized algorithms, the algorithm gets an input $x$ and a parameter $k$. The usual usage of $O^*(f(k))$ is saying there exists an algorithm which runs in time $$O(f(k)\cdot \text{poly}(|x|))$$ (e.g. $O^*(2^{2^k})$ means the algorithm is allowed to run in $O(2^{2^k}|x|^6)$, but not in $O(2^{2^k+k}+|x|)$) This is somewhat different from the ...


2

It is called bin packing problem, and is an NP-complete problem which doesn't admit a PTAS. In other words, there is no polynomial-time algorithm that gives exact or even arbitrarily-good approximation algorithm. There is an algorithm called first-fit-decreasing with bound $FFD \leq \frac{11}{9}OPT + 4$. To apply it, you should consider the items one by one ...


2

There is definitely some general relation between the two subjects within complexity theory, and as likely one of the few people who know what both fields entail, I've not come across anything specific or even general linking the two fields in a direct manner. I've seen some research that ties the two fields separately to other areas in an indirect manner, ...


3

Start from a coloring, you label the vertices increasingly by color: the vertices colored by color 1 are the first vertices in the list, then the vertices colored by color 2 are next and so on. Now, if you do a greedy coloring, you can prove that you get (a possibly new) coloring of this graph. You can prove that this coloring has the desired property by ...


1

The sum of the submatrice consisting of rows $i_1$ through $i_2$ and columns $j_1$ through $j_2$ is basically $$(\sum_{i=i_1}^{i_2} A[i]) \times (\sum_{j=j_1}^{j_2} A[j])$$ From this property, we can construct an $O(N+K)$ solution (there are many alternative solutions, of course, for example, we can also do this in $O(d(K) N)$). Edit: OP asked how to do ...


2

One way to show that their remainders are the same is to show that their difference has no remainder: $$\frac{ax+b}{c-x}-\frac{ac+b}{c-x} = \frac{ax-ac}{c-x} = -a\frac{c-x}{c-x} = -a$$


1

in short You can calculate the focal length of the zooming camera $f_z$ $$ f_z = \frac{d_z f_m}{d_m} $$ with $d_z$ the distance to the object from the zooming camera. $f_m$ represents the focal length of the the moving camera and $d_m$ represents the distance to the object from the moving camera. explanation You can use the magnification formula to ...


1

The introductory post actually describes the solution pretty well. But in another way, the idea is as follows: 1) Suppose there are $n+1$ entries in the string. To get the value for the first element, calculate the largest number $q$ of complete cycles through all of the permutations of remaining entries in such way that $q(n!) \leq N$. Then the $q^{th}$ ...


1

Take two tasks next to each other. Perform $i$ then $j$, you will pay $p_id_i+p_j(d_i+d_j)$. Perform $j$ then $i$, you will pay $p_i(d_i+d_j)+p_jd_j$. The other costs are unchanged. The sign of the difference $p_id_j-p_jd_i=\left(\frac{d_j}{p_j}-\frac{d_i}{p_i}\right)p_ip_j$ tells you to swap or not. If you keep doing this until there are no more ...


1

I'm guessing you need a more formal definition of the score you are looking for. For example if a player in team A wins one time is that better than a player in team B that came 2nd two times? Being said that, you can for example assign scores with the following expression $$s_k = \sum_i \dfrac{c_i}{i}$$ Where $c_i$ is the number of times the player $k$ ...


1

I can compute $DP[i][j][k]$ in $O(N^2)$. To see this, note that the first term of the summation ($DP[i][m][0]$) can always be computed in $O(1)$, and the second term of the second term of the summation ($j$ from $DP[m+1][j][k-1]$)... is always $j$. ...assuming everything is memoized, of course.


0

Generally both BFS and DFS works in $O(V+E)$, but for your case, it can be made to work in $O(V)$ by immediately terminating upon finding/checking such cycle. BFS can be made to work, but it's less trivial than DFS, so I'll do the DFS one instead: Do an ordinary DFS, but the first time you are going to add a node $v$ to the stack that is already in the ...


0

A cheap answer for part 3 is to note that there is a general theorem that says that every finite symmetric normalform game has a symmetric Nash equilibrium (which may involve mixed strategies). This is a finite normalform game. Therefore the theorem applies. I don't have a reference for the theorem. But it is well-known. One may prove it using the standard ...


1

You seem to be basically on the right track already. To prove correctness, a good first step is to prove that the algorithm will always terminate. From the behavior of i and the condition of the while loop you can deduce that the while loop can only execute a finite number of times. So as long as the binary search always terminates in finitely many steps, ...


2

As you run through the list of integers you keep track of the sum. Compare the next element to the sum before adding it to the sum. Sum=0 For i=1 to n if a(i) > Sum then appendToL(a(i)) Sum += a(i) Next


1

For $D$ arbitrary, let $A=1$, $B=1$, $C=D-1$. Then the only solution is $X=0$, $Y=1$.


2

$\log_4(3)<1$ , so $n^{log_4(3)}<n<n\ log(n)$ "Polynomially larger" means that the quotient of the two functions does not exceed some polynomial function, here $n^2$.


0

It seems the following. Proposition. Let $B$ be a statistics of size $N$ in which each $B_i$ is an integer. Then there exists a valid statistic $A$ of size $N$ such that after rounding it up, it becomes $B$ iff $100\le B<100+N.$ Proof. The necessity is obvious. To prove the sufficiency put $A_i=B_i-(B-100)/N$ for each $i$.


0

The story began many years ago in 1974 when I wanted to find a formula for the n'th digit of Pi. I was studying rational and irrational numbers. With my calculator I was computing inverses of primes and could easily find a way to compute those inverses in base 10 to many digits using congruences and rapid exponentiation. Since it appeared ...


1

The coefficient of $x^n$ is called the Hilbert polynomial. It can be calculated, see the book R. Stanley, Enumerative combinatorics. Vol. 1., Cambridge Studies in Advanced Mathematics. 49. Cambridge: Cambridge University Press. (1999). See the Theorem 4.1.1 and Proposition 4.1.1 of the book. Related sofware see here I sure those calculation can be ...


2

It's not always possible to find an answer to this problem: for instance, with $n = 5$, there are 70 NE-paths in the full lattice from $(1,1)$ to $(5,5)$, and you can remove edges such that there are 66, 68, or 69 paths, but you can't have 67 paths. We can see this by marking each edge in the lattice by the number of paths that cross that edge. We can ...


0

If $n$ is size of input, and $T_n$ the time it takes. Super linear time means faster than any $C\cdot n$, i.e. $\limsup T_n/n=\infty$. Examples $T_n=n\ln(n)$, $n^2$, $n^n$ ... Sub linear time means slower than $n$, i.e. $\limsup T_n/n<\infty$. Examples $T_n=\sqrt{n}$, $\ln(n)$, ... $o(1)$ is something that tends to zero, $O(1)$ is something bounded ...


0

If $$f(x) = \sum_{n} a_n x^n $$ then $$ f(g(x)) = \sum_{n} a_n g(x)^n $$ so you just set the coefficients on $x$ equal in the equation $$ h(x) = \sum_{n} a_n g(x)^n $$ and solve for the $a_n$. (hint: start with the highest degree terms)


0

Given just $h$, you know the degree of $g$ must divide that of $h$. For each given divisor of the degree of $h$, taken as degree of the desired $g$, you trivially find what the lead coefficients of $g,f$ must be -- if there is a decomposition of that degree at all, which there might not be. Then you find the next-to-lead coefficients of $g,f$ and so on -- ...


0

If $f$ is to have degree $n$, take $n+1$ values $x_i$ such that $g(x_i)$ are distinct and use Lagrange interpolation on $f(g(x_i)) = h(x_i)$. EDIT: If you don't know $g$, the problem is rather more interesting. Note that $g'$ is a factor of $h'$. If you can guess which of the roots of $h'$ are roots of $g'$, that determines $g$ up to a linear ...


3

A matrix $A$ is orthogonal iff $$A^T A = I.$$ If we denote the (known or unknown) $(i, j)$ entry as usual by $a_{ij}$ then the above condition is equivalent to the system $$\sum_{k = 1}^n a_{ik} a_{jk} = \delta_{ij}, \qquad 1 \leq i \leq j \leq n,$$ where $\delta_{ij}$ is the Kronecker delta symbol (that is, it has value $1$ if $i = j$ and value $0$ ...


1

There are some missteps in your application of the master theorem. First $$ T(n) = 7\left[ 7T\left(\frac{n}{4}\right) + \frac{1}{4}n^2\right] + n^2 = 49 T\left(\frac{n}{4}\right) + \frac{11}{4}n^2, $$ so let's call $a = 49$, $b = 4$, and $f(n) = \frac{11}{4}n^2$. Clearly $f(n) \in O(n^2)$, so let's also call $c = 2$. Then $$ 2 = c < \log_b a = ...



Top 50 recent answers are included