# Question
Title: Does exist NP language that is Cook Levin deterministic reducible to xor satisfiability in polynomial time?
We say that the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time if and only if for each word $w\in\Sigma^\*:w\in L\iff f(w)\in XORSAT$ where $\Sigma=\\{0,1\\}$ and $f:\Sigma^\*\rightarrow\Sigma^\*$ is the function in the Cook Levin reduction that was introduced in 1971.

In other words if the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time and $M$ is non deterministic Turing machine that decides the language $L$ in polynomial time then for each word $w\in\Sigma^\*:\Phi\_{M,w}$ is satisfiable if and only if $M$ accepts $w$, according to Cook Levin theorem since 1971, and also $\Phi\_{M,w}$ is in XNF, i.e. XOR Normal Form.

Every boolean formula is in XOR Normal Form or XNF if and only if it is conjunction of clauses and each clause is XOR of literals.

It's well known, according to Cook Levin theorem since 1971, that every NP language is Cook Levin deterministic reducible to CNF satisfiability in polynomial time, i.e. if $L$ is arbitrary NP language and $M$ is non deterministic Turing machine that decides $L$ in polynomial time then for each word $w\in\Sigma^\*:w\in L\iff f(w)\in CNFSAT\land\Phi\_{M,w}$ is satisfiable if and only if $M$ accepts $w$ and $\Phi\_{M,w}$ is necessarily in CNF, i.e. conjunctive normal form, that is conjunction of clauses and each clause is disjunction of literals.

But I don't know if exists special language that is in NP and if we apply the Cook Levin reduction then not only SAT instance is produced, but actually CNFSAT instance is produced and not only just CNFSAT instance is produced, but actually XORSAT instance is produced.

So my question is does exist special language in NP that after applying Cook Levin reduction, for each word $w\in\Sigma^\*$, we get XORSAT instance?

Note that I don't want the function of the reduction to be identity and the NP language that needs to be found that it is Cook Levin reducible to XORSAT in polynomial time is not XORSAT itself.

Also the function of Cook Levin reduction isn't identity at all.

# Answer
XORSAT is in P, so any such language would have to be in P as well.

As such, it is easy to exhibit such an example: the problem XORSAT itself satisfies all your requirements, as XORSAT is Cook-Levin reducible to XORSAT (let $f$ be the identity function).
> 1 votes

---
Tags: complexity-theory, reductions, logic, satisfiability, propositional-logic
---


title: Set partition refinement with subtrees

text:
# Question
Title: Set partition refinement with subtrees
In trying to design an algorithm, I needed a datastructure to implement a restricted kind of set partition refinement, where the sets $X$ to split on are subtrees. Specifically, given an arbitrary tree $T$ (computed earlier in the algorithm), and an initial partition where everything is in the same set, I need to do two things efficiently:

1. Refine the partition by splitting nodes in some subtree $T'$ of $T$ from the rest of the nodes.
2. Given a node $n$ in the tree, figure out the farthest (closest to the root) ancestor in its subset $S\_n$.

The algorithm may have to do both up on (close to) every node on the tree, in any order. There's an obvious algorithm, similar to the one described on Wikipedia, where each node stores a pointer to the farthest ancestor in its set, and then when given a subtree $T'$ to split, we walk through every node in $T'$, and update the pointer to the root $r$ of $T'$ if it's an ancestor of $r$. The problem with this implementation is that since splitting can take up to $O(n)$ time (where $n$ is the size of the tree) to update all the pointers, the whole thing would be $O(n^2)$. Another implementation would be store, for each node, whether it's been split with its parent node. This makes splitting $O(1)$, since we just have to set the flag for the root node, but now finding the ancestor is $O(n)$ (we have to walk up the tree) so the whole thing is still $O(n^2)$. Is there a way to make this faster than $O(n^2)$ by taking advantage of the structure of the problem?

# Answer
Yes. You can build a data structure with the property that each operation takes at most $O(\log n)$ time. Thus, your overall running time for doing $n$ operations will be $O(n \log n)$ instead of $O(n^2)$ -- a significant improvement.

As a warmup, imagine that the tree $T$ was balanced and in particular had depth $O(\log n)$. Then it is immediate to see how to achieve $O(\log n)$ time per operation; your second approach suffices. In particular, you set a flag in each node that is a split point. Since the tree has height $O(\log n)$, walking up the tree takes $O(\log n)$ time.

What if $T$ isn't balanced? We can generalize that answer. Number the leaves of $T$ with the numbers $1,2,\dots,n$, from left to right. Now build a new balanced binary tree $T^\*$ with leaves $1,2,\dots,n$. The shape of $T^\*$ will be unrelated to the shape of $T$, but by construction the depth of $T^\*$ will be $O(\log n)$.

Now, we store flags inside $T^\*$ instead of inside $T$. In particular, we will store a flag inside a node $v \in T^\*$ if (1) the entire subtree of $v$ (including $v$ itself) is in the same partition, and (2) the parent of $v$ is in a different partition from $v$. The flag identifies the partition that $v$ is in. To find the partition that a node is in, you just walk up $T^\*$, which takes $O(\log n)$ time.

And here is the key part. When you split a partition, you can update the flags in $O(\log n)$ time. In particular, when you split off a subtree of $T$, that corresponds to a set of leaves that are in a consecutive interval (namely, leaves numbered $i,i+1,i+2,\dots,j$ for some $i,j$). But over in $T^\*$, every consecutive interval is covered by a (disjoint) union of at most $O(\log n)$ subtrees of $T^\*$. So, you update the flags of the roots of those subtrees to reflect the new partition they are in. That requires only $O(\log n)$ updates, so can be done in $O(\log n)$ time.
> 0 votes

---
Tags: data-structures, trees, partitions
---


# Question
Title: Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point?
The problem is, we are given points $p\_1,\ldots,p\_n$ on positions of a length-$n$ binary sequence $x\_1,\ldots, x\_n$, and if the $i\_{th}$ position of a sequence is $1$, then we "earn" $p\_i$ points. So the total points is $\sum\_{i=1}^{n}x\_ip\_i$. Our rule is that we cannot have three consecutive $1$'s, and we want to know what is highest possible points we can get from a length-$n$ sequence.

I propose an algorithm, but I find examples that leads to non-optimal solution. My algorithm basically goes as follows: let $P(k-1)$ be the highest possible points we can get for the length-$(k-1)$ sequence, with points $p\_1,\ldots,p\_{k-1}$, and it corresponds to an optimal length-$(k-1)$ sequence $s\_{k-1}$, then I add an $1$ at $k\_{th}$ position if it's possible to do so. If it is not possible to add $1$, then the previous 3 terms must be $011$. Then I compare $p\_k,p\_{k-1}$ and $p\_{k-2}$, and put two $1$'s at two positions with the highest points, and put $0$ on remaining position. Hence I get $P(k)$, and $P(n)$ is computed by computing each $P(i)$.

However, consider the example of $n=4$, and $p\_1=1,p\_2=3,p\_3=2,p\_4=4$, this algorithm will produce $0101$, and $P(4)=7$, while $1101$ will have $8$ points.

Anyone has a suggestions on what is a true algorithm for this problem? Thanks!

# Answer
Without loss of generality, assume $p\_i\> 0$. Otherwise we can set all $x\_i=0$ where $p\_i\le 0$ and consider the separated sequences by these $i$'s respectively.

Let $P(k)$ and $Q(k)$ be the highest possible points we can get for $p\_1,\ldots,p\_k$ where $x\_{k-1}x\_k=11$ and where $x\_{k-1}x\_k\neq 11$ respectively.

If the last two bits are $11$, $x\_{k-2}$ must be $0$, and there are no constraint for $x\_1,\ldots,x\_{k-3}$, hence $$P(k)=p\_{k-1}+p\_k+\max\\{P(k-3),Q(k-3)\\}.$$

If the last two bits are not $11$, there are two cases: $01$ or $10$. Note to get the highest points, the last two bits cannot be $00$.

* If the last two bits are $01$, there is no constraint for previous bits, the highest possible points are $p\_k+\max\\{P(k-2),Q(k-2)\\}$.
* If the last two bits are $10$, then $x\_{k-3}x\_{k-2}\neq 11$, the highest possible points are $p\_{k-1}+Q(k-2)$.

So

$$Q(k)=\max\left\\{p\_k+\max\\{P(k-2),Q(k-2)\\},p\_{k-1}+Q(k-2)\right\\}.$$

Use the two recursion formulas above, you can compute the final result $\max\\{P(n),Q(n)\\}$.
> 2 votes

---
Tags: algorithms, dynamic-programming, greedy-algorithms
---


title: Simplifying this Boolean Expression

text:
# Question
Title: Simplifying this Boolean Expression
I have to simplify A+C'+B'CD but I don't see how.

I had to deduce the expression starting from a logic diagram in which two AND gates were used for the B'CD part. Seeing the diagram all I can think of is to use one AND gate instead of two, but I don't see how the actual boolean expression can be simplified.

# Answer
> 1 votes
Using the property $X+YZ = (X+Y)(X+Z)$, you can silmplify $C' + B'CD$ as $C' + B'D$.

---
Tags: logic, boolean-algebra
---


# Question
Title: Packing objects into bins to minimize the number of bins
There is a list of objects. Each object cannot be in a bin with some other objects. How can I find the minimum number of bins required to hold all the objects (and the objects in them)?

My current algorithm:

For each object in the list, see if any of the currently existing bins will hold it. If yes, stick it in the first bin we come to that will hold it. If we exhaust the list of bins without finding a bin, create a new bin and stick the object into it.

Will this algorithm find the minimum number of bins? If not, what algorithm will (NP-hard algorithms OK: I have only about 12 objects)?

*Feel free to add any tags you think appropriate - I'm not sure which one is*

# Answer
This is the clique cover problem in disguise, and finding an optimal solution NP-hard.
> 1 votes

# Answer
This problem can also be viewed as a graph coloring problem. You basically have a graph of objects, and each objects linked together must have different colors (i.e going to different bins)

In practice, some simple search (such as simulated annealing) is going to give you a pretty good solution for graph coloring. If you insist on the smallest number of bins, you can try constraint programming or similar exact solution techniques.
> 0 votes

---
Tags: space-partitioning
---


# Question
Title: Which of the following expressions is TRUE if and only if NOT all three variables a, b, and c have the same value?
I am trying to solve this problem and I am stuck. I think it is B, but I think I'm wrong. Thanks.

Which of the following expressions is TRUE if and only if NOT all three variables a, b, and c have the same value?

A. a != b || b != c

B. (a == b || b == c || a == c)

C. a \>=b && b \>= c && c \>= a

D. a \> b || b \> c || a \> c

E. a != b && b != c

# Answer
My teacher:

This kind of tricky wording is to be expected the AP Exam. The phrase "have the same value" we can take to mean equal. Now, "not all three equal" does not mean "all three different", it means at least one is different. So let's use the test case {a=0, b=0, c=1}

! (a == b || b == c || a == c)

! (0 == 0 || 0 == 1 || 0 == 1)

! (true or false or false)

! (true)

false

a \> b || b \> c || a \> c

0 \> 0 || 0 \> 1 || 0 \> 1

