# Question
Title: Arithmetic network to compute floor of binary logarithm
I wonder how to build efficient arithmetic network (using logical gates only) to compute floor of binary logarithm of the given input number. I have read some articles on stackoverflow.com about this problem, respectively its implementation in C/C++ using bitwise operations only.

Stackoverflow: Computing the floor of log\_2(x) using only bitwise operators in C
Stackoverflow: Computing the floor log of a binary number
Bit Twiddling Hacks
I am pretty sure there's a simpler way to get this done. Using De Bruijn sequences seems to be a magic for me.

# Answer
> 9 votes
It can be done with a fairly simple log-depth circuit without resorting to such hacks that only really make sense in software.

The "position of most significant set bit" function `pmsb` can be defined recursively:

$\begin{split}pmsb(\`\`0") &= Nil \\ pmsb(\`\`1") &= Nil \\ pmsb(a:b) &= \`\`0":pmsb(b) \text{ if a=0}\\ &= \`\`1":pmsb(a) \text{ otherwise} \end{split}$

Where `:` divides a power-of-two string down the middle or concatenates two strings, depending on its context.

This can already be implemented as a circuit, but it includes some annoying wide comparisons. They can be removed by returning a tuple with an extra bit that tracks the zero-ness of the whole string (it is applied to the halves so you get the result from the halves in the recursion):

$\begin{split}pmsb(\`\`0") &= (Nil, T) \\ pmsb(\`\`1") &= (Nil, F) \\ pmsb(a:b) &= \text{let } (pa, za) = pmsb(a) \\ &\phantom{=}\quad\quad (pb, zb) = pmsb(b) \\ &\phantom{=}\\;\\; \text{in if } za \text{ then } (\`\`0":pb, zb)\\ &\phantom{=}\quad\quad\quad\quad\text{else } (\`\`1":pa, F) \end{split}$

This can then be evaluated bottom-up by a circuit of depth O(log n) and size O(n) where n is the length of the bit-string at the top level, which must be a power of two and not one. The zeroness bit circuit has the structure of an AND-reduction, but it is used at the intermediate nodes instead of only at the end. The main result is computed by a similar tree of MUXes that take those bits as control input.

# Answer
> 6 votes
The floor of the binary logarithm of $n$ is the integer $i$ such that $2^i \leq x \< 2^{i+1}$. This is also the leftmost (most significant) 1 in the binary expansion of $x$. If $x = x\_{n-1} \ldots x\_0$, then the answer is $i$ if $x\_{n-1} = \cdots = x\_{i+1} = 0$ and $x\_i = 1$. This leads to a simple circuit that computes $i$.

---
Tags: arithmetic
---


title: Prove longest path shares two points

text:
# Question
Title: Prove longest path shares two points
If there are two longest paths in a connected graph with path lengths of 79 (going through 80 vertices each). How can I prove that they share more than 1 vertex.

# Answer
If they only cross at a single vertex $v$, consider the distance from that $v$ to the four path ends. Since the lengths are odd, $v$ can not be in the exact middle of the paths. But then, are the paths really the longest ones?
> 0 votes

---
Tags: graphs
---


# Question
Title: Continuation-passing style: what is meant by "CPS'ing"?
I'm reading Dijkstra Monads for Free for a presentation I'll be doing and it's pretty meaty. One of the things that I keep running into is the term "CPS'ing". I've read a little bit on continuation-passing style (i.e., I've read through most of the Wikipedia page and it didn't feel like utter nonsense...) but I'm still not clear what the phrase "CPS'ing" means.

They give an example, which I will duplicate here, after which I will present the main pattern I see:

> Rather than being given manually, we show that these predicate transformers can be automatically derived by CPS'ing purely functional definitions of monadic effects (with answer type `Type`). For instance, rather than defining `WP_ST`, one can simply compute it by CPS'ing the familiar `ST` monad (i.e., `state -> a * state`), deriving
>
> ```
> WP_ST a = ((a * state) -> Type) -> state -> Type
>
> ```

(For context, this can be found on page 1, first full paragraph at the top of the second column).

So there is a pretty obvious pattern here: Given some type

```
a1 -> a2 -> ... -> an

```

we can map it via the contraviariant functor `F (a -> b) = (b -> a)` that just reverses the arrows, yielding

```
an -> ... -> a2 -> a1

```

and then replacing each `ai` with `(ai -> Type)`.

Is this a reasonable interpretation of the term "CPS'ing"? Also, it's not clear to me why this is useful - is there any motivation for what is gained by applying such a transformation?

# Answer
I had only a quick look at the paper, but I believe that they are referring to moving from $$ t\_1 \to t\_2 \cdots \to t\_n $$ to $$ t\_1 \to t\_2 \cdots \to \lnot \lnot t\_n $$ where $\lnot t = (t \to r)$ for some fixed return type $r$. In the paper, they choose $r = \sf Type$. So, we get $$ t\_1 \to t\_2 \cdots \to (t\_n \to {\sf Type}) \to {\sf Type} $$ In the case of the state monad we get $$ state \to ((a \times state) \to {\sf Type}) \to {\sf Type} $$ which is isomorphic to (exchanging the order of the arguments) $$ ((a \times state) \to {\sf Type}) \to state \to {\sf Type} $$

Anyway, Sect. 2.3 of the paper shows the actual transform.
> 3 votes

---
Tags: software-verification, hoare-logic, continuations
---


title: Why is $\mu$ finite looping?

text:
# Question
Title: Why is $\mu$ finite looping?
It is said that the intuitive meaning of $\mu$ is finite looping where as the intuitive meaning of $\nu$ is infinite looping in $\mu$ calculus. I understand this for finite systems, but why is this true in general?

Is there any theorem which proves this ?

# Answer
> It is said that the intuitive meaning of μ is finite looping where as the intuitive meaning of ν is infinite looping in μ calculus

Here's a better phrasing: µ is about looping with a known bound on the number of iteration. For ν we do not necessarily know the bound, and there may in fact not even be one.

> Is there any theorem which proves this ?

Theorems can not prove how apt an intuition is. The property you have in mind follows from the definitions and can be illustrated by some examples.
> 1 votes

---
Tags: computability, mu-calculus
---


title: Show that 0^n1^n is decidable

text:
# Question
Title: Show that 0^n1^n is decidable
I would like to know how would one go about and answer this question. I know that a language is decidable if a turing machine exists that accepts the strings in that language, and rejects otherwise. Would I need to create a turing machine to show this or is it enough to create a PDA and claim a TM can be created from a PDA such that it accepts and halts all strings in it and rejects otherwise. Also, if anyone can refer a good post to learn how to create a PDA from CFL would be greatly appreciated. Thanks!

# Answer
> 0 votes
If a language decidable by a PDA then it is also decidable by a TM. In other words TM are more computationally powerful than PDA, i.e., the class of languages decidable by PDA is a proper subclass of the class of languages decidable by TM. You can also easily simulate a PDA on a TM.

However not all languages are decidable by PDA. So your approach does not work in general.

As to CFG to PDA conversion I would recommend the textbook by Sipser (pg 116). Google search for "CFG to PDA" also gives a good result.

---
Tags: computability, turing-machines, undecidability, pushdown-automata
---


title: How was Idris' `rewrite` implemented?

text:
# Question
Title: How was Idris' `rewrite` implemented?
I know in Agda, `rewrite` is a syntax sugar that desugars to a `with` abstraction.
For example, if we have (I'm using the `Data.Vec` from the standard library):

$$ \DeclareMathOperator{Set}{Set} \DeclareMathOperator{xs}{xs} \DeclareMathOperator{where}{where} \DeclareMathOperator{proof}{proof} \DeclareMathOperator{data}{data} \DeclareMathOperator{rev}{rev} \DeclareMathOperator{ff}{ff} \DeclareMathOperator{lemma}{lemma} \DeclareMathOperator{intro}{intro} \DeclareMathOperator{id}{id} \DeclareMathOperator{refl}{refl} \DeclareMathOperator{params}{params} \DeclareMathOperator{Vec}{Vec} \DeclareMathOperator{rewrite}{rewrite} \DeclareMathOperator{with}{with} \DeclareMathOperator{revrevid}{revrevid} \begin{align\*} & \revrevid : \forall \\{n \ m\\} \\{A : \Set n\\} (a : A) (v : \Vec A \ m) \rightarrow \rev (v \ {:}{:} ^r a) \equiv a \ {:}{:}\rev v \\ & \revrevid \ \\\_ \ \[\] = \refl \\ & \revrevid \ a \ (\\\_ \ {:}{:} \ \xs) \ \rewrite \revrevid \ a \ \xs = \refl \end{align\*} $$

This will be desugared to:

$$ \begin{align\*} & \revrevid : \forall \\{n \ m\\} \\{A : \Set n\\} (a : A) (v : \Vec A \ m) \rightarrow \rev (v \ {:}{:} ^r a) \equiv a \ {:}{:}\rev v \\ & \revrevid \ \\\_ \ \[\] = \refl \\ & \revrevid \ a \ (\\\_ \ {:}{:} \ \xs) \with \ \rev (\xs \ {:}{:}^r \ a) \ | \ \revrevid \ a \ \xs \\ & ... \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ {.}(a \ {:}{:} \rev \xs) \ | \refl = \refl \end{align\*} $$

But in Idris, there's nothing like a `with` abstraction, or a dot pattern (which are available in Agda).
So how does Idris' `rewrite` implemented? Is that just a syntax sugar or a language feature which cannot be implemented in pure Idris code?

# Answer
I talked to be5invis and he said it's implemented using `replace`.

`replace` is something like this in Agda: $$ replace : \forall \\{a \ b\\} \rightarrow (a \equiv b) \rightarrow P \ a \rightarrow P \ b $$ or, using universal polymorphism: $$ replace : \forall \\{n\\} \\{a \ b : Set \ n\\} \rightarrow (a \equiv b) \rightarrow P \ a \rightarrow P \ b $$

This is obvious, in both Agda and Idris.

And we use it like this:

$$ \begin{align\*} & proof : \ (a \equiv b) \rightarrow P \ a \rightarrow P \ b \\ & proof \ theory \ pa = replace \ theory \ pa \end{align\*} $$

While `rewrite in` is just a mixfix version of `replace`, so, the code above can be written like this:

$$ \begin{align\*} & proof : \ (a \equiv b) \rightarrow P \ a \rightarrow P \ b \\ & proof \ theory \ pa = rewrite \ theory \ in \ pa \end{align\*} $$

In conclusion, `rewrite` is syntax sugar which desugars to `replace`, while `replace` is a library function that can be implemented by anyone.
So there's nothing special.

Actually, Idris desugars it to a function like this:

```
rewrite__impl : (P : a -> Type) -> x = y -> P y -> P x
rewrite__impl P Refl prf = prf

```
> 4 votes

---
Tags: formal-languages, term-rewriting
---


# Question
Title: Is $Ω(n\log n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?
Is $Ω(n\log n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?

If the latter, is it possible for there to be general-purpose sorting algorithms which perform better than $Ω(n\log n)$?

General-purpose, for example, means you aren't assuming elements have a fixed number of bits.

The input to the algorithm is a sequence of $n$ bits. The bits are an encoding of integers.

# Answer
Integers can be sorted in $o(n\log n)$ time, depending on your exact computation model – see Wikipedia. Going in the other direction, the $\Omega(n\log n)$ lower bound also holds for algebraic decision trees (so for example, comparing sums of elements doesn't enable you to get an $o(n\log n)$ algorithm). See for example Erickson's Lower bounds for external algebraic decision trees, which considers an even more general model.

As a further comment, if all you are assuming about your elements is that they are comparable, then all you can do is compare them, and so you get comparison-based sorting. In that sense your question isn't really well-defined, since you are not explaining which operations on your elements are legal.
> 4 votes

# Answer
O($n$ $log$ $n$) lower bound complexity assumes the length of each key bit is constant. If not, then in the worst case you must compare nearly all bits, and multiply the complexity by that length and get O($kn$ $log$ $n$)

In contrast, some non comparison sorts with arbitrary key lengths can be done in worst case O($kn$).

EDIT: To add more detail:

For Counting Sort, the worst case and average case are O($n+r$) where $r$ is the range of keys (max - min).

For LSD Radix sort the worst case and average case are O($n+k/d$) where $k$ is the key length and $d$ is the digit size.

You mention that there is no limit on key bit length. It would seem that LDS Radix has better worst case performance: $O(k(n+ln\ n))$ \> $O(n+k/d$), putting aside other factors such as space.
> 5 votes

# Answer
It is lower bound for all comparison based algorithms. Non-comparative algorithms such as Counting sort may work in linear time.
> 1 votes

# Answer
Another example for a linear time sorting algorithm is Bucket Sort when used with (strongly) limited keys.
> 1 votes

---
Tags: algorithms, complexity-theory, sorting, lower-bounds
---


# Question
Title: Why postfix arithmetic expression is not ambiguous?
A binary tree can be written as an expression, no matter prefix, postfix or infix.
But why an infix expression needs brackets, while the others don't?

Say, why postfix, prefix produce only one binary tree, while infix can produce many (and become ambiguous)?

I'm looking for a formal proof...

# Answer
> 4 votes
With operator precedence infix is not ambiguous. Brackets are a convenience but not necessary to form an expression. However when parsing you have to resolve each precedence level in precedence order (e.g., $^,\[\*,/\],\[+,-\]$).

A postfix expression is written exactly in computation order: $e0\ e1\ o1\ ... (ek\ ok) ... eN\ oN$ Computation is

* $r\[1\] = o1(e0,e1)$
* ...
* $rk = ok(r\[k-1\],ek)$
* ...
* $rN = oN(r\[N-1\],eN)$

Infix is subjectively thought by many to be easier for humans to read and write.

There is no reason why brackets couldn't be added to postfix or prefix with the obvious meaning, but it is generally not done as those formats are intended for machines rather than humans.

---
Tags: binary-trees, ambiguity, syntax
---


# Question
Title: How do proof assistants nowadays avoid floatpoint error?
I heard that Coq is using "Dedekind cut", but how's that related to floatpoint errors?

Can we just use something like

```
data Q : Type where
  div : N -> N -> Bool -> Q

```

To replace all usages of floatpoint numbers?

# Answer
> 3 votes
It depends on whether you want to "simply" reason about the properties of real numbers, or if you want to perform actual calculations.

If you want to prove things about their general properties, then using Dedekind cuts is feasible.

If you want to compute actual numerical things, then you need a numerical representation of the cut, and then you're back to some computable representation of (some of) the reals (you can't get all of them). It doesn't strictly have to be floating point numbers - you could use arbitrary precision arithmetic for example - more accurate but slower in general.

Your type however seems to be aiming to represent the Rationals, for which floating point numbers are unnecessary, you could just have a type with one constructor: `nat -> nat -> Q`.

---
Tags: floating-point
---


title: Effectiveness of TLB

text:
# Question
Title: Effectiveness of TLB
This is a book question:

> Suppose that a machine has 48-bit virtual addresses and 32-bit physical addresses.
>
> Suppose this same system has a TLB (Translation Lookaside Buffer) with 32 entries. Furthermore, suppose that a program contains instructions that fit into one page and it sequentially reads long integer elements from an array that spans thousands of pages. How effective will the TLB be for this case?

Answer: I think that we cannot know the effectiveness of the TLB because we do not know the number of instructions the program has. I hope I make sense.

source: Modern Operating Systems Question 15, chapter 3 ISBN-13: 978-0-13-359162-0

# Answer
Assuming size of long is $32$ bits, each page frame in physical memory exactly contain $1$ long number, therefore in $TLB$ at particular instance of time $31$ long integers would be present. Hence, $1$ page fault in every $32$ memory accesses. Now, I am not sure what is criteria of effectiveness here. But $1$ per $32$ memory access seems pretty good.
> -1 votes

---
Tags: operating-systems, memory-management, paging
---


# Question
Title: Why is the target function minimized at (0,0) if I can get to a negative number?
I just started learning LP and I saw this Q in my textbook:

$$ min : -x -y \\ S.T. : x + 2y \le 3, 2x +y \le 3, x \ge 0, y \ge 0 $$

It is easy to see that the polygon created from these constraints can't have a negative coordinate. In my textbook it says the answer is $(0,0)$ since $-0 -0 = 0$ and this is the minimum value of the target function (i.e. $f(x,y) = -x -y$).

Why is that the minimum? If I choose any other values (S.T. the constraints are satisfied) I can get, for example, $(1,1)$ which will result in $-1 -1 = -2 \< 0$!

Another thing that I don't understand - would there be a difference if my function was different? If the min is $(0,0)$ - wouldn't it be the case for any other $f(x,y) = a\*x + b\*y$ for any other $a,b$?

# Answer
> 2 votes
Is easy to prove that $(0,0)$ is the maximum of your suggested target function, so it may be an errata of your text.

Your second question is way more interesting, the answer is no, if you change your target function to another linear function the maximum or minimum may change, suppose you change your target function to $x+y$, the minimum now is $(0,0)$, previously it was $(1,1)$.

However, as you suggested in the comments, if you only change your function by a positive scaling factor $a$, the maximum/minimum remain the same. This is easy to prove as $$\alpha\leq \beta\iff a\alpha\leq a\beta$$ holds (I leave the details to you).

In general, there are branches of linear programming called "postoptimization" and "sensitivity analysis" in which your second question is studied in detail, for example, describing algorithms to obtain an optimal solution of the same problem for various target functions in almost the same running time of solving just one problem.

---
Tags: linear-programming
---


# Question
Title: Why the number of adresses stored on RAM is equal to $2^x$ when has "x" adress lines?
I know that a RAM when has 20 adress lines can store up to 2^20 data. I don't know the reason. What is that for and how?

On the image, where and what is the 2^20?

# Answer
$2^{20}$ "data" is rather a vague value. If you have 20 bits for address lines you can possibly have $2^{20}$ combinations. If each address line represent 1 bit of data then you've got total $2^{20}$ bits of data to store in a memory. However most machines store 1 byte of data for every address combination giving you $2^{20}$ bytes or $1$ MB
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Rooted Binary Tree - Chain Nodes Algorithm
The question is that I have to give a recursive algorithm in pseudocode, that counts the number of chain node in a rooted binary tree. Chain node is defined as a node that has only one child and that child is not a leaf. I am stuck any help would be appreciated, so far I have done this:

```
Algorithm Chainnode(x) {
    if (not Leaf(x)) and (left[x] XOR right[x] == Null) {
        return True
    }
    else {
        return False
    }
}

Algorithm ChainnodeCount(x) {
    i = 0
    if (x == Null or Leaf[x]) then {
        return i
    }
    else if ChainNode(left[x]) == True {
        i = ChainNodeCount(left[x]) + 1
    }
    else if ChainNode(right[x]) == True {
        i = ChainNodeCount(right[x]) + 1
    }
    else {
        i = ChainNodeCount(left[x]) + ChainNodeCount(right[x])
    }
}

```

# Answer
The number of chain nodes of a rooted binary tree with two non-empty sons is the sum of the chain nodes in its sons.

Also, the number of chain nodes of a rooted binary tree with only one non-empty son is the number of chain nodes of the son plus one.

If a rooted binary tree has no non-empty sons, its number of chain nodes is zero.

And finally, the number of chain nodes of an empty rooted binary tree is zero.

So, following this properties we have

```
int chainNodes(tree T) {
    if (T is empty)
        return 0;
    if (T has no nonempty sons)
        return 0;
    if (T has only one nonempty son)
        return chainNodes(son)+1;
    if (T has two nonempty sons)
        return chainNoodes(leftSon)+chainNodes(rightSon);
}

```

which is similar to your try.
> 1 votes

---
Tags: algorithms, binary-trees, binary-search-trees
---


# Question
Title: Do we need regular expression first or finite state automata in lexical anlysing?
I'm a bit confused about the concept of finite state automata (FSA) and regular expression (RE) in lexical analysis. I have reading some books about compiler construction. At the part of tokenization, all the books I read talk about the regular expression first to recognize the tokens. For example, the regex below is to recognize the `identifier`:

```
([a-zA -Z] | _ | $ )([a-zA -Z0 -9] | _ | $)*

```

Then, they jumped to explain another technique which is finite state automata (FSA). As a result, some questions have come to my mind which are:

1- What part I should learn first? RE or FSA?.

2- Programmatically, which part should be converted to other to build the lexer? RE ==\> FSA or FSA to RE.
3-Since all tokens can be recognized by regular expression, then, why we need finite state automata?.

Sorry for the to many questions, but I really can't figure out how to start. many thanks in advance.

# Answer
> 0 votes
A regular expression is a language used to describe a finite state automaton. It allows you to define the fsa without drawing nodes and edges all over the place. The two go hand in hand in that regard.

---
Tags: finite-automata, regular-expressions, compilers, lexical-analysis
---


# Question
Title: Terminology for property of recursion definitions
I have a question about generally accepted terminology (and whether it exists at all).

Some recursive algorithms on hierarchical data structures (trees) have the property that they are expressed as a function which does a single recursive function call on each of its children, and that this call takes no parameters other than the child node.

Example in Python:

```
def sum_of_values(node):
    result = node.value
    for child in node.children:
        result += sum_of_values(child)
    return result

```

Other algorithms do not have this property, and fundamentally cannot have this property.

Consider, for example, a mechanism for pretty-printing an AST, which has the property that we want the first child of any node to be displayed on a single line, but all the other nodes on their own line.

Also sketched in Python, leaving out many details (e.g. indentation):

```
def pretty_print(node, single_line_mode=False):
    if single_line_mode:
        return "(" + " ".join([pretty_print(child, True) for child in node.children]) + ")"

    result = "("
    if len(node.children) >= 1:
        result += pretty_print(node.children[0], True)

    for child in node.children[1:]:
        result += "\n" + pretty_print(child, False)

    result += ")"
    return result

```

The key point of the above is: The recursive call contains more information than simply the fact that some work must be done recursively. This information flows from the structure higher up in the tree (in this case: whether the some node in the path of presently printed node to the root of the tree is the first child of its parent).

If we were to rewrite the above by replacing the boolean parameter with 2 functions, our algorithm is no longer expressed in terms of a single recursive function call for each on each of the children.

So we can see a distinction: algorithms in which we can do calculations for constituent parts of a composite data structure independently from the data structure of which they are a part, and those for which this is not possible.

Is there an accepted terminology for this distinction?

Edit to add:

In the context of parallel computing, recursive definitions of the first kind (no additional parameters in the recursive call) are automatically Embarrassingly Parallel

# Answer
This sounds to me like a Catamorphism, specifically, a Tree Fold. If you're familiar with the foldr list function of functional programming (I believe Python has this too), this is also a catamorphism.

In general, the categories functions are divided into like this are called recursion schemes. The classic introduction to them is Bananas, Lenses, Envelopes and Barbed Wire. If you're familiar with Haskell, the modern translation guide might help.

Some more information is provided in the Origami Programming paper.
> 2 votes

---
Tags: algorithms, terminology
---


# Question
Title: Minimum pumping length of regular language
I know the method to the find the minimum pumping length of regular language by constructing minimal DFA and finding the number of states but I am not able to quite understand why is it working.

For example, $L = (10)^\*$. Here minimum pumping length is 1 by constructing DFA. But by pumping lemma, how can there be a string of length 1 belonging to $L$? As pumping lemma says the string $S$ should be such that $|S| \le p$ and $S$ should belong to $L$, where $p$ is the pumping length, and here there is no string of length 1 belonging to $L$.

# Answer
> 1 votes
Your example in fact demonstrates that the pumping length can be smaller than the number of states in the minimal DFA. In your case the minimal DFA contains 3 states, but the pumping length is 2.

The pumping length of a language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be written as $w = xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$.

If $L$ contains no words of length $p$ that's not problematic at all. For example, the pumping length of $\\{ w \\}$ is $|w|+1$. In that case the pumping property holds vacuously.

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Why polynomial time is called "efficient"?
Why in computer science any complexity which is at most polynomial is considered efficient?

For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms that run in time, say, $n^{80}$, but the first is considered inefficient while the latter is efficient. Where's the logic?!

(a) Assume, for instance, the number of atoms in the universe is approximately $10^{80}$.

# Answer
> 34 votes
Another perspective on "efficiency" is that polynomial time allows us to define a notion of "efficiency" that doesn't depend on machine models. Specifically, there's a variant of the Church-Turing thesis called the "effective Church-Turing Thesis" that says that any problem that runs in polynomial time on on kind of machine model will also run in polynomial time on another equally powerful machine model.

This is a weaker statement to the general C-T thesis, and is 'sort of' violated by both randomized algorithms and quantum algorithms, but has not been violated in the sense of being able to solve an NP-hard problem in poly-time by changing the machine model.

This is ultimately the reason why polynomial time is a popular notion in theoryCS. However, most people realize that this does not reflect "practical efficiency". For more on this, Dick Lipton's post on 'galactic algorithms' is a great read.

# Answer
> 27 votes
In theory, we care for the asymptotic behaviour, and describe classes of problems and algorithms based on their asymptotic behaviour. The keyword here is *asymptotic*. $O(n^{80})$ is faster than $O(n^{\log n})$ asymptotically, i.e., starting from $n \> 1208925819614629174706176$ (which by the way is called: septillion!), assuming unit constant coefficients, and no low-order terms.

In practice, however, attention is paid to both exponents and constant coefficients. In practices, input sizes can not grow to septillions, so, yes, $n^{\log n}$ for all purposes will be a superior choice to $n^{80}$. Other factors also matter in practices: parallelism, memory access patterns (e.g. locality).

For example, most libraries for integer multiplication, e.g. GMP will implement a mixture of algorithms, and select inferior algorithm based on the input size select the practically superior algorithms based on the input size, though these algorithms might be asymptotically inferior. Some asymptotically "inferior" algorithms will be faster on certain input sizes, and will be selected over the optimal algorithms.

Another example, the fastest matrix multiplication algorithm known is Coppersmith-Winograd algorithm which runs in $O(n^{2.3737})$ (there are recent improvements; more here). However, it was never implemented because (1) it's hard (2) the constant coefficient is gigantic. All linear algebra packages use the less optimal of Strassen.

*TL;DR theory cares for asymptotic behaviour in order to compare algorithms as the limit of input size goes to arbitrarily large numbers.*

# Answer
> 4 votes
This answer will look at the "bigger picture" context of your question. Computer science is actually a relatively young and somewhat open science and it doesn't yet have great or even good answers to some basic & fundamental questions. The basic question "what is efficiently computed" is either *accurately* or *roughly* formalized in CS (depending on opinion) as the famous P vs NP problem (or the closely related P vs Exptime problem), and its still *open* after more than four decades of being initially introduced by Cook/Levin ~1970 and intense work by the worlds greatest computer scientists (and many mathematicians are also interested in the problem as fundamental).

So in other words, even with a *rough* definition of "efficient" as P time, and one of the highest valued scientific awards — namely $1M award attached to the problem for over 10yrs — computer science cannot even prove that some problems (close to this borderline) must or must not have efficient (Ptime) algorithms. Therefore the exact definition of "efficient" more precise than P time is not necessary or even *possible* at this time. If/when the P vs NP conjecture is settled one way or the other, a more strict definition of "efficient" may or presumably will be possible.

Moreover, one might feel that the Ptime definition of "efficient" might even be a bit "sloppy", and most computer scientists would probably agree, and almost all of them think the P vs NP conjecture is of the utmost importance to resolve, to the point that they might even regard this assertion or observation as trivial.... in other words, so to speak, *its a work in progress / we're working on it*. (in fact mainstream computer scientists even go so far, only half-jokingly, to routinely refer to the gap & lack of progress/definitive separations as *embarrassing*.)

In fact there is even a closely related/*significantly stronger* conjecture than P vs NP, namely NP vs P/poly, which also cannot be resolved by computer science at this time. it conjectures that NP-time problems cannot be solved by *any* "P-sized" circuits, ie not even restricted to those circuits that can be created by algorithms/Turing machines.

As for how hard P vs NP may be — there is some solid reason to think it may be *at least as hard* as the very old Riemann conjecture in mathematics (now 1.5 *century* old), because both have had the same $1M award for over a decade, and neither has been solved yet/first.

So in other words, to precisely define what algorithms are really "efficient" is actually one of the *most important & hardest existing open problems in theoretical science and mathematics*.

In fact the question of "what is efficiently computed" is actually even more subtle, because there is a variant of the Church-Turing thesis called the P-time CT thesis, and it is not known if quantum computing actually *violates* it. With Shor's breakthrough result of P-time QM, factoring considered a dramatic twist in this research. In other words, the problem of what is efficiently computed actually plausibly descends all the way to deep physics principles, and relates to whether quantum computing can compute more efficiently than classical computation, which is also a generally open problem in theoretical CS and advanced physics.

So one can even add that P vs NP & the question of efficient computing may be of crucial or fundamental importance to in — addition to CS and mathematics — *physics*.

\[1\] P vs NP problem, wikipedia

\[2\] Millenium prize problems

\[3\] P/Poly class, wikipedia

\[4\] Shor's algorithm

# Answer
> -2 votes
Polynomial time algorithms are considered efficient only in comparison with the hardest non-polynomial time especially the so called NP-Complete. See image: Euler diagram for P, NP, NP-complete, and NP-hard set of problems.

---
Tags: algorithms, complexity-theory, terminology, efficiency
---


# Question
Title: Language Accepted by a Turing Machine with a Useless State?
What language is accepted by a Turing machine which has a state that it does not enter on input I?

Specifically,

1.If the accept state is the state that it never enters then should L={empty}?

2.If the reject state is the state that it never enters then should L={everything}?

3.What if the TM has multiple accept/reject states?

4.What if the state that it never enters is neither the reject nor accept states? How does that affect L?

I have searched around and I have found a couple threads that helped prove that this problem is undecidable but is it Turing-recognizable? Co-Turing Recognizable? Both?

# Answer
The definition of the language accepted by a Turing machine is valid for *all* Turing machines, whether they have useless states or not. Absolutely nothing changes. If there is a useless state, removing it wouldn't change the language accepted by the machine, as does adding another useless state.

Consider a similar question about C programs. What if I have a function which is never called? Does this affect the way the program executes? It doesn't.1 The same holds for Turing machines.

1Actually it might, since you might run out of memory a tiny bit faster.
> 1 votes

---
Tags: formal-languages, turing-machines, automata, reductions, undecidability
---


# Question
Title: Why the restriction on the length of the proof in a $(r,q)$-verifier in PCP is inconsequential?
In the textbook by Arora-Barak, they define PCP verifier as

While in the definition they put a restriction of $q2^r$on the length of the proof, later, they say that it is inconsequential as the machine can look on at most this number of locations with nonzero probability over all $2^r$ choices for its random string.

# Answer
> 2 votes
The formal version of "the limitation on the proof length is inconsequential" is the following:

If $L$ has a $(r(n),q(n))$ PCP verifier, then it also has an $(r(n),q(n))$ verifier with proof length bounded by $q(n)2^{r(n)}$.

The above holds since as you mentioned, the verifier can ask $2^{r(n)}q(n)$ different queries on a length $n$ input ($q(n)$ queries for each possible outcome of the verifier coins). Let $f\_x$ be an embedding (one to one mapping) of the possible verifier queries on input $x$ in the set $\\{1,2,...,q(|x|)2^{r(|x|)}\\}$. Let $V'$ be the verifier who acts like $V$, with the sole difference that when $V$ asks for index $i$, $V'$ requests $f\_x(i)$. It is easy to see that $V'$ is a verifier for $L$ with the same properties, and bounded length proofs.

---
Tags: complexity-theory
---


# Question
Title: Can we add dependent type into an existing imperative programming language?
As we know, dependent type allows programmers to write bugless programs.
But as I know there's only very few languages support dependent type, like Haskell with extensions, Idris, Agda, F\*, etc.

Since these are all functional languages, is there any possibility to add dependent type into an imperative language?

I've googled and found some papers like http://www.ats-lang.org/MYDATA/Xanadu-lics00.pdf or https://www.cs.bu.edu/~hwxi/academic/papers/XanaduAbs.ps, but they create their own languages.

# Answer
> 4 votes
So, it's possible, but there are certainly some barriers:

* What kinds of expressions are allowed in types? What does it mean for a type to have a side-effect? Can typrchecking my program perform IO?
* Just because dependent types are in the system doesn't mean they provide a type safe language. It may be possible to produce proofs of False if the underlying type system is not consistent.
* Many imperative languages don't have type systems complex enough to make dependent types useful. For example, Go has no higher kinded types, so if you can't index types by types, indexing types by values probably won't work.
* Depending on the language, some additional type annotations might be necessary to make type checking decidable.
* It may be hard to interpret dependent types in the context of side effects. What does a value of type $x=y$ even mean if $x,y$ can change their values at runtime? Does this mean a term can be well typed at one point, and dynamically become ill typed? Or can you only use dependent types for immutable values?

I'm sure that imperative dependent types are possible. In particular, I'd keep my eyes on Rust for adding these in a limited way.

But doing dependent types in a pure functional language is just so much easier.

---
Tags: dependent-types, imperative-programming
---


# Question
Title: Extending ordered tree edit distance to DAGs
Computing edit distance (shortest sequence of edit operations) on ordered trees is a well studied problem with many known algorithms (e.g. Zhang & Shasha, RTED). There is also considerable literature on edit distance for general graph (e.g., this review). I am however interested in a mixed case that has arisen in our inquiries into RNA structures in computational biology: how to compute edit distance between directed acyclic graphs (DAGs) with ordered children, i.e. a DAG where each node imposes a total ordering on its outgoing edges. There seem to be multiple ways to define edit operations on such "ordered DAG" but as a first approximation, I don't care about which edit operations are primitive. I was unable to find any literature on this problem.

Is there a known algorithm for edit distance on ordered DAGs (or more general graphs with ordered outgoing edges)? Or can some of the known tree edit distance algorithms be easily extended to cover DAGs?

Note that I cannot defer to algorithms for general graph edit distance as those (AFAIK) don't take order of outgoing edges into account.

# Answer
> 1 votes
So after some thinking and digging around, I know believe (no rigorous proof) that edit distance between ordered DAGs is NP hard (in fact even Max-SNP hard) and thus no efficient algorithm is likely. The informal reasoning follows:

1. Edit distance between RNA structures with pseudoknots is Max-SNP hard and the reduction to Max-Cut works even if we ignore the RNA sequence (Ma, Wang & Zhang, 2002: Computing similarity between RNA structures)
2. One can represent an RNA structure with pseudoknots as a DAG with ordered children and labelled edges by extending the tree representation from Zhang & Shasha 1989: Nodes still represent base pairs and unpaired nucleotides, "normal" edges represent the "is contained in" relationship and new type of edges to represent a "contains only first nucleotide of a base-pair" relationship let us represent crossing base pairs.
3. An algorithm for edit distance on labelled DAGs would therefore likely give an algorithm for Max-Cut which is Max-SNP hard. This obviously depends on what edit operations are allowed, but it seems to work for any sensible set of edit operations I came up with.

---
Tags: graphs, edit-distance
---


title: Dynamic programming tree algorithm

text:
# Question
Title: Dynamic programming tree algorithm
> We have a network of sensors organized in tree form, where the sensors occupy the nodes. Most of the time the sensors are turned off, until the root sensor wakes up the rest of the sensors. This process of awakening the nodes requires a certain amount of time since, in a unit of time, a sensor can awaken only one of its children. Obviously, the total wake-up time for all sensors depends on the order in which each sensor wakes up your children.
>
> It is asked to design an efficient algorithm that gives a sorting of the children of each node in the tree providing the minimum time to wake up all the sensors.

The solution must use dynamic programming.

I have got no clue where to start from; I know dynamic programming exercises are based on suboptimal structure and overlapping problems, and in this case, at least, overlapping problems is quite obvious since the tree structure is used.

Have you got any clue about the underlying recurrence? -- I am not asking you the solution since those are my homework :)

Thanks.

# Answer
> 1 votes
Suppose that the root of the tree has subtrees $T\_1,\ldots,T\_m$, and that you found the optimal wake-up times $t\_1,\ldots,t\_m$ for each of the subtrees (that's the "dynamic programming" part, though I'd just call it recursion). In which order should you wake up the subtrees? If $t\_i \> t\_j$, should you wake $T\_i$ or $T\_j$ first? Use this to come up with a recursive formula for the optimal wake-up time of the tree.

---
Tags: algorithms, trees, dynamic-programming
---


# Question
Title: What is the Code2 and other concepts of variable encoding in Coding Redundancy?
Am learning the concept of Coding Redundancy in image compression and am finding it hard to understand the table on page 3 of this document. All other explanations seem to follow the same symbols and methodology but don't explain the concept clearly.

**Question1:**
In the first column, r1=1/7, r2=2/7 etc and r7 is 1. Why is that? According to the column "Code1", the Code1 is created based on the `r` value which should range from 0 to 7. Why then are there fractions like 1/7, 2/7 etc?

**Question2:**
What is "Code2"? At least for Code1, when the value is 000, I know it is the binary representation of 0. But the same thing in Code2, is 11. I don't understand what and how they are trying to represent with Code2.

**Question3:**
Even if 0 is represented by 11 and 6 is represented by 000001 in variable length encoding, how is the algorithm supposed to know which 0 starts where and which 1 ends where? For example, to represent 60, I'd have to encode it as 00000111. When decoding, how is the algorithm supposed to know that it's 60?

# Answer
> 1 votes
In the first column, $r\_k$ is the gray level. It ranges from 0 to 1, where 0 is 0% white (i.e., black) and 1 is 100% white. There are 8 gray levels arranged in regular intervals of 1/7.

Code 1 and Code 2 are two different ways of encoding the gray level. Code 1 is a fixed-length code (all codewords have the same length) whereas Code 2 is a variable-length code, specifically a prefix code, presumably a Huffman code for the distribution in the second column. Code 2 is better because the expected codeword length is 2.7 bits, which is smaller than the 3 bits that you get with Code 1.

Since Code 2 is a prefix code, decoding it is actually very simple, and requires no lookahead. (That's why prefix codes are sometimes called *instantaneous* codes.)

---
Tags: image-processing, data-compression
---


# Question
Title: Computability of a function and decidability
Let $A$ and $B$ be finite alphabets and let $\\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^∗$ to $B^∗$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x ∈ A^∗$, always halts with $f(x)$ on its tape.

Let $L\_f$ denote the language $\\{x\\#f(x)∣x∈A^\*\\}$.

This is a part of the question and the answer says that if $L\_f$ is recursive then $f$ is computable. If $L\_f$ is recursive then we can accept all the string in the language but we have to reject the strings not in the language. A function is said to be computable when it has a halting Turing machine which computes the value for $f(x)$ for every $x$ in the domain and HALTS.
Then what about the values outside the domain?

# Answer
Since $L\_f = \\{x\\#f(x);x ∈ A^\*\\}$, $f$ must be total, otherwise $L\_f$ isn't defined at all. So, we suppose that $f$ is total.

Let's prove : $L\_f$ is recursively enumerable $=\> f$ is computable. We will use a technic called dovetailing. For the need of the proof, suppose that $c\_i$ denotes the $i^{th}$ element of $A^\*$ (it's a function, we write $c\_i$ instead of $c(i)$ for clarity). We use the lexicographic order to define the $i^{th}$ element of $A^\*$.

$L\_f$ is recursively enumerable, there exists so a Turing machine $M\_{L\_f}$ that, for each input $x ∈ (A \cup\\{\\#\\}\cup B)^\*$, halts if and only if $x ∈ L\_f$. Let's try to define a Turing machine $M$ that computes $f(x)$ foreach $x∈A^\*$. We will just describe this machine, we won't give a formal definition. Let $x$ be the input of $M$, the machine will proceed by this way :

* Execute one step of $M\_{L\_f}$ with input : $x\\#c\_0$. If $M\_{L\_f}$ halts, then $f(x) = c\_0$. Else, continue.
* Execute two steps of $M\_{L\_f}$ on both inputs : $x\\#c\_0$ and $x\\#c\_1$ sequentially. If $M\_{L\_f}$ halts on one of them, let's call it $x\\#c\_i$, then $f(x) = c\_i$. Else, continue.
* Go by this way, at step $i$, $M$ executes $i$ steps of $M\_{L\_f}$ with inputs : $x\\#c\_0, x\\#c\_1 ... x\\#c\_i$. If $M\_{L\_f}$ halts on one of them, suppose it's $x\\#c\_k$, then $f(x) = c\_k$.

Since $f$ is total, $x\\#f(x)$ exists for each $x$. In addition, $L\_f$ is recursively enumerable, so, when $M$ arrives to $x\\#f(x)$, $M\_{L\_f}$ will halt after $k$ steps because $x\\#f(x) ∈ L\_f$. $M$ then computes $f(x)$ for every $x∈A^\*$.

I hope i have explain it well.

To complete the proof, $c\_i$ must be proved to be computable, it's somewhat easy to do.
> 1 votes

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


# Question
Title: How do we derive the runtime cost of Karatsuba's algorithm?
I've read the Wikipedia article explaining the complexity analysis of the Karatsuba algorithm, but I'm not fully grasping it. I seem to have gotten about 75% of the way to the solution on my own, but lack the last 25% to fully understand why the complexity is $O(N^{\log3})$ where the log function is base $2$.

I worked out myself that the recursion tree has height $\log N$ (easy to see), and I understand the coefficient $3$, which can trade places with $N$ due to the properties of logs, comes from the fact that each level of recursion results in three leaves per node of the tree.

I think the main thing that's tripping me up is I'm that not clearly seeing why $\log N$ can be expressed as the exponent of $3$, although I see where $\log N$ and $3$ come from, and I see how in the next step you can swap $N$ and $3$ to get $N^{\log3}$ (something I learned in highschool).

To put this another way, I've been unable to work this problem out to visualize sequentially how this formula plays out for the algorithm. I.E, without already knowing the Master theorem, how does one derive this formula (I assume it's possible) by simply walking through the Karatsuba algorithm and watching the patterns emerge.

**UPDATE: In writing out my understanding of the wikipedia explanation line by line to identify where I got stuck, I finally saw the pattern. However, maybe putting it here will help someone else.**

# Answer
> 3 votes
"Karatsuba's basic step works for any base B and any m, but the recursive algorithm is most efficient when m is equal to n/2, rounded up."

I understood this to mean that for integers with n digits, m is the ceiling of half n (m being the exponent applied to the Base in the algorithm). This can be seen if you simply look at the definition of the algorithm.

"In particular, if n is $2^k$, for some integer k, and the recursion stops only when n is 1, then the number of single-digit multiplications is $3^k$, which is nc where c = ${\log3}$"

I took this to mean, given n is some power of 2 (2, 4, 8, ...), the number of single digit multiplications performed is 3 * (exponent of 2). I worked out how this conclusion was reached by writing out the tree and finding that each sub-problem involves 3 multiplications, and at the base of the recursive tree, you should have $3^{m - 1}$ sub-problems for that bottom level. However, the -1 can be ignored as, using the properties of exponents, you can factor that out into a constant, which Big-O doesn't consider. Therefore, if we are looking for the exponent of 2, we can get that exponent of 3 as a log relative to n, thus $3^{\log n}$, which by a law of logarithms turns into $n^{\log 3}$. Since the computational complexity of each sub-problem by itself is a constant 7 (4 additions and 3 multiplications) independent of the number of digits in the number representation, the computation itself can be ignored in the efficiency analysis, giving us $O(n^{log 3})$

# Answer
> 4 votes
Thank @Josiah for the question and Wiki explanation! To clearly see the runtime of Karatsuba's algorithm for the multiplication of two complex numbers by recursion with Gauss's trick, I would like to add some derivation details:

* Note that the original runtime $T(n) = 3 T(n/2) + O(n)$. By mathematical induction we can observe that $T(n) = 3^{\log n} + O(n)$, where $\log(.)$ is the logarithm with base $2$
* Define $x = 3^{\log n}$. Take $log\_3(.)$ with base $3$ to both sides we have $\log\_3 x = \log n$.
* By logarithm's change of base, $\log\_3 x = \frac{\log x}{\log 3}$ (see Remark below). Thus, $\log x = \log 3 \cdot \log\_3 x = \log 3 \cdot \log n = \log n^{\log 3}$. Hence the result follows: $x = n^{\log 3}$ and the runtime $T(n) = O(n^{\log 3}) = O(n^{1.59})$.

*Remark:* Why $\log\_3 x = \frac{\log x}{\log 3}$?

* Set $y = \log\_3 x$. Thus $3^y = x$ and by taking $\log(.)$ to both sides we have $\log 3^y = \log x$.
* Since $\log 3^y = y \log 3$, we obtain the result: $y = \log\_3 x =\frac{\log x}{\log 3}$.

---
Tags: algorithm-analysis, runtime-analysis, master-theorem
---


title: When are edges adjacent?

text:
# Question
Title: When are edges adjacent?
What conditions must be fulfilled for two edges of a graph to be called adjacent?

I found a lot about adjacent nodes, but our CS course script refers to adjacent edges, with no explanation.

# Answer
> 4 votes
Two edges are adjacent if they're incident on the same vertex:

> Two edges are *adjacent* if they have exactly one common endvertex.
> —Bollobás, *Modern Graph Theory* (Springer, 1998; page 2).
>
> Two edges $e\neq f$ are *adjacent* if they have an end in common.
> —Diestel, *Graph Theory* (2nd Edition, Springer, 2000; page 3).

---
Tags: graphs, terminology
---


# Question
Title: Is impredicative Set consistent with the excluded middle?
While studying Coq, I found a few references that impredicative Set might not work well with classical axioms, in particular the axiom of choice.

I'm working on a dependent type system based on the calculus of constructions (with Prop and Set), on which I intend to add Peirce's law on sets, as in the computability side it represents `call/cc` (capturing/resuming the whole computation).

My question is: is the calculus of constructions\* with an impredicative Set, with the excluded middle working on sets (precisely, `forall P: Set, ((P -> False) -> P) -> P` being of type `Set`), *without the axiom of choice*, consistent? I didn't manage to find a reference for that.

*(\* Would inductive types make any difference, from CoC to CIC?)*

# Answer
> 2 votes
I'm not an expert, but my understating was not that it it was inconsistent, but that it implies proof irrelevance. That is, if $s,t:T$ then $s=t$.

This gives many undesirable properties, like having $1=2$, but I'm not sure it actually implies bottom. This answer had similar details.

---
Tags: type-theory, coq
---


# Question
Title: Game of Nim (Find winning states in large range)
If I want to solve a game of nim with 3 piles containing (x, 2x, 3x) respectively

I know that the solution of (winning) iff x^2x^3x != 0

but if x can be in the range from 1 to 2^61 so How many winning states in this range?

I want to solve this problem ... I tried to find a pattern but I think there is no pattern for that

# Answer
Let $a=a\_{n-1} \cdots a\_0$ and $b=b\_{n-1} \cdots b\_0$ be two positive integers with given binary expansion. Since $z+w = 2(z \land w) + (z \oplus w)$, we have $$ a + b = a \oplus b + 2(a \land b), $$ where $a \oplus b$ and $a \land b$ are bitwise XOR and AND. In particular, $a + b = a \oplus b$ iff $a \land b = 0$.

Consider now the equation $x \oplus 2x \oplus 3x = 0$. We can rewrite it as $x \oplus 2x = 3x = x + 2x$. Above we have seen that this is equivalent to $x \land 2x = 0$. If $x = x\_{n-1} \ldots x\_0$ then $$ x \land 2x = 0 (x\_{n-1} \land x\_{n-2}) \ldots (x\_1 \land x\_0) 0. $$ Thus $x \oplus 2x \oplus 3x = 0$ if the binary expansion of $x$ doesn't contain two adjacent 1s.

It remains to count how many binary strings of length $n$ (in your case, $n = 61$) satisfy this condition. It is a standard exercise to show that the answer is the Fibonacci number $F\_{n+2}$.
> 2 votes

---
Tags: algorithms, game-theory
---


# Question
Title: Computational power difference between all interconnected qubit vs few interconnected qubit
Recently I came across some news that Google and IBM are planning to unveil a 50 qubit quantum computer. I read that in this design, each qubit is not connected to all other qubits rather only to the two nearby qubits(neighours). In layman terms, what difference will this create in terms of the system's computational power?

I can't find the article but the architecture image is below. Hopes that will help.

# Answer
> 1 votes
A linear chain of qubits has two big disadvantages over a planar grid of qubits:

1) **Resilience.** If you arrange your qubits into a line, and *any one* of them doesn't work well, your quantum computer has been cut in half. In a grid you instead end up with a hole that, while inconvenient, can be routed around.

2) **Closeness.** In a linear chain, the qubits are on average farther apart. So if you want to interact two states, it may take longer to swap them towards each other so that they can interact. That being said, in highly parallel algorithms where you're already saturating all the connections with operations, you tend to be able to combine the swaps with the interactions you wanted to do anyways for no extra cost (e.g. see the paper "Quantum Simulation of Electronic Structure with Linear Depth and Connectivity").

---
Tags: quantum-computing
---


# Question
Title: Finding all unique paths from a source to a sink in a specially-formed DAG
Let $G$ be a directed, acyclic graph of order $n$, such that:

1. $G$ has exactly one source vertex $s$;
2. $G$ has exactly two sink vertices $t\_1, t\_2$;
3. The out-degree of any non-sink vertex in $G$ is *exactly* 2; and
4. The longest path from $s$ to either of $t\_1,t\_2$ has length $k$.

What is the most efficient way of finding all unique paths from $s$ to $t\_1$ (or $t\_2$, doesn't really matter in this case) in $G$? What would the time complexity of this algorithm be? It is acceptable to use $k$ as a parameter if that would produce a better analysis.

# Answer
If you are interested enumerating all the unique paths, then a recursion would be suitable since it is a dag. Observe that suppose v is a non source vertex and has incoming arcs from X1,...,Xn then every path from the source through v needs to pass through X1,...,Xn. . So if you enumerated all the paths from the source to each of these vertices you simply need to append v to them to compute all the paths through v originating from the source. This computation can be done very efficiently via dynamic programming. The reason DP will work is precisely because none of the paths from source to X1,...,Xn would have contained v since it is a dag.You should be able to work out the time complexity for the algorithm i described easily since it has a standard dp structure.
> 0 votes

---
Tags: graphs, time-complexity
---


# Question
Title: Time complexity of searching an element in Binary Search Tree
I want to know what will be the time complexity to search, insert and delete an element in a) balanced binary search tree. b) unbalanced binary search tree.

# Answer
> 1 votes
Best case time complexity for search, insertion, and deletion is `O(log n)`. This would correspond to a balanced tree.

The worst case is `O(n)`. This would correspond to the unbalanced tree

# Answer
> 0 votes
In addition to user9023727's answer, the time complexity for insert and delete is dependent on the time complexity of the search function. This is because for insert you need to find the correct position to insert, and for delete you need to find the node of the value you are deleting.

---
Tags: algorithm-analysis, data-structures, runtime-analysis, binary-search-trees
---


# Question
Title: Complexity of 1-in-3 SAT variant with restrictions on "unique" variables per clause
I'm interested in the complexity of a particular variant of 1-in-3 SAT. Assume, as is usual, that clauses are allowed to be of length 1, 2, or 3. Then add the restriction that for any clause of length 3, at least one variable must be "unique," meaning it must appear in no other clause.

Another way to phrase this is, for each clause, at most two variables can be "non-unique" and appear in other clauses.

What is the complexity of this variant of 1-in-3 SAT?

# Answer
This variant of 1-in-3 SAT is polynomial time solvable. I will try to show this using the fact that 2-CNF-SAT is polynomial time solvable: wikipedia 2-SAT. (There may be better ways or more efficient algorithms for this particular problem)

Given a special 1-in-3 sat formula $F$, do the following:

* Keep the size-1 clauses
* Replace any size-2 clause $(\ell\_1, \ell\_2)$ by formula $(\ell\_1\vee \ell\_2) \wedge (\neg \ell\_1 \vee \neg \ell\_2)$
* For a size-3 clause $(\ell\_1,\ell\_2,u)$ where $u$ is unique to this clause: replace it by $(\neg \ell\_1 \vee \neg \ell\_2)$

It is easy to see that this results in a 2-CNF formula, let's call it $F'$. Use your favorite way to solve 2-SAT to find out whether $F'$ is satisfiable.

Verify that the original 1-in-3 SAT formula is satisfiable, if and only if $F'$ was satisfiable. (If this needs more explanation let me know)
> 1 votes

---
Tags: complexity-theory, np-complete, logic, satisfiability
---


title: Lexical analysis and reserved words

text:
# Question
Title: Lexical analysis and reserved words
My book says lexical analysis detects reserved words.

How can lexical analysis detect whether we are using reserved words in incorrect places ?

For eg :- while(a\>0) and int while = 5.

How can lexical anaylsis differentiate the usage of while in both the above examples based on the context?

# Answer
Briefly, lexical analyzer reads source code character by character and generates tokens. It does not care about in what order tokens are generated. Relationship between tokens are checked by syntax analyzer and specified by a context free grammar. Let me give you a simple example. Consider the following piece of code

```
 int while = 5

```

Lexical analyzer emmits the following tokens:

KEYWORD (INT)
KEYWORD (WHILE)
ASSIGN (=)
NUMBER (5)

Then then syntax analyzer checks these tokens, detects (based on the corresponding CFG) that the keyword WHILE cannot be lvalue, and reports the syntax error. In fact the syntax analyzer expects IDENTIFIER after the token KEYWORD (INT).
> 1 votes

---
Tags: compilers, lexical-analysis
---


# Question
Title: Closest-point heuristic approximation problem
I have an Approximation Algorithm problem and its answer but I am having a hard time to clearly understand.
The problem is as follows:

> Consider the following closest-point heuristic for building an approximate traveling-salesman tour whose cost function satisfies the triangle inequality. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex $u$ that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest $u$ is vertex $v$. Extend the cycle to include $u$ by inserting $u$ just after $v$. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.

The answer is (I apoligize for including an image but I couldn´t get the some special characters displayed correctly)

What I do not understand is the part surrounded by the red rectangle. I will very much appreciate if you help me to get the idea behind it. I am studying for an exam and I am stuck with this problem.

Respectfully,
Jorge Maldonado

# Answer
> 5 votes
I think there's some problem with the LaTeX formula. It should look like this:

$c(H\_i)\leq c(H\_{i-1})+2c(u\_i, v\_i)$

Let's say initially it was $u\to x$. Then you add $v$ directly after $u$, forming $u\to v\to x$. This increases the total distance by $c(u,v)+c(v,x)-c(u,x)$. From the triangle inequality, we have $c(u,v) + c(u,x) \geq c(v,x)$ and thus $2c(u,v)\geq c(u,v)+c(v,x)-c(u,x)$, hence $c(H\_i)\leq c(H\_{i-1})+2c(u\_i, v\_i)$.

The next paragraph should make more sense now.

---
Tags: approximation
---


title: Reducing Exact Cover to Subset Sum

text:
# Question
Title: Reducing Exact Cover to Subset Sum
> Show that the subset sum problem (Given a sequence of integers $S=i\_1, i\_2, \dots , i\_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete.
>
> Hint: Use the exact cover problem.

The exact cover problem is the following: Given a family of sets $S\_1, S\_2, \dots , S\_n$ does there exist a set cover consisting of a subfamily of pairwise disjoint sets?

First of all, to show that this problem is in $\mathcal{NP}$ do we have to do the following?

A nondeterministic Turing machine can first guess which the subsequence of that we are looking for is and then verify that it sums to exactly k in linear time. Is this correct?

To show that it is NP-complete how could we reduce the exact cover problem to subset sum? Is it as follows?

The exact cover problem has a solution iff every element is in exactly one set.

We consider the set $S$ and the number $k$ such that each number corresponds to a set of elements and $k$ corresponds to the whole set. Suppose there are $n$ elements and $k$ different sets.

We replace each set S with a number that is $1$ in its ith position if i is in S and has a $0$ in its ith position otherwise.

We set k to a number that is $n$ copies of the number $1$.

# Answer
> 6 votes
**Basic idea**: In the exact cover problem, each element is reduced to a number. Then, each set is reduced to the sum of the numbers it covers. Finally, set $k$ to be the sum of all numbers.

This reduction always works one way: If a solution exists for the exact cover problem, a solution also exists for the subset sum problem.

The hard part is to prove the other way. Trivial numbers don't work. Suppose the elements are reduced to $1,2,3,4$, and the sets are

* $S\_1=\\{3,4\\}$
* $S\_2=\\{3\\}$

The reduction to subset sum is the numbers $7,3$ and $k=10$, which return YES but there's no solution to the exact cover problem!

We need to be smarter in choosing the numbers. Noticed the flaw in the previous numbers is that $3$ can *replace* $1,2$. We don't want any number to be replaced. Hence, we want the numbers to have sufficiently large gaps. Suppose in an exact cover problem of $n$ elements, the first element is reduced to $1$. How large should the second number be? There are $2^{n-1}$ sets that can include the first number. So, the second element should be reduced to a number larger than $2^{n-1}$ such that no matter how many times $1$ appears, it cannot replace the second number. Let's just reduce the second element to $2^n$. The same argument applies to the third argument, so we reduce it to $2^n\times 2^n=4^n$.

In conclusion, the $i$-th element in the exact cover problem has a value of $2^{in}$. Each set is reduced to the sum of numbers it covers.

Now we showed that exact cover is in NP-Hard. We need to prove that it is also in NP in order to show that it is NP-Complete. I think that's relatively simple. If you need help for that, I'll provide some hints for you.

# Answer
> 3 votes
Subset Sum can be easily transformed from Partition problem. The proof of reducing Exact Cover to it is similar to the one from 3-Dimensional Matching, and you can find it in the textbook by Garey and Johnson. The proof is somewhat complicated.

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


title: Symbol table usage

text:
# Question
Title: Symbol table usage
In which phases of the compiler, is symbol table used and updated ?

---

According to me,

In lexical analysis, new entry for each variable is created in symbol table so symbol table is only **updated**

In syntax and semantic analysis, symbol table is just used to check the information about attributes during parse tree creation and type checking. So in both of these phases , symbol table is only **used** and not **updated**

In intermediate code generation and code optimization, entry in symbol table is added in case any temporary variables are created and to check the type of temp variable, symbol table is used.So symbol table is both **used** and **updated** here.

I am not sure about Target code generation.

Can someone please tell me if I am correct?

# Answer
> In which phases of the compiler, is symbol table used and updated?

Symbol table are interacted during *all* phases of a compiler.

Basically, a compiler operates in phases which are grouped as *backend* and *frontend*. The front end deals with those part of code which is independent of the target platform and mainly depends on the language structure, while backend does not depend on the structure of the language but depend on the target platform.

Essentially, a symbol table is a data structure (usually a hash table) containing information about identifiers. Identifiers are detected and stored in the symbol table by the lexical analyzer. During the analysis phase (frontend) the compiler collects various information about identifiers (scope, type, size, etc.), stores it into the symbol table, and later this information are used in various ways in remaining phases, for example by code generator and optimizer. The symbol table are used and updated as necessary and for the most part depends on what kind of compiler you are writing (target platform, architecture, structure of language, etc.).

For example, initially the symbol table may store keywords. The syntax analyzer may store information about types of identifiers, and semantic analyzer may use this information to check semantics of expressions. The code generator uses types of identifiers and store the information about the storage assigned to identifiers.

---

Using of Symbols Tables are discussed in Chapters 2 and 7 of the Dragon book.
> 3 votes

---
Tags: compilers
---


# Question
Title: How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?
In Strassen's matrix multiplication, we state one strange ( at least to me) fact that matrix multiplication of two 2 x 2 takes 7 multiplication.

**Question :** How to prove that it is impossible to multiply two 2 x 2 matrices in 6 multiplications?

Please note that matrices are over integers.

# Answer
This is a classical result of Winograd: On multiplication of 2x2 matrices.

Strassen showed that the exponent of matrix multiplication is the same as the exponent of the tensor rank of matrix multiplication tensors: the algebraic complexity of $n\times n$ matrix multiplication is $O(n^\alpha)$ iff the tensor rank of $\langle n,n,n \rangle$ (the matrix multiplication tensor corresponding to the multiplication of two $n\times n$ matrices) is $O(n^\alpha)$. Strassen's algorithm uses the easy direction to deduce an $O(n^{\log\_27})$ from the upper bound $R(\langle 2,2,2 \rangle) \leq 7$.

Winograd's result implies that $R(\langle 2,2,2 \rangle)=7$. Landsberg showed that the border rank of $\langle 2,2,2 \rangle$ is also 7, and Bläser et al. recently extended that to support rank and border support rank. Border rank and support rank are weaker (=smaller) notions of rank that have been used (in the case of border rank) or proposed (in the case of support rank) in the fast matrix multiplication algorithms.
> 23 votes

# Answer
You can find the result at:

S.Winograd, *On multiplication of 2×2 matrices*, Linear Algebra and Appl. 4 (1971), 381–388, MR0297115 (45:6173).
> 7 votes

---
Tags: algorithms, complexity-theory, lower-bounds
---


# Question
Title: How can i draw a general resource graph which cannot be completely reduced but which is free from deadlock?
How can i draw a general resource graph which cannot be completely reduced but which is free from deadlock?

A general resource graph which can be completely reduced and hence is free from deadlock is shown below.

As depicted above, R1 and R2 are resources and P1 and P2 are processes.

# Answer
> 0 votes
A general resource graph which cannot be completely reduced but which is free from deadlock is illustrated below.

R1 and R2 are reusable resources, and P1 and P2 processes.

---
Tags: operating-systems
---


# Question
Title: Some questions regarding an approximation algorithm for Cardinality Maximum Cut Problem in Vazirani's textbook!
In Vazrani's textbook, page 22, the following exercise:

> 2.1 Given a n undirected graph G=(V,E), the cardinality maximum cut problem asks for a partition of V into sets S and G\S so that the number of edges running between these sets is maximized. Consider the following greedy algorithm for this problem. Here $v\_1$ and $v\_2$ are arbitrary vertices in G, and for $A \subset V$, $d(v,A)$ denotes the number of edges running between vertex v and set A.

> Show that this is a factor 1/2 approximation algorithm and give a tight example. What is the upper bound on OPT that you are using? Give examples of graphs for which this upper bound is as bad as twice OPT.

First: the upper bound on OPT is easily the number of edges. Second: I have an example of graph that shows that we have 3/5 (so close to 1/2 but not exactly) I tired for several days to find 1/2 but no sign to find one. Now, can I use the limit to show that we have 1/2. i.e. lim as m goes to infinity, $\frac{m/2 + 1}{m} = \frac{m+2}{2m}=1/2$ Is this correct?!! if not, then why! Third: I want to understand the different between "Give examples of graphs to show that this upper bound is as bad as twice OPT" and "tight example"! I mean Are they the same thing?!! For example: tight example would show an approximation ratio 1/2 for this algorithm while "Give examples of graphs to show that this upper bound is as bad as twice OPT" would give 1/2 approximation ratio for this algorithm. Also it seems from the context of the question that "upper bound" we use is not good! do you know any other better upper bound than the number of edges to give a better bound!!

I'm here not to ask for solving problem, instead I just want to understand what the question wants exactly and different between some parts of this question.

Thank you!

# Answer
> 1 votes
An $\alpha$-approximation algorithm $A$ for a maximization problem is an algorithm which on instance $x$ produces a solution $y = A(x)$ of value $V(y) \geq \alpha OPT(x)$, where $V(y)$ is the value of $y$ and $OPT(x)$ is the value of the optimal solution.

A tight instance for such an algorithm is an instance $x$ such that $V(A(x)) = \alpha OPT(x)$. This instance shows that $A$ isn't a $\beta$-approximation algorithm for any $\beta \< \alpha$.

In some cases it is impossible to find a single tight instance, yet it is still possible to show that the algorithm isn't a $\beta$-approximation algorithm for any $\beta \< \alpha$ using a *sequence* of solutions $x\_i$ satisfying $V(A(x\_i))/OPT(x\_i) \longrightarrow \alpha$. Such a sequence is sometimes also called a tight instance, even though in reality it is a sequence of instances rather than a single instance.

---

You are also wondering what is the correct answer to the question about which upper bound you are using. Your algorithm presumably uses the trivial upper bound, which is the total number of edges. If you find an "integrality gap" instance in which the ratio between this upper bound and the maximum cut is $\alpha$, then this means that any algorithm using this upper bound cannot have an approximation ratio better than $\alpha$. In your case you can take a large clique, for example (this is actually a sequence of bad instances).

---

The famous Goemans–Williamson algorithm uses a better upper bound, namely the value of a semidefinite relaxation of maximum cut. Using this better upper bound, it manages to increase the approximation ratio from 1/2 to roughly 0.878, which is conjectured to be optimal.

---
Tags: approximation
---


# Question
Title: Triangulating a simple polygon via its trapezoidal map
Given a trapezoidal map of a simple polygon $P$, is it possible to compute the triangulation of $P$ in $\mathcal{O}(n)$ time?

# Answer
Yes, "it's easy to derive from such a decomposition of $P$ in linear time a triangulation of $P$."

Take a look at lemma 1. here.
> 0 votes

---
Tags: algorithms, computational-geometry, polygons
---


title: Element wise product sum of two arrays

text:
# Question
Title: Element wise product sum of two arrays
I have two arrays, namely $a$ and $b$. Both have the same length $n$. I have to find the maximum value of $\sum a\_i b\_j$, in which every element can be used at most one time. My algorithm for solving this problem is:

1. Sort both $a$ and $b$ in non increasing order.
2. Pick the values from the array in order of greatest to smallest. Calculate their product and add them to sum.

On the arrays $a = \\{2,3,4\\}$ and $b = \\{4,5,6\\}$, the algorithm runs as follows:

* Firstly, sorting the arrays: $a = \\{4,3,2\\}$ and $b = \\{6,5,4\\}$.

Then picking values from the first to last, gives the answer $(4\cdot6) + (3\cdot5) + (2\cdot4) = 24 + 15 + 8 = 47$.

Here what I have used is a greedy algorithm. How to prove its correctness? What I want to know is, how to prove that this algorithm always gives the maximum answer?

# Answer
The usual formulation of this problem is: find a permutation $\pi$ that maximizes $\sum\_i a\_i b\_{\pi(i)}$.

Towards solving this problem, suppose that we have some permutation $\pi$ in mind, and let $\sigma$ result from switching $\pi(j)$ and $\pi(k)$ (that is, $\sigma(k) = \pi(j)$ and $\sigma(j) = \pi(k)$. When is this beneficial? $$ \sum\_i a\_i b\_{\sigma(i)} - \sum\_i a\_i b\_{\pi(i)} = a\_j (b\_{\sigma(j)} - b\_{\pi(j)}) + a\_k (b\_{\sigma(k)} - b\_{\pi(k)}) = (a\_j-a\_k)(b\_{\pi(k)}-b\_{\pi(j)}). $$ That is, if $a\_j \> a\_k$ and $b\_k \< b\_j$ then it is beneficial to switch $\pi(j)$ and $\pi(k)$. Conversely, any local maximum must satisfy the constraint that if $a\_j \> a\_k$ then $b\_{\pi(j)} \geq b\_{\pi(k)}$.

Using this property you can prove that your algorithm is optimal. I'll let you fill in the remaining details.
> 1 votes

# Answer
Generally, to prove a greedy algorithm is optimal what you do is come up with a theorem that captures the idea of “moving away from” the greedy strategy and show that that decreases the optimal value. It’s important that you phrase the theorem in a way that can be iteratively applied, as otherwise it might be that the objective function goes down immediately after departing from the greedy algorithm, and then goes back up. In this case, you want

> **Theorem:** If $a\geq b$ and $c\geq d$ then $ac+ bd\geq ad+bc$

Given any way of pairing numbers, this theorem says that if you swap two numbers so that you move closer to the greedy algorithm then the value cannot go down, and if you swap two numbers so that you move further from the greedy algorithm the value cannot go up. So prove this, and the correctness of the greedy algorithm follows.

It’s sufficient to consider only vectors of length two because any permutation of the vectors can be generated from exchanging two numbers. Equivalently, $S\_n$ is generated by its two-cycles for every $n\>1$
> 1 votes

---
Tags: optimization, proof-techniques, correctness-proof, greedy-algorithms
---


# Question
Title: How to explain/understand brackets of applicative functor [[f u1... un]]?
I am reading article about Applicative Abstract Categorial Grammars http://okmij.org/ftp/gengo/applicative-symantics/AACG.pdf and this article uses brackets \[\[...\]\] for action on terms inside applicative functors. These brackets are introduced and somehow explained in "Functional Pearl: Applicative programming with effects" http://strictlypositive.org/IdiomLite.pdf. I understand what applicative functor is and what what is functor generally (both in category theory and Haskell) but I still can not understand the meaning and value of these brackets. I understand the sentence `idiomatic expression [[f x y]] means ηf * ηx * y, or, alternatively, map (f x) y` \- that means that `[[F(tau)]]` is sitting inside brackets, but I can not understand the difference between `F(tau)` and `[[F(tau)]]` in brackets (see page 4 of AACG article about context and notation). Also - brackets are not always used with 3 arguments, sometimes there are even on or none arguments!

Do those brackets have meaning, explanation and use in Haskell world? Any explanation - rigorous or not, associative and free-style of not is really appreciated.

http://learnyouahaskell.com/functors-applicative-functors-and-monoids contains example:

```
pure (+) <*> Just 3 <*> Just 5

```

Its fine, but what benefit can we get by applying brackets \[\[\]\] around this expression, what additional meaning such application created?

# Answer
In it's simplest, original form, $\[\\!\[f\ x \ y\]\\!\]$ just means $\eta(f)\circledast x \circledast y$ where $\circledast$ is what Haskell calls `<*>` and $\eta$ is what Haskell calls `pure`. Of course, this is only type correct if $x$, and $y$ have types like $\mathcal{F}(\dots)$ where $\mathcal{F}$ is an applicative functor. If they don't, we can be a bit smarter and automatically use $\eta$/`pure` to "lift" them to that type. From there, the translation can simply be $\[\\!\[f\ x\_1\dots x\_n\]\\!\]\leadsto \[\\!\[f\]\\!\]\_1\circledast \[\\!\[x\_1\]\\!\]\_1\circledast\cdots\circledast \[\\!\[x\_n\]\\!\]\_1$ where $\[\\!\[e\]\\!\]\_1$ is either $e$ or $\eta(e)$ depending on the type of $e$. More systematically, $\[\\!\[e\ x\]\\!\]\leadsto \[\\!\[e\]\\!\]\circledast \[\\!\[x\]\\!\]\_1$ where $\[\\!\[e\]\\!\] = \[\\!\[e\]\\!\]\_1$ when $e$ is not an application. You can easily imagine a variation that recursively applies the transformation.

The idiom brackets are just for convenience. The example you show of an applicative expression would become `[[3 + 5]]` using idiom brackets which is quite a bit shorter and more readable than `pure (+) <*> pure 3 <*> pure 5` (which is in this case just `pure (3 + 5)` and thus is a fairly trivial case).

I have no idea what you mean by `[[F(tau)]]`. Idiom brackets don't apply to types.

There's a quasi-quoter that implements a notation similar to idiom brackets. Idiom brackets are also implemented by the Strathclyde Haskell Enhancement (SHE) which is made by the person who originally introduced the notation and author of that Functional Pearl, Conor McBride.
> 4 votes

---
Tags: formal-grammars, lambda-calculus, functional-programming, category-theory, haskell
---


# Question
Title: Why doesn't descriptive complexity theory solve P = NP?
According to the Wikipedia page on Descriptive complexity theory:

> In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time.
>
> Existential second-order logic yields NP, as mentioned above.

If P = NP, wouldn't it be possible to convert any Existential second-order logic into a corresponding first-order logic with a least fixed point operator? That would also imply a bijection between those sets (is there a bijection between existential second-order logic and first-order logic with a least fixed point operator?).

My understanding is first order logic cannot express second-order logic - why doesn't this prove P != NP?

# Answer
> 8 votes
Note the difference between second-order logic, and existential second order logic. Full logic is *much* more powerful than existential logic.

Also, it's important not to underestimate the power of a least-fixed point operator. Linearly-ordered first order logic is likely far less powerful than the version with fixed-points.

In short, we know that vanilla first-order logic is weaker than vanilla second-order logic, but we don't know that linearly-ordered first order logic with a least-fixed point operator is weaker than the existential fragment of second order logic.

---
Tags: complexity-theory, p-vs-np, descriptive-complexity
---


title: Formal names of nested functions

text:
# Question
Title: Formal names of nested functions
I have a nested function as follow:

```
def make_adder(n):
    def add(x):
        return x + n
    return add
>>> plus_3 = make_adder(3)
>>> plus_5 = make_adder(5)
>>> plus_3(4) 7
>>> plus_5(4) 9

```

What's the formal names of `make_adder` and `add`?
Can I call them 'outer function' and 'inner function'?

# Answer
> 1 votes
A function that either takes a function as argument or returns a function as result is called a High Order Function in functional programming. Your function `make_adder` is doing the latter.

# Answer
> 0 votes
One specific name for that kind of construct is "closure". That term specifically refers to a situation where the inner function uses variables from the outer function's "enclosing" namespace.

---
Tags: terminology, reference-request, programming-languages
---


# Question
Title: Remove duplicates of first elements of pairs
A list of pairs is given using Python. I want to remove duplicate occurrences of the first element of the pair leaving only one occurrence of each first element paired with the highest second element it comes with. I am looking for an efficient solution that returns the pairs sorted.

```
>>> myfunc([[2, 0], [3, 0], [4, 0], [5, 0], [3, 2], [4, 0], [5, 3], [5, 3]])
[[2, 0], [3, 2], [4, 0], [5, 3]]

```

# Answer
You can do this pretty easily in $O(n log(n))$ time by using a hash table (such as Python's `dict`) to map from the first value in a pair to the largest second value it's been seen with.

```
def myfunc(pairs):
   mapping = {}
   for key, value in pairs:
       if key not in mapping or value > mapping[key]:
           mapping[key] = value
   return sorted(mapping.items())

```

Hash table lookups take $O(1)$ time on average, so eliminating the duplicates in the loop will take $O(n)$ time. Sorting is (asymptotically) slower, taking $O(n log(n))$ time.
> 1 votes

---
Tags: algorithms, lists
---


# Question
Title: An infinite decidable language that is a subset of $\overline { A_{TM}}$
What is an example of an **infinite decidable** language $L$, such that $L \subseteq \overline { A\_{TM}}$ (which is known to be not Turing Recognizable)?

*And of coures some evidence that L is indeed decidable and a subet as required*

# Answer
Fix a special TM $M\_d$ which infinitely loops on any input $x$. In other words, $M\_d$ does not care about input $x$ and always infinitely loops on any input. Such a TM could consist of a single state and instructions such as $\delta(q\_0, a) = (q\_0,a)$ for all input symbols $a \in \Sigma$, which tells $M$ to stay in the same state and never move the head. So, given its description $\langle M \rangle$ it is easy to recognize this machine by inspecting its states and instructions.

Since $M\_d$ never halts on any input $x$ the following language must be infinite

$$L = \\{\langle M\_d,x \rangle \mid x \in \Sigma^\*, M\_d \text{ is the fixed TM} \\}$$. This language is also a subset of $\overline{A\_{TM}}$ since $M\_d$ never halts on any input $x$. Thus, if we are given $\langle M\_i,x \rangle$ we simply decide by checking whether $i=d$, i.e., whether $M\_i$ is the same as $M\_d$ by inspecting $M\_i$'s states and instructions meaning $L$ is decidable.
> 3 votes

# Answer
A Turing machine $M$ whose head always moves right and never modifies the tape is essentially a deterministic finite-state automaton (https://en.wikipedia.org/wiki/Read-only\_right\_moving\_Turing\_machines), and it is decidable if $M$ accepts a given input $w$. Moreover, we can easily check if a Turing machine description $\langle M \rangle$ describes a read-only right-moving Turing machine.

Therefore the language

$$\\{ \langle M,w \rangle \mid M \text{ is a read-only right-moving TM that does not accept } w\\}$$

is a subset of $\overline{A\_{\mathsf{TM}}}$ that is decidable. It is easy to see that this language is infinite, as the set of read-only right-moving Turing machine is infinite.
> 1 votes

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


# Question
Title: Prove that the coding $\pi_k$ is effective
I have to prove that the coding $\pi\_k$ is effective given that $\pi\_k$ is a surjective coding of $\mathbf N^k$ and $\pi\_k$ is a recursive function.

What I've got:

A coding by definition is an injective function from a set $X$ to $\mathbf N$. I know by definition that a coding $\pi\_k$ is effective if it is recursive and there exist decoding functions $J\_0^k, ..., J\_k^k$ for which $J\_i^k=x\_i$ in $(x\_0, ..., x\_k)$ and which are also recursive functions.

How can I find such functions or prove they exist?

# Answer
> 1 votes
Since $\pi\_k$ is bijective, for every $x∈N$, there exists a unique tuple $(x\_1, ..., x\_k)∈N^k$ such that $\pi\_k(x\_1,...,x\_n) = x$. So, how can we define $J^k\_i$ ? A solution would be to use a coding that is already known to be effective, let $\alpha\_k$ be that effective coding and $\beta^k\_1,..., \beta^k\_k$ the associated decoding functions. Let $x∈N$, we can put : $$J^k\_i(x) = \beta\_i^k(\mu y(\ \pi\_k(\ \beta^k\_1(y)\ , ...,\ \beta^k\_k(y)) = x))$$

For $\alpha\_k$, we can take the cantor tuple function, which is known to be primitive recursive.

Of course, that's not a proper definition, we need mathematical induction to throw away those horrible dots.

---
Tags: computability
---


# Question
Title: Which "entity" is working at more deeper level than Characters of a program?
It is commonly told that, while we write a program, we input with our language (A, B, C, D etc), whom computer translates into machine language into machine language made up of Zero (0) or switch off and One (1) or switch on, a.k.a. ASCII code.

Letter ... ASCII Code .... Binary

A ........... 065 ............ 01000001

B ........... 066 ............ 01000010

But I don't think it is that simple.

When I type A on the keyboard, the programming prompt (say C-programing) screen shows me a letter A or a (depending upon caps lock or not) that have a definite geometric shape and orientation. There are other factors, like which part on screen the letter will be shown.

Even if A=01000001 I don't think just turning off 6 pixels (Six ZEROS) and turning on 2 pixels (two ONES) it is possible to render triangular capital-letter A.

*Now my question is; What is the "Entity" (maybe a software) which is rendering a small 0-1 code into a **geometric figure (glyph)**? Such as 01000001 into a triangular shape (**A**) or rendering 01000010 into a vertical line with two bulge at right hand side (**B**) etc.*

# Answer
There are many pieces of software involved in rendering an "A" when you type it in to a program like a text editor.

* First, the key press is handled by the hardware of the keyboard, which sends a signal to the OS's keyboard driver. This is where stuff like the state of the shift key and caps lock get noted (though the information about which modifier keys are pressed will usually just be passed along with the information about the key pressed, rather than "a" turning into "A" just yet).
* The key press information next gets passed to the window manager (which is usually part of the OS), to determine which program has "keyboard focus" at the moment. If nothing has focus, the window manager might discard the key press here (though it might also intercept other presses, like ALT+Tab).
* Next the active program likely gets a key-press event. Often the program's event processing happens in a library provided by the window system, though what it will do with the events after they happen is up to the application itself.
* An editor program will likely interpret a key press like "A" as input for a file you have open. It will add the character to its memory buffer representing the file's contents. This may be the first place where the ASCII representation for "A" becomes relevant, as keyboards and windowing systems often use their own codes for key presses. (Note though that a modern editor will probably use some encoding of Unicode, rather than ASCII to represent text. This adds some extra complication, but makes it possible to handle text in any language, not only English.)
* Now the program has to draw the "A" to the screen. First it will probably have to do a bunch of calculations to determine how it wants to lay out all its text. Many editors wrap long lines of text, for instance, which can be pretty complicated to get right.
* Once the program has decided exactly where on the screen it wants to put each part of its text, it will render them using a font. The font describes what each glyph should look like (this is also very complicated). The font render (which is often part of a library provided by the OS or window manager, though an application can do its own rendering if it really wants to) transforms the "A" to a specific set of pixels.
* Next, the pixels for the "A" (along with those for the other text, and the rest of the editor's UI) get sent to the graphics driver. Other programs may also be sending their own pixels if other windows are visible alongside the editor. The window manager will usually also have some parts of the screen that it manages itself (like the taskbar, but sometimes also the borders of the windows).
* The graphics driver sends on all the data to the hardware graphics card in the machine. Some PCs these days (especially laptops) don't have a dedicated graphics card, but they'll have a chip on the motherboard that does essentially the same thing. The graphics card will assemble all the graphics into a buffer representing all the pixels of the screen. It will send the contents of that buffer to the monitor every time it needs to redraw the screen (usually 60 times per second, though other refresh rates are becoming more common).

The steps above are intended to be fairly general. Typing a key into a specific program on your computer may not have exactly the steps I describe (it could have more or fewer). For instance, if your editor is a console application rather than a graphical one, you may not have any window manager involved, and very basic fixed-width font rendering might be done directly by the hardware of the graphics card.

The exact boundaries between some of the layers may also be hard to distinguish in some cases, especially when the application is using libraries provided by the OS, window manager or graphics driver for some of the steps (like the event loop and font rendering).
> 3 votes

---
Tags: programming-languages, software-engineering, user-interface
---


# Question
Title: Construct an equivalent NFA for the given regular grammar
> Given is the regular grammar `G = ({A,B}, {a,b}, P, A)` with the rules
>
> ```
> P : A → aB, a, ε (where ε is the empty word)
>     B → bA, b
>
> ```
>
> For this regular grammar, create an equivalent NFA.

A regular grammar is a 4 tuple `G = (N, Σ, P, S)`.

So our NFA is made up of 2 states, `A` and `B`. The initial state is `A` and it's also the ending state because the rule says we have the empty word `ε` in the state `A`. If we read an `a` from state `A`, we go to the state `B`. But I don't know what that single `a` means in the first rule?

From state B, if we read a `b`, we go to state `A`. But again, what does this single `b` mean in this rule?

All in all I would construct the NFA for the regular grammar `G` like that:

# Answer
> 3 votes
The single $a$ indicates that if we are in state $A$, and read $a$, we must go to an ending state, same with single $b$. If we follow that, we get this automaton :

If we were less prudent, we would argue that if we can generate an $a$ with variable $A$ and stop, and because $A$ is an ending state, then we can put a loop on state $A$ labeled with $a$, like this :

But this automaton doesn't match with grammar $G$. This one recognize strings of the form $a^i$, but grammar $G$ can't generate them.

But something that can be done to lighten our automaton would be to remove state $B\_f$, and count on our ending state $A$ to handle the case where we end generation with a single $b$, like the following :

And that actually correct, because we have : empty word on variable $A$, and a rule $B \rightarrow bA$ (In fact, we can remove from $G$ the rule $B \rightarrow b$, because it can be replaced with $B \rightarrow bA \rightarrow \epsilon$).

EDIT : As @rici said, if we apply subset construction to the last automaton, we get this one : (without dead states)

So this is an automaton that matches with $G$.

---
Tags: formal-languages, regular-languages, automata, finite-automata, formal-grammars
---


# Question
Title: Konig's Theorem for Min Weight Vertex Cover?
Koning's theorem states that the cardinality of the maximum matching in a bipartite graph is equal to the size of its minimum vertex cover.

Wikipedia states that there is an equivalent version of the theorem for weighted graphs as well. I tried searching in a lot of places but could not find this theorem.

To be more specific, I want to know what is the equivalent version of Konig's theorem in the case of Minimum Weight Vertex Cover in Bipartite Graphs where each vertex $v \in G$ is assigned a weight $w\_v$ and the task is to find a vertex cover of the minimum possible weight.

If the equivalence is just the maximum weighted matching in $G$, what are the weights of the edges in this graph? Because as far as I understand, we have only assigned weights to the vertices of the graph $G$.

Thank you for your time :)

# Answer
> 4 votes
So I found the answer.

The equivalence is that the min weight vertex cover of a bipartite graph can be computed as the maximum flow in a related bipartite graph. In the unweighted case, this maximum flow corresponds to the maximum carnality matching in a bipartite which is exactly the version of Konig's theorem that we all know and love.

For the sake of completeness here is the reduction of bipartite min weight vertex cover to max flow.

Let $G = (A,B)$ be the given bipartite graph. Construct a flow network $N$ by connecting the a source $S$ to all nodes in $A$ and all nodes in $B$ to a sink $T$.

Let the capacity of all original edges in $G$ be $\infty$. The capacity of all edges of the form $(S,a)$ where $a \in A$ will be $w\_a$ and the similarly the capacity of all edges $(b, T)$ where $b \in B$ will be $w\_b$. Every $S-T$ cut in this network corresponds to exactly one vertex cover and every vertex cover corresponds to an $S-T$ cut. Thus the min-cut a.k.a. the maximum flow will give us the minimum weight vertex cover.

For a more detailed proof refer this.

---
Tags: weighted-graphs, bipartite-matching
---


# Question
Title: Are their problems that we can not even approximate efficiently?
Most hard problems can either be solved efficiently in average time, or an approximation can be efficiently found. Are there any natural problems for which this is not the case? In particular, is there a natural problem that can not be solved in polynomial time in the average case, even if we only demand an approximation?

# Answer
> Are there any natural problems for which this is not the case?

Consider the scheduling jobs with deadlines on a single machine problem. I cannot say anything about its average time but this problem has no $\rho$-approximation unless $P=NP$.

Suppose that there are $n$ jobs to be scheduled on a single machine, where the machine processes at most one job at a time. Suppose also each job $J\_i$ has

* release time $r\_i \geq 0$
* deadline (due time) $d\_i$

Define the *delay* by $D\_i = t\_i - d\_i$ if the job $J\_i$ finishes at $t\_i$. So, we are interested in the minimization of the maximum delay, i.e.,

$$\text{minimize: } \max\\{D\_i\\}, i=1,\dots,n$$

Now assume we have $\rho$-approximation algorithm for this problem. This means that our algorithm would find a solution which is not more than $\rho OPT$ (where $OPT$ is the optimal value). If for any problem instance with the optimal value equal to $0$ our approximation algorithm would find the solution at most $\rho 0 = 0$ in (polynomial time) and this would imply $P=NP$.
> 1 votes

# Answer
Consider the 3-colouring problem. Every planar graph can be 4-coloured. Determining if it is 3-colourable is NP-complete. Finding the number of colours required with less than 14% error is NP-complete.
> 0 votes

---
Tags: efficiency
---