title: Incorporating event handlers

text:
# Question
Title: Incorporating event handlers
In IDE's we can drag a small continuous collection of pixels in a particular configuration to a place on the screen .This collection of pixels are called as controls .

Corresponding to every control, there are various kinds of event handlers,like for a button , some subroutines for events like "double click" , "single click" are available ,for a grid there might be "right click ", "gaining mouse focus" event handlers might be available .

The collection of available event responding subroutines,from what I could conclude , further depend on the framework or library we are using.

Now let us imagine that we have certain hardware with us and only one programming language available and we are accommodating some aliens in this world for whom , nose, is a very important sense organ for communication .Avoiding the concerns of scientific feasibility of such creatures let us say that to provide input to anything they exhale and inhale air into some device . And to meet their requirements we might need programs that can manipulate the fragrance that they are smelling , like ,let's say we need a computer program for a messaging app that is to be designed for them to be able to emit the smell of rose at the receiver's end when the sender scratches the screen and many more .

Now given such a situation , if I want to design a GUI for them or may be (OUI,olfactory user Interface ) how can I make my systems compatible with their method of input and output .I mean how can I design event handlers for them like , "One nostril snort event ", "double nostril snort event ","deep inhale event " and many more that we can imagine .

What are the changes that I would require :

1. Do I need to add some new things in my programming language ?
2. Do I need to change my hardware (counting out their input device ,namely ,snake :P) ?
3. Do I need to change my OS ?

P.S : I asked this question ,because,to put in the most general manner and basically I wanted to deconstruct and see from the bottom , how can computer programs(including the OS ,which in essence is also a computer program ) control hardware and as such I might get a better idea on how to direct myself in learning about all this.

# Answer
Those kinds of aliens presumably wouldn't use a GUI. A GUI is a *graphical* user interface, i.e., directed at the *visual* senses. Your aliens have no sight, and wouldn't use such a user interface. They'd use something else.

The user interface is programmed as part of the software application. So, you wouldn't necessarily need to change the programming language or the hardware or the OS -- just the application (and its libraries). (Of course, you would need additional peripherals to emit smells etc., but you say you're counting that out -- apart from that, there would be no changes to hardware needed.)
> 1 votes

---
Tags: computer-architecture, programming-languages, operating-systems
---


# Question
Title: Why does the app I downloaded say that 1 in binary is 00110001?
I've just started learning binary so mind me if I'm bad at this. I think that the binary for 1 ought to be just "1" but, when I key it in to an app I downloaded, the answer has extra 0s and 11s in it. Why?

# Answer
> 4 votes
The app you have converts strings in the ASCII character set to their binary representation. This representation assigns eight bits for each character in the string. For example, the word "cat" is composed of characters number 99, 97 and 116, which is 01100011 01100001 01110100.

What your app is doing is converting the string "1" into its binary ASCII representation. "1" is character number 49 in ASCII, which is 00110001, and it's pure coincidence that this ends in a 1.

You're completely correct that, as a number, 1 in decimal is 1 in binary.

# Answer
> 3 votes
What you see is the ASCII code for the digit 1, in binary.

---
Tags: arithmetic
---


# Question
Title: Lemma 2 in Knuth's "Notes on Open Addressing"
I'm trying to read Knuth's *Notes on Open Addressing*, and I don't quite follow the proof of Lemma 2.

**The set-up** We're thinking about hashing $k - 1$ keys into a size $N$ array, with collision resolution via linear probing. In particular, we're considering sequences of hash values $a\_1, ..., a\_{k-1}$ ($1 \leq a\_i \leq N$). All we keep track of is variables $X\_1, ..., X\_N$, where $X\_i = 0$ if the $i$th entry of the array is open, and $X\_i = 1$ if the $i$th entry of the array is storing a key.

**Example** Suppose that $N = 5$, $a\_1, a\_2, a\_3 = 1, 4, 1$. Then $X\_1 = 1$, $X\_2 = 1$, $X\_3 = 0$, $X\_4 = 1$, $X\_5 = 0$.

**Definition** $\begin{bmatrix} n \\ k \end{bmatrix}$ is the number of sequences $a\_1, ..., a\_k$ ($1 \leq a\_i \leq n$) such that no *overflow step* occurs. The overflow step is when a key hashes to an index near the end of the array, but because $X\_{\text{hash}} = X\_{\text{hash} + 1} = ... = X\_N = 1$ already, we have to try to insert the key at the beginning of the array $X\_1$.

In Lemma 1 Knuth proves that, for $0 \leq k \leq n + 1$, $\begin{bmatrix} n \\ k \end{bmatrix} = (n + 1)^k - k (n + 1)^{k - 1}$.

