# Tag Info

2

There are 8-byte signed or unsigned integers that cannot be represented as a double-precision floating point. For instance, the range of 64-bit unsigned integers is from 0 to $2^{64}-1$. This is a total of $2^{64}=18446744073709551616$, the maximum possible for a 64-bit value. Signed integers represent a different range, but the total number of integers ...

1

If now it's “Wednesday, 4pm”, then $16$ hours ago it was “Wednesday, 0:00”. Thus the problem is to know what hour it is $47^{74}+16$ hours after “Wed, 0:00”. This is obviously solved by computing the remainder of $47^{74}+16$ divided by $24$; since $47$ is coprime with $24$ and $\varphi(24)=8$, from Fermat-Euler we can say $$47^{8}\equiv 1\pmod{24}$$ ...

1

If the cycle is $abcd$, where $a,b,c,d$ are vertices of the graph, the possible coloring patterns are $xyxy$, $xyxz$, $xyzy$, $xyzw$ where $x,y,z,w$ are different colors. (Of course if you only have $\lambda=2 \text{ or } 3$ colors available, not all these patterns are achievable.) For the first pattern, choose a color for $x$, choose a color for $y$. This ...

1

Suppose the vertices of the cycle are $w$, $x$, $y$, and $z$, in that order. You can choose a color for $w$ in $\lambda$ different ways. After choosing the color for $w$, you can choose a color for $x$ in $\lambda-1$ different ways. Now you have two possible choices for $y$: color it the same as $w$ (in 1 way), or color it a different color than $w$ (in ...

1

Definition of space-constructible functions goes like this: A function $f$ is space-constructible if there is a TM that, on input $1^n$, uses $\Theta(f(n)$ cells of the TM. There might be slightly different version of this definition, but the point is that you can prove that a function is space-constructible simply by constructing a multi-tape TM that ...

1

Yes: $$T(n)=O(n\log(n))\implies\lim_{n\to\infty}\frac{T(n)}{n\log(n)}=c\in\mathbb{R}\\ \lim_{n\to\infty}\frac{T(n)}{n^2}=\lim_{n\to\infty}\frac{T(n)}{n\log(n)}\frac{\log(n)}{n}=c*0=0\implies T(n)=o(n^2)$$

1

As gmath shows, you can never take the logarithm of both sides in view of proving asymptotic estimates. More explicitly, you cannot deduce (say) $f = O(g)$ from $\log f = O(\log g)$. Stated differently, if $f = O(g)$ then it doesn't follow that $e^f = O(e^g)$. Even more simply, it is not the case that $e^{O(f)} = O(e^f)$. The root cause of this is the ...

1

If you are in state $\{2,3,4\}$, on input $a$ you can go to $\{2,3\}$, because those are the only states reachable from states $2$, $3$, and $4$ on input $a$. Similarly, if you are in state $\{2,3,4\}$, on input $b$ you can go to $\{1,2,3\}$, because those are the states that can be reached in the NFA on input $b$ from $2$, $3$, and $4$.

Only top voted, non community-wiki answers of a minimum length are eligible