false || false || false

false

a \>=b && b \>= c && c \>= a

0 \>=0 && 0 \>= 1 && 1 \>= 0

true && false && true

false

a != b && b != c

0 != 0 && 0 != 1

false && true

false

0 != 0 || 0 != 1

false || true

true

When you think about it logically, given three things, one of them has to be not equal to one of the other two in order for all three of them to not be the same.

Thus the correct answer is A.
> 0 votes

# Answer
Quoting from your answer

> it means at least one is different

the statement **Not all of them are equal** implies two cases:

$a≠b≠c$

and

$a≠b=c$

Secondly, you have added **!** in the 2nd option which wasn't there in the original question. Finally, with these revised options, (A) is correct, (B) is also correct when $a≠b≠c$ ,(D) also holds good when $a=2b=1c=1$, and (E) is also correct , as I referred to in my previous answer. Now, out of (A) (B) (D) (E), we have to eliminate options which give true when $a=b=c$, because

> expression is TRUE if and only if NOT all three variables a, b, and c have the same value

which is not the case with any of the option. So, these 4 options are correct.
> 0 votes

---
Tags: logic, propositional-logic
---


# Question
Title: Maximizing the sum of adjacent pairs of elements
I encountered the following interesting problem on stackoverflow:

> Given numbers $a(1)\<\cdots\<a(n)$, find a permutation $\pi$ that maximizes $$\sum\_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1)).$$

The answers there claim that the answer doesn't depend on the numbers themselves, and is always given by the order $$\ldots,a(n-5),a(n-3),a(n-1),a(n),a(n-2),a(n-4),\ldots$$ However, the proof (given in the comments) isn't convincing.

> Is the answer on stackoverflow correct? Can we prove it?

# Answer
The following answer is due to Reuven Bar-Yehuda.

Let us call an order *maximal* if it maximizes the objective function $\sum\_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1))$.

**Lemma 1.** If $\pi$ is maximal then for all $1\<i\<j\<n$, $$\pi(i-1) \< \pi(j+1) \text{ iff } \pi(i) \< \pi(j).$$

