Tag Info

New answers tagged

0

For small $n$, a depth-first search using a list or set of "already seen" subsequences does the trick.


3

One of the reasons why the methods you mentioned do not work for multiple roots is that, in this situation, the root-finding problem is numerically ill-posed. That is, an arbitrarily small perturbation of the input will change the structure of your solution (just as you recognized, multiple roots will split into clusters). The same holds for the computation ...


1

It's not being changed. The author is looking at the base cases to see for which constant $c$ the proof will work. The formulation "Now we can complete the inductive proof [...] for some constant $c$" is a bit sloppy; I can see how you may have thought that the proof was started, then $c$ was chosen, and then the proof was completed; but that's not what is ...


0

I would like to say that Joriki's approach is the right one, but that the answer he has given in the n = 3 case is incorrect. Specifically, he says "From symmetry, we can expect the last four to have the same probability p at equilibrium". That is wrong. 2 is not like 1 and 3, and 2 appears after fewer questions in the sequence 123 than in 132, so you ...


4

It is not possible to give a finitary proof of this fact. Consider, for instance, the statement that all Goodstein sequences terminate. This is an arithmetic claim, it is independent of $\mathsf{PA}$, and it is equivalent to the claim that some (very specific) computable non-increasing sequences of polynomial towers stabilize. Instead of Goodstein ...


1

By relaxation the feasible set stays equal or becomes larger. Thus, the global minimum might decrease (depending on the objective function). However, since you have a non convex problem, gradient projection method computes a stationary point, a local minimum at best. So it may give you the same, a larger, or a smaller value. You can't really predict what ...


2

No, you can't in general produce a postfix expression where all of the operands are pushed before any operator appears. For example, $(1\times 2)-3$ cannot be represented that way. The $3$ needs to be on the top of the stack at the time of the subtraction, so it needs to be the last thing pushed -- but once you push $3$, it will be impossible to do anything ...


0

Too see why we need this multiplier $\frac{1}{2(p_{j,y}-l_y)}$ for $(x - p_{j,x})^2$ we must notice what shape of parabola changes with sweep line movement. At the very beginning, when new site is just hit the line it is effectively just a vertical line and while sweep line moves downward it became wider and wider.


1

Let the initial set of points be $\mathbf P_i, i = 0,\dots, n$. Let also $S$ be the B-spline of second degree with knot vector $$ \mathbf T = \left\{u_{-1}, u_0 = 0, \dots, u_{n+1} = n+1, u_{n+2}\right\}, \quad u_0 \leq 0, \quad u_{n+2} \geq n+1 $$ and $\mathbf P_i$ as its control polygon. $u_{-1}$ and $u_{n+2}$ are boundary knots and can be defined ...


1

What you are looking for is called a square factor of a string. Finding all square factors can be done in O(n lg n) [paper]. If the size of alphabet is bounded, then all square factors can be found in linear time [paper]. Although they didn't solve your problem exactly, you probably can find more relevant research from these two papers.


2

First, note that even if you obtained an algorithm of complexity $O(r)$, this would still not be an efficient one, because "fast" means $O(\log ^p r)$ for some integer $p$. $O(r)$ still means exponential time, because $r = 2^{\log r}$ which is exponential in $\log r$. As customary in computer science, when I write $\log$ I mean $\log _2$. Second, your ...


1

One solution—not the easiest to find, but a more general one that could be helpful in the future—is to show: If $g(n)$ and $f(n)$ both tend to infinity, and $\log g(n) = o(\log f(n))$, then $g(n) = o(f(n))$. Once proved, this changes your problem into showing that $4\log\log n = o(\epsilon \log n)$, which leads to much more straightforward calculus ...


1

By changing $\epsilon$ by $\epsilon/4$ you have just to prove that: $$\lim_{n\to\infty} \frac{\text{log}n}{n^\epsilon} = 0$$ But if we multiply by $\epsilon$ (which does not change the result) and by substitution $m= n^{\epsilon}$ we get : $$\epsilon \lim_{n\to\infty} \frac{\text{log}n}{n^\epsilon} =\lim_{n\to\infty} ...


2