**Definition** $Q(N, k, t)$ is the number of sequences $a\_1, .., a\_{k - 1}$ ($1 \leq a\_i \leq N$ satisfying (\*): $X\_{N - t - 1} = 0$, $X\_{N - t} = ... = X\_{N - 1} = 1$, $X\_N = 0$.

**Proof of lemma 2** Lemma 2 states that $$Q(N, k, t) = \begin{bmatrix} N - t - 2 \\ k - t - 1 \end{bmatrix} \begin{pmatrix} k - 1 \\ t \end{pmatrix}.$$

If $a\_1, ..., a\_{k-1}$ satisfies (\*), then there is a subsequence, of length $t$, which falls into the range $X\_{N - t}, ..., X\_{N - 1}$. The complementary subsequence, of length $k - 1 - t$, falls into the range $X\_1, ..., X\_{N - t - 2}$. Knuth counts the number of each such subsequence, and the number of combining these two subsequences together to produce $a\_1, ... a\_{k - 1}$.

**My question** He seems to argue that

$$Q(N, k, t) = \begin{bmatrix} t \\ t \end{bmatrix} \begin{bmatrix} N - t - 2 \\ k - t - 1 \end{bmatrix} \begin{pmatrix} k - 1 \\ t \end{pmatrix}.$$

But $\begin{bmatrix} t \\ t \end{bmatrix} = (t + 1)^t - t(t+1)^{t-1} = (t + 1)^{t - 1} \not = 1$, so I don't see how the conclusion holds.

# Answer
> 3 votes
I think that the notes have been reported incorrectly. Indeed CruiskeenLawn, you are right. I've found some very old notes here which report the correct result. Indeed, in your copy, they simply forgot to add $\left\[\begin{matrix} t\\ t\end{matrix}\right\]$ term. The Lemma you are looking for is on Page 2.

---
Tags: hashing
---


title: Meaning of double colon $::$

text:
# Question
Title: Meaning of double colon $::$
I've came across this expression regarding function composition in some notes by people from computer science, and I don't know what the notation "$::$" means.

\begin{equation} g \circ f : A \rightarrow C :: a \mapsto g(f(a)) \end{equation}

I get what this expression is trying to tell me, but I am pretty disturbed by the fact that I don't know what "$::$" means exactly and how to read it. Can anyone tell me what is "$::$"?

# Answer
It stands for "given by" or "defined by". The function $g \circ f$ is a function from $A$ to $C$ which maps $a$ to $g(f(a))$.
> 3 votes

---
Tags: notation
---


# Question
Title: is size of maximum matching less than that of maximum k-parity k-set packing?
My application problem can be modeled as maximum k-parity k-set packing problem, which is NP-hard. I know that maximum matching is polynomial time, hence I want to reduce k-parity k-set packing into bipartite maximum matching. I am wondering if there is any relation between their size.

**Maximum k-parity k-set packing problem**: We're given a universe $U$, which is a union of $k$ disjoint sets, $ U = V\_1 \cup \cdots \cup V\_k$, and a family $ \mathcal{S} $ of subsets of $ U$, each $S$ contains exactly one vertex from each set, i.e., $S \in V\_1 \times \cdots \times V\_k$. A packing is a subfamily ${\mathcal {C}} \subseteq {\mathcal {S}} $ of sets such that all sets in ${\mathcal{C}}$ are pairwise disjoint. The size of that packing is $|{\mathcal {C}}|$. We are looking for the maximum-size packing.

In order to take advantage of polynomial time maximum matching we reduce $U$ to $U' = V\_i \times V\_j, i , j = 1, \cdots, k$ and $\mathcal{S}'$ be a family of subsets of $U$ such that each $S'$ contains exactly one vertex from $V\_i$ and $V\_j$. Let $d\_{i,j}$ be the size of maximum matching and $d = \min\_{i,j} \\{d\_{i,j} \\}$.

For example in the figure below: $|C| = 2, d\_{2,3} = d\_{1,2} = d\_{1,3} = 2$ hence $d = \min(2,2,2) = 2$.

My question: is this inequality true $|{\mathcal {C}}| \le d \le k \times |{\mathcal {C}}|$ ?

I think $|{\mathcal {C}}| \le d$ is obvious, do we also have $ d \le k \times |{\mathcal {C}}|$?

# Answer
> 1 votes
Consider the case $k=3$, and the following set system: $$ (a\_1,b\_1,c),\ldots,(a\_n,b\_n,c) \\ (a'\_1,b',c'\_1),\ldots,(a'\_n,b',c'\_n) \\ (a'',b''\_1,c''\_1),\ldots,(a'',b''\_n,c''\_n) $$ Every packing contains at most 3 sets, but $d=n+2$.

---
Tags: complexity-theory, graphs, approximation
---


title: Speculating big O for a binary tree

text:
# Question
Title: Speculating big O for a binary tree
I have a binary tree with $n$ nodes. The tree is **not** necessarily balanced.

For each node of the tree, I count down the total number of the nodes for its left sub-tree as $n\_L$ and then I count down the total number of the nodes for its right sub-tree as $n\_R$. Then I calculate $\min(n\_L,n\_R)$ and then assign the minimum value as a *tag* to the node. I repeat this process to produce appropriate *tags* for all the nodes of the tree.

Now I wonder what is the big O for the *sum of all the tags*. I mean, I wonder if the *sum of tags* is $O(n\log n)$ or $O(n)$ or $O(n^2)$.

---

In the most **un**balanced case, the binary tree is just a long list like figure below. In this case, I think *sum of tags* would be 0, therefore the big O would be $O(0)$.

---

In the case of a perfect binary tree, the tag of the root node might be $2^0\frac{n}{2^{0+1}}$ and at the next level, i.e. root's left and right children, sum of tags might be $2^1\frac{n}{2^{1+1}}$ and for the $i$th level of the perfect binary tree, the sum of tags might be $2^i\frac{n}{2^{i+1}}$.

At the $i$th level, sum of tags might become $2^i\frac{n}{2^{i+1}}=\frac{n}{2}$ therefore looks like that some of tags at each level might be $\frac{n}{2}$ and because a perfect binary three has a total height of $\log\_2n$ hence the total sum of tags might be $\frac{n}{2}\log\_2n$ and this implies that for a perfect binary tree, the big O for sum of tags might be $O(n\log\_2n)$.

# Answer
> 2 votes
Let us denote by $\sigma(T)$ the sum of tags of a tree $T$. As you notice in your worked out examples, $\sigma(T)$ in general depends on the tree structure and not only on the number of nodes. What you are looking for is a *tight upper bound* on $\sigma(T)$ in terms of the number of nodes.

What is this tight upper bound? For each $n$, we want to know what is the maximal $\sigma$ for a tree having $n$ nodes. Denoting this by $\tau(n)$, this quantity satisfies $\sigma(T) \leq \tau(n)$ for all trees $T$ on $n$ nodes, and furthermore $\tau(n)$ cannot be replaced by any smaller value.

In fact, in practice we often don't care about finding the tight upper bound to this degree of accuracy. It is often enough to find a function $f(n)$ such that for some constant $C\>0$, $\sigma(T) \leq Cf(n)$ for all trees $T$ on $n$ nodes, and furthermore for some constant $c\>0$, $\sigma(T) \geq cf(n)$ for some tree $T$ on $n$ nodes.

You can prove by induction on $n$ that $\sigma(T) = O(n\log n)$ for all trees on $n$ nodes. Conversely, by taking a nearly complete binary tree $T\_n$ on $n$ nodes (that is, a binary tree all of whose leaves are at heights $h,h+1$ for some $h$), you can check that $\sigma(T) = \Omega(n\log n)$. Hence $O(n\log n)$ is a tight upper bound for the sum of tags of binary trees on $n$ nodes.

---
Tags: binary-trees
---


# Question
Title: Meaning of Steve Wozniak's epiphany on register addition/subtraction in 1975?
I just finished reading Walter Isaacson's *Innovators* and on page 350 there is a quote from Steve Wozniak recalling things he learned from the March 1975 Homebrew Computer Club meeting:

> A person at the meeting passed around the specification sheet for the new Intel microprocessor. "That night, I checked out the microprocessor data sheet and I saw it had an instruction for adding a location in memory to the A register," he recalled. "I thought, Wait a minute. Then it had another instruction you could use for subtracting memory from the A register. Whoa. Well, maybe this doesn't mean anything to you, but I knew exactly what these instructions meant, and it was the most exciting thing to discover ever."

Referencing the book, Intel started selling the 4004 microprocessor in 1971. By definition, I thought a microprocessor has to have registers, so did they just add functionality to the new 1975 microprocessor? Do you believe he was referencing the Intel 4040 microprocessor that came out in 1974? Also, does adding and subtracting memory allow arrays in RAM to be indexed in O(c) / constant time? Is that the significance or are there even more layers to this tale?

Thanks!

# Answer
This was 1975. Microprocessors were not common knowledge. Wozniak had some experience with mainframe computers, but most likely hadn't seen a 4004 processor ever.

Reading the instruction set of the 6502 processor showed him that this wasn't a useless toy but a real computer. The original price for a 6502 was 25 dollars plus 10 dollars for the documentation (which you were encouraged to copy), compared to a 6800 for $300 including added chips that were required.

Wozniak's epiphany was realizing that you could take a $25 microprocessor and turn it into a *real computer*. Apple Inc. is now valued a bit over 700 billion dollars, a direct consequence of Wozniak's realisation, so this was a kind of important event.

Not that it has much to do with computer science, except that eventually it put computers into everyone's hands.
> 2 votes

---
Tags: complexity-theory, computer-architecture
---


# Question
Title: Numerical problem on Access time in Cache memory
For a system with two levels of cache, define:

* $T\_{c\_1}$ is the first-level cache access time
* $T\_{c\_2}$ is the second-level cache access time
* $T\_m$ is the memory access time
* $H\_1$ is the first-level cache hit ratio
* $H\_2$ is the combined first/second level cache hit ratio

Provide an equation for the average access time $T\_a$ of a read operation.

# Answer
Here is the algorithm for a read operation:

1. Check if the cell is in the first-level cache.
2. If not, check if it is in the second-level cache.
3. If not, access it from main memory.

The data you are given allow you to calculate how much time each operation takes, and what is the probability that each of the steps is being taken. Using this, you can calculate the average time of a read operation.
> 1 votes

---
Tags: cpu-cache
---


# Question
Title: Little-O: $\forall c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in \mathbb{N}, n ≥ n_0 ⇒ g(n) \leq cf(n)$
So I'm assuming everyone's familiar with the definition of Big-O: \begin{align} ∃c \in \mathbb{R^+}, \exists n\_0 \in \mathbb{R^+}, \forall n \in N, n \geq n\_0 ⇒ g(n) ≤ cf(n) \end{align}

Here is a variation of this: $\text(Little-O)$: \begin{align} \text{Let $f, g : \mathbb{N} → \mathbb{R^{≥0}}$. We say that $g$ is little-oh of $f$, and write $g ∈ o(f)$, when:}\\ \forall c \in \mathbb{R^+}, \exists n\_0 \in \mathbb{R^+}, \forall n \in \mathbb{N}, n ≥ n\_0 ⇒ g(n) \leq cf(n) \end{align}

As you can see, this is a stronger property than Big-O, in the sense that if $g \in o(f)$, then $g \in \mathcal{O(f)}$. Basically, we switch to universal quantification leading to a more powerful claim. In general, if the statement $\forall c \in \mathbb{R^+}, P(c)$ is true, then $\exists c \in \mathbb{R^+}, P(c)$ is also true. While $g \in \mathcal{O(f)}$ says (colloquially) that “it is possible to scale up $f$ so that it eventually dominates $g$,” $g \in o(f)$ says that “no matter how you scale $f$ (up or down), it will always eventually dominate $g$.” Or, in terms of rates of growth, $g \in \mathcal{O(f)}$ means that $g$ grows at most as quickly as $f$, while $g \in o(f)$ means that $g$ grows strictly slower than $f$. I hope you get my gist.

Can someone please prove the following challenge question for me? It would be much appreciated and I've been at it for a long time now.

Prove the following statements about *Little-o*:

1. Prove that for all positive real numbers $a$ and $b$, if $a\<b$ then $n^a \in o(n^b)$.
2. Prove that for all functions $f, g : \mathbb{N} → \mathbb{R^+}$, if $g \in o(f)$ then $f \notin \mathcal{O(g)}$.

I see that in the $2^{nd}$ part they've restricted the range of $f$ and $g$ to exclude $0$ and that we are to use only the definitions of *Little-o* and *Big-o* in order to prove both statements.

# Answer
> 1 votes
For positive functions $f,g\colon \mathbb{N} \to \mathbb{R}\_+$, you can show that

* $f(n) = o(g(n))$ iff $\lim\_{n\to\infty} \frac{f(n)}{g(n)} = 0$.
* $f(n) = O(g(n))$ iff $\limsup\_{n\to\infty} \frac{f(n)}{g(n)} \< \infty$.

Using this, it is not hard to prove the two statements. Once you have done that, try translating your proofs to the definitions you were given.

---
Tags: algorithm-analysis, asymptotics, correctness-proof
---


# Question
Title: In Lbest PSO, how is the local best position in a neighbourhood defined?
I am implementing a couple of PSO (particle swarm optimization) algorithms, and I got stuck on a bit of detail which I could not clearly determine from the papers I have read. In lbest PSO, for each particle, the velocity update step takes the best particle's position in that particle's neighbourhood into account. What I am not 100% clear on is how that "best particle" is defined. To my understanding, it could be

(a) the best *current* position of each particle in the neighbourhood,

(b) the best *pbest* position (in memory) of each particle in the neighbourhood, or

(c) the best *lbest* psoition of each such particle, which could be initially determined from (a) or (b) as above, but over time allow information about other neighbourhoods' best positions to distribute across the swarm.

I realize that each of the above may be a valid and published version of PSO. I just want to know which version is usually referred to as "lbest PSO".

# Answer
> 2 votes
In general option b) is how a Lbest PSO is implemented.

This makes sense, as the Lbest particle is meant to be the social influence, and from an optimization perspective you would utilize the best candidate solution information from you neighborhood, which would inherently be the best of the pbest positions.

---
Tags: artificial-intelligence
---


title: Exercise about First-order logic

text:
# Question
Title: Exercise about First-order logic
I try to express the following statements in first order logic:

1. X is a subset of Y.
2. A set can be uniquely characterised by its elements.
3. The power set p(X) contains all subsets of X.
4. A set X is the union of all its subsets containing just one element.

Thus far I managed:

1. $\forall x \in X \Rightarrow x \in Y$
2. $X=Y \Leftrightarrow (\forall x \in X \Rightarrow x \in Y \land \forall y \in Y \Rightarrow y \in X)$
3. $ x \in p(X) \Leftrightarrow (\forall y \in x \Rightarrow y \in X) $

However now I don't know to express the 4th problem via FOL.

I tried: $ X = \cup x.(\forall z \in X \exists t. z \in t \land t = x \land z \not \in \forall y. y \neq t)$

If possible I would also like to convert 3. in an expressing $p(X)$ with $=$ rather than $\Leftrightarrow$

Any form of constructive comments are welcome. Thanks in advance.

EDIT: Regarding problem 4.: My main problem is that I am not really sure, how to express or write down the solution - I am not too sure, what is allowed, what not. Thus I take any idea that seems remotely right or constructive.

$ X = \underset{|x| = 1, x \subset X} \cup \Leftrightarrow \forall y \in X \exists x . (y \in x \land \lnot \exists z .(z \lnot = x \land y \in z) ) $

On the LHS of $\Leftrightarrow $ I simply tried to express the property given in the problem above and on its RHS I tried to express this property in terms of FOL.

# Answer
It might be useful to take a look at the ZFC axioms. The existence of one element sets is guaranteed by the Axiom of pairing.

The axiom of pairing says that given $A$,$B$ sets, one can construct a third set $C = \\{A, B\\}$. Formally: $$ \forall A. \forall B. \exists C.\forall D. (D \in C \iff D = A ~\lor~ D = B) $$

A singleton set is just the pairing $\\{A,A\\} = \\{A\\}$.

The axiom of union says that for any set $A$ there is a set $U$ whose elements are exactly the **elements of the elements** of $A$. That is:

$$ \forall A. \exists U. \forall c. (c \in U \implies \exists D.(c \in D ~ \land ~ D \in A)) $$

> A set $X$ is the union of all its subsets containing just one element.

Let's look at some example, let $X = \\{a, b\\}^\star$ be a set, take $X^\prime = \\{\\{a\\},\\{b\\}\\} $, which is also a set by the axiom of pairing. By the axiom of union there exists a set $\cup X^\prime$ such that:

$$ \cup X^\prime = \\{a,b\\} = X$$

So you can look at the Union Axiom and try to modify to fit your problem, you have to make a union on a set of singleton sets, which means you have to find a way to define $X^\prime$.

$\star$: I'm assuming $a$ and $b$ are also sets.

---

> EDIT: Regarding problem 4.: My main problem is that I am not really sure, how to express or write down the solution - I am not too sure, what is allowed, what not. Thus I take any idea that seems remotely right or constructive.

Well, from your previous answers it seems you're only allowed to use basic operations like membership and equality, if more stuff is allowed you can literally just write something that looks like natural language while still being formal.
> 1 votes

---
Tags: first-order-logic
---


# Question
Title: Runtime of sorting a partially-sorted array
I have an array of $n$ items which is partially sorted like below:

$$A\[i\]\le{A\[i+k\]}$$

where:

$$i=1,2,...,n-k$$

For sorting the array completely, I wonder what the runtime big O is.

I feel only an array of size $k$ needs to be sorted. Because if the sub-array $A\[1\le{i}\le{k}\]$ is sorted, then all the subsequent sub-arrays are automatically sorted: $A\[1+k\le{i}\le{2k}\]$ and $A\[1+2k\le{i}\le{3k}\]$ up to $A\[n-k\le{i}\le{n}\]$

