# Tag Info

0

Your definition is wrong. All lists will evaluate to equal. You need to actually check that h1 and h2 are the same, and that the lists are the same length. If I recall the exercises correctly, you may want to look back at beq_nat and andb.

3

Metric TSP is NP-complete - hence yes, assuming you can solve the metric TSP in $6(n^{12})$, this is good enough to prove $P=NP$. Giving a blackbox that can do that, would be a quite strong evidence (if it actually works). But there are some considerations one should take into account: it actually could be somewhat dangerous, as someone else could figure ...

-2

Rules for conversion of CFG to CNF https://www.geeksforgeeks.org/converting-context-free-grammar-chomsky-normal-form/ Here is the solution of question:

0

Try this: Require Import Nat. Require Import List. Import ListNotations. (* given a natural n, produces a list of n zeroes *) Definition zeros (n : nat) : list nat := repeat 0 n. Compute (zeros 3). (* = [0; 0; 0] : list nat *) Definition sum_natlist (lst : list nat) : nat := fold_left add lst 0. Compute sum_natlist [1; 2; 3]. (* = 6 : nat *) (* ...

1

I have come up with a solution. To show that the old $B(A)$ is larger than the new $B(A)$, it is necessary to show that $$\text{f}(x_1)\times\text{c_len}(x_1) + \text{f}(x_2)\times\text{c_len}(x_2) > \text{f}(x_1)\times\text{c_len}(x_2) + \text{f}(x_2)\times\text{c_len}(x_1)$$ ($\text{f}(x)$ = frequency of $x$, $\text{c_len}(x)$ = length of $x$'s ...

0

A bit simpler: Assume $L$ is regular, so it satisfies the pumping lemma. Call the constant of the lemma $p$, and take the string $w = 0^p 1^p$, we have that $w \in L$ and $\lvert w \rvert = 2 p \ge p$. By the lemma, we can write $w = x y z$ with $\lvert x y \rvert \le p$, $y \ne \epsilon$, so that for all $k \ge 0$ we have $x y^k z \in L$. Now $y$ is $0^r$, ...

1

According to this Wikipedia page: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between $1$ and $2^h$ nodes at the last level $h$. An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some ...

1

It doesn't matter in which order we place the guards, so we can assume that we place the guards in such an order that each guard covered the first artwork from the right that isn't covered yet (since there must be a guard covering that artwork). The guard can be placed anywhere from 5m to the left of the artwork to 5 to the right. Wherever we place him, ...

0

Let us prove your greedy algorithm is optimal in the sense of the least number of guards returned by simple reasoning. Consider all "closest artwork"s found by your greedy algorithm. The algorithm ensures that each neighboring pair of them is over 10 meters apart. So any two of them are over 10 meters apart, which means one guard can monitor at most one of ...

1

You can achieve this per induction over the position of the last artwork. Note that in the optimal strategy the guard must be put 5 meter ahead of the left most artwork and not exactly at it. In the induction step you have to consider an additional artwork and distinct two cases, whether it is covered by the last fixed guard or not. If it is, you do not ...

0

That really makes no sense. Check out e.g. Hildebrand's "Short course on Asymptotics" for details of the meanings and usage of asymptotic notations. In a nutshell, for typical CS use: $O(f(n))$ is some function $g(n)$ that satisfies $g(n) \le c f(n)$ for some (unspecified) positive constant $c$ for all $n \ge n_0$ for some (again unspecified) constant $n_0$....

0

We need to inspect the factors after that, since the factors of $n!$ grows linearly while the factors of $2^n$ stays constant. We use the first four factors and the rest of them to formulate the constant factors used for the big-O proof. It is obvious that $2^4 = 16$ while $4! = 24$. However, by observing the factors, we notice $2^n$ has $16$ as a factor and ...

Top 50 recent answers are included