Take the fourth root of your second ratio, and then you will have $\log n$ in the numerator and $n^\delta$ in the denominator where $\delta = \epsilon / 4 > 0$. Then apply L'Hopitals. If the fourth root of the ratio goes to zero, then so does the original ratio


0

Okay! After taking your advice, I've discovered you both handed me the answer :) Since Levenshtein distance is a metric, and the triangle inequality holds, then: $$ L(A,C) <= L(A,B) + L(B,C) $$ So it doesn't matter what threshold we define the Sim(a, b) function to have, at most Sim(A,C) will be 2*L(A,B). Therefore all matches for any member of A' ...


0

$1$ is placed between $n$ and $2$, so I assume there are at least 3 cards. I think $n$ operations are needed when $n \equiv 1 \mod 3$ or $n \equiv 2 \mod 3$. It is never a good choice to pick the same card twice. You will just change the orientation of the card and the two adjacent cards two more times and nothing happens. From every three subsequent ...


0

You need a linear program with a binary variable. $x_{ij}=\begin{cases} \text{1, if wine i is stored in tank j} \\ \text{0, else} \end{cases}$ $c_j$:=capacity of tank j $w_i$:=amount of wine i n=amount of tanks m=amount of type of wines $\color{blue}{\texttt{constraints}}$ Sum of the tanks, in which wine i is stored has to be greater or equal than ...


2

Problem: Let $m,n\in\mathbb{N}$. There are $n$ coins labelled $1$, $2$, $\ldots$, $n$. A move consists of a selection of $i\in\{1,2,\ldots,n\}$ and flipping of coins $i,i+1,i+2,\ldots,i+m-1$ (where the coin labels are considered modulo $n$). Initially, all coins are tails up. When is it possible to flip these coins according to the rule so ...


1

The "danger" in this exercise is in writing the proof in such a way that $c$ depends on $n$. But you haven't done this. I think that it is ok. But to make things clearer, you can stablish from the beginning a value for $c$, say $c=4$. Your original work is useful as a draft, to find this $c$.


1

Strong induction is necessary for this proof because weak induction isn't enough to solve the problem. Specifically, weak induction looks at $T(n-1)$, but you need to plug different values into $T$, so you need to assume the claim is true for more cases. The base case is enough, you showed that $T(0)\leq c\cdot 0$. Your attempted proof is backwards ...


0

I sense here the Eulerian numbers and Eulerian Polynomials at work. Consider the following small GNU Maxima script display2d : false; load("simplify_sum"); for r : 1 thru 10 do block( h : ratsimp(factor(simplify_sum(sum(a^i*i^r,i,1,n))*(a-1)^(r+1))), can : ratcoef(h,a^n), print(r,"|",ratexpand(factor((h-can*a^n)/a*(-1)^(r+1)))) ); which ...


0

@HelloWorld I am too late to answer this question. Imagine a calculator. When you say 2+3 in a calculator, it is a single instruction. Similarly, 2*3 is also an instruction. So, every operation is an instruction to CPU, whether it may be sum or multiplication or division. In UG%, while working on 8086 processor, I saw vividly how every operation ...


0

Here is a sample computation. Suppose the number you start with is 29. Thus, you want to find the shortest string of 1's divisible by 29. Equivalently, you want the smallest positive integer n such that $$10^n-1 \equiv 0 \;\;\;mod (29)$$ (to see this note that the left hand is a string of n 9's but, as 9 and 29 are relatively prime, we can divide by 9 ...


1

Yes. The approach which finds an Eulerian cycle of an $(n-1)$-dimensional graph is easily adapted to find all Eulerian cycles starting at a given vertex. Since rotating a sequence corresponds to tracing the same Eulerian cycle but starting at a different vertex, this adaptation generates exactly one representative for each equivalence class of sequences. In ...


0

Seven races: Five heats of 5 horses A final of the 5 winners, to crown the fastest horse. Retire the horses that finished fourth and fifth. A playoff, with the remaining horses from the final, as well as the horses from the heats that finished second and third to the champion, and second to the runner-up. The champion doesn't need to be in the playoff. The ...


1