Therefore the runtime big O might be just $O(k\log{k})$

# Answer
The optimal algorithm to sort your array in a decision-tree model takes time $\Theta(n \log k)$. One arrow is trivial, an algorithm that sorts $A$ in time $O(n \log k)$ is, for example, mergesort.

The other arrow is more interesting. Assume, for the sake of simplicity, that $n$ is an integer multiple of $k$ and that $\lambda = n/k$. First of all, unwinding your condition we get:

* $A\[1\] \le A\[k+1\] \le A\[2k+1\] \dots \le A\[(\lambda-1)k + 1\]$
* $A\[2\] \le A\[k+2\] \le A\[2k+2\] \dots \le A\[(\lambda-1)k + 2\]$
* $\dots$
* $A\[k\] \le A\[2k\] \le A\[3k\] \dots \le A\[n\]$

Observe that no other conditions are imposed on the elements of $A$, therefore any permutation of $\\{1 \dots n\\}$ that satisfies those conditions is a valid starting state for $A$.

Now, let's count how many such permutations are there. This is equivalent to asking in how many ways we can choose $\lambda$ elements from $n$ to be assigned to the first subarray, then $\lambda$ elements from the remaining $n - \lambda$ to be assigned to the second and so on. We can compute this number in the following way:

$$ N = \prod\_{j=0}^{k-1} \binom{n-j\lambda}{\lambda} = \prod\_{j=0}^{k-1} \frac{(n-j)!}{\lambda!(n-j-\lambda)!} = \frac{1}{\lambda!^k} \prod\_{j=0}^{k-1} \frac{(n-j)!}{(n-j-\lambda)!} = \frac{n!}{\lambda!^k} $$

Since we assumed that we are working in a decision-tree model, sorting $A$ requires a number of comparisons bounded by:

$$ \Omega\left(\log \frac{n!}{\lambda!^k} \right) = \Omega\left( n \log n - k \frac{n}{k} \log \frac{n}{k} \right) = \Omega \left(n \log \frac{nk}{n} \right) = \Omega(n \log k) $$

Which proves our assertion.
> 6 votes

# Answer
Your argument is not correct: Even if the subarrays a\[0\] to a \[k-1\], a \[k\] to a \[2k-1\] and so on are sorted, that doesn't make the whole array sorted. For example if k = 3 you could have \[1, 2, 10000, 3, 4, 10001, 10002, 10003, 10004\] and there's still a lot of sorting to be done.

You basically have k sorted sequences of length about n/k, so you have k sequences to merge, which you should be able to do in O (n log k).
> 6 votes

# Answer
1. If the runtime would in fact be $O(k\log{k})$, then growing the array/increasing $n$ would not affect the runtime at all. This would imply that we could change the input in `[1, n-k]` (while still fulfilling the conditions) while the output must stay the same.
$\implies$ Contradiction as the output depends on all array values.
2. The cost of sorting the subarray `[n-k+1, n]` is $O(k\log{k})$. Merging the subarrays `[1, n-k]` with `[n-k+1, n]` takes us $O(n)$.
Thus the final runtime is $O(n + k\log{k})$.
> 1 votes

---
Tags: algorithms, data-structures, sorting, arrays
---


# Question
Title: why is H = {www | w ∊ (0,1)* } not regular language
I know pumping lemma and also know how to prove if languages are not regular or are regular using proof by contradiction methodology. But I am stuck on this one.Especially, I don't know exact string it produces.

$$ H = \\{www \mid w ∊ (0,1)^\* \\} $$

How do I prove this is not regular language? Thanks!

# Answer
> 1 votes
You can use the Myhill–Nerode criterion. Consider the words $0^n1$ for all $n$. These are pairwise inequivalent since $0^n10^n10^n1 \in H$ while $0^m10^n10^n1 \notin H$ if $m \neq n$. Since we have found infinitely many pairwise inequivalent words, it follows that the language is not regular.

As mentioned in the comments, you can probably also use the pumping lemma, but it might take more work.

---
Tags: computability, pumping-lemma
---


# Question
Title: "Combinational" Decision Graph - Cheapest search algorithm
I have a special kind of decision graph, where Multiple decisions must be made in combination, to accomplish the path. Not sure if *Multiobjective* or *Combinational* is the right term here, let me know if there is a better one. Picture better then words:

We have:

* **Joining Nodes** (e.g. "Start") which joins decisions or costs nodes together - meaning **solution path MUST cover all edges of joining nodes**.
* **Decision Nodes** (e.g. D1,D2,...) and **Decision Edges** (aka "local solution" - e.g. D1-1, D1-2,...) each solution path may cover only one of the edge of a decision.
* **Costs Nodes** \- (e.g. 3,7,5...) that have cost/reward applied to the Paths that cover it. Technically any node even decision or joining can have costs associated. **COSTS MAY BE NEGATIVE**.
* **Solution Path** \- goes from a starting node and must cover all edges of connected joining nodes and only one edge of each decision node it meets

**Green** is the cheapest Path for this example (D1-2,D2-1,D3-1) that you can calculate yourself empirically or combining all possible combinations and sorting by total costs. Total costs of Green path is $5.

**Constraints**:

* Costs may be negative - in this case it's a reward.
* Cycles are possible - they must be resolved as invalid path.
* Decisions are NOT binary

**Goal**:

Find the best (BigO runTime) algorithm to find cheapest path covering this kind of graphs (without iterating all possible combinations and calculating its costs)? Pseudo code would help. Also what is the name of such type of decision graph?

# Answer
> 1 votes
Your problem is $\mathcal{NP}$-hard, by reduction from $\mathcal{3SAT}$. Let $\Phi = \phi\_1 \wedge \dots \wedge \phi\_m$ be a CNF formula with variables $V = \\{x\_1, \dots x\_n\\}$. Let $\mathcal{L}(V)$ be the set of literals of $V$. Let joining nodes, decision nodes, cost nodes be defined as in your question.

For each $x\_i$, we create four cost nodes $t\_i$, $f\_i$, both with cost $1$, representing an assignment of, respectively, true and false to $x\_i$. Let $S$ be the set of all such nodes.

Let $\phi\_i = \psi\_{1i} \vee \psi\_{2i} \vee \psi\_{3i}$ be a clause with $\psi\_{1i}, \psi\_{2i}, \psi\_{3i} \in \mathcal{L}(V)$. Without loss of generality, we may assume that $\psi\_{1i}, \psi\_{2i}, \psi\_{3i}$ are literals obtained from different variables. Of the eight possible assignments of truth values to those variables, seven satisfy $\phi\_i$. For each of those assignments, we create a joining node $c\_{ki}$, which has as a successor every node $s \in S$ corresponding to the values relative to such assignment. For example, if the $k$-th assignment were "$x\_\alpha$ true, $x\_\beta$ false, $x\_\gamma$ true", $c\_{ki}$ would have $t\_\alpha, f\_\beta, t\_\gamma$ as successors. Finally, we create a decision node $d\_i$ with successors $c\_{1i}, \dots, c\_{7i}$ and let the starting node have as successors each of the $d\_i$.

Now, observe that any solution path in the decision graph that we have built has weight at least $n$. In fact, whenever we encounter a fresh variable $x\_i$, we are forced to take either $t\_i$ or $f\_i$, both of which have cost $1$. Furthermore, any path with cost not exactly $n$ has taken, by the pigeonhole principle, both $t\_k$ and $f\_k$ for some $k$, which means that it does not correspond to a consistent assignment of truth values to the variables of $V$.

On the other hand, an assignment of truth values to variables that satisfies $\Phi$ corresponds to a path of weight exactly $n$ (choose $t\_i$ for every variable $x\_i$ set to true, $f\_i$ for every variable $x\_i$ set to false, follow every arrow in the opposite direction).

We conclude that determining the optimal path is at least as hard as $\mathcal{3SAT}$, and consequently, as every problem in $\mathcal{NP}$.

As always with $\mathcal{NP}$-hard problems, your choice is to go with either heuristics or approximation schemes. If I may make a suggestion, problems like this are a good fit for logical programming tools, such as CSP/ASP.

---
Tags: algorithms, graphs, decision-problem, weighted-graphs
---


# Question
Title: $L$ is decidable. Prove that "similar" language is also decidable
Assume that $L$ is decidable. Is the following language decidable? $$ L' = \\{w | \text{ there is } u \in L \text{ such that u and w are equal to at most two positions.}\\}$$

For example, let $u=abcd$. The following words are equal to $u$ at most two positions: $\\{aba, agg, ab, zzz, dsa, ...\\}$, but not $\\{ abc, zbcd \\}$

My approach:

> A language is decidable iff some enumerator enumerates the language in lexicographic order.

I use above theorem.

So, $L$ is decidable. Therefore, let's take enumerator $E$ for it. Let We construct a $TM'$ for $L'$. Let enumerator $E$ be connected to $TM'$. For every input $w$ given to $TM'$ the $TM'$ compare it position by position with every string $v$ generated by $E$ in lexicographical order till $|v|\le|w|$ If number of the same positions $\>2$ reject $w$. Otherwise, accept.

Ok?

# Answer
Let's consider for simplicity the language $$ L'' = \\{ w : \text{there exists $u \in L$ such that $u,w$ disagree on all positions} \\} $$ instead of your more complicated one.

Consider the language $$ L = \\{ 0^n10^m : \text{the $n$th Turing machine halts on the empty input after exactly $m$ steps} \\}, $$ which is computable. You can check that $1^n0 \in L''$ iff the $n$th Turing machine halts, hence $L''$ is not computable.

In order to answer your original question, just repeat each bit 3 times.
> 2 votes

---
Tags: complexity-theory, computability, turing-machines, automata
---


# Question
Title: Transform PDA with acceptance of final state + empty stack to just final state
"It is a well known result that every PDA with acceptance condition of an empty stack and reachability of a final state can be transformed to an equivalent PDA with acceptance condition requiring only reachability of a final state. Transform PDA \____ to an equivalent PDA with acceptance requiring only reachability of a final state."

I'm just a bit confused on what steps I have do to. My thought process is...final state + empty stack acceptance is a subset of just a final state acceptance? When I try to 'transform' my PDA, it ends up looking exactly the same as the original.

# Answer
> 1 votes
Given a PDA $M$, you can define the following associated languages:

* The language of all words $w$ such that there is a computation path for the PDA on $w$ in which it ends at a final state with an empty stack. We denote this language by $L\_1(M)$.
* The language of all words $w$ such that there is a computation path for the PDA on $w$ in which it ends at a final state. We denote this language by $L\_2(M)$.

The two languages are not always the same, that is, it could well be that $L\_1(M) \neq L\_2(M)$. You have to show that for each PDA $M$ there is another PDA $M'$ such that $L\_1(M) = L\_2(M')$.

---
Tags: automata
---


# Question
Title: Proving that $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$?
It is known that $\mathrm{SPACE}(o(\log \log n)) = \mathrm{SPACE}(O(1))$ (see e.g. these lecture notes by Christian Scheideler).

One inclusion is trivial, so I'm trying to show that $\mathrm{SPACE}(o(\log \log n)) \subseteq \mathrm{SPACE}(O(1))$ as follows.

