New answers tagged computer-science
1
Suppose that your original algorithm had complexity $O(N)$. Like, the brute force method requires $N=n!$ with $n$ the number of destinations. Then depending on at which of your checks you find the minimum, it could be the 1st, 2nd, third check, ..., all the way to the last one. On average, you will need $\frac{1+2+...+n!}{n!}=\frac{n!(n!+1)}{2n!}=\frac{n!+1}{...
1
In the worst case, it is as difficult as the original problem without the hint. For example, suppose that all weights are $1$, and I tell you that the shortest tour has length $n$, where $n$ is the number of nodes.
2
Proof that $L$ is not regular
Assume that $L$ is regular, then there exists $p$ such that for all $|w|\geq p\:, \exists x,y,z, \: y\neq \varepsilon \text{ and } \forall k, \: xy^kz \in L$.
Take $n>p$ (we're not going to be subtle here. Then $w=0^n10^n10^n1 \in L$, so we can slice it into three part $x,y,z$. Let us consider $y$
if $1 \in y$ then $xy^kz \...
0
$(\mu f)(4) =$ smallest $n$ such that $f(n,4) = \max\{0,4-2^n\}$ is zero, which is $n=2$.
$(\mu f)(9) =$ smallest $n$ such that $f(n,9) = \max\{0,9-2^n\}$ is zero, which is $n=4$. Here $n=3$ would lead to $\max\{0,9-2^3\}=1$.
3
We start with $f_2(n)$. We have two cases:
Case 1: There are arbitrarily long sequences of consecutive $7$'s in $\pi$, then $f(n)=1, \forall n$, and this is clearly computable.
Case 2: There is a longest sequence of length $k$ of consecutive $7$'s somewhere in $\pi$ and $k$ is fixed. Hence, $$
f_2(n)=\left\{\begin{array}{ll} 1, & \text{if } n \leq ...
0
Let's generalize the description of the problem slightly, so that item $R_i$ has weight $w_i$, and is moved to the front with probability $p_i = \frac{w_i}{w_1 + w_2 + \dots + w_N}$. Let $f(w_1, w_2, \dots, w_N)$ be the stationary probability of state $(R_1,R_2,\dots,R_N)$: by symmetry, that's the only probability we need to find.
Start the Markov chain in ...
1
Here, $Hv=(I-2ww^*)v=v-2w(w^*v)$
Notice that $w^*v$ is the length of the perpendicular from the $v$ onto the orthogonal complement of $w$.
In the above image, $w=\left(\frac1{\sqrt2}, \frac1{\sqrt2}\right)$, it's orthogonal complement is the line $y=-x$, and $w^*v$ is the length of the line $VP$.
As can be seen in the image, $w(w^*v)$ is the vector $\...
1
This is a nice question. Let $\Gamma$ be the two premises (statement 1 and 2) and let us write $\Gamma\models A$ for "$A$ is a valid conclusion from $\Gamma$".
Then for example the formalization of "Only conclusion $1$ is correct" is the (false) statement $$(\Gamma\models\text{conclusion 1})\text{ and }(\Gamma\nvDash\text{conclusion 2}).$$...
0
Conclusions I and II can be restated as "some pathogens are bacteria" and "no pathogens are bacteria".
Whether option C is a tautology or not depends on the meaning of "some", and whether it is to be interpreted as "at least some" (i.e. some and possibly all) or "only some" (I.e. some but not all).
It is only ...
1
Intro This type of questions tends to be problematic because you can't be really sure at what level of precision is the author of the question working. So sometimes what looks like a purely logical exercise (which should have a clear answer) ends up being rather vague or weird.
I think that there is one more ambiguity that is missing in the discussion of the ...
0
Since you care about the speed of IsCoprime(n, m), I'm assuming that you're calling that function many times. So let's assume that we're minimizing the time the following code takes to run (K is some constant):
for (int n = 1; n <= K; ++n)
for (int m = 1; m <= K; ++m)
IsCoprime(n, m);
You can precompute prime factors all ints up to K, which ...
0
I'm not sure what your example has to do with the Incompleteness Theorem. If the Goldbach Conjecture is false, then yes, your program will eventually find a counterexample and thus prove it to be false. But if it is true, we might still be able to prove it true as well.
For example, suppose I have a computer program that tests the hypothesis that every even ...
3
This thing would be possible. I really struggle to believe it would be remotely as ergonomic as e.g. Lean, though. Phrasing your proofs as types in a strong type system gives the compiler perfect knowledge, and allows it to be extremely helpful (if you haven't experienced Agda or Idris's hole-filling, it is actually miraculous). The extremely dynamic nature ...
0
I don't understand your question. First of all search for 'Hann window STFT'. From it you should be able to get the frequences/pitches when the input wave is $\le$ 3 pure sines, if you want to do it in real-time then be prepared for a lag of about 50ms.
Don't even expect to make it work on piano chords and more general real-life music. Look at https://www....
0
Since you asked about computer science as one option, note the line of code
x = 2+3
causes the l-value x to be $5$, whereas the r-value from which that was obtained was $2+3$.
0
I think at a fundamental level, your confusion comes from definitions of mappings. Take your example of addition. Then we could more formally create a mapping:
$$
\phi : \mathbb{N}\times \mathbb{N}\to \mathbb{N}
$$
given by
$$
\phi(a,b) = a+b
$$
now - as with your example - you could ask "what is ${\phi(2,3)}$?", and someone could keep answering ...
0
Note that the problem requires strong $2$-universality of $H$, i.e. pairwise independence; this implies uniformity (a key is equally likely to map to any hash).
Instead of $V$, suppose $H$ maps from an arbitrary set $M$ to an arbitrary set $N$. Define an indicator random variable $I_x$ for each key $x\in M$ that is $1$ when $x\in A$ and $h(x)\in B$.
Because ...
0
And you need an invariant
that describes what is going on.
In this case,
I would put this just after the
WHILE statement:
$z = a*(b-w)
$
To prove it,
note that
it is true upon first entry
($w=b; z=0$)
and each time through the loop
$w$ is decremented
and $z$ increased by $a$.
Upon exit,
$w = 0$
so, by the invariant,
$z = a*b$.
This brings back memories of
...
0
In short you are asked to explain why the output is $z$ equals $a*b$ when any $a,b$ is input, at least for any $b\geq 0$.
In long:
How many times does the loop execute for any allowed $b$? Consider:
What is the initial value for the the loop iterator, $w$.
When is the loop iterator tested?
How is the loop iterator iterated?
Is the loop safe when the ...
2
$\mathcal A \vDash \varphi$ says: "statement $\varphi$ is a semantic consequence of the list of statements $\mathcal A$ (often called the premises, or assumptions)" and a semantic consequence must be true when all the premises are interpreted as true. [Note: this list may be of zero, one, or several statements.]
In propositional logic, you can use ...
1
We sort all the blocks according to the descending order of their minimal elements. We name the blocks $B_1, B_2, \dots$ in that order.
For every $i\geq 1$, let $m_i$ be the smallest element of $B_i$. Thus $m_j \geq m_i$ whenever $j \leq i$.
For any $1 \leq j \leq i$ and any element $x \in B_j$, we know that $x \geq m_j \geq m_i$.
This means that, for any $i$...
3
The knapsack problem is a case where you can see it: a genral knapsack problem is NP-hard and worst-case NP-complete, but in developing the cryptosystem we must be able to mask an easily solvable instance to look like a hard one, so the problems that were used were easy ones (super-increasing) then modified by a modular multiplication and modular reduction ...
0
I am giving some hints.
Let $Pr[\omega]$ be the probability of some event $\omega$. Given distinct $x_i$ and $x_j$, then we have a collision if $h_a(x_i)=h_a(x_j)$. We need to prove the following inequality by definition of $2$-universality of hashing functions.
Theorem: If $x_i,x_j \in \{0, \cdots, p-1\}$ and $x_i \neq x_j$, then $Pr[h_a(x_i)=h_a(x_j)] \leq ...
0
Yes, it's a basic property of the GF (generator polymonial of cyclic codes, on which CRC are based), its independent coefficient cannot be zero. That's explained in every textbook, see eg here, proof in page 3.
1
Step 4 could use some more work. Namely, you need to show that $(\log(n))^{2} \in O(n^{c})$ for some $c < 1/2$. This shouldn't be too hard. For example, take $c = 1/3$. We have that:
\begin{align*}
\lim_{n \to \infty} \frac{(\log(n))^{2}}{n^{1/3}} = 0.
\end{align*}
I'll leave it to you to fill in the details for the limit computation.
So $(\log(n))^{2} \...
0
Please always cite the whole reference, including author and journal, instead of just the name of the paper (which you have also stated wrong!).
You are refering to "Wang, H., He, C., & Li, Z. (2020). A new ensemble feature selection approach based on genetic algorithm. Soft Computing, 24(20), 15811-15820."
For a):
$W_{opt}$ is the optimized ...
1
Run the following C program:
double x = 1.00111011;
double y = 1.00111001;
printf("\n0x%llx", *((long long int*) & x));
printf("\n0x%llx", *((long long int*) & y));
It will show that both 8-byte floating-point numbers in fact do not have the same byte representation:
0x3ff0048c08e251c4
0x3ff0048bee0a5f2a
You can get a visual ...
2
0.1+0.2=0.30000000000000004 in floating point IEEE representations arithmetic addition manual proof.
Your value is the correct one, it's just that most programming languages don't print all those digits. But Python, for example, will show them if you ask for it:
>>> 0.1+0.2
0.30000000000000004
>>> '{0:.52f}'.format(0.1+0.2)
'0.3000000000000000444089209850062616169452667236328125'
0
Let's say we the following propositional formulas: (A∧B),(A∧C),(C∧B)
where each of is satisfiable and each of A, B, C is a propositional
formula.
You don't mention whether they are simultaneously satisfiable, so I assume not. In that case, one can have $A\wedge B\wedge C$ not satisfiable: take propositional variables $p$ and $q$ and define
$$A=p, \quad B=q \...
1
It would be helpful to think of an automaton as some kind of "Snakes and Ladders Game". The circles which represent states correspond to the squares in the board game. The arrows represent movement from one square to another. The label on the arrow specifies which input ("dice throw") leads to that move. In board game there is a ...
1
We are dealing with a deterministic finite automaton according to the provided picture. It is defined as a $5$-tuple $(Q, \Sigma, \delta, q_0, F)$.
The set of states: $Q=\{\{1,2\}, \{1,2,3\}, \{2,3\}\}$
The set of input symbols $\Sigma=\{a,b, \epsilon\}$
The transition function $\delta: Q \times \Sigma \to Q:(\{1,2\},a) \mapsto \{1,2,3\}$, $(\{1,2,3\},a) \...
1
I know this is old, but the inverse of a transformation matrix is just the inverse of the matrix. For a transformation matrix $M$ which transforms some vector $\mathbf a$ to position $\mathbf v$, then to get a matrix which transforms some vector $\mathbf v$ to $\mathbf a$ we just multiply by $M^{-1}$
$M\cdot \mathbf a = \mathbf v \\
M^{-1} \cdot M \cdot \...
0
You are describing a Constraint-Satisfaction Problem (https://en.wikipedia.org/wiki/Constraint_satisfaction_problem). In the last few years, it was shown that every CSP is either $\textsf{NP}$-complete or in $\textsf{P}$. This result was proven independently by Zhuk and (IIRC) Bulatov.
The Generalized Sudoku Problem is also known to be $\textsf{NP}$-complete ...
3
Specifically for the question about functional programming, I'd note that lambda calculus is essentially a direct formalization of computation for higher order functions using syntax that is reasonable/desirable to actually use. First-class functions are highly desirable when programming, and once you have them, a 'function literal' is a natural thing to ...
0
The problem is actually equivalent to the traveling salesman problem, except we don't have to return to where we started. The general traveling salesman problem is an NP-hard problem in theoretical computer science. Furthermore, it is well-known that the traveling salesman problem cannot even be approximated within a constant factor.
However, it seems like ...
4
There's no difference. Lambda Calculus can't tell if you write $\lambda x . M$, if you write $f(x) = M$ or if you write $\hat{x} . M$ (which apparently was church's original notation? I haven't fact checked that, though).
The reason people care about lambda calculus is because it has exactly 3 combinatorial rules from which all computation follows. The dream ...
2
I like to think of Finite State Automata as memory-less algorithms. Effectively, each state corresponds to a Boolean flag. That is, arriving at a state indicates a true/false condition.
In using a programming analogy, it might be helpful to rename states using descriptive variable names. I might recommend the states:
$q_{0}$: The initial state.
$q_{a}$: We ...
2
A Boolean function $\varphi$ is specified by its truth table. For the conjunctive normal form, we look at the rows where the function evaluates to $0$. Each row yields a distinct clause, and we take a conjunction of the clauses. Note that $\varphi(x_{1}, \ldots, x_{n}) = 0$ if and only if the specific values for $x_{1}, \ldots, x_{n}$ correspond to one of ...
0
Welcome to MSE!
Hint:
A word is in $L(D)$ if it ends in an accepting state.
So if you want $w$ to be a prefix of some word in $L(D)$, what can we say about the end state of $w$?
Well, if $w\beta \in L(D)$ that means if we start where $w$ ended and then follow $\beta$, we find ourselves in an accepting state.
Can you show the converse? That is, if there is a ...
1
You are not using right array division. Using "/" instead of "./" yields to a single scalar.
Change your function handle to
F = @(n) sqrt(2.pi.n).(n./exp(1)).^n . (12.*n+1)./(12.*n)
For the input
n=[1:6]
we then get
ans = 0.9990 1.9990 5.9983 23.9959 119.9862 719.9404
as desired.
0
An elementary argument.
Comparing $1.001^n$ and $n^{10}$ is the same as comparing $(\sqrt[10]{1.001})^n$ and $n$. To ease the computation, we note that $\sqrt[10]{1.001}>1.00001$, and we compare $1.00001^n$ to $n$.
Both $1.00001^n$ and $n$ grow unboundedly. (As you can check, $1.00001^{n+1}>1.00001^n+0.00001$, and this is enough to ensure growth.) Now ...
0
We can say that $$(1.001)^n = e^{n\log(1.001)} \geq \frac{(n\log(1.001))^{11}}{11!} $$ using the series expansion of $e$. The result should then be clear.
1
First, consider time complexity once again. The basic idea is simple. When considering a Turing machine $T_M$, we simply "count" the steps $T_M$ needs to halt for any given input, whereby we usually consider a "step" being a transition made by $T_M$. We can consider time complexity as a function $t_c:\Sigma^* \to \mathbb{N}$ of some ...
1
One way of defining a well-formed formula goes that it comes as possible to construct a sequence of symbols where every step $\alpha$ gets built up according to the following :
$\alpha$ is a propositional variable.
$\alpha$ got obtained from a well-formed formula $\beta$ by prefixing a '$\lnot$' to $\beta$.
$\alpha$ got obtained from two well-formed ...
0
Your screenshot proves a $\Theta(n)$ function's values from $1$ to $n$ have a $\Theta(n^2)$ sum. The sum of $n$ functions in $O(n)$ being $O(n^2)$ (if that's what you were asking about) requires a different treatment. Indeed, since each of the $f_i(n):=in\in O(n)$ but $\sum_{i=1}^nf_i(n)\sim\tfrac12n^3$, it's not true in general. If however some $f\in O(n)$ ...
0
$\Theta$ is the two sided version of big $O$. If something is $O(n^2)$ it can be anything smaller, like $n$. $\Theta$ says it is within a constant factor, so $n=O(n^2)$ but $n \neq \Theta(n^2)$ The statement you quote is true if the leading $f$ is replaced by $f_i$, meaning that each $f_i(n)=O(n)$
0
As a general principle, filtering should happen as early as practical: joins tend to multiply the number of rows in each table, which means more work for the filters and for later joins.
In this case:
$S1 ⋈ C1$ creates 14 rows; $E1 ⋈ (S1 ⋈ C1)$ creates another 14 rows; $\sigma_{sujet=BD}(E1 ⋈ (S1 ⋈ C1))$ filters those 14 rows down to 5. The filter is run ...
0
$GF(2)$ forms a boolean ring.
It follows that $GF(2)^n$ forms a boolean ring, because the operations are defined row by row and the rows are independently considered (as in linear algebra).
3
As other answers gave a way to actually prove the result, I would like to add something to "feel" why this is true, or at least a way to remember it without having to do the proof each time this question shows up in your life !
Surely, if one of the two functions grows faster than the other, the same can be said about their logarithms.
We will ...
1
Let $f(n)=1.001^n$ and $g(n)=n^{10}$
For $n \approx 116735$ we have $f(n)=g(n)\approx 4.699\times 10^{50}$
and for $n>116735$ we have $f'(n)=\log_{e}(1.001)f(n) \approx 0.001 f(n)$ while $g'(n) = \frac{10}{n} g(n) \lt 0.0001 g(n) $
so for $n>116735$ we have $f(n) > g(n)$ and $f'(n) > g'(n)$
so past this point $1.001^n$ is larger than $n^{10}$ ...
Top 50 recent answers are included