For cubic cells, I think the way to do it is to calculate distance for just one point component-wise, and if the distance in any component is greater than 1/2, switch to a different point. I thought about this in 2-d: There's two points, $A$ and $B$. Since both $A$ and $B$ form a grid, because they're periodic, you can forget about the original unit grid ...


0

Of the top of my head, check which faces your $A$ point is closer to than the $B$ point. So for a box, compare relative $x, y, z$ coordinates. This would at least cut the check requirement in half, as you don't need to test the points beyond $B$ point in your cell.


0

In 1972, J. H. Conway proved that a natural generalization of the Collatz problem is algorithmically undecidable Specifically, he considered functions of the form $$g(n) = a_i n + b_i, {n\equiv i \pmod P}$$ where $$a_0,b_0,\dots,a_{P-1},b_{P-1}$$ are rational numbers which are so chosen that g(n) is always integral. The standard Collatz function is given ...


1

Some assumptions: loop free, not a multi graph, that is, no edges from a node to itself, at most 1 edge between any two nodes. For part 1: Take the set of discovered nodes E, and the set of discovered edges E. Add all nodes connected to by an edge in E to N. Add all edges touch by any node in N to E. Repeat until N and E no longer get bigger. To slightly ...


1

A simple strategy : if your rate is at 1 ticket/s, clip one ticket every second if your rate is under 1 ticket/s, clip one as soon as possible This way, in $t$ seconds, you're always have clipped either $t$ tickets if $t$ or more people did come or $n$ ticket if $n<t$ people did come


0

My own attempt: In the ideal sequence, the distance between consecutive points is $1$. When the density increases or decreases locally, it changes to $1\pm\epsilon$. When a point is displaced, the distance becomes $1-\epsilon$ on a side and $1+\epsilon$ on the other. When one or more point is missing, the distance jumps to about $2,3\cdots$ When one or more ...


2

The answer to (1) is yes: it's easy to show that there are distinct continuous functions $f, g$ such that the domain of $f$ and $g$ is $D=\{a+bi: a, b\in[0, 1]\}$, on the boundary of $D$, $f$ and $g$ are zero, and $f(Q), g(Q)\subseteq Q$ (where $Q=\{a+bi: a, b\in\mathbb{Q}\}$). Now say that a function $h$ is a quilt if it is gotten by pasting together ...


0

My attempt: Let $(x_i)$ be the sequence of points you have. I would first order this sequence (if it is not ordered yet). Now I would do something like: xs // list of given x_i, ordered ys // final list for i in 0 ... len(xs): if i == 0: ys[0] = round(xs[i]) else: ys[i] = max( round(xs[i]), ys[i-1]+1 ) endif endfor So the ...


-1

A rule for the order of all compositions of a positive integer n is derived in the paper, “Relationships between Ordered Compositions and Fibonacci Numbers” published in the Journal of Mathematics research $(Vol-7, No-3, 2015)$ under Canadian Center of Science and Education. ‘Rule for Significant Order of Compositions of n’ or ‘SOC(n)’ : Under ...


1

Let's call the original curve $\mathbf{F}(t)$. Compute the derivative curve $\mathbf{G}(t) = \mathbf{F}'(t)$, where the prime denotes differentiation with respect to $t$. It is well known that $\mathbf{G}(t)$ will be another Bezier curve whose degree is one less than the degree of your original curve $\mathbf{F}(t)$. So, if $\mathbf{F}(t)$ is a cubic curve ...


1

In other words, you are asking whether there exists any set of 9 integers $a\le b\le c\le d\le e\le f\le g\le h\le j$ such that $a+b+c+d+e+f+g+h+j = 45$ and simultaneously $a^2+b^2+c^2+d^2+e^2+f^2+g^2+h^2+j^2 = 285$ other than the trivial solution $1,2,3,4,5,6,7,8,9$. In Mathematica, that's FindInstance[ a^2 + b^2 + c^2 + d^2 + e^2 + f^2 + g^2 + ...


0

We ought to be developing the points of the desired curve, not serially (by bumping the value of the parameter by a fixed amount), but recursively (wherein each new value of the parameter would be the median of the parameter values of the last two points that were created). During this recursive process, the distance from each new point to both of the two ...