Let $L$ be a language and $A$ is a Turing machine with alphabet size plus tape symbol is equal to $c$, to solve the problem $L$. We know that number of configurations is going to be at most $c^ {o(\log \log n)}\times\mathrm{poly} (o(\log \log n))$ (roughly), but even $c^ {o(\log \log n)} \notin O(1)$.

For example, $ s(n) = \log \log \log n \in o(\log \log n)$ but $c^{s(n)} \notin O(1) $. I don't know, how to proceed further.

**My question:** How to prove that $\mathrm{SPACE}(o(\log \log n))\subseteq \mathrm{SPACE}(O(1))$?

# Answer
You're basically there. If the machine uses at most $s(n)$ tape cells for inputs of length $n$, then it can't visit more than $C(n)=|Q||\Sigma|^{s(n)}s(n)$ different configurations (possible states times possible tape contents times possible head positions). Since the machine decides a language, it must halt for all inputs, which means that it can't repeat a configuration, since a deterministic machine that repeats a configuration must loop forever. Therefore, by the pigeonhole principle, it can't run for more than $C(n)$ steps on any input of length $n$.

If $s\in o(\log\log n)$ then $C(n) = o(n)$ so the machine terminates after fewer than $n$ steps for all sufficiently large $n$. Intuitively, the machine can't stop in, say, $\sqrt{n}$ steps because, in that many steps, it hasn't seen the whole input, so it doesn't even know what $n$ is.

More formally, let $t(n)$ be the greatest number of steps taken by the machine on inputs of length $n$. Let $w$ be an input long enough that $t(n)\<n$ for all $n\geq |w|$, and choose $w$ so that the machine runs for $t(|w|)$ steps on this input. We know that $t(|w|)\leq C(|w|)\<|w|$, so the machine must terminate before it has time to read the whole input. Because it doesn't read the whole input, its execution on input $wz$ must be the same as its execution on $w$, for any string $z$. Therefore $t(|wz|)=t(|w|)$ for all strings $z$, so the function $t$ is constant for all inputs greater than length $|w|$.

Because it halts in a constant number of steps, it only uses a constant number of tape cells, so the language it decides is in $\mathrm{SPACE}(O(1))$.
> 9 votes

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Graph isomorphism problem for labeled graphs
In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is exponential, one usually has a polynomial running time.

I was hoping that the situation is similar in the case of labeled graphs. However, I have a really hard time to find any reference which proposes an "practically efficient" algorithm.

Remark: Here, we require that the isomorphism preserves the labels. That is, an isomorphism between two finite automata/process algebra terms would imply that the automata/terms are essentially "equal up to renaming of the nodes".

The only reference I found was the one in Wikipedia that states the the isomorphism problem of labeled graphs can be polynomially reduced to that of ordinary graphs. The underlying paper, however, is more about complexity theory than practical algorithms.

I am missing something, or is it really the case that the there are no efficient "heuristical" algorithms to decide whether two labeled graphs are isomorphic?

Any hint or reference would be great.

# Answer
> 6 votes
You might be interested in this paper:

Aidan Hogan: Skolemising Blank Nodes while Preserving Isomorphism. WWW 2015: 430-440

It has an algorithm (based on Nauty) for testing the isomorphism of RDF graphs, which are essentially directed labelled graphs that may contain fixed labels. The algorithm takes labels into account to narrow the search space.

If you can represent your input labelled graph as an RDF graph, you could try use the associated software package "`blabel`" to test isomorphism.

# Answer
> 3 votes
I've found out that the algorithm belongs in the category of k-dimension Weisfeiler-Lehman algorithms, and it fails with regular graphs. For more here:

http://dabacon.org/pontiff/?p=4148

Original post follows:

Years ago, I created a simple and flexible algorithm for exactly this problem (graph isomorphism with labels).

I named it "Powerhash", and to create the algorithm it required two insights. The first is the power iteration graph algorithm, also used in PageRank. The second is the ability to replace power iteration's inside step function with anything that we want. I replaced it with a function that does the following on each iteration, and for each node:

* Sort the hashes (from previous iteration) of the node's neighbors
* Hash the concatenated sorted hashes
* Replace node's hash with newly computed hash

On the first step, a node's hash is affected by its direct neighbors. On the second step, a node's hash is affected by the neighborhood 2-hops away from it. On the Nth step a node's hash will be affected by the neighborhood N-hops around it. So you only need to continue running the Powerhash for N = graph\_radius steps. In the end, the graph center node's hash will have been affected by the whole graph.

To produce the final hash, sort the final step's node hashes and concatenate them together. After that, you can compare the final hashes to find if two graphs are isomorphic. If you have labels, then add them (on the first iteration) in the internal hashes that you calculate for each node.

For more on this you can look at my post here:

https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF

The algorithm above was implemented inside the "madIS" functional relational database. You can find the source code of the algorithm here:

https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py

---
Tags: algorithms, graphs, graph-isomorphism
---


# Question
Title: Regular expression generating the language $L=\{w: |w|\le 5\}$
Im trying to find a regular expression to generate the language that has words with length at most 5, over $\Sigma =\\{0,1\\}$ How can i represent the at most ? I know i can do it if ill just write all the $2^5$ possibilties with 'or' between them. But it seem to me not the right way. Is it even possible to represent the state : "I've choose 0, 1, or nothing" ?

I can use only the elemntary operators : $\cup , \cdot , ^\*$

Also it was easyer to find a NFA that will represent L but the algorithem to get the regex from the aotomton will give me the exponential answer.

# Answer
> 2 votes
If you are allowed to use $\epsilon$, then you can represent "0, 1, or nothing" using $0+1+\epsilon$, and using this it is easy to come up with a short regular expression.

If you are not allowed to use $\epsilon$, then you can use the fact that $L = \bigcup\_{i=0}^5 \\{ w : |w|=i \\}$ to come up with a fairly short regular expression, though I don't know how you would match the empty string.

# Answer
> 2 votes
Yes, for "0,1 or nothing", you can write it as $$(\Sigma | \epsilon)$$ where $\Sigma$ is your alphabet.

So, for strings of length at most $5$, the expression would be $$(\Sigma | \epsilon)^5$$

---
Tags: computability, regular-languages, finite-automata
---


# Question
Title: Why is data in computer science considered to be discrete?
I understand that "structure" of data is totally dependent on Boolean Algebra, but:

> Why is data considered to be a discrete mathematical entity rather than a continuous one?

Related to this:

> What are the drawbacks, or invariants, that are violated in structuring data as a continuous entity in $r$ dimensions?

I am not an expert in the field as I am an undergrad math student, so I'd really appreciate it if someone would explain this to me like I'm five.

# Answer
# Answer

> why was the data considered to be a discrete mathematical entity rather than a continuous one

This was not a choice; it is theoretically and practically impossible to represent continuous, concrete values in a digital computer, or actually in any kind of calculation.

Note that "discrete" does not mean "integer" or something like that. "discrete" is the opposite of "continuous". This means, to have a computer that is truly able to store non-discrete things, you would need to be able to store two numbers `a` and `b` where `abs(a-b) < ε` for any arbitrarily small value of `ε`. Sure, you can go as deep as you want (by using more and more storage space), but every (physical) computer *always* has an upper bound. No matter what you do, you can *never* make a (physical) computer that stores arbitrarily finely resolved numbers.

Even if you are able to represent numbers by mathematical constructs (for example `π`), this does not change anything. If you store a graph or whatever that represents a mathematical formula, then this is just as discrete as anything else.

# Addendum

*The rest is just a little perspective beyond the field of computer science. As the comments have shown, the physical topic is not undisputed, and as you can see I have formulated my next paragraph in a way that is rather uncommitted to whether it's true or not. Take it more as a motivation that the concept of "continuum" is not a trivial one. The answer given above does not depend on whether space is discrete or not.*

Note that all of this is not so much a problem of computers, but a problem with the meaning of "continuous". For example, not everyone even agrees, or did agree in the past, that the *Universe* is continuous (e.g., Does the Planck scale imply that spacetime is discrete?). For some things (e.g., energy states of electrons and many other features in Quantum (sic) Mechanics) we even *know* that the Universe is not continuous; for others (e.g., position...) the jury is still out (at least regarding the interpretation of research results...). (Notwithstanding the problem that even if it is continuous, we could not measure to arbitrary precision =\> Heisenberg etc.).

In mathematics, studying the continuum (i.e., the reals) opens up a *lot* of fascinating aspects, like measure theory, which makes it utterly impossible to actually store a "continuous" kind of number/data.
> 45 votes

# Answer
Computers represent a piece of data as a finite number of bits (zeros and ones) and the set of all finite bit strings is discrete. You can only work with, say, real numbers if you find some finite representation for them. For example, you can say "this data corresponds to the number $\pi$", but you cannot store all digits of $\pi$ in a computer. Hence, computer programs that work with real numbers actually only work on a discrete subset of $\mathbb{R}$.
> 30 votes

# Answer
It's all in the implementation.

If you think about it, computers really are continuous devices. This is easily shown by the fact that all the EM equations governing how they work are continuous. The thing which is discrete is the models we use to decide how to use these computing devices. The abstract machines we use to describe computation are all discrete.

The huge practical advantage of this is in having independence from a lot of quality control challenges. If our models of computers leveraged the full continuous nature of their transistors and capacitors, then we would have to care about how well we built every transistor to a tremendous degree. We can see this in the audio world. In the world audiophiles inhabit, it's reasonable to spend \\$2000 on an amplifier that might have 10 very carefully chosen and matched transistors that do exactly the continuous thing they want. Contrast this with 1,400,000,000 transistors in a Core i7 CPU at the mighty cost of \\$400.

Because our computational models are discrete, we can model all of the signals we see in a computer as a discrete signal plus some continuous error term. We can then filter out the errors simply by observing that they aren't the right shape to be part of the discrete signal.

A major part of this is the removal of time terms in our abstract models. Many of our models don't measure time against some physical process, but against some "logical" signal known as a clock. If you interrupt a clock, the system stops moving, but doesn't break down. It just finishes clearing out any analog errors it might have, and sits waiting for the next discrete pulse of the clock. Removing continuous time terms *drastically* simplifies computation and proofs about computation. Instead, our concepts of time are measured discretely, as seen in P and NP categorizations of algorithms.
> 9 votes

# Answer
To add to all of these great answers, it's worthy to note that Alan Turing , when defining his machines, argues that the amount of symbols needs to be finite (even if arbitrarily large) since a computer (meaning: a human) could not distinguish all the symbols otherwise.

Here's some excerpts from his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem":

And then on section 9:
> 9 votes

# Answer
Because:

* Digital computers cannot store arbitrary real numbers.
* Analog computers are plagued by thermal noise (if electronic), friction (if mechanical or hydraulic), disturbances, sensitivity to temperature variations, inevitable imperfections and ageing. Dealing with such difficulties is what (experimental) physicists and engineers do. Most computer science simply abstracts the physics away.

Here are some papers on real computation:

and here's a paper on analog computation:
> 9 votes

# Answer
The term "computer" in modern parlance means "digital computer"; the essence of a digital computer is that it has a finite number of discrete states. One could have an interesting debate about whether the reasons that digital computers won favour over analogue computers were primarily about engineering practicality, or were primarily due to better underpinning from theoretical computer science. But whatever the reasons, digital computers are what we ended up with, and any useful mathematical model of a digital computer (and therefore its data) is going to be discrete rather than continuous.
> 5 votes