**Proof.** Suppose that $\pi(i-1) \< \pi(j+1)$ and $\pi(i) \> \pi(j)$. Form the permutation $\sigma$ by reversing the order all $\pi(i),\ldots,\pi(j)$. Then $$ \sum\_{k=1}^{n-1} a(\sigma(k)) a(\sigma(k+1)) - \sum\_{k=1}^{n-1} a(\pi(k)) a(\pi(k+1)) = \\ a(\sigma(i-1)) a(\sigma(i)) + a(\sigma(j)) a(\sigma(j+1)) - a(\pi(i-1)) a(\pi(i)) - a(\pi(j)) a(\pi(j+1)) = \\ a(\pi(i-1)) a(\pi(j)) + a(\pi(i)) a(\pi(j+1)) - a(\pi(i-1)) a(\pi(i)) - a(\pi(j)) a(\pi(j+1)) = \\ (a(\pi(i-1)) - a(\pi(j+1)) (a(\pi(j)) - a(\pi(i)) \> 0. \quad \square $$

**Lemma 2.** If $\pi$ is maximal then $\pi(1) \< \pi(i)$ for all $i \neq n$ and $\pi(n) \< \pi(j)$ for all $j \neq 1$.

**Proof.** Both claims have a similar proof, so we only prove the first. Suppose that $\pi(1) \> \pi(i)$ for some $i \neq n$. Form the permutation $\sigma$ by reversing the order of $\pi(1),\ldots,\pi(i)$. Then $$ \sum\_{k=1}^{n-1} a(\sigma(k)) a(\sigma(k+1)) - \sum\_{k=1}^{n-1} a(\pi(k)) a(\pi(k+1)) = \\ a(\sigma(i)) a(\sigma(i+1)) - a(\pi(i)) a(\pi(i+1)) = \\ (a(\pi(1)) - a(\pi(i)) a(\pi(i+1)) \> 0. \quad \square $$

**Theorem.** If $\pi$ is maximal then $\pi$ is the following permutation or its reverse: $$ 1,3,5,\ldots,6,4,2. $$ **Proof.** Lemma 2 shows that $a(\pi(1))$ and $a(\pi(n))$ are both smaller than $a(\pi(2)),\ldots,a(\pi(n-1))$, and so $\\{\pi(1),\pi(n)\\} = \\{1,2\\}$. Without loss of generality, assume that $\pi(1) = 1$ and $\pi(n) = 2$.

Lemma 1, applied with $i=2$ and $j=3,\ldots,n-1$, shows that $\pi(2)$ is smaller than $\pi(3),\ldots,\pi(n-1)$, and so $\pi(2) = 3$.

Lemma 1, applied with $j=n-1$ and $i=3,\ldots,n-2$, shows that $\pi(n-1)$ is smaller than $\pi(3),\ldots,\pi(n-2)$, and so $\pi(n-1) = 4$.

Continuing in this way, we recover the rest of $\pi$. $\quad \square$
> 3 votes

---
Tags: optimization, permutations
---


# Question
Title: Distinguishing between side-by-side liquid streams
I'm new to computer vision and am looking for advice. I'd like to perform computer vision on a spiral system, in this system a down flowing liquid separates into different regions based on density:

The regions can be visually distinguished based on colour. What I'm hoping to do is automatically detect changes in the average colour of each region, width of each region and perhaps total breakdown of regions.

Could you please suggest which techniques of computer vision would be best for this type of analysis? and would you suggest an approach using Matlab or python + library (any)?

# Answer
I would suggest looking into standard methods for image processing. You could use the Hough transform to detect circles. You could potentially use morphological transforms and the watershed algorithm to smooth out and remove noise and detect boundaries between the regions.
> 1 votes

# Answer
I would cluster (e.g. kmeans) the pixels in the interesting area by their hue (in the HSL color space), and then extract the information you want from each cluster.
> 1 votes

---
Tags: image-processing, computer-vision, python
---


# Question
Title: What are some problems in the class P which we used to think were in the class of NP?
I was recently watching a video on the classes of P and NP, in which it was claimed that there have been 'several' problems that were presumed to be in the class of NP, which have since been shown to be in the class of P. Unfortunately, no examples of such problems were given. Could anyone verify this statement by providing an example of such a problem?

# Answer
> 3 votes
Consider the following problem $A$: given $n$, is $n$ a composite integer (i.e., not a prime)?

It is easy to prove that $A$ is in NP: any nontrivial divisor acts as a certificate.

Proving that $A$ is also in P is much harder, and it is equivalent to proving that its complement, i.e. primality, is in P as well. Still, this has now been proved.

---
Tags: complexity-theory, np
---


# Question
Title: Ideal value of d in a d-ary heap for Dijkstra's algorithm
I stumbled upon the following statement:

> By using a $ d $-ary heap with $ d = m/n $, the total times for these two types of operations may be balanced against each other, leading to a total time of $ O(m \log\_{m/n} n) $ for the algorithm, an improvement over the $ O(m \log n) $ running time of binary heap versions of these algorithms whenever the number of edges is significantly larger than the number of vertices

Applications of d-ary heaps

I don't understand why we choose to have a heap where nodes have exactly $ m/n $ children to speed up Dijkstra's algorithm. Remove min takes overall $ O(n \log\_d n) $ time and decrease takes $ O(m \log\_d n) $, so total runtime is $ O(m \log\_d n) $.

What I don't understand is say we have $ m=3, n=1 $, $ m/n $ gives 3, but $ O(m \log\_3 n) $ is slower than $ O(m \log\_4 n) $, so why not choose 4 as value of $ d $ instead? What motivates taking $ m/n $?

Thanks!

# Answer
> whenever the number of edges is significantly larger than the number of vertices

What they probably mean is that $m \in \omega(n)$. Then, $m/n \in \omega(1)$ -- the base of the logarithm *grows* with $n$, that is the resulting sequence of values grows more slowly than with a fixed base.

For dense graphs in the sense that $m \in \Theta(n^2)$, the effect is most pronounced. For the sake of simplicity, say $m = cn^2$ for some $c \in (0,1)$. Then, $m/n = cn$ and therewith $\log\_{m/n} n = \log\_{cn} n \in O(1)$ -- the logarithmic factor has vanished, the algorithm has running-time in $O(m)$.

Note that all of this is discussing only the upper Landau-bound. In which way the true running-time cost is affected by this change is not per se clear, and the Wikipedia article is bold in claiming that it's an "improvement".
> 1 votes

# Answer
Please note that $ m \leq n(n-1)/2 $, thus $m/n \< n/2$. So the example $m=3, n=1$ does not happen.

**First**, the article clearly claims that this improvement is achieved whenever $ m $ is larger than $ n $,

> By using a $d$-ary heap with $d = m/n$, ..., an improvement over the O(m log n) running time of binary heap versions of these algorithms **whenever the number of edges is significantly larger than the number** **of vertices**.

**Secondly**, the article claims that $d$ must create a balance between $m$ and $n$ in order to improve the running time,

> By using a $d$-ary heap with $d = m/n$, **the total times for these two types of operations may be balanced against each other**...

Generally, we need $n$ `min-extract` and $m$ `decrease-key` operations. In the case of $d=2$, each of these operations takes $O(\log n)$ time. However, when you increase $d$, the `decrease-key` operation becomes faster, but `min-extract` can become slower. Because, within each `min-extract`, we also need to run `min-heapify` that depends on the number of children of the parent in each level.

In the extreme case, if you consider $ d=n $ then $m \log\_n n \< m \log\_{m/n} n$, but the running time won't be better in practice. Because you need at most $ n $ `min-extract` operations, each includes a `min-heapify`. Therefore, you need $ n $ `min-heapify` operations, that will cost $ O(n) $ in this case (because $d=n$ and there are $n$ numbers in the next level of your tree). Thus the running time of your algorithms becomes $O(n^2)$ ($n$ times running `min-heapify`).
> 4 votes

# Answer
Runtime of Dijkstra with $n$ nodes and $m$ edges and using a $d$-ary heap for the priority queue will be $O((nd+m)\log\_d n)$:

* $O(nd\log\_d n)$ from ExtractMin operations and
* $O(m\log\_d n)$ from ChangePriority (strictly DecreaseKey) operations.

We want to balance $nd$ against $m$, given $m\gg n$. I.e. $nd=m$, or, $d=m/n$. If we have a constant $d$, asymptotic time will lean towards $O(m)$ \[$m\gg n$\].

In practice you'll need to play around a little to know what value of $d$ works for you.
> 0 votes

---
Tags: algorithms, data-structures, shortest-path, heaps
---


# Question
Title: If set $C$ is recursively enumerable and $B$ is Recursive, and if $B-C$ is recursively enumerable then is $C$ recursive or not?
So this is how i solve it but someone told me its wrong:

$B-C = B\cap \overline C $ and since $B\cap \overline C $ is r.e and B is recursive recursive sets are closed under intersection then $\overline C $ is not Recursive(because if both of them were recursive then the intersection would be recursive), also since r.e sets are closed under intersection then $\overline C $ must be r.e

and since $\overline C $ and $C$ are r.e then C is recursive

so am i wrong? is C recursive or not and why?

# Answer
The argument is wrong.

Your argument is: $B\cap \bar C$ is r.e., $B$ is recursive, so $\bar C$ has to be non recursive, otherwise $B \cap \bar C$ would be recursive -- contradiction.

However, there is no contradiction: $B\cap \bar C$ *can* be both r.e. and recursive. This is equivalent to $B\cap \bar C$ being recursive. There is no hypothesis contradicting that.

Indeed, take $C$ to be the halting problem (r.e., and not recursive). Take $B=\emptyset$ which is recursive. Then $B\cap\bar C = \emptyset$ which is (recursive and) r.e. . So all the hypotheses are satisfied, but $C$ is not recursive.
> 1 votes

---
Tags: turing-machines, computability, undecidability, recursion
---


# Question
Title: Why isn't deque implemented as a dynamic array?
We know that `std::vector` in C++ is implemented as a dynamic array with specific pattern of reallocation (multiplying capacity by a constant), which allows it to reach O(1) amortized `push_back` time. But changing capacity of a vector is essentially allocation of new memory block and copying old data into it. That means we can as well implement a vector which can grow in both directions with amorized O(1) `push_back` and `push_front` time.

But `std::deque` is implemented in different, rather complicated way, not storing data in a contiguous manner and suffering from related issues (e.g. more frequent page faults when iterating). Why so? Are there any obstacles disallowing to implement deque as a dynamic array?

# Answer
> 3 votes
The reason why `std::deque` is implemented as a sequence of non-contiguous blocks is to guarantee different complexity bounds (and different concrete performance) for operations with regards to `std::vector`.

You already partially said it: changing the capacity of an `std::vector` requires reallocating the memory and copying the *entire* content to the new memory. While it is true that the `std::vector`reallocation scheme achieves a O(1) amortised complexity, the implementation of `std::deque` guarantees a true O(1) complexity bound for appending.

---
Tags: algorithms, queues, c++
---


# Question
Title: Why can't we sort an Array in O(n) using Fibonacci Heap?
**If we can insert to a Fibonacci Heap in O(1), and increase-key and find-min in the same W.C time complexity, then why can't we sort an array in time complexity O(n)?**

Given an array with n elements:

1. Find the maximum of the array (largest key) in O(n).
2. Build a Fibonacci Heap of the elements in O(n), emptying the array in the proccess.
3. Use find-min and add the result to the now empty array.
4. Use increase-key on the element you found in step 3, and increase it by the maximum of the old array + 1 (making it now larger than any element of the old array)
5. Reapet steps 3 and 4, n times. Each time a new element from the old array is added, because all added elements are larger than max+1.

# Answer
> 8 votes
Increase-key is not a $O(1)$ operation on Fibonacci heaps. You're thinking of decrease-key.

Exercise: Why can't increase-key be a $O(1)$ operation on this data structure?

# Answer
> 0 votes
If it was possible, Heapsort would take $\Theta(n)$ time. This is a contradiction to the lower bound of $\Omega(n\lg n)$ when sorting by comparisons.

---
Tags: sorting, heaps
---


# Question
Title: Evaluating correctness of various definitions countable sets
I was trying to understand the definition of countable set (again!!!). Wikipedia has a very great explanation:

> 1. A set $S$ is **countable** if there exists an $\color{red}{\text{injective}}$ function $f$ from $S$ to the natural numbers $\mathbb N$.
> 2. If such an $f$ can be found that is also surjective (and therefore $\color{red}{\text{bijective}}$), then $S$ is called **countably infinite**.
> 3. In other words, a set is **countably infinite** if it has $\color{red}{\text{bijection}}$ with the $\mathbb N$.

So I summarize:

1. $S$ is **countable** iff $S\xrightarrow{injection}\mathbb N$
2. $S$ is **countably infinite** iff $S\xrightarrow{bijection}\mathbb N$

But then wikipedia confuses by stating following points:

> **Theorem:** Let $S$ be a set. The following statements are equivalent:
>
> 1. $S$ is countable, i.e. there exists an injective function $f : S → \mathbb N$.
> 2. Either $S$ is empty or there exists a surjective function $g : \mathbb N → S$.
> 3. Either $S$ is finite or there exists a bijection $h : \mathbb N → S$.

**Q1.** I feel 2nd statement is wrong, as it allows some element in $S$ to not to map to any element in $\mathbb N$. That is $\mathbb N \xrightarrow{surjection} S$ does not imply $S\xrightarrow{injection}\mathbb N$. Hence $S$ is not countable. Right?
**Q2.** 3rd statement defines countably infinite set, so its countable also. Right?
**Q3.** Also I dont get if the extra restrictions of emptyness and finiteness in statements 2 and 3 are required.

Wikipedia further says:

> **Corollary:** Let $S$ and $T$ be sets.
>
> 1. If the function $f : S → T$ is injective and $T$ is countable then $S$ is countable.
> 2. If the function $g : S → T$ is surjective and $S$ is countable then $T$ is countable.

**Q4.** Here, too, I feel 2nd statement is incorrect for the same reason as 2nd statement in the theorem. Right?

# Answer
The Wikipedia theorem is correct. More generally, if $A$ is an ordered set and there exists a surjection $g\colon A \twoheadrightarrow B$ then there exists an injection $f\colon B \hookrightarrow A$ given by $f(b) = \min g^{-1}(b)$. This is an injection since $g(f(b)) = b$.

More generally, if you assume the axiom of choice then you don't need to assume that $A$ is ordered, since the axiom of choice guarantees the existence of a function $f\colon B \to A$ satisfying $f(b) \in g^{-1}(b)$ for all $b \in B$.
> 1 votes

---
Tags: sets
---


title: Proof of Demorgan's law

text:
# Question
Title: Proof of Demorgan's law
how can i prove Demorgan's law **(X+Y)'=X'. Y'**?I already tried studying book but doesn't understand the first step so plz answer in detail.(beginner here)

# Answer
> 0 votes
In order to prove $A = B$, It is sufficient to prove that $A'B = 0$ and $A' + B = 1$. Try to think of why this should be the case intuitively. In case you are unable to understand, then think of $A$ and $B$ as sets, Boolean $+$ operation as set union operation and Boolean $.$ operation as set intersection operation.

Therefore, take $A = (X+Y)'$ and $B = X'Y'$.

So, $A'B = (X+Y)X'Y' = XX'Y' + YX'Y' = 0$.

Also, $A' + B = X + Y + X'Y' = 1$.

(Use the property $A + BC = (A + B )(A + C)$ for simplifying above expression.

---
Tags: logic, boolean-algebra
---


# Question
Title: Dynamic Programming for a variant of the coin exchange problem
I am interested in solving a variant of the coin exchange problem. Recall the formal definition of the coin exchange problem:

Given a value *N*, if we want to make change for *N* cents, and we have infinite supply of each of *S = {S1, S2, .. , Sm}* integral-valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for *N* = 4 and *S = {1,2,3}*, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For *N* = 10 and *S = {2, 5, 3, 6}*, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5. See here for further detail.

Here, one can find a tabulation-DP-based solution for this problem. This solution is based on the following recurrence relation:

```
count(S, m, n) = count(S, m - 1, n) + count(S, m, n - S[m - 1]);

```

With base cases:

```
count(S, m, n < 0) = 0
count(S, m, n = 0) = 1
count(S, m <= 0, n >= 1) = 0

```

Intuitively, this recurrence relation defines a problem as the solution to two sub-problems: Those in where we discard coins, and those for which we assume the coins a progressively used once at the time.

**Question**: How can I modify this recurrence relation to count the number of ways we can sum to *N* disregarding order and with an even number of summands? For example, for *N* = 4 and *S = {1,2,3}*, there are four solutions total (disregarding order): {1,1,1,1},{1,1,2},{2,2},{1,3}, but only 3 of them have an even number of summands, i.e. {1,1,1,1},{2,2},{1,3}.

**Previous research**: At first I thought I could double the requested sum for the case of discarding coins, and requesting that each coin is consumed twice for the cases in where we would use some of the coins, i.e.:

```
count(S, m, n) = count(S, m - 1, 2*n) + count(S, m, n - 2*S[m - 1]);

```

This works for some sample cases, but it does not work. Any hints?

# Answer
Add a parity parameter to $C$ and check for it in the base case, making the wrong parity invalid:

$$ \newcommand{\for}{\text{for }} C(S, m, n, p) = \begin{cases} 0& \for n \< 0\\ 0& \for n = 0 \wedge p = 1\\ 1& \for n = 0 \wedge p = 0\\ 0& \for m = 0\\ C(S,m-1,n,p) + C(S, m,n-S\_m, 1-p)& \text{otherwise} \end{cases} $$

Note that I'm using mathematical notation above so $S$ and $m$ are using one-based indices.

Since we want only an *even* number of summands we want $p = 0$, thus $C(S, m, n, 0)$ gives the answer you want.
> 1 votes

---
Tags: dynamic-programming, coin-change
---


# Question
Title: How to represent software code for code generation / automatic programming? How to integrate procedural and declarative knowledge?
I am learning about deontic logics and there I can make the following inferences: `If A then there is **duty to create an entity of class C**`, `If B then there is **duty to assign value 5 to the attribute c.a**`, `if A and B then **the computation D should be executed**`. I. e. those deontic logic statements contain the usual propositional variables A, B, C, but they also contain actions - pieces of procedural knowledge, like `create an entity of class C` and so on. The questions are:

* **How do I represent those actions in such manner that they can be used for the code generation/automatic programming?** The simple approach can be to represent them by their content - e.g. by the code in the industrial programming language.
* The goal of such reasoning is to create the syntactical tree of the program from which the source code in the industrial programming language can be read as source file. **How do I represent actions that they can form the syntactical tree?**

I feel that the deontic logic (formalized norms) are enough for generating software code (at least business layer - classes and their behavior), but I am struggling with the consequent end of the inference - how to represent actions/source code?

This may be seen as the more general question as well: formalized norms can be seen as the declarative knowledge and we should create reactive, procedural programs / procedural knowledge from the declarative knowledge - **how to represent procedural knowledge and how to create procedural knowledge from the declarative knowledge?** Are there research efforts to do this and what are keywords for this type of reasearch (so - I can find the already achieved results in Google or journal databases).

# Answer
Use some form of metamodelling :

> The outputs are represented as abstract syntax trees (ASTs):

> and constructed by a decoder with a dynamically-determined modular structure paralleling the structure of the output tree.

**References**
> 1 votes

---
Tags: logic, software-engineering, knowledge-representation, code-generation, modal-logic
---


# Question
Title: Does every undecidable problem contain a decidable subset?
I know being a decidable language doesn't necessarily mean that every subset is of it is decidable, but does every undecidable language contain a decidable subset?

# Answer
Yes. The empty language is decidable and subset of every other language. You can also say that every undecidable language has a superset which is decidable ($\Sigma^\ast$ for example).
> 0 votes

---
Tags: formal-languages, undecidability
---


# Question
Title: How to partition a tree on a fixed budget of edge cuts?
Suppose I have a tree $T=(V,E,w)$ with vertex weights $w(v)\ge 0$ for all $v\in V$. I want to partition this tree into $k+1$ trees by cutting $k$ edges such that the deviation from the mean of the sum of vertex weights in each partition is minimized.

Is there an algorithm to get a good approximation in polynomial time?

Literature research has yielded this method finding a partitioning with bounded partition size, but it doesn't seem to adapt readily to the desired fixed number of cuts. Likewise, there is a lot of research on *tree partitionings* where multiple subtrees can be placed into one partition, an NP-hard problem. This doesn't seem relevant either as each partition must be a single subtree in my case, significantly changing the problem. This question seems to ask the same question I ask but doesn't specify what kind of partitioning is optimal. The dynamic program given in this answer would work for the unweighted case, but my graph is weighted, so it doesn't apply.

# Answer
> 2 votes
There is a straightforward dynamic programming algorithm to find the exact answer whose running time is something like $O(nk^2t^2)$, where each partition's total weight is about $t$. This is far too slow for your parameter settings.

To get an approximation, one trick is to pick a parameter $r$ and divide every weight by $r$ and then round to the nearest integer. Then, you have a new instance where the weights are much smaller, and you can find an exact solution to this using dynamic programming. That will then be an approximate solution to the original problem -- not necessarily the optimal answer, due to rounding, but it might get close.

When rounding, you might get some improvement by using randomized rounding. For example, if the division gives you a number like $2.7$, you flip a biased coin; with probability $0.7$, you round this to the integer $3$, and with probability $0.3$, you round it to the integer $2$.

There may be better solutions, but this is one simple thing you could try.

---
Tags: graphs, trees, partitions
---


title: NP-hard - Definition

text:
# Question
Title: NP-hard - Definition
The definition of NP-hard problem in Wikipedia is : NP-hardness (non-deterministic polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP".

There are NP-hard problems not in NP class. My question (more curiosity) concerns the **NP** in the definition. Since a NP-hard maybe is not in NP class, why we call it **NP**-hard?

When we say we have a NP-complete problem, then this problem is indeed in NP class.

# Answer
Here is a definition which describes the relationship between hard and complete:

> Given a set `C` of problems and a reduction `R`, it is natural to ask if there are problems `Π ∈ C` such that any problem `Π′∈C`, `R`-reduces to `Π`. Such “maximal” problems are called in complexity theory complete problems. Let `C` be a class of problems and `R` be a reduction. A problem `Π ∈ C` is said to be `C`-complete (under `R`-reduction) if for any `Π ∈′ C`, `Π′ ≤R Π`. A `C`-complete problem (under reduction `R`) is then (in the sens of this reduction) a computationally hardest problem for class `C`. For instance, in the case of `NP`-completeness, `NP`-complete problems (under Karp-reduction) are the hardest problems of `NP` since if one could polynomially solve just one of them, then one would be able to solve in polynomial time any other problem in `NP`. Let `C` be a class of problems and `R` a reduction. A problem `Π` is said to be `C`-hard (under `R`-reduction) if for any `Π ∈′ C`, `R Π≤ Π ′`. **In other words, a problem `Π` is `C`-complete if and only if `Π ∈ C` and `Π` is `C`-hard**.

**References**
> 1 votes

---
Tags: np
---


# Question
Title: Turing machine halting in at least 100 steps on all inputs
L = {\< M \> $\mid$ L(M) = M halts on all inputs in atleast 100 steps }.

Answer to this question is given undecidable in my book without any explanation but I think it is decidable.

---

$\overline{L}$ = {\< M \> $\mid$ L(M) = M halts on **some** input in **atmost** 100 steps }

For the above language, we can feed strings of length ranging from 1-100 (finite amount of strings) and run Turing machine for finite amount of steps (100) on each string and check if at least one of them halts in atmost 100 steps.

So, as the complement of L is recursive, L should also be recursive and decidable according to me.

Where am I going wrong ?

# Answer
> 0 votes
You have not correctly computed $\overline{L}$. It contains

* machines which halt in less than 100 steps for some input (which is a finite set of possibilities, as you say), and
* machines which don't ever halt for some input.

The second part requires a solution to the halting problem, so $\overline{L}$ is not decidable (nor recursively enumerable).

---
Tags: formal-languages, turing-machines
---


# Question
Title: It is possible to write any program (i.e. Turing complete) with just one single expression?
So I'm currently taking discrete math II at my university and I came across a somewhat philosophical question (so I apologize if this is question is hard to answer precisely) of whether mathematicians and computer scientists view computation in the same way.

We computer scientists define computation with the Turing machine and/or lambda calculus. **I was simply wondering if there is some language/notation (lambda calculus??) that allows a mathematician to write a computable (i.e. Turing computable) program using only one mathematical expression.**

Again, I apologize if that's a bit of an abstract question (I'm new to these concepts and my terminology isn't great) but let me try to clarify: in math (or at least when I did math in school), there isn't the notion of control flow over time with different statements--there is only a single expression that evaluates to a value. Evaluating the expression may involve partially evaluating nested expressions in a certain order but the end result and the expression itself represented computation in some sort.

**So now my question is this:**

(Through the use of lambda calculus) is it possible to write any program (i.e. Turing complete) using only one expression with no more than one statement? Is lambda calculus set up in a way that removes or hides the notion of control flow?

# Answer
I think that your general question is pretty broad, because you'd need to specify what you consider a program (e.g. is the identity function that outputs the input it receives a program?).

It is possible to have some sort of control flow in lambda expressions (there are only expressions in lambda calculus); consider e.g. Church Booleans that enable conditionals.

If you would like to see examples of lambda calculus expressions put to work like regular programs, I can recommend John Tromp's binary lambda calculus. I have been able to evaluate some of his programs using plain β-reductions (examples), so I can say it's definitely possible to write programs even with pure lambda calculus.
> 2 votes

---
Tags: formal-languages, turing-machines, automata, lambda-calculus, church-turing-thesis
---


# Question
Title: PSpace-completeness under PSpace reductions
A language $L$ is PSpace-complete, if it meets two conditions:

1. It is in PSpace.
2. Every other PSpace-complete language reduces to it in polynomial time.

Question: suppose we change the second condition to polynomial space (instead of time)? Why is it so that then SAT would be PSpace-complete?

# Answer
> 6 votes
Every language $X$ in PSPACE would be complete under your proposed definition, except for $\emptyset$ and $\Sigma^\*$. You could reduce any PSPACE language $Y$ to $X$ by a reduction that first decides whether its input $w$ is in $Y$ and then maps to a fixed "yes" instance of $X$ if so, and a fixed "no" instance if not.

Note also that the actual definition of PSPACE-completeness requires that every language in the whole of PSPACE reduces to the complete language. The definition you've given is circular, since it defines PSPACE-completeness in terms of itself.

---
Tags: complexity-theory, reductions, complexity-classes, space-complexity
---


# Question
Title: General algorithm for generating a description of the language it is written in
Does there exist a general algorithm which can output a finite and complete description of the (programming) language in which it is written, if it is given the permission to execute programs in that language?

The description should be sufficient to associate a correct output for any given program in that language.

# Answer
> 1 votes
The algorithm you ask for cannot exist. To show this, consider 'programming languages' where every program $P$ is a single integer (we can interpret most programs as a number, but here we will explicitly use the number). Now, consider the following class of 'compilers': $C\_k$, such that the compiled program is $C\_k(P):= \begin{cases}1 & \text{if $P\geq k$}\\ 0&\text{if $P\<k$}\end{cases}$.

Now, suppose our compiler-reverse engineering program has come to the conclusion that some black box compiler $C$ behaves as $C\_{k^\*}$ for a finite number of programs, the largest one being $P'$. But then $C\_{k^\*}$ is indistinguishable from $C\_k$ for all $k\>k^\*$, so our procedure cannot determine the behaviour of $C$ with only a finite number of inputs.

So, as any algorithm must test an infinite amount of inputs, there is no algorithm that correctly decides even these simple languages.

---
Tags: algorithms, programming-languages
---


# Question
Title: What is the difference between a tight Big $O$ bound, a tight Big $\Omega$ bound and a Big $\Theta$ bound?
I occasionally see these terms used and I'm not really sure what is meant by all of them. Is it possible for an asymptotic bound that is not Big $\Theta$ bound to be "tight"? What does it mean for bounds that are not Big $\Theta$ to be tight?

Is there a difference between a tight Big $O$ bound and a Big $\Theta$ bound?

# Answer
> 1 votes
$O$ and $\Theta$ refer to different properties of some function. In a sense, we know more of a function when we can describe it with $\Theta$ than with $O$.

However, usage of $O$ or $\Theta$ doesn't imply tightness of a bound. You have some function $f(n)$ that is a bound which you could either describe with $f(n)\in O(g(n))$ or $f(n)\in \Theta(g(n))$, but whether the bound is tight depends on the actual bound $f$.

So, as a tight bound means simply that there is no 'better' bound for all cases, a tight asymptotic bound (either in $O$ or $\Theta$, or even $\Omega$), simply means that there is no better asymptotic description of a bound.

An example of a tight bound with only $O$ is the time complexity of finding an element in an unordered list of size $n$. This complexity is bounded by $O(n)$ and this is tight. The complexity is *not* $\Theta(n)$, as there are cases when we find the element without scanning the entire list. (The asymptotic complexity of the worst case is $\Theta(n)$, though)

For more reading on bounds with Landau ('big $O$') notation, see the reference question How does one know which notation of time complexity analysis to use? and its answers.

---
Tags: asymptotics
---


# Question
Title: What is the time and space complexity of Rete algorithm
I am working on pattern matching algorithm. Its working and using very less memory. For the comparison, I have to compare it with the Rete Algorithm. I have checked it in the thesis of the author, some of his paper and he has provided some complexities which are not based on then, nor does its efficiency is provided in the space complexity.

My algorithm despite large inputs worst case is $O(n^2)$. Can someone point me to a good reference where I can find its complexity? I have been searching for a while now, and I did not even get the pseudo code. Things not to consider in order to save your time is algorithms, software, expert systems based on Rete algorithm e.g. Jess etc. reference link for algorithm thesis pdf Click to download

citation of the paper "Forgy, C.L., 1982. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artificial intelligence, 19(1), pp.17-37."

# Answer
> 0 votes
finally i found what was needed, thought i wil share here for others who might need it. http://reports-archive.adm.cs.cmu.edu/anon/1995/CMU-CS-95-113.pdf

---
Tags: algorithms, machine-learning, runtime-analysis, pattern-recognition, space-analysis
---


# Question
Title: How to prove that a minimum edge cover is a forest?
How can it be proved that any minimum edge cover is a forest? As far as I understand an edge cover could be one connected component therefore a spanning tree). If it's the case then it wouldn't be a forest.

# Answer
> 2 votes
A forest is a graph in which every component is a tree. If there is only one component, and that component is a tree, the graph is a forest.

So why is every minimum edge cover a forest? Suppose you have a graph $G=(V,E)$ and an edge cover $C\subseteq E$. Suppose some component of the graph $(V,C)$ contains a cycle, say $x\_1x\_2\dots x\_kx\_1$. Then $C\setminus\\{x\_1x\_2\\}$ is a smaller edge cover than $C$: $x\_1$ is covered by the edge $x\_kx\_1$, $x\_2$ is covered by $x\_2x\_3$ and every other vertex in $V$ is still covered by whatever covered it in $C$. Therefore, every minimum edge cover must contain no cycles, and an undirected graph that contains no cycles is a forest.

Indeed, we can go even farther. If an edge cover $C$ contains a path $x\_1x\_2x\_3x\_4$ then $C\setminus\\{x\_2x\_3\\}$ is a smaller edge cover, by essentially the same reasoning as above. Therefore any minimal edge cover is a forest that contains no path of three or more edges. So, not only is every minimum edge cover a forest, but it's a forest where every component is a star (a complete bipartite graph $K\_{1,k}$ for some $k\geq 1$; note that $K\_{1,1}$ is an edge and $K\_{1,2}$ is a two-edge path).

---
Tags: graphs
---


# Question
Title: What is the difference between a Standardization and a Specification?
While asking this question on "what exactly is standardization", I remebered that another related term that always came up while reading about C libraries was the term "specification".
To avoid asking more than one question in a single post, I decided to open another post that I hope will clarify what is the difference between this two "popular" terms.
The C POSIX library is defined as a specification of the C standard library, for POSIX systems. Anyway, is Posix usually considered standardized as well, isn't it? Well, I'm a little bit confused by the use of this words.
I'd love to see reference and examples about other langauges, as much as clarification in the C case.

# Answer
You ask for the definition of "specification". Here's one: https://en.wikipedia.org/wiki/Specification\_(technical\_standard). You asked for the definition of a standard. Here's one: https://en.wikipedia.org/wiki/Technical\_standard.
> 1 votes

---
Tags: terminology, programming-languages
---


# Question
Title: If there's algorithm which returns true if Hamiltonian cycle exists in polynomial time then an algorithm to find the cycle in such time also exists?
> How can it be proved that if there's an algorithm which in polynomial time determines whether a graph has a Hamiltonian cycle then there's an algorithm which can find such Hamiltonian cycle in polynomial time as well?

**Note:** there's no need to devise the actual algorithm I just need to prove that one causes the other to hold.

I thought that perhaps the algorithm A which just determines whether the graph contains a Hamiltonian cycle has to perform the same amount of work as the algorithm B which has to find the actual cycle because each node has to be visited.

But I'm not sure how to actually prove this.

# Answer
Input: A graph G = (V, E) for which the checker algorithm is true.

if you remove an edge $e\in E$ from The graph and run the algorithm then if it returns false the removed edge must be part of every hamiltonian cycle in the graph.

If the result is true then we can remove the edge and remove another edge we haven't checked yet and run the algorithm again.

Eventually the graph will only contain a hamiltonian cycle. in O(e) applications of the algorithm.
> 7 votes

---
Tags: algorithms, graphs
---


title: Question about IO automaton

text:
# Question
Title: Question about IO automaton
I'm currently reading Nancy Lynch book about distributed systems, chapter about IO automaton. And I have following questions related to book exercise 8.13(c).

We are given some automaton A with sig(A) is empty. Traces(P) is the set of sequences over {1,2} in wich every occurance of 1 is immediatly followed by a 2. I need to show that P is neither a safety property nor a liveness property. and show explicitly that P could be expressed as intersections of S and L.

Here is my problem: I can show that P is not safety because it breaks prefix-closed property, e.g. {2,1,2} has no prefix belonging to P (it should be of the form {...,1} which is impossible for P). But I don't know how to deal with L property -- either it is empty or include trace(P) -- trace(P) $\subset$ trace(L). If it is empty then traces(P) is empty because traces(P)= traces(S) $\cap$ traces(L) which is wrong. So I think that traces(P) is subset of traces(L).

Is my conclusion related to traces(L) is right?

How can I explicitly express traces(P)=traces(S) $\cap$ traces(L) for this problem?

Thanks in advance.

# Answer
> 1 votes
Let S be the set of all traces in which "11" does not appear (a safety property) and L be the liveness property defined such that if 1 appears then eventually 2 will appear after (in temporal logic: $\square( 1 \rightarrow \lozenge 2)$). Then trace(P)=trace(S)$\cap$trace(L).

---
Tags: automata, distributed-systems, concurrency
---


# Question
Title: Why isn't every vertex connected to every other vertex in TextRank?
I've been reading up on the automatic text summarization approach TextRank, particularly for generating summaries of a text using sentence extraction as opposed to keyword or phrase extraction.

In the published paper, an example body of text and the resulting ranked graph of all sentences/vertices and their edges is given. I'm unclear as to why every vertex doesn't have an edge connecting it to every other vertex in the graph - shouldn't all sentences be compared with each other?

This doesn't seem to be addressed in the paper. One possible explanation I've produced is that there is no edge if the similarity between two sentences is 0. Does anyone know for sure?

Link to paper: https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf

# Answer
> 1 votes
After getting in touch with the authors of the paper, the reason why every vertex isn't connected to every other vertex in the graph is because only edges with a non-zero weight are added to the graph.

---
Tags: graphs, artificial-intelligence
---


# Question
Title: Computation Complexity of stream algorithm
I want to analyze a clustering algorithm that clusters data stream. Since the stream can be unbounded, I cannot write O(N^2), or explicitly denote the size of the stream. How can I use the arrival rate of the data for the computation complexity? Do you have any other idea for correct analysis of stream computation (for clustering problems)?

Thank's

# Answer
One standard way to measure the running time of streaming algorithms is to count the amount of time taken *per item* that the algorithm processes. For instance, one algorithm might take $O(1)$ time per item.

Also it is common to analyze the memory usage (space complexity) of these algorithms, as in many practical situations memory can be a limiting factor. That is straightforward to measure. Usually the space complexity is measured not as a function of the number of elements seen, but rather as a function of something else -- e.g., the accuracy of the answer, or the number of distinct items in the input stream, or something else that is appropriate to the application and that makes it possible to do analysis.

I suggest you read about streaming algorithms. There's lots of work on those topics and those fields certainly measure the running time of their algorithms. See, e.g., https://en.wikipedia.org/wiki/Streaming\_algorithm and textbooks on the subject.
> 2 votes

---
Tags: algorithm-analysis, time-complexity
---


# Question
Title: Is the consensus number of SetAgree(3, 2) 2 or 1 (proof needed)?
SetAgree(n, k)

---

* An object that allows n threads to propose() n values.
* It guarantees Each thread will decide() on a (single) value.
* The cardinal number of the set of all values decided on is lower or equal to k.
* All values decided on were proposed.

It is obviously trivial if n \<= k so the first interesting case is SetAgree(3, 2).

Consensus(n) is the same as SetAgree(n, 1). A consensus number of an object is the highest number of threads that can arrive at a consensus using that object and shared memory access.

Alright, I'll start by saying I think the consensus number of SetAgree(3, 2) is not two.

My line of proof is that I assume there is a protocol that solves a binary consensus(2) using the strongest SetAgree(infinity, 2).

At some point in the algorithm (which has to be deterministic) we arrive at a node where if thread A acts, the consensus will be its proposal (without loss of generality 1) and if thread B acts, it will be its proposal (without loss of generality 0).

Lets say, both of them wish to access the SetAgree object at this node, they could get the values they proposed no matter the order of access they use so the state of the system will be the same (no matter the order). If only one of them accesses the object and the other one reads or writes to a memory register then the order is meaningless for sure simply because memory doesn't affect the SetAgree object and SetAgree doesn't affect any of the shared memory registers. So obviously regardless of the order, the state of the system will be the same after these two operations which means, it is not possible that one leads a consensus on (1) and the other on (0).

The line of proof that suggests consensus number 2 states (the known fact) that setAgree(3, 2) cannot be build with shared memory alone. This is well known but it doesn't suggest setAgree(3, 2) has a stronger consensus number cause that line of proof only applies to data structures, cause it relies on universal construction.

Is there any stronger proof that it's consensus number 1 or 2?

# Answer
We can prove that 2-set-consensus among 3 processors (noted (3,2)) cannot be used (together with registers) to solve consensus among 2 processors (noted (2,1)) using the Borowsky-Gafni simulation (BG simulation for short).

The BG simulation allows 3 processors using registers only to simulate any algorithm in which 2 processors use registers and (3,2). Therefore, the BG simulation transforms an algorithm A solving consensus among 2 processors using (3,2) into an algorithm B solving consensus among 3 processors using registers only. Since the latter is impossible, there is no such algorithm A.

Note that by solving I mean solving wait-free.

This proof first appeared in Borowsky and Gafni, "Generalized FLP impossibility result for t-resilient asynchronous computations." Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. ACM, 1993. (In particular see the end of section 3.3).
> 2 votes

---
Tags: consensus, multi-tasking
---


# Question
Title: How come $REC$ languages are included in $NRE$
How come $REC$ languages are included in $NRE$.

The definition of a language in $REC$ is . $L \in REC$ if there is a turing machine $M$ that recognizes the language $L$ and that stops on any given input.

It makes sense that $REC$ is included in $RE$;

$L \in RE$ if there is a turing machine $M$ that recognizes the language $L$ but may stop on some inputs;

The inclusion still makes sense right now. But when we go to the $NRE$ i find it hard to understand;

$L \in NRE$ if there DOES NOT EXIST ANY turing machine $M$ that can recognize the language.

How can a language in $REC$ be in $NRE$ if $REC$ assumes that such a language would have a turing machine that stops on every intput yet a language that is $NRE$ must not have any turing machine that can recognize it?

Could the given definition of $NRE$ be wrong? An explanation would be welcomed!

# Answer
> 1 votes
I've never seen "NRE" defined to mean "not recursively enumerable", which is the short way of saying what you've defined. If you take it to mean "not recursively enumerable" then no recursive language is in NRE because every recursive language *is* recursively enumerable.

The only definition of "NRE" that I've seen is that people in the field of DNA and membrane computing seem to use it for the set of Turing-computable sets of natural numbers, i.e., the sets that can be written as $\\{|x|\mid x\in L\\}$ for some RE language $L$.

---
Tags: turing-machines
---


# Question
Title: Reverse cartesian product matching all given rows
I´m looking for an efficient algorithm that will find reverse cartesian products.

Mathematically, given $S \subseteq T^n$, I want to express $S$ as a union of sets $A\_{i,1} \times A\_{i,2} \times \dots \times A\_{i,n}$, for $i=1,2,\dots,k$; and I want to minimize the number $k$. Is there an efficient algorithm to solve this problem?

This may be easier to explain by example. Calculating the cartesian product (cross product) is trivial, e.g. `{1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5}` results in:

```
    1 1 1
    1 1 2
    1 1 3
    .
    .
    .
    5 5 3
    5 5 4
    5 5 5

```

All 125 (5 x 5 x 5) rows are created.

Now let's say you remove some rows from this result, i.e. you are left with these 14 rows as a starting point:

```
    1 2 3
    1 2 4
    1 2 5
    5 2 3
    5 2 4
    2 2 5
    3 2 5
    1 3 3
    1 3 4
    1 3 5
    5 3 3
    5 3 4
    2 3 5
    3 3 5

```

Now, how do I find a cartesian product that if calculated can generate only those 14 rows back? (order of rows is irrelevant). It can no longer be represented by only one cartesian product `{1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5}` since e.g. `5 5 5` is not in the list.

One way to now represent the rows as cartesian products is this answer:

```
    {1} x {2,3} x {3,4,5}
    union
    {5} x {2,3} x {3,4}
    union
    {2,3} x {2,3} x {5}

```

But the above merge of rows is not optimal although it is a valid solution, we can do better and write it in only two cartesian products:

```
    {1,5} x {2,3} x {3,4}
    union
    {1,2,3} x {2,3} x {5}

```

This result is better since 2 \< 3 and I want to find the smallest possible number of cartesian products that still represents all the rows. There is no way to reduce (merge) this any further given the 14 rows so this is the best answer in this case.

Now if the starting point would have been all the 125 rows (as in example above) the optimal answer would have been one: `{1,2,3,4,5} x {1,2,3,4,5} x {1,2,3,4,5}`.

Some known facts about the input:

* All rows are unique, no duplicates exists in the list.
* Row are of same length, fixed with either 3,4,5,6,7,8 in length.
* Numbers in a row range from 1 to 20
* There could be millions of rows as a starting point but typically around 100k, hence speed is of importance rather than low memory consumption.

One possible idea is that rows can be merged if `n-1` numbers (or group of numbers in the slot) are equal, e.g.,

```
    1 2 4
    1 2 5
    1 2 6
    1 3 4
    1 3 5
    1 3 6

```

can merge into

```
    1 2 456
    and
    1 3 456

```

which further can be merged to:

```
    1 23 456

```

and written as:

```
    {1} x {2,3} x {4,5,6}

```

My question is similar to https://stackoverflow.com/q/20890802/781723, but that one is limited to triples ($n=3$); I am interested in generalizing, where rows can be longer than 3. I also found https://stackoverflow.com/q/46084505/781723, but that has no answer.

# Answer
Unfortunately the problem is NP-hard when the number of columns ($n$) is unlimited. In particular, consider the case with $n$ columns and where every number in every row is either 0 or 1. Then your problem is equivalent to: given a truth table for a boolean function, find a minimal DNF formula (with the minimum number of clauses) for that function. This is NP-hard.

I know you said you'll have at most 8 columns, so this theoretical result doesn't necessarily imply there is no hope for your specific situation, but it does suggest that you shouldn't expect an efficient algorithm that will generalize to a large number of columns.

One approach you could use that might work well enough in your situation is to use a SAT solver. Encode each of the sets $A\_{i,j}$ with a one-hot encoding; i.e., you have variables $x\_{i,j,t}$, which is true if $t \in A\_{i,j}$ or false otherwise. Then it is easy to write down a bunch of constraints (clauses) that enforce that these $A\_{i,j}$ form a solution to your problem. For instance, for each row $r$ that *isn't* in the input (each $r \notin S$), you get a constraint that $r\_1 \notin A\_{i,1} \lor r\_2 \notin A\_{i,2} \lor \dots$ for each $i$, i.e., $(\neg x\_{i,1,r\_1}\lor \neg x\_{i,2,r\_2} \lor \dots)$. And so on. In this way, for any $k$, you can set up a SAT instance that will be satisfiable iff it is possible to express your input using $k$ reverse cartesian products. Then you can use binary search on $k$ to find the minimal $k$ such that this is possible.

Because SAT is NP-hard, this won't scale to very large inputs, but it's possible it might work well enough on the problem sizes you mention. The only way to know for sure is to try it and see.
> 1 votes

---
Tags: algorithms, combinatorics, sets, set-cover
---


title: Binary code and Hamming distance

text:
# Question
Title: Binary code and Hamming distance
I'm learning about CRC and Hamming distance and I have three questions. Lets say we have binary code described by ($+$ refers to sum modulo $2$):

\begin{alignat\*}{1} a\_1 &+ a\_2 &+ a\_3 &+ a\_4 &+ a\_5 &= 0\\ a\_6 &+ a\_7 &+ a\_8 &+ a\_9 &+ a\_{10} &= 0\\ a\_1 &+ a\_6 &+ a\_{11} &&&= 0\\ a\_2 &+ a\_7 &+ a\_{12} &&&= 0\\ a\_3 &+ a\_8 &+ a\_{13} &&&= 0\\ a\_4 &+ a\_9 &+ a\_{14} &&&= 0\\ a\_5 &+ a\_{10} &+ a\_{15} &&&= 0 \end{alignat\*} We received: $11011\ 01010\ 10111$

So if I would like to check minimal Hamming distance, then I should compare each codeword with others, right?

$\begin{pmatrix} 1&1&1&1&1& & & & & & & & & & \\ & & & & &1&1&1&1&1& & & & & \\ 1& & & & &1& & & & &1& & & & \\ &1& & & & &1& & & & &1& & & \\ & &1& & & & &1& & & & &1& & \\ & & &1& & & & &1& & & & &1& \\ & & & &1& & & & &1& & & & &1\\ \end{pmatrix}$

I have done so, and minimal Hamming distance $ = 6$. Is there any faster method?

Second question: how many distortions causing undetectable errors? Is there any formula for that?
And last one, how to compute redundancy using above information. I'm using formula:
$ R = \dfrac{n-k}{n}$. In above example $n=15$, but I don't understand how to obtain $k$.

# Answer
> 1 votes
In a linear code, the minimum distance is the same as the minimum weight of a non-zero codeword. It's a nice exercise to prove this, and reduces the computation time quadratically.

Computing the minimum distance of a code given the generator matrix (or the parity check matrix) is NP-hard, that is, given a generator matrix (or a parity check matrix) and an integer $w$, it is NP-complete to determine whether the minimum distance of the code generated by the matrix is at most $w$. The task could become easier if the code has some structure, but for arbitrary codes it is quite difficult.

---
Tags: coding-theory, hamming-code, binary
---


title: Question regarding $O(n^2)$ efficiency

text:
# Question
Title: Question regarding $O(n^2)$ efficiency
I'm going through a video of EDX course which talks about Big O notation. At the end of the video they have some questions but the $O(n^2)$ answer is confusing me. It feels like a mistake, but I just want to make sure.

The question is :

> Imagine that we have a data set of 10 items. We run an algorithm on that data set, and it performs 10 operations.
> Now imagine that we doubled the size of the data set to 20 items. Approximately how many operations might now be required if the algorithm is of...
>
> * Linear order? 20
> * Constant Order? 10
> * Quadratic Order? 40

I don't understand why the answer if 40 if it's quadratic.

At first I thought it would be 400, because n2 is 400. But the drop-down answer menu doesn't have 400. The highest it has is 100.

So I thought it might be 100, because if 10 items take 100 operations, then increasing by 10, would increase by 100. However 100 seems to be wrong as well.

So why is the answer 40?

The course in question is here:

https://www.edx.org/course/introduction-computing-using-python-gtx-cs1301x Chapter 5.2

# Answer
Say the time spent is some constant factor $c$ times $n^2$. Then we have:

$$c \cdot 10^2 = 10$$ $$c = 0.1$$

Thus then $c\cdot 20^2 = 40$.
> 1 votes

# Answer
It's easiest to remember how different asymptotic growths affect the outcome when n grows.

O (1) means: Growing n doesn't make a difference.

O (n) means: If n gets twice as large, it takes twice as long. If n gets ten times as large, it takes ten times as long.

$O (n^2)$ means: If n gets twice is large, it takes four times as long. If n gets ten times as large, it takes hundred times as long.

Of course if we are looking at asymptotics, all these things only work if n is large enough.

Still, with growth of $O (n^2)$ the numbers should be four times as large when n gets twice as large, so going from n=10 to n=20, the number of operations should go from 10 to four times as large, that is to 40.

Raphael's comment is of course right. Well, to some degree. Both $O(n)$ and $\Theta(n)$ are only valid for large numbers. So given the numbers for n=10, the outcome for n=20 is more or less guessing. We have $O(n^2) ≤ c\dot n^2$ and $c\dot n^2 ≤ \Theta(n^2) ≤ C\dot n^2$ for large enough n. n=10 or n=20 might not be "large enough" and we can't say anything about the outcome for n=20. And even if n=10 is large enough, there is still a wide range of values possible. We might have $0.01n^2 ≤ f(n) ≤ 100n^2$, and f(10) = 10,000, f(20) = 4 would be possible.
> 1 votes

---
Tags: asymptotics, landau-notation
---


title: Sorting by tuples

text:
# Question
Title: Sorting by tuples
This is more of a practical question for me, but I have a few team members $n$ who I'd like to sort by two characteristics (just call them $a$ and $b$ for now). These characteristics are just a rating (given from 1-10). Among these $n$ team members, I am trying to find those who fit a definition of being *good* i.e. given a team member $i$, there is no team member $i'$ who has both a higher $a$ rating *and* a higher $b$ rating. There can by many people who would fit this definition of *good*.

Not sure if this qualifies as a sorting problem or not, but basically I think I have an intuition for it: I was thinking about first sorting by the $a$ values. And then somehow using that information, I was thinking about sorting by the $b$ values but using the $a$ values somehow conditionally to determine swaps in positions. Does anyone have a good idea of how to boil this down to a problem that's a bit easier to think about/more common?

# Answer
> 0 votes
The problem can be solved in $\mathcal{O}(n\log{}n)$. I don't know if there are faster solutions.

Assume all $a$ ratings to be distinct, the general case can be solved in the same way with little modifications.

We say that a member $j$ is $\textit{better }$than a member $i$ if $\\;(a\_i\<a\_j \wedge b\_i\<b\_j)$. Obviously a member is $\textit{good}$ if there aren't members $\textit{better}$ than him.

The idea is to first sort in ascending order by $a$ rating. The key observation is:

* Fixed a member $i$, there is a member $j \textit{ better}$ than him if and only if $\\;i\<j\\:\wedge\\:b\_i\<b\_j$

In other words if, for each member $i$, we know $\max\limits\_{i\<j}\\{b\_j\\}$ we can deduce if $i$ is $\textit{good}$ or not.

The idea in pseudocode

---

---

$N\gets{}|\mathcal{Members}|$

$Sort(\mathcal{Members})$

$MAX\gets{}\mathcal{Members}\[N\].b$

$\mathcal{Members}\[N\].is\\\_good\gets{}\texttt{true}$

$\textbf{for}\\;\\;i\gets{}N\\!-\\!1\\;\\;\textbf{to}\\;\\;1\\;\\;\textbf{do}$

$\qquad\textbf{if}\\;\\;\mathcal{Members}\[i\].b\geq{}MAX\\;\\;\textbf{then}$

$\qquad\qquad\mathcal{Members}\[i\].is\\\_good\gets{}\texttt{true}$

$\qquad\qquad{}MAX\gets{}\mathcal{Members}\[i\].b$

---

---

---
Tags: algorithms, sorting
---


# Question
Title: What if the travelling salesman travelled by plane?
It seems intuitive to solve a 2D dot-to-dot travelling salesman problem by eye using a greedy strategy. However we can only solve the TSP by eye if the graph is topographically accurate e.g. if A to B is 10 and A to C is 10 then B to C can't be 1000.

Is the greedy strategy still sub-optimal when we obey 2D scaling, ie travelling by plane? Below I managed to create a topographically accurate example where the greedy strategy is indeed sub optimal:

Starting at S:

* Greedy: `S B C A S` =\> 2.83 + 4 + 5 + 2.2 =\> 14.03
* Optimal: `S A B C S` =\> 2.2 + 3 + 4 + 3.16 =\> 12.36

Is there something special about the example above that will be common to all suboptimal greedy routes? Can geometry be used to minimize error?

# Answer
I suggest you read more about the Traveling Salesman Problem. All of your questions are answered in other standard references (such as the Wikipedia link I gave). No, the greedy algorithm is not optimal. You may be interested in the Euclidean TSP, which remains NP-hard. The greedy algorithm is not optimal for that case, either. No efficient algorithm is known that can always find the optimal solution, though there are algorithms that may be useful in practice.
> 6 votes

---
Tags: algorithms, graphs, computational-geometry, traveling-salesman
---


# Question
Title: Relation with the perfect partition problem and the single machine task schedule problem
Perfect partition problem (PPP): given $x\_1,...,x\_n\in \mathbb{N}$ we want to know if there's a set $S\subset \\{1,2,...,n\\}$ such that $$\sum\_{i\in S}x\_i=\sum\_{j\notin S}x\_j.$$

Single machine task schedule problem (SMP): a machine can perform only one task $T\_i$ with duration $d\_i$ at a time and we want to know if all tasks can be done, given that $T\_i$ can't start before the time $a\_i$ or be finished after the time $b\_i$ with $i\in \\{1,2,3,...,n\\}$.

I want to know how to reduce PPP to SMP.

EDIT: I tried modelling SMP using the constraints and the existence of a bijection $f:\\{1,2,3,...,n\\} \rightarrow \\{1,2,3,...,n\\}$ such that $$a\_{f(i)}\leq \sum\_{j=1}^i d\_{f(j)}\leq b\_{f(i)}$$ for all $i\in \\{1,2,3,...,n\\}$. And I tried to make $x\_i=d\_i$ and get the conditions of the SMP to make the sum be equal to que complementary $\left (\frac{\sum\_{i=1}^{n} x\_i}{2}\right)$ at some point, but I got stuck as I can't find how to relate $f$ to $S$ from the PPP, that's not really working.

# Answer
Just let $d\_i=x\_i$, $a\_1=\frac{\sum\_{i=1}^n x\_i}{2}-d\_1$ and $b\_1=\frac{\sum\_{i=1}^n x\_i}{2}$, and $a\_i=0$ and $b\_i=\sum\_{i=1}x\_i$ for other $i$'s. Then easy to see there is a solution for the original PPP instance iff there is a solution for this SMP instance.
> 1 votes

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: Efficiently labelling training data in machine learning
Obviously it always depends on the specific case. However, my question is how to label data efficiently without writing a source code from scratch which solves the final problem itself?

For example, suppose that I want to use the $k$-Nearest Neighbours algorithm to classify tables from images according to their shape (square tables, rectangular tables, round tables).

For this purpose, I need to find let's say at least 500 images of various tables and then label them.

However, if I do not want to label them manually then I must write extensively a program to do this which essentially is the program I would like to have overall.

In other words, there is no point in writing from scratch an algorithm for accurately labeling data if I want to use machine learning finally because then this algorithm would solve my overall problem without machine learning. However, it is obvious that this algorithm would be very difficult to write to cover all the possible cases e.g. of tables from various images etc.

So how can I label data quickly without writing so many source code lines?

# Answer
> 4 votes
You can't. You can't squeeze blood out of a stone. There's no such thing as a free lunch. You can't get something from nothing. If you want labelled images, you will need to label them yourself, or find some existing data set that comes with labels. There are no shortcuts.

Yes, this is tedious and labor-intensive. This is one of the less-well-known and less-glamorous aspects of working on machine learning: in practical projects, we often spend the majority of our time (or more!) just assembling data sets, and only a small fraction on the actual learning algorithms themselves.

I know you could do various shortcuts, like trying to write a quick program to label them. But if that program makes mistakes, you'll just be training your machine learning algorithm to make the same mistakes -- so that's not actually helpful.

If you want to reduce the amount of labelling effort, there *are* ways to reduce the effort -- but still they will require a significant amount of manual labelling. Nothing comes for free. For instance, you can use active learning algorithms to identify which instances to label. A simple example of that is to manually label a few hundred images as your initial training set, train a classifier, apply it to all remaining images, pick out the 20 images that the classifier is least confident on, manually label those 20 images, add them to the training set, and repeat. (This is an application of uncertainty sampling.) There are other, more sophisticated methods out there as well.

Another plausible approach is to somehow cluster the images, then manually label a few images from each cluster. This has issues, though, as you'll need some reasonable way to cluster the images, and that might be a non-trivial task. (One possible approach for clustering is to take some existing, pre-trained ImageNet classifier -- e.g., VGG, Inception, ResNet, etc. -- throw away the last layer or last two layers, and use the output before those layers as the input to some clustering algorithm like k-means. Doing k-means clustering directly on the raw image probably won't work well, but if you do it on the vector of activation values at some deep layer near the end of a good pre-trained classifier, then you might get better results.)

Finally, we often use data augmentation to make the classifier more robust. For instance, for each image in the training set, we might generate 10 more copies, where each copy is rotated or translated or cropped by a random amount, and add that to the training set. This tends to help make the classifier more robust to changes in orientation or pose -- but it doesn't give you something for nothing. You still need a large training set that contains many different kinds of tables.

# Answer
> 0 votes
There exist non machine-learning approaches to feature detection in images, but those are generally complicated and not very successful in comparison with machine learning methods.

Labeling data somehow without involving the algorithm to be trained is a hard requirement when doing *supervised* learning. As most decent automated labeling methods would use machine learning, this seems like a bootstrapping issue.

There also exists *unsupervised* learning methods, e.g. clustering approaches such as $k$-means. But most of these are unsuitable for very complex classification tasks such as image recognition. (Sure, Google did a reasonable large unsupervised image classification a few years a go, but they required computational resources that aren't available to most of us)

In the end, image recognition and other hard machine learning tasks are approached with ML methods precisely because humans are a lot better at them than computers, so we hope to 'learn' the computer to make decisions similar to the human. This means that, unfortunately, human effort is a required to train these algorithms.

# Answer
> 0 votes
What you are looking for is very similar to a clustering task. So you should look into clustering algorithms for images (in the field of unsupervised learning), for example, the JULE algorithm (here and here) from 2016 does that sort of thing.

# Answer
> 0 votes
It is standard practice to label stuff by a human in the beginning. You could assist the human, but there is always a human component in creating a new dataset.

Interesting things to mention:

* AWS mechanical Turk
* Online learning
* Active learning

---
Tags: machine-learning, artificial-intelligence, computer-vision
---


title: Transitive dependency in 3NF

text:
# Question
Title: Transitive dependency in 3NF
Came across this question : State whether True or False

> A prime attribute can be transitively dependent on a key in 3NF

Answer: True
How could this be true? Because as far as I know, A relation initially in 1NF is said to be in 3NF when partial and transitive dependencies have been eliminated. Correct me if I'm wrong.
Also, would it be correct to say that given a relation which doesn't have any non prime attribute along with no partial dependencies, then the relation is in BCNF ?
(I don't have any knowledge beyond BCNF).

# Answer
> 0 votes
An accepted definition of Third Normal Form is that any non-trivial dependency with a single attribute on the right part must have a superkey as left part, **or** the right part must be constituted by a prime attribute.

In other words, if you have a dependency with a prime attribute on the right part, that dependency *does not violates* the 3NF.

For your second question, a relation is in BCNF if any non-trivial dependency has a superkey as left part. If a relation does not have partial dependencies, and all the attributes are prime, this means that no dependency exists with attributes that are not a full key or that are not constituted by non-prime attributes. So, the answer is yes, that relation is in BCNF.

---
Tags: database-theory, databases, normal-forms
---


# Question
Title: Number of edges in a graph with N vertices and K components
What is the possible biggest and the smallest number of edges in a graph with N vertices and K components?

I think that the smallest is (N-1)*K. The biggest one is N*K. Is this correct? I think it also may depend on whether we have and even or an odd number of vertices?

# Answer
Think of the extreme case when all the components of the graph except one have just one vertex. This is the case which will have the most no. of edges. We can prove it by contradiction as follows:
Suppose there were two strongly connected components having $m$ and $n$ vertices where $m \< n$. Now if you remove a vertex from the one having $m$ vertices and add it to the other component, then effectively you have removed $m-1$ edges from the first graph and added $n $ edges to the second graph. So, there is a net *gain* in the number of edges.
So the maximum edges in this case will be $\dfrac{(n-k)(n-k+1)}{2}$.
As for the minimum case, since we have seen that distributing the edges with uniformity among the graphs leads to an overall minimization in their number, therefore first divide all the $n$ vertices into $k$ components to get the number of vertices in each component as $n/k$. We will still be left with $n\mod k = f'$ vertices. Let's call $\Biggl\lfloor{\dfrac{n}{k}}\Biggr\rfloor$ = $f$. Then, the $k$ components each already have $f$ vertices with them. Now , give away $1$ vertex each to first $f'$ components. This completes our *vertex distribution*.
So, total edges$ = (f + 1 - 1)\*f' + (f-1)\*(f - f')$ *(because we have minimum of* $x-1$ *edges for $x$ available vertices)*
where
the first term counts minimum edges for first $f'$ components which have 1 vertex extra and the second term is for the remaining components.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Detect whether one Turing machine invokes another
Given two Turing machines $M,M'$, is it possible to check whether $M$ invokes $M'$?

In other words, is the following problem computable/decidable?

Inputs: Turing machines $M,M'$
Question: Does $M$ ever invoke $M'$?

Perhaps we can look whether $M$ includes the code of $M'$ in it? In a C program we can check whether a function `f` invokes a function `g`, right? Can we do this for Turing machines too?

# Answer
The notion of "one machine invokes another" is ill-defined. To emphasize the point of @AbdousKamel, let us observe an even trickier example:

```
function g():
   do_something;

```

And now:

```
function f():
   k = 0
   while not "k encodes a proof of Riemann hypothesis":
     k = k + 1
   "simulate the Turing machine encoded by k"

```

In order to tell whether `f` "invokes" `g`, you have to:

1. Decide whether Riemann hypothesis is provable, and
2. Calculate whether the smallest `k` which encodes a proof of Riemann hypothesis also happens to encode a Turing machine whose behavior is equivalent to the behavior of `g`.

Question: does `f` invoke `g`?
> 2 votes

# Answer
Following the comments of the post, i will try this example, and hope that it shows how hard it is to decide if a function `f` calls a function `g`.

Here is function `g` :

```
function g()
    do_something;

```

Here is function `f`, we will use a function called `foo` whose declaration and definition is not needed :

```
function f()
    foo();
    g();

```

Now, does `f` calls `g` ? If I look at the code of `f` I will say yes, because the call to `g` is trivially apparent. But how do I know that the call to `foo` will return ? Maybe `foo` loops forever and never halts, in this case, `f` never calls `g` because it never returns from `foo`. So deciding in a program if a function calls another needs you to decide if some pieces of programs halt, which is in fact as hard as an undecidable problem can be.
> 0 votes

---
Tags: turing-machines, computability
---


title: Why do we need assembly language?

text:
# Question
Title: Why do we need assembly language?
We mostly write programme in high level language. So while studying I came across assembly language. So an assembler converts assembly language to machine language and a compiler does the same with high level language. I found assembly language has instructions like move r1 r3 , move a 5 etc. And it is rather hard to study. So why was assembly language created?or was it the one that came first even before high level language? Why am I studying about assemblers in my computer engineering class?

# Answer
"So why was assembly language created?"

Assembly language was created as an exact shorthand for machine level coding, so that you wouldn't have to count 0s and 1s all day. It works the same as machine level code: with instructions and operands.

"Which one came first?"

Wikipedia has a good article about the History of Programming Languages

"Why am I studying about assemblers in my computer engineering class?"

> Though it's true, you probably won't find yourself writing your next customer's app in assembly, there is still much to gain from learning assembly.
>
> Today, assembly language is used primarily for direct hardware manipulation, access to specialized processor instructions, or to address critical performance issues. Typical uses are device drivers, low-level embedded systems, and real-time systems.
>
> Assembly language is as close to the processor as you can get as a programmer so a well designed algorithm is blazing -- assembly is great for speed optimization. It's all about performance and efficiency. Assembly language gives you complete control over the system's resources. Much like an assembly line, you write code to push single values into registers, deal with memory addresses directly to retrieve values or pointers. (source: codeproject.com)
> 36 votes

# Answer
> Why do we need assembly language?

Well, there's actually only one language we will ever *need*, which is called "machine language" or "machine code". It looks like this:

```
0010000100100011

```

**This is the only language your computer can speak directly.** It is the language a CPU speaks (and technically, different types of CPUs speak different versions). It also sucks to look at and try to understand.

Fortunately, each section of binary corresponds to a particular meaning. It is divided into a number of sections:

```
0010|0001|0010|0011

operation type  source register  other source  destination register
0010            0001             0010          0011

```

These values correspond to:

```
operation type 0010 = addition
source register 0001 = register 1
other source 0010 = register 2
destination register 0011 = register 3

```

So this operation would add the numbers in registers 1 and 2 and put that value in register 3. If you literally put these values into a CPU and tell it "go", it will add two numbers for you. The operation "subtract" could be a 0011 or something, instead of 0010 here. Whatever value will make the CPU do a subtraction.

So a program could look like this (don't try to understand it, since I made up this particular version of machine code to explain things):

```
instruction 1: 0010000100100011
instruction 2: 0011000110100100
instruction 3: 0101001100010111
instruction 4: 0010001001100000

```

Does this suck to read? Definitely. **But we need it for the CPU**. Well, if every machine code corresponds to a particular action, lets just make a simple "English" shorthand, and then once we understand what the program is doing, convert it into real binary machine code and give it to the CPU to run.

So our original instruction from above could look like:

```
(meaning)      operation type  source register  other source  destination register
(machine code) 0010            0001             0010          0011
("English")    add             r1               r2            r3

```

Note that this English version has an *exact mapping to machine code*. So when we write a line of this "English", we're really just writting friendlier and more understandable machine code.

Well, *this is assembly language.* That's why it exists, and why it was originally created.

To understand why we need it now, read the above answers, but the key this to understand is this: High level languages do not have a single representation is machine code. E.g. in C, or Python, or whatever:

```
z = x + y

```

This sounds just like our addition from above, assuming `x` is in register 1, `y` is in register 2, and `z` should end up in register 3. But what about this line?

```
z = x * 2 + (y / 6) * p + q - r

```

Try representing *that* line in 16 bits of binary and telling a CPU "go". You can't. Machine code has no single operation instruction to perform an addition, subtraction, and whatever else with 4 or 5 variables at once. So it has to be converted to a *sequence* of machine code first. This is what you do when you "compile" or "interpret" a high level language.

Well, we have programs to do that, so why do we need assembly now? Well say your program is running more slowly than you expect, and you want to know why. Looking at the machine language "output" of this line, it might look like:

```
1010010010001001
0010001000010000
0110010000100100
0010001011000010
0010100001000001
0100010100000001
0010010101000100
0010101010100000
0000100111000010

```

Just to get that one line of Python done. So you really want to debug that?!?!?! *NO*. Rather, you ask your compiler to kindly give you the output in the form you can actually understand easily, which is the assembly language version corresponding *exactly* to that machine code. Then you can figure out if your compiler is doing something dumb and try to fix it.

(Extra note on @Raphael's advice: You could actually construct CPU's that work with things other than binary codes, like ternary (base 3) or decimal codes, or even ASCII. For practical purposes though, we really have stuck to binary.)
> 35 votes

# Answer
> So why was assembly language created? or was it the one that came first even before high level language?

Yes, assembly was one of the first programming languages which used text as input, as opposed to soldering wires, using plug boards, and/or flipping switches. Each assembly language was created for just one processor or family of processors as the instructions mapped directly to opcodes run by the processor.

> Why am I studying about assemblers in my computer engineering class?

If you need to program device drivers or write compilers then understanding how a processor works is invaluable, if not required. The best way to understand this is to write some code in assembly.

If you take a look at how a compiler writes code it is common to see options for calling conventions which without knowing assembly probably can't be understood.

If you have to resolve a bug and the only input you have is a core dump, then you definitely need to know assembly to understand the output which is assembly code and if lucky augmented with higher level statements of a high level language.
> 16 votes

# Answer
Let me add one less practical aspect. This is (probably) not a historic reason but a reason for you, today.

Assembly (compared to high-level languages) is *naked*. It does not hide anything (that is done in software), and it is simple in the sense that it has a relatively small, fixed set of operations.

This can be helpful for exact algorithm analysis. Semantics and control flow are so simple that counting all operations (or the expected number) can be done by annotating the control flow graph with transition counts (probabilities). Knuth does this in his TAoCP books to great effect, demonstrating some of the most rigorous algorithm analyses there are.

Anecdote: my colleague has learned to read Java Bytecode for exactly this purpose.
> 14 votes

# Answer
There are answers here:

All these answers point to:

* Speed/Memory Optimization
* Understanding how the machine works
* So Noob Programmers become Experts
* If you know assembly, you know how to write compilers for your High Lvl language
* etc
> 4 votes

# Answer
**Assembly = machine code**
Some people keep harping on about how assembly language is different from the numeric codes that the CPU understands.
This (whilst true) completely misses the point.
As far as translation goes assembly language and the numeric (binary, hex whatever) are one and the same thing.

**Grok it or drop it**
If you grok assembly you know how an actual computer works.
grokking assembly involves:

If you grok assembly you well have a nearly complete picture of how the CPU connected to your keyboard works.
You need to use this knowledge like a brain surgeon uses his scalpel.

**Don't need no stinking abstractions**
Unless you grok assembly (and thus the CPU on the operating table) you will never be free of the clutches of the abstractions of the RAM machine (or god forbid the Turing machine *the horror*).

**L33t Hax0r 5k1llz**
Assembly also helps to you understand how the 133thax0r manages to defeat the protection schemes. (Q: why does ASLR not work? because `mov rax,fs:[28h]` breaks it).

**The 0.1%**
It is not the knowledge of assembly that matters, but knowledge of the machine your working on that matters.
If you want to know the machine, you must understand it and that means speaking the language of the machine.

If you don't then you're stuck with the abstraction.
That's science and that's good, but that's never the complete picture.

It's like learning to speak Xhosa
Unless you aim for guru level, best stick with what you know, those clicks will complicate your life.

Because it's fun.
> 1 votes

# Answer
To date myself, I first learned RPG II using an IBM System 32, and later learned APL on a 370. I was all about size and speed. My mantra was smaller and faster. Assembly is the most compact and fastest language out there. I would make test programs in both C and Assembly. Where C programs would require 100's of Kb, an equivalent Assembly program would often be less that 5 Kb. When studying the output of the C compiler I would find code that would check and recheck parameters make conditional checks for possible errors that were quite often rare and exotic and quite unnecessary, all of which took time, but the biggest memory bloat was passing absolutely everything to and from the stack.

In today's programming environment writing code provides an extra level of security and protection. Being able to read info directly from a piece of hardware that is not accessible to high level languages, allows you to encrypt with Assembly in a way that a program can only be used on that particular machine. For example encrypting a user key using the MAC address of the network interface, and then parking that key on a specific unregistered sector of the hard drive then marking the sector as bad so that other files can't overwrite it. Of course you lose the sector, but what is that? 2048 or 4096 bytes out of billions or trillions?
> -1 votes

---
Tags: programming-languages, education, history
---


# Question
Title: Finding the Voronoi cell a point belongs to
Given a set of Voronoi edges. Each edge consists of (indices of, pointers to) 4 points: $\mathrm{left}$ and $\mathrm{right}$ are sites, $\mathrm{begin}$ and $\mathrm{end}$ are vertices (one of them or even both (in case if all the sites lies on a straight line) may point to infinity). $\angle \Big(\overrightarrow{(\mathrm{left},\mathrm{right})},\overrightarrow{(\mathrm{begin},\mathrm{end})}\Big) \equiv +{\pi \over 2}$. Sites and vertices lies in two dedicated arrays. Sites are lexicographically ordered (i.e. by $x$ then also by $y$), vertices also can be easily sorted in the same manner.

What is the best way to locate point in Voronoi diagram defined as above (here, find closest site)? What are the best *online* and best *offline* ways (if differs)? I sure both of them can be constructed in linear-logarithmic time, but maybe one of them can have much lesser constant factor?

# Answer
I will consider this problem on a Voronoi diagram with $n$ sites and $m$ query points. Generally, trapezoidal decompositions work nicely for point-location. However, as we here have a subdivision of convex cells, we instead can construct a triangulation of the Voronoi diagram in $O(n)$ that can answer point location queries in $O(\log n)$, which is in fact optimal$^\*$. (The complexity for the triangulation is in terms of the edges, but this doesn't matter as the number of edges of a Voronoi diagram is it most $3n-6$).

So, if we are given a Voronoi diagram on $n$ sites and $m$ query points at once, this gives an $O(n+m\log n)$ time algorithm. It makes no difference when we get the query points, so this algorithm is also online in that sense.

It isn't very clear what would be provided if the sites would be 'online', as some edges will be removed and others added when adding sites. If the number of edges added and removed are given, there is a constant number of them and the triangulation can be updated in constant time, so the total running time would remain $O(n+m\log n)$.

Another approach that may not be as good in theory but might work better in practice is to use quadtrees: you can store the set of closest sites for every square in the tree and partition the squares until the size of all those sets is small enough. Then simply locate the square containing the query point and compare all sites in the set for that square to find the nearest site.

---

\*: See the paper: Kirkpatrick, David. "Optimal search in planar subdivisions." SIAM Journal on Computing 12.1 (1983): 28-35.
> 1 votes

---
Tags: algorithms, algorithm-analysis, computational-geometry, voronoi-diagrams
---