0

In general, if you want to prove that a given function is the solution of a recurrence relation you will need the following relations: $$x-1< \lfloor x \rfloor \leq x \leq \lceil x \rceil < x+1$$ $$\lg \left( \frac{a}{b}\right)= \lg a- \lg b$$ Also, I would suggest you to take a look at the Master Theorem with which you can easily find the solution ...


0

Step 2: $$2 c \lfloor n/2 \rfloor \operatorname{lg} \lfloor n/2 \rfloor \le 2 c (n/2) \operatorname{lg} (n/2)=2cn \operatorname{lg}(n/2)$$ Step 3 (property of logarithm): $$\operatorname{lg}(n/2) = \operatorname{lg}(n)-\operatorname{lg}(2)$$


1

I assume by "hypercube" you mean a $d$-dimensional cube, that is, the graph with $2^d$ vertices indexed by length-$d$ bit strings, and edges joining two vertices precisely when their bit strings differ in exactly one bit. If that's the case, then finding shortest paths in this graph is very simple: if two vertices' bit strings differ in $k$ spots, then just ...


1

From Introduction to algorithms, Thomas Cormen: "... Another way to perform topological sorting on a directed acyclic graph is to repeatedly find a vertex of in-degree 0, output it, and remove it and all of its outgoing edges from the graph.' Which is precisely what the pseudocode I wrote does. So I will just forget about the word "level" and perform a ...


1

Let $P_{ij}$ be the permutation matrix that exchanges row $i$ with row $j$. Then you can exchange column $i$ with column $j$ by applying the associated permutation matrix to the transpose of your matrix, then transposing back:


1

Your proposed method gives too much weight to the most recent test. If you want each test (of the most recent 5) to have the same weight the formula you want is: $$New\;Average=\frac{4(Old\; Average) + New\; Score}{5}$$ In the first example you mention (old average = 3, most recent test = 8) you get 4.


1

Let the function $f(n, k, a, b, i)$ gives the $i$-th lexicographically smallest partition of $n$ into $k$ parts, each between $a$ and $b$, inclusively. I show how to compute $f$. Let $g(n, k, a, b)$ be the number of partitions of $n$ into $k$ parts, each between $a$ and $b$, inclusively. Clearly $g(n, k, a, b) = \sum_{a \le j \le b} g(n-j, k-1, a, b)$. To ...


1

What you define there isn't even a partial ordering, The set {A} is higher than {G} (G can't reach A), and {G} is higher than {A} (A can't reach G), so your levels aren't actually correct A>G, G>A. It is a pre-ordering but there's not as much one can assume about pre-orders. Also that algorithm doesn't halt on $1-> 2-> 3$ which has the adjacency ...


0

In my answer here I've described a probabilistic test for squaredness that can achieve an arbitrarily small error with time complexity very close to $\mathcal O$(log $n$) for an integer $n$. This is much better than Newton et. al. It's the same style of probabilistic test used to determine primality for huge numbers, except it's based on properties of ...


2

Here is a probabilistic test for squaredness that can achieve an arbitrarily small error with time complexity very close to $\mathcal{O}$(log $n$) base $r$. It's sort of a generalization of the approach used in the GMP library. Premise 1: If an integer $n$ is a perfect square and $P$ is any odd prime, then $n$ (mod $P$) is a quadratic residue modulo $P$. ...


1

Perhaps there are some other solutions, but the simplest I can think of needs an understanding of the concept of augmenting paths. I don't know how much it will be useful to you, nevertheless I will post some hints, maybe it will clear some things. Hint: The basic approach is to calculate for each $v \in V$ a maximum cardinality matching in $G_v = G ...


0

You could use Proportional Share Scheduling that is used for CPU time resource allocation. Start by granting all your sensors the same share, then adjust their share periodically based on the proportion of data that actually collect. You'll have to determine a reasonable time interval to do the re-evaluation. If the amount of data the sensors collect is ...


0

The "mod" operator in computer languages is simply the remainder. For example, 17 mod 3 = 2 because 17 / 3 = 5 rem 2 which in turn means 17 = 3 * 5 + 2



Top 50 recent answers are included