# Answer
The word `data` derives from the Latin word `datum`, which means something which was given. Over time the plural form has changed usage and is now commonly used as both singular and plural. It has also come to be associated with information specifically.

Note that there is a difference between an item of information (a datum) and its representation.

Information Theory deals with (amongst other things) discrete pieces of information represented by variables. These are countable entities. For example, velocity, location, mass, and so on are all continuous quantities, but discrete from each other: there is no transformation between mass and location. When these quantities are represented numerically, their data items , however they are represented, are also discrete from each other.

On the other hand, the vast majority of our current computers use some form of electrical charge to represent information. The charge is either present or it is not; there is current in the circuit or there is not. This is also discrete, but it need not be! It is simply because of the way our technology has developed that we use binary representation. It is possible that developments in Quantum Computing will change this in the near future. It is also not inconceivable that analogue computers will make a resurgence and our notions that numbers have to be represented by binary will be washed away!

To summarise: `data` are composed of discrete items of information, each of which is a datum; whereas each datum does not need to be represented using discrete mathematics, but currently is purely by contemporary coincidence.
> 2 votes

# Answer
I want to challenge your fundamental premise:

> Why is data considered to be a discrete mathematical entity rather than a continuous one?

It isn't.

For example, the study of Algorithms is an important subfield of Computer Science, and there are many algorithms that work with continuous data. You are probably familiar with Euclid's Algorithm for computing the greatest common divisor of two natural numbers, but did you know that Euclid also had a geometrical version of that same algorithm which computes the longest common measure of two commensurable lines? That is an example of an algorithm (and thus an object of study of computer science) over real numbers, i.e. continuous data, even though Euclid didn't think about it this way.

There are many different ways to classify algorithms, but one way that is used, is to classify them by their "continuousness":

* Digital Algorithms (discrete-event algorithms over digital data):
    + the numerical variant of Euclid's algorithm
    + long-hand division, multiplication, etc. as taught in school
    + any computer program, λ-calculus program, Turing Machine
* Non-digital data, discrete-event algorithms (algorithms over continuous data, which however still have a notion of "step", i.e. continuous data but discrete time):
    + the geometrical variant of Euclid's algorithm
    + algorithms on real numbers (e.g. Gauss' Elimination Procedure)
    + algorithms on continuous functions (e.g. the bisection algorithm)
* Analog Algorithms (continuous time, continuous data):
    + electrical circuits
    + mechanical gyroscopes
* Hybrid Algorithms (any combination of the above)
    + robots

Other answers have already mentioned Real Computation in Computability Theory, another important subfield of Computer Science.

> What are the drawbacks, or invariants, that are violated in structuring data as a continuous entity in $r$ dimensions?

The only real (pun very much intended) drawback is that such data cannot be represented with common digital computers. You can *think* about algorithms over continuous data, but you cannot *run* them on the standard machines we usually use to run algorithms.

That's the main reason why continuous data is not as "visible" as digital data.

However, an implementation of an analog algorithm doesn't actually need to be complicated to imagine or even to build. For example, this is an implementation of an analog algorithm:By Andrew Dressel – Own work, CC BY-SA 3.0, Link

Now, you might say "Wait, that's not a computer, that's a bicycle", but actually, you can use it as an analog computer: it computes the multiplication of a real number $r$ by a fixed rational number $q$. Turn the crankshaft $r$ times and the rear wheel will turn $q×r$ times. You can use this to scale *any* real number, e.g. turn the crankshaft $π$ times and the rear wheel will turn $q×π$ times; this is something you can *not* do with a digital computer.
> 2 votes

# Answer
To take a more abstract tack, any possible computation that will eventually give a result, whether on a computer or in your head, can only deal with a finite amount of data. This means that the data can be represented by a string of symbols. This string could be the digits of a number ("42") or the text of a program that creates the data ("4\*atan(1)" for $\pi$). The string has to be finite or the entire thing could never be read to run the program.

Now, the set of all possible finite data can be put in lexicographic order, meaning the set is countable. But, the set of continuous real numbers is uncountable, so there are always numbers in the continuum that cannot be stored by a given computation system. From this, we can conclude that the storage of an arbitrary real number requires infinite resources.
> 1 votes

# Answer
Data is not always considered as discrete. Scientific programming often involves floating-point arithmetic. The programmer usually pretends that the variables involved are continuous, while keeping in mind the issue of numerical stability, which stems from the fact that data is stored to only a finite precision.
> 0 votes

# Answer
* For a computer to work with data, the data must exist within the computer's accessible memory
* A computer's accessible memory is finite
* Only finite data can exist within a computer's accessible memory
* Non-discrete values are infinite

Data in computer science is considered to be discrete.
> -2 votes

---
Tags: data-structures, mathematical-foundations
---


title: Buchi Automaton G(Xa->b)

text:
# Question
Title: Buchi Automaton G(Xa->b)
I have a question regarding buchi automatons. The automata for the LTL formula, G(Xa-\>b) is as the attached picture. Why dosen't a have to be true in order to make the automaton correct?

My suggestion

Best regards

# Answer
The formula states that for all $n$, if $a$ holds at time $n+1$ then $b$ holds at time $n$. If $a$ never holds then the formula is trivially true.
> 1 votes

---
Tags: automata, linear-temporal-logic, buchi-automata
---


# Question
Title: How is RANSAC used to estimate a homography given the descriptors of both images computed with SIFT?
Let image $x$ be an original (non-warped) image. Let $I\_1$ be $I\_1'$ having suffered some projective transformation and possibly some noise. Suppose we have computed SIFT descriptors for both images.

Can you explain how RANSAC is concretely used to find the homography that aligns image $x$ and $y$?

More concretely, I understand we give to the RANSAC function the keypoints ($I\_1$) and keypoints ($I\_1'$).

My understanding (from various papers/tutorials I've read) is that it will take the positions of keypoints in $I\_1$, which I denote as $(x,y)$, and the positions of keypoints $I\_1'$, $(x', y')$, i.e. RANSAC($(x,y),(x',y')$), and then take randomly pairs of $(x',y')$ and $(x,y)$, and then compute the homography by trying to solve for each $x\_i', y\_i'$: $$\[x'\_i, y'\_i\]=H\*\[x\_i, y\_i\]$$

But then how to estimate inliers? I guess by looking at the Euclidean distance between each pair of points found in the homography.

However, I don't really see the 'big picture'. I don't completely link this process of 'finding homography' and checking inliers etc.

It would be great if someone could summarize that in a clear way?

P.S. In general, tutorials say that they "find the homography" and then check for inliers - in some way - but they don't explain in a more pragmatic way what really happends.... w.r.t sift descriptors

# Answer
How do you estimate inliers? You use RANSAC. That's what RANSAC does for you: it computes a homography *and* gives you a prediction for which pairs are inliers and which are outliers.

In SIFT, we first generate keypoints and the feature vector for each keypoint. Also, if $k$ is a keypoint in image $x$ and $k'$ is a keypoint in image $x'$, the feature vectors give a way to tell whether $k,k'$ are good matches. For each $k$, we look for a good match: a $k'$ from $x'$ that is significantly closer to $k$ than any other keypoint in $x'$. The set of good matches forms a set of possible inliers.

Then, we apply RANSAC. We randomly pick four good matches, compute a homography from these four, and test how good this homography is by checking how many of the good matches are consistent with the homography (if $k,k'$ are a good match, we're hoping that in most cases the homography will map $k$ to something near $k'$). Good matches that are consistent with the homography are called inliers (for this homography), and those that aren't are called outliers (for this homography). We count the number of outliers for this homography. Then, we repeat this 1000 times (picking a set of four good matches anew each time), in each iteration deriving a homography and counting the number of outliers associated with it. We keep the homography with the smallest number of outliers.

This is a simplification of the procedure but it will give you the gist of how SIFT works.
> 4 votes

# Answer
Ok. I think that I found out by myself. If I understand correctly we first need to do a 'direct matching' i.e. find some couple of matching keypoints (SIFT descriptors having lowest Euclidean distance, e.g. using the technique proposed by D.Lowe, which is to say we have a match if no other candidate keypoint has a lower or equal Euclidean distance as the best match)

then we give to findHomography function those pair of matching keypoints and we let him try to find a decent homography matrix.
> 0 votes

---
Tags: computer-vision
---


# Question
Title: Proof of Randomized Self-Adjusting Binary Search Tree
I developed a randomized self-adjusting binary search tree years ago, which I called a shuffle tree, but was unable to ever have it published because my proofs were rejected (with little explanation). I've since given up the hope of publishing (I'm not an academic so it doesn't matter so much), but perhaps I can have some closure: I'm going to present the tree here, and perhaps someone can help me understand where my proofs fall short? Through testing, I'm quite certain that my understanding of the data structure is correct, but the proofs were always lacking.

First, understand how a top-down splay tree can be implemented around a traverse() function. Shuffle trees can be implemented similarly, where all operations defer to a traverse() function for the balancing operation.

I'm going to begin with a C traverse function for shuffle trees, then I'll explain:

```
// returns node with key k,
// or returns the leaf containing
// the closest key to k.
node *  Traverse( key k, node *root, int treesize ) {
    signed int iCounter = rand() % treesize;
    node *pRet = 0;
    node *p = root;
    while ( p ) {
        pRet = p;
        if ( k < value(p) ) {
            p = left(p);
            if (( ! iCounter )&& p ) {
                RotateRight( pRet );
                pRet = parent(p);
            } // end if
        } else if ( value(p) < k ) {
            p = right(p);
            if (( ! iCounter )&& p ) {
                RotateLeft( pRet );
                pRet = parent(p);
            } // end if
        } else
            break ; // break while
        --iCounter;
        iCounter >>= 1;
    } // end while
    return ( pRet );
}

```

The rotations used are simple single rotations.

Like a scapegoat tree, shuffle trees sample depth to find imbalance, but unlike scapegoat trees, they execute at most one rotation per access to attempt to restore balance.

At the beginning of traversal, we set an integer count-down value, to a random number in the range \[0,N-1\], where N is the size of the tree. As we iterate from a parent node to its child, we decrease the counter with I := (I-1)/2. When the counter equals zero, then the current node becomes a candidate rotation pivot. If we need to iterate past the candidate pivot, then we will commit to the rotation. We rotate the pivot away from the direction of traversal.

As search depth increases, the likelihood of a rotation increases. No rotations will occur beyond depth lgN. The counter requires lgN random bits per operation. Shuffle trees also record their size, so that the counter can be set. No balancing information needs to be recorded in tree nodes. Searches may not navigate to a leaf; if the working set is clustered near the root, then deep searches will not be required. As a result, rotations can occur less frequently in a well-configured tree. If a node in the tree is not weight-balanced, then an access is more likely to traverse into its larger sub-tree. A rotation at the node probably moves some of the descendants from the larger sub-tree to the smaller one. Since these operations are probabilistic, rotations will occur which can deteriorate balance; but as the imbalance increases, the likelihood of a rotation that improves balance increases. In effect, the balancing technique is a kind of random sampling. Nodes are selected randomly from traversal paths and their balance is manipulated. Frequently used data attract more attention and, therefore, benefit more from balancing activity than infrequently used data. The tree eventually approximates a weight-blanced configura tion for the data set, where the probability of access is the weight for each node.

Here's where it gets dicey: proving that a traversal occurs in lgN.

I argue the probability that an adversary can select a node to force a rotation that impairs balance is

```
(1 - Pw) * Product over A of ( 1 - px )

```

Where Pw is a number estimating the overall weight balance of the tree (Pw \>= 0.5) and px is the weight of node x, the probability it is accessed. Set A is the set containing the pivot and all its ancestors.

If rotations occur which impair balance, and Pw increases, then the overall probability of a favorable rotation increases. As Pw increases, the probability of a favorable rotation dwarfs the probability of a poor rotation. The tree does not linearize, and lgN is maintained.

Eh. What do you think?

# Answer
Your proof/argument is not valid.

First, I see a claim about the probability that the adversary can trigger a rotation, but no proof of this claim. Every claim should be justified. Also, the claim is not precisely defined; it is not entirely clear how "a rotation that impairs balance" should be interpreted.

Second, a statement like "The tree does not linearize, and lgN is maintained" has no place in a proof. In a proof, you must *justify all statements*: every statement must follow logically from things you've previously demonstrated. That statement comes out of nowhere and doesn't follow. For instance, as @Discrete lizard explains, just because a tree's height is less than $n$ doesn't necessarily imply the height is $O(\lg n)$; there are many other possibilities for what its height could be.
> 3 votes

---
Tags: data-structures, randomized-algorithms, correctness-proof
---


# Question
Title: Nominal unification: How this lemma is proved?
I was reading nominal unification paper. I could not understand the proof of a lemma. The paper is here nominal unification. The lemma is following. $\sigma$ is a substitution, $\pi$ is a permutation (swapping of atoms).

Lemma 3.3. if $\Delta \vdash \sigma(\pi .X) \approx \sigma(t)$, then $\sigma.\[X:=\pi^{-1}.t\] = \sigma $.

The paper said, to prove the lemma, need to show that $\Delta \vdash \sigma(\pi^{-1}.t) \approx \sigma(X)$. It first showed $\Delta \vdash \sigma(t) \approx \pi.\sigma(X)$, from which, then the paper finished the proof by saying the following.

> The case the follows from the assumptions by symmetry and commuting the permutation inside the substitution.

I could not imagine how $\sigma.\[X:=\pi^{-1}.t\] = \sigma $ is obtained from $\Delta \vdash \sigma(\pi^{-1}.t) \approx \sigma(X)$. what does that "assumptions by symmetry" mean?

Could anyone point out what proof technique is used here?

Thanks.

# Answer
chi's answer is mostly correct, but I've poured through the paper, and can probably fill in the gaps a bit:

The proof proceeds in 3 steps:

1. Show that **it suffices** to prove: $$\nabla\vdash \sigma(\pi^{-1}.t) \approx \sigma(X) $$
2. Show that the above derivation **is implied by** $$\nabla\vdash \sigma(t)\approx\pi.\sigma(X) $$
3. Show that in turn this is **implied by** the assumptions of the theorem.

The structure of the proof is a bit confusing, since it proceeds "backwards", from the conclusion of the theorem to the hypothesis.

The first step involves mostly unpacking the definition of substitutions and the notation $\sigma\ \circ\ \[X:=t\]$.

The second step is handled by lemmas in the paper (lemmas 2.14 and 2.12 if we're reading the same version). This step is the most complex of the proof.

The last part is performed by changing $\nabla\vdash \sigma(t)\approx\pi.\sigma(X)$ to $\nabla\vdash \pi.\sigma(X)\approx\sigma(t)$ by applying symmetry and once again applying using lemma 2.14 to move $\pi$ "inside" the permutation to get $$\nabla\vdash \sigma(\pi.X)\approx\sigma(t) $$

which is exactly the assumption!

Again, the only real difficulty is that the proof is working backwards, starting from the conclusion and finding stronger and stronger statements until you get the hypothesis.
> 3 votes

# Answer
My guess is that, once you have proved $\Delta \vdash \sigma(t) \approx \pi.\sigma(X)$ you can derive, applying $\pi^{-1}$ on both sides, the relation $\Delta \vdash \pi^{-1} . \sigma(t) \approx \pi^{-1}.\pi.\sigma(X)$, which simplifies to $\Delta \vdash \pi^{-1} . \sigma(t) \approx \sigma(X)$. This is the "symmetry" step the paper mentions.

Then, if we can commute $\pi^{-1}$ with the substitution, we can rewrite $\Delta \vdash \pi^{-1} . \sigma(t) \approx \sigma(X)$ as $\Delta \vdash \sigma(\pi^{-1} . t) \approx \sigma(X)$.

This implies that $\sigma$ does not distinguish between $X$ and $\pi^{-1} . t$: in both cases it produces the same result (modulo $\approx$). Hence, performing substitution $\sigma$ is equivalent to first replacing $X$ with $\pi^{-1} . t$ and then applying $\sigma$.

Note -- I have not checked the paper in detail, so I can't guarantee this fits the paper exactly, but it looks plausible to me.
> 2 votes

---
Tags: proof-techniques, lambda-calculus
---


# Question
Title: A question on instruction executing speed
I am new to computer science, so excuse me if the question is inappropriate or sounds absurd to you.

In the textbook, it says that a typical laptop can execute 1 billion instructions per second. Therefore, I thought that if I wrote a never-ending piece of algorithm, it would generate tons lines in the program counsel after running it for 10 seconds. Taking into account the time it needs to convert to machine instructions, and the fact that other programs needed to be executed as well, the number I expected was some where about one million of instructions per second and thus 10 millions per 10 second.

I tried to run something like this:

```
        While 1+1=2:
               Print(0)

```

To my surprise, I found that the print instruction had been executed for less than 4,000 times within 10 seconds. I know that my original estimation was not meant to be accurate but I was not expecting the speed to be this slow. I think maybe the read-writing speed of my ssd was the major drawback. I know that sending instruction to the screen is even slower, but that should not affect the CPU's performance.

So, here are my questions:

> 1. What are the major factors that slow down the speed?
> 2. Are there any other factors that I overlook?
> 3. Is there a way to know exactly or make reasonably accurate estimation of the Python code execution rate?
> 4. And are there any suggestions to speed up the execution rate?
> 5. Even if it takes time to send instructions to the monitor, the processor can still utilize the gap in between to execute other instructions. So, does that exclude slow I/O speed as a drawback?
> 6. If the hidden layer between me and the machine already figures out what to do in the beginning, is it going to repeat the same instruction without executing extra instructions?
> 7. It is possible to have the processor focus on a piece program without executing any other program at all?

Thank you for your help in advance.

# Answer
There are a number of reasons for this.

* Other processes were probably running at the same time.
* Printing to the console takes many, many instructions per print, especially when the console starts to scroll.
* You may have been using an interpreted language. In this case, the computer must figure out what each line of your program means before running it. Some interpreters figure this out again every time they come to a line, even if they've run it before. Again, this takes many, many instructions per line.
> 2 votes

# Answer
You are misinterpreting "instruction". Check out for example http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf or https://www.scss.tcd.ie/~waldroj/3d1/arm\_arm.pdf (a bit outdated) to find what is meant by "instruction".

Print (0) is not an instruction. It is a statement in an interpreted language. The processor will probably execute thousands of instructions to interpret the statement. And the Print statement will eventually start scrolling the screen, which consists of a million pixel or more, which are moved up smoothly, pixel by pixel, which may take millions of instructions.
> 2 votes

# Answer
Most likely, printing was the slowest bit. In fact, whenever your program issued a `print` instruction to the operating system, it is likely that the operating system did something that made your program wait for the print to be completed. In addition, it is unlikely that the operating system performed the print immediately. Instead it took the opportunity to do other things. Input/output is slow.

What you should do is run your program again and observe how much CPU it is actually using. On my computer it uses about 77% of CPU in Python and 55% in OCaml compiled to native code. That is, the program is waiting for the operating system to perform the print on the console.

A much better way to test speed of CPU is to write a program which will make *only* the CPU busy. That would be a small loop which computes something (and don't use any arrays of memory). But you should make sure to compute something that the compiler cannot just optimize. Good compilers know about arithmetic and gemetric series, and lots of other things.
> 1 votes

---
Tags: memory-hardware
---


# Question
Title: Definition of valid partner in Stable Matching Problem
From Tardos and Kleinberg's *Algorithm Design*, the definition for "worse valid partner" is basically — $m$ is $w$'s worse valid partner if $m$ is a valid partner of $w$, and no man whom $w$ ranks lower than $m$ is a valid partner of hers. (page 11 in case anyone has the pdf/book)

Is this a typo? Shouldn't it be "no man whom $w$ ranks higher" or am I understanding this wrong?

# Answer
> 0 votes
Nvm, it's right. A woman w's best valid partner is m where m is a valid partner and no man w ranks higher than m is a valid partner.

A woman w's worst valid partner is m where m is a valid partner and no man w ranks lower than m is a valid partner.

---
Tags: algorithms, matching
---


# Question
Title: Does Gale-Shapley work when the number of men and women are not equal?
According to the Wikipedia page on the Stable Marriage Problem, the problem is presented in a way in which the number of men and women are both the same.

> Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.

And then later on the Gale-Shapley algorithm is presented as a solution. However, based on my thinking, I believe the Gale-Shapley algorithm would work on inputs where the number of men and women do not have a 1:1 ratio. The reasoning for this is because by definition, if you look at the while loop's predicate, the men keep on proposing until they have either proposed to all of their preferences or are matched. This means that the algorithm will necessarily terminate as the men have a finite number of preferences. In the end, the men only end up matched to a woman if another man couldn't "out-bid" them for that woman. Thus it must be stable as if it were not we would have a contradiction as that man/woman that is unmatched should have proposed or been proposed to. (In general, it may be useful to let the side with a smaller number of people propose since the while loop would terminate sooner in expectation).

Overall, I'm just wondering whether the condition that the number of men and women are the same for the GS algorithm is superfluous.

# Answer
> 3 votes
First thing is algorithm will definitely terminate in the case even when number of men are not equal to women. Now at the end of Gale-Shapley algorithm for the case when number of men$(m)$ and women$(w)$ are equal.

> Each man can have the best partner that he can have in any stable matching.

If you only **care about men** then there are two cases:

* If $m \> w$ then algorithm will terminate but at the end t**here are going to be some men left out without matching**
* If $m \< w$ then algorithm will terminate then at the end, each man can have the best partner that he can have in any stable matching.

---
Tags: algorithms, matching
---


# Question
Title: Upper bound and lower bound of a custom function T(n)
Assume a function $T(n)$: $$T(n)=\log{\log^{\*}{n}}$$ Let's define: $$\log^{\*}{n}=\min\\{i\ge{0}:\log^{(i)}{n}\le1\\}$$ and: $$\log^{(i)}{n}=\log{(\log^{(i-1)}{n})}$$ Is the following $f(n)$ function an upper bound or a lower bound of $T(n)$? $$f(n)=\log^{\*}{\log{n}}$$

---

To see if $f(n)$ could possibly be an upper bound, I feel like the following limit needs to be gone through: $$\lim\_{n\to\infty}{T(n)}=\lim\_{n\to\infty}{\log{\log^{\*}{n}}}=?$$ Now I wonder if the above limit might boil down to this: $$\lim\_{n\to\infty}{T(n)}=\lim\_{n\to\infty}{\log{(\min{\\{\log\log\log\cdots\log^{(0)}{n}\\}})}}$$ I'm not quite sure how to solve the above limit to get an idea of the upper bound of $T(n)$. Also, the lower bound is another story which I have little idea about.

# Answer
> 2 votes
For $n$ satisfying $\log n \> 1$, we have $\log^\* \log n = \log^\* n - 1$ (exercise). On the other hand, $\log \log^\* n $ is much smaller than $\log^\* n$. Hence $\log \log^\* n = o(\log^\* \log n)$.

---
Tags: algorithms, data-structures, asymptotics
---


# Question
Title: Example of inductive sets that are neither least nor greatest fixed point
Do there exist a set of inductive rules and a fixed point of these rules but is neither the least nor the greatest fixed points?

# Answer
> 7 votes
Here's a non-trivial example:

Suppose we want to define inductively a subset of reals, so we work on the complete lattice $\mathcal{P}(\mathbb{R})$ ordered by inclusion.

Then, consider the rules $$ \dfrac{\qquad}{0} \qquad \dfrac{x}{x+1} $$ This induces the (monotonic, Scott-continuous) function $f : \mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R})$ given by $$ f(X) = \\{0\\} \cup \\{ x+1 \ |\ x\in X\\} $$

All of the following are fixed points of $f$:

* $\mathbb{N}$ (least)
* $\mathbb{Z}$
* $\\{x/2 \ |\ x\in \mathbb{Z}\\}$
* $\\{x/3 \ |\ x\in \mathbb{Z}\\}$
* etc.
* for any natural $k \geq 1$, the set $\\{x/k \ |\ x\in \mathbb{Z} \\}$
* $\mathbb{Q}$
* $\mathbb{R}$ (greatest)

If we want our definition to be well-formed, beyond specifying the rules, we need to single out one the fixed points. This is typically done by taking the least (induction) or the greatest (coinduction).

# Answer
> 6 votes
Any set is a fixed point of the empty set of rules or of the trivial rule $x\in X\Rightarrow x\in X$.

---
Tags: logic, inductive-datatypes
---


# Question
Title: outside of bitcoin, how does a network negotiate what the next blockchain should be?
There are two problems I see with negotiating the next block chain:

1. which transactions to include in the chain (because consider transaction T which has propagated through exactly 49% of the network at the time the next block is negotiated)
2. which proposed block to consider the next legitimate block in the chain, because even assuming all nodes have all transactions, what's to stop every node from attempting to propose the next block, thus forcing the network to attempt to propagate and resolve N different block collisions.

In bitcoin, number 2 above is easily resolved by intentionally imposing conditions on the resulting hash of the blockchain such that it is computationally difficult to derive the hash, and thus collisions (where 2 nodes propose a valid block/hash at the same time) are very rare.

Outside of bitcoin, I'm skeptical as to how new blocks are announced and agreed upon. If you have a blockchain structure where a new block should be announced at an artificial time interval of every 10 minutes (assume the network is time sync'd) then what's to stop all your nodes from attempting to propose many different next blocks all at once? In a general blockchain network that isn't bitcoin, I don't see any restriction like #2 above that reduces the ability for many nodes to come up with their own proposed blocks and to stop them from trying to announce these blocks to the network.

Also, assuming we can resolve this issue ^ and manage to negotiate which block to use as the next one in the chain, we're assuming here that the contents of all the proposed blocks are also equal. How can a network negotiate the next block if 49% of nodes contain a transaction that the other 51% of nodes do not?

# Answer
> 1 votes
Here's how Bitcoin works. I suppose we could say that each node can "propose" a different next block. What this really means is that each node can select a "proposed" next block and start mining to attempt to append that block to the blockchain. Bitcoin's proof-of-work basically creates a lottery among all of the nodes who are doing this; it's random which one will win, but there will be only one winner, and once there is a winner, everyone will know which one won.

Nothing stops dishonest nodes from attempting to "propose" many different next blocks and mine from them. If 100% of the network is dishonest, then you're screwed anyway. So if you want any security at all, you need to assume that at least 51% of the nodes are honest. And the crucial part is to look at how the *honest* nodes will behave.

The way that a protocol works is that it specifies how an *honest* node should work. If the node is honest, it will follow the protocol faithfully -- that's more or less the definition of honest, in the world of protocols. The Bitcoin protocol specifies how an *honest* node should determine what transactions to include in its proposed next block: include *all* of the transactions that it is aware of, and that are valid. It also provides a mechanism to help all of the honest nodes learn of all possible transactions.

So, if at least 51% of the nodes are honest, they'll all "propose" the same next block (since they're all honestly applying the same validity checks) and start mining from that next block.

What about protocols *other* than Bitcoin? No one ever promised that other protocols would be secure. No one ever promised that merely using a blockchain (a hash-chained ledger) is sufficient to ensure security. Bitcoin is a clever combination of multiple interlocking mechanisms that work together to provide security -- the beauty and magic is in how they fit together. If you take away some of those mechanisms and keep only others, there's no reason to expect the result to necessarily be secure. And it's not really possible to analyze the security of an unspecified protocol, where the only information we have about it is that "it uses a blockchain but isn't Bitcoin".

# Answer
> 1 votes
Here is how some other blockchain protocols ensure consensus about the next block:

* **Ethereum** currently uses a Proof-of-Work approach that is similar to Bitcoins, but will change the protocol to use a **Proof-of-Stake** mechanism instead. This means that people who have a lot of ETH (the Ethereum currency) or have had ETH for a long time and haven't written a block in a long time will be more likely to be allowed to write the next block.
* **Ripple** and **Tendermint** use **Voting Systems**: Nodes send votes for proposed blocks around the network until they are sure that enough nodes voted for the same block, at which point it is "commited" to the blockchain.
* There are also some other projects that use proof of...
    + **Space**
    + **Ellapsed Time**
    + **Bandwidth**

---
Tags: distributed-systems, network-topology, peer-to-peer
---


title: Low-level shift operator implementation

text:
# Question
Title: Low-level shift operator implementation
I want a shift operator for an architecture that implements boxing. Basically, the high-level constructs represent integers as 31 bits followed by 1 bit set to one as a tag (so to represent binary int i I use instead 2i+1). Let's denote the box representation as $\[\[\cdot\]\]$, then I was able to make the following deductions. Consider x the number to be the shifted value and y the shift value (read the following to understand the whole process):

$\[\[\text{shift} \\, x \\, y\]\] = 2\*{\text{shift} \big\[\frac{\[\[x\]\]-1}{2} \\, \frac{\[\[y\]\]-1}{2}}\big\] + 1 = 2\*{\text{shift} \big\[\frac{\[\[x\]\]-1}{2} \\, \frac{\[\[y\]\]}{2}}\big\] + 1 = $

$= {\big\[\text{shift} \\; \[\[x\]\]-1 \\, \frac{\[\[y\]\]}{2}}\big\] + 1$

Here we can use $\frac{\[\[x\]\]-1}{2}$ or $\frac{\[\[x\]\]}{2}$ because $\[\[x\]\]$ always ends with a one however in the last step we remove the division by two and for $\[\[x\]\]$ we have to keep $-1$ but not for $\[\[y\]\]$. Please note that this translation is meant for left shifts where the bit structure of $x$ is important, namely if we have $x\_1 x\_2 x\_3 1$ the last bit will be actually used in contrast with the right shift case.

The following is the version for the right shift (again read what follows to understand the process):

$\[\[\text{shift} \\, x \\, y\]\] = 2\*{\text{shift} \big\[\frac{\[\[x-1\]\]}{2} \\, \frac{\[\[y-1\]\]}{2}}\big\] + 1 = 2\*{\text{shift} \big\[\frac{\[\[x\]\]}{2} \\, \frac{\[\[y\]\]}{2}}\big\] + 1 = $

$= {\big\[\text{shift} \\; \[\[x\]\] \\, \frac{\[\[y\]\]}{2}}\big\] + 1$

Here the point is that the last bit is no longer useful and can be ignored.

I wonder if me scheme is correct and efficient in the sense that it may exist other procedure that is more efficient than mine. I would appreaciate as well that you clarify the intuitive ideas I gave for my procedure (if it is correct) reelaborating my assertions with possibly more accurate ones. Also I would appreciate ideas that suggest how to mix this two implementations.

# Answer
Yes, it is correct. Yes, it is efficient: your implementation for left-shift requires only four basic operations (i.e., about four instructions), and your implementation for right-shift requires only three basic operations.
> 1 votes

---
Tags: compilers, integers
---


# Question
Title: "strongly relational m-consistency when the domains contain at most m elements implies satisfiability" plain wrong?
Wikipedia states

> A constraint satisfaction problem may be relationally consistent, have no empty domain or unsatisfiable constraint, and yet be unsatisfiable. There are however some cases in which this is not possible.
>
> The first case is that of strongly relational m-consistent problem when the domains contain at most m elements.

This would imply that any problem with domains of size m that is stongly m-consistent, is satisfiable. However on the same page they mention 3-colorability. It is NP-complete and consists of binary constraints on variables with domain size 3. Generally it should be possible to achieve strong-3-consistency in about $O(n^3)$, so the above statement should be wrong as it implies P=NP. What did they mean to say when the wrote the above statement? Or am I interpreting it in a wrong way?

# Answer
Yes, the quoted statement is correct. Wikipedia gives a proof in the next four sentences that immediately follow the quote you gave.

The constraints that arise from 3-colorability are not strongly relational 3-consistent, so the quoted statement implies nothing about 3-colorability. Consequently, there is no contradiction.

(Why aren't the constraints from 3-colorability strongly relational 3-consistent? Consider a star graph, with a vertex $v$ that is connected to three other vertices $w,x,y$. There is one constraint per edge in the graph: e.g., one constraint that constrains the colors assigned to vertices $v,w$; one for $v,x$; and one for $v,y$. Suppose we have a partial assignment that assigns $w$ the color red, $x$ blue, and $y$ green. Then there is no way to assign a color to $v$ that makes the three constraints for $vw$, $vx$, and $vy$ all valid. Thus, the constraints do not satisfy the definition of strongly relational 3-consistency.)
> 1 votes

---
Tags: satisfiability, constraint-satisfaction
---


title: Time complexity of nested loops help

text:
# Question
Title: Time complexity of nested loops help
How exaclty do you determine this specific codes runtime is theta(n^2)??I can see theres two while loops which go from i and j to n but would like a more precise way of determing this? If someone could explain is simple terms as I am very new to this I would appreciate it.

```
def f(n):

i = 0

  while i < n:

   j = 0

     while j < n:

      j = j + 1

 i = i + 5

```

# Answer
**Solution 01)** Analysis what code does.

Your code execute the first loop n times.

And for each executions on first loop it will execute n times.

So the result will be n * n = n^2

**Solution 02)** Try to count how many times execute the instruction

```
def f(n):
count = 0
i = 0
  while i < n:
   j = 0
     while j < n:
      j = j + 1
      print("execute:" + count)
      count = count + 1
 i = i + 1

```
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, loops
---


title: Algorithm in O(logn)

text:
# Question
Title: Algorithm in O(logn)
I have a project where I should write the following algorithm :

> Let an integer function $f\colon\\{1,2,3,\ldots,n\\} \to \mathbb{Z}$ be monotone and suppose that $f(1) \> 0$ and $f(n) \< 0$. We would like to find the smallest integer $i$ with $f(i) \< 0$. Design an algorithm for this purpose that run in time $O(\log n)4.

I tried to search in the middle ($\frac{n+1}2$) and then go in the right half or in the left half (like binary search) but the input is not sorted. Could someone give me an idea of how I can continue?

# Answer
This can be viewed as an array with indices given by $1,2,3,\dots,n$ such that $f(i)$ is stored at index $i$.

As $f(i)$ is monotonic, and the sign changes from positive to negative with increasing $i$, it can be concluded that $f(i)$ is a decreasing function, which tells us that the array is sorted in decreasing order.

Here, we are looking for the smallest index $i$ such that $f(i)\lt 0$. We need to find a particular value of $i$ such that $f(i-1)\ge 0$ and $f(i)\lt 0$. Such an $i$ must be unique because for all indices greater than $i$, $f$ must be negative and for all indices less than $i-1$, $f$ must be non negative. Such an $i$ must exist as it is given that for at least one value each, $f$ takes positive and negative values. The index $i$ can be found by binary search as you suggested.
> 3 votes

---
Tags: algorithms, divide-and-conquer
---


title: Sorting Algorithm with constraints

text:
# Question
Title: Sorting Algorithm with constraints
I am looking for a sorting algorithm to help me in my work. My objective is the following: after receiving an input of this kind:

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

```

The first line tells me how many ids I have, and the second number tells me how many connections. The following lines tell me the connections, and tell me that the first Id comes before the second one, for example: 1 comes before 2, 2 comes before 3, and so on. And if an impossible situation occurs:

```
3 2
1 2
2 3
3 1

```

or

```
2 2
1 2
2 1

```

I want to be able to send an error message.

Or even when there is not enough information to have a conclusive sorting:

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

```

Is there an algorithm that already does this? or can u give me some guide lines to how to start my work? The sorting part is not hard, but the impossible/insuficient info cases is what I am struggling to implement.

Thanks in advance for your time.

# Answer
> 2 votes
In other words, you are given a directed graph, and you want to know:

1. Whether there are any directed cycles, i.e., whether your graph is a DAG.
2. Assuming there are no directed cycles, whether the corresponding partial order is a linear order.

As KWillets comments, this is just topological ordering. In your case, to find whether your digraph is a DAG supporting a unique topological ordering, try the following algorithm:

1. Verify that there is a unique source (a node with no incoming edges).
2. Remove the unique source, and repeat.

This succeeds iff your digraph is a DAG which has a unique topological ordering.

---
Tags: algorithms, sorting, c
---


# Question
Title: Can a subset of an NP-complete problem be in P?
The problem is NP-complete (proven) for all input data (without exception).

We assume that P != NP.

Is it possible that there is an (infinitely large) subset of the problem, for which this subset is in P?

Theoretical question.

# Answer
> 23 votes
Your question doesn't make sense:

> The problem is NP-complete (proven) for all input data (without exception).

This is not a thing. NP-completeness is a property of entire sets, not of specific inputs. It's fairly trivial to show that, if you choose a specific input, *any* problem is $O(1)$ on that input: you just output yes or no, depending which is correct for your input. When you do this, all of algorithm analysis breaks down and everything ends up useless. So, we don't do this.

$P$, $NP$, $NP$-completeness, polynomial time, etc. are all related to *asymptotic complexity*: as the size of input grows, how does the run-time grow? This only makes sense when you look across different input, the same way the derivative of a point in calculus is a property that takes into account the curve surrounding the point.

> We assume that P != NP.

Again, this doesn't affect your answer. If $P = NP$, then every $P$ set is $NP$-complete,* so there are a bunch of subsets in $P$. And if $P=NP$, the examples that people have given are all valid.

> Is it possible that there is a subset of the problem (infinitely large), that this problem is in P?

Yes, and the other answers have given great examples of this. But for posterity, here's yet another counter example.

* $k$-coloring is $NP$-complete if you take $k$ as input, but $2$-coloring is an infinite subset of this that is in $P$.

---

* Except for $\emptyset$ and $\Sigma^\*$, which aren't $NP$-complete for technical reasons relating to the form of reductions we use to define completeness.

# Answer
> 13 votes
In fact, you don't need the **P$\\,\neq\\,$NP** hypothesis, since there are even infinite *constant-time* decidable subsets of **NP**-complete problems. For any **NP**-complete language $L\subseteq\\{0,1\\}^\*$, let $L' = \\{0w\mid w\in L\\}\cup\\{1w\mid w\in\\{0,1\\}^\*\\}$. $L'$ is still **NP**-complete (trivial reduction from $L$), but it contains the infinite constant-time decidable subset of all strings beginning with $1$.

# Answer
> 10 votes
As I understand your question, yes, this is possible. As an example, consider the (infinitely large) subset of SAT that contains all satisfiable formulae with no negations. This subset is trivially in P.

# Answer
> 10 votes
Take the example of $\mathsf{3\text{-}Coloring}$ problem, it is $\mathsf{NP\text{-}Complete}$ in general, but for trees (there are infinitely many ) it is in $\mathsf{P\text{}}$

# Answer
> 1 votes
Graph coloring, maximum clique and maximum independent set are $\mathcal{NP}$-complete (decision versions), but polynomial on perfect graphs.

# Answer
> 0 votes
Take the Travelling Salesman problem: Given are n cities, and the distances between each pair of cities, and a limit d. Is there a route touching each city once and then returning to the starting point with a total length ≤ d?

For any set of cities and distances, for small values of d ("small" depending on the distances) it will be easy to show that there is no solution, and for large values of d it is easy to find a solution. So you can find a subset of the problem where d is large or small enough where you can solve any instance in polynomial time.

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


# Question
Title: Definition of efficiency versus complexity of algorithm
When I read introductory textbooks I get contradictory answers. In some cases efficiency and complexity are treated the same and the big-O notation is used to indicate that (for example) for an O(n) algorithm the time to execute is linearly proportional to the input dataset size.

From other sources I have read that efficiency is a measure of the computing resources required to execute an algorithm, but not the same as the complexity of the algorithm. So for example is it possible to have an algorithm (say to multiply two decimal numbers) that is efficient in terms of its resources (it does not need much to execute) but is complex in that as the input dataset increases in size the time to execute is O(n^2) ???

# Answer
An algorithm is often called "efficient" if its runtime is short, compared to the inherent difficulty of the problem.

For example, you cannot sort arbitrary arrays by comparing keys in less than O (n log n). Once sorted you can lookup values in O (log n). Looking up a value in the sorted array by doing a linear search has lower complexity then sorting the array, but it is inefficient because linear search takes time O (n) and could be done in O (n log n).
> 2 votes

# Answer
In algorithms textbooks, efficiency and complexity are often used (loosely) as synonyms. Both are often used to refer to the running time of an algorithm. The computation time it takes to run an algorithm *is* a computing resource; it's often the primary resource that elementary algorithms textbooks focus on. The complexity of a problem is the minimum running time (or minimum amount of resources, more generally) needed to solve some particular problem -- so a very similar notion.

At this stage, don't get too caught up in trying to understand the precise definition of words like efficiency and complexity or trying to understand what the distinctions between them are. Odds are, the textbooks are using them in a loose sense and not trying to draw any particular distinctions between the two. Your time is probably better spent learning how to figure out the running time of an algorithm (such as the algorithm to multiply two numbers). The names you assign to concepts are often less important than understanding the concepts and techniques themselves. There are formal definitions of what is meant by "complexity" but sometimes people use complexity and efficiency in informal/imprecise ways, which might explain why what you read didn't seem 100% consistent.

See also What is the difference between an algorithm, a language and a problem?, Meaning of complexity of a computational problem, and https://en.wikipedia.org/wiki/Computational\_complexity\_theory.
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: Efficiently determine relative ordering between two elements in a PO-set
What algorithms/heuristics exist for efficiently determining the relative order between two elements in a partially ordered set?

In my case, the PO-set is stored as a directed acyclic graph where an edge is an `happened before` relation and I am streaming live data into this PO-set. Nodes usually have less than 5 backward edges, with 1 being the most common, and there will be at most 10^6 nodes. The newly inserted nodes usually have edges to the previously most recently inserted nodes.

I am usually doing this query just after I've added a node to the graph, to find the relative ordering between the inserted node and a few select other nodes, so the traversal paths tend to overlap a lot. I am also maintaining a total order of the PO-set as I go, which might be useful for this as well.

My current solution consists of starting at both nodes and moving backwards one step at a time from both simultaneously (or rather, one step for the left node, then one step for the right) until I find a common ancestor node, or run out of edges to traverse. This is not very fast, but I don't have that many elements in the set yet so it works for now.

The main problem is the worst case runtime of `O(n)` as `n` will grow in the future. Is there a way to do this faster?

# Answer
> 1 votes
This is the dynamic reachability problem for DAGs, where you only need to handle vertex/edge insertion (but not deletion). It's sometimes known as incremental reachability or incremental DAG reachability.

There's lots written in the research literature on the subject. Here are some pointers to get you started:

---
Tags: sorting, partial-order
---


# Question
Title: Sum of 2^Pi mod 1000000007 for all i where Pi is sum of numbers in ith subset of a set X
I am stuck on a problem in which I have to print **sum of 2Pi mod 1000000007** for all **i** where **Pi** is sum of numbers in **i**th **subset** of a **set X**.

**Length of set** can be upto **100000**.

**Value of element** in the range **\[0,1012\]**.

Here's the link of the Problem. Problem Statement

I could not find any approach other than Brute-Force which gives verdict TLE.

@Moderators,admins etc. Before putting this question on hold or marking off-Topic or closed.... Please comment the reason so that I can know the reason and if possible reword it or ask on any other StackExchange Site. I first posted it on codegolf.stackexchange.com and people(moderators) there have suggested me to post it here as it comes under algorithm category.

You can read about it here.

Programming Puzzles and Code golf

Thank You

# Answer
> 4 votes
If the set you're using is $X=\\{x\_1,x\_2, \dotsc,x\_n\\}$, then the expression you want to evaluate is equivalent to $$ (2^{x\_1}+1)(2^{x\_2}+1)\dotsm(2^{x\_n}+1)\bmod{1000000007} $$ This isn't too hard to prove; here's an example to help you see what's going on:

Suppose $X=\\{a,b,c\\}$. Then the subsets of $X$ are, obviously, $$ \\{\\},\\{a\\},\\{b\\},\\{c\\},\\{a,b\\},\\{a,c\\},\\{b,c\\},\\{a,b,c\\} $$ and the corresponding sums of elements in those subsets will be $$ 0,a,b,c,a+b,a+c,b+c,a+b+c $$ leading to the sum $$ 2^0+2^a+2^b+2^c+2^{a+b}+2^{a+c}+2^{b+c}+2^{a+b+c}=(2^a+1)(2^b+1)(2^c+1) $$ The general result can be established by a fairly simple induction proof.

---
Tags: discrete-mathematics, sets
---