# Question
Title: How to determine maximum stack size of LL(1) parser?
I am generating an LL(1) parser generator for LL(1) grammars that have a maximum stack size when executed in the table-driven parser. Specifically, I'm parsing HTTP headers using a parser generated by the LL(1) parser generator.

In case somebody asks, yes, it's possible to parse plaintext HTTP using LL(1) parser, if the parser works together with the lexer, so that the parser automatically turns on and off tokens in the lexer. So, only those tokens that are valid in the context are matched in the deterministic finite automaton (DFA).

The particular grammar I'm using for my tests is this (yes, I know it's possible to fold the first header line incorrectly using the grammar, I'll fix this later):

```
headerField -> foldstart httpfield
headerField -> httptoken colon optspace httpfield
httpVersion -> httpname slash digit period digit
requestLine -> httptoken onespace uri onespace httpVersion crlf
requestHdrs -> (epsilon)
requestHdrs -> headerField crlf requestHdrs
requestWithHeaders -> requestLine requestHdrs crlf

```

The start nonterminal is `requestWithHeaders`. The terminals are:

```
crlf, onespace, httpname, slash, digit, colon, optspace
httptoken, httpfield, period, uri, foldstart

```

...so every name that is lowercase only is terminal, and if there are uppercase characters in the middle, it's nonterminal.

Now, if I start using the stack `[(endOfFile), requestWithHeaders]`, the maximum stack size is ever going to be 9 according to my tests. So, this grammar appears to have a maximum stack size.

The question is: how to prove the maximum stack size? I'm looking for an algorithm that terminates and gives me the answer `9` for this grammar. The algorithm need not terminate for a grammar that doesn't have a maximum stack size, so infinite recursion and infinite loops are permitted if the maximum stack size doesn't exist. (I can always limit the amount of CPU time given to the algorithm.)

I already have the code to calculate first-sets and follow-sets, and the code to generate the parser table, and the code to execute the parser using the parser table, so I'm not looking for advice for standard LL(1) parser implementation. I have already tested my parser with valid and invalid HTTP examples, and everything seems to work just fine.

The reason I'd like to determine this maximum stack size is that I want to avoid dynamic memory allocation in the parser. There is no need to allocate memory dynamically for cases where there is an upper bound for the stack size.

# Answer
> 2 votes
OK. So you have a pushdown automaton, and out of all reachable stack configurations, you want to know the stack depth (length) of the longest such configuration.

I have two answers: a simple, practical answer that might suffice for your specific situation but doesn't scale, and a general answer that will apply more broadly.

# Simple answer

Enumerate all possible stack configurations. This should be easy. Just think of this as a giant graph, with one vertex per reachable stack configuration, and an edge from each such stack configuration to every other configuration that is reachable in a single step. Now use any graph exploration algorithm, such as DFS, to explore the graph. Out of all the configurations you visit, keep track of which one had the largest stack depth.

You have 5 nonterminals. If the maximum stack depth is $9$, there will be at most $5^9$ reachable stack configurations, i.e., about 2 million of them. It's easy to explore all such configurations and store them all in a simple data structure.

Of course this would not scale to larger cases, as the complexity is exponential.

# General solution

The set of reachable stack configurations of a pushdown automaton is regular. Therefore, you can build a DFA that concisely represents all such reachable stack configurations. This DFA is not too large (linear in the size of the PDA, I think) and can be built efficiently (in quadratic or cubic time, I think). Then, you can check whether the DFA has any cycles and the length of the longest path in the DFA, and that will tell you the stack depth of the deepest reachable stack configuration.

This will give you an efficient, polynomial-time algorithm that scales even to large, non-trivial grammars. The cost is that it takes more work to understand the algorithms and implement them correctly, so I'd try the simple solution above first, and only fall back to this if necessary.

# Answer
> 0 votes
Not sure if this is the correct answer, but I quickly crafted the following algorithm in Python:

```
crlf, onespace, httpname, slash, digit, colon, optspace = range(0,7)
httptoken, httpfield, period, uri, foldstart = range(7,12)

terminals = [crlf, onespace, httpname, slash, digit, colon, optspace,
             httptoken, httpfield, period, uri, foldstart]

headerField, version, requestLine, requestHdrs, requestWithHdrs = range(20,25)

rules = [(headerField, [foldstart, httpfield]),
         (headerField, [httptoken, colon, optspace, httpfield]),
         (version, [httpname, slash, digit, period, digit]),
         (requestLine, [httptoken, onespace, uri, onespace, version, crlf]),
         (requestHdrs, []),
         (requestHdrs, [headerField, crlf, requestHdrs]),
         (requestWithHdrs, [requestLine, requestHdrs, crlf])]

max_stacks = {}
changed = True
for a in terminals:
  max_stacks[a] = 1
while changed:
  changed = False
  for rule in rules:
    lhs, rhs = rule
    cursz = 0
    if len(rhs) > 0:
      cursz = len(rhs) - 1 + max_stacks[rhs[0]]
    if lhs not in max_stacks or max_stacks[lhs] < cursz:
      changed = True
      max_stacks[lhs] = cursz
print 1 + max_stacks[requestWithHdrs]

```

Note the `1 +` which takes into account the special `endOfFile` indicator.

It prints `9`, although I'm not 100% confident that I got the algorithm correctly.

**Edit: the algorithm might be incorrect, now I assume the following would be the correct algorithm, it also prints `9`:**

```
max_stacks = {}
changed = True
for a in terminals:
  max_stacks[a] = 1
while changed:
  changed = False
  for rule in rules:
    lhs = rule[0]
    rhs = list(rule[1])
    cursz = len(rhs)
    while len(rhs) > 0:
      tmpsz = len(rhs) - 1 + max_stacks.setdefault(rhs[0], 0)
      del rhs[0]
      if tmpsz > cursz:
        cursz = tmpsz
    if lhs not in max_stacks or max_stacks[lhs] < cursz:
      changed = True
      max_stacks[lhs] = cursz

```

**Edit again, I implemented D.W.'s algorithm:**

```
def get_max_sz_dfs(Tt, rules, terminals, S, eof=object()):
  visiteds = set()
  maxvisited = 0
  # in case somebody uses without EOF symbol:
  initial = (eof is None) and (S,) or (eof, S)
  visitqueue = []
  visitqueue.append(initial)
  while visitqueue:
    current = visitqueue.pop()
    visiteds.add(current)
    if len(current) > maxvisited:
      maxvisited = len(current)
    last = current[-1]
    if last in terminals:
      if current[:-1] not in visiteds:
        visitqueue.append(current[:-1])
      continue
    if last == eof:
      continue
    A = last
    for a in terminals:
      if Tt[A][a] != None:
        rule = rules[Tt[A][a]]
        rhs = rule[1]
        newtuple = current[:-1] + tuple(reversed(rhs))
        if newtuple not in visiteds:
          visitqueue.append(newtuple)
  return maxvisited

```

`S` is the start token, `Tt[A][a]` tells which rule to use for state `A` and terminal `a`, i.e. it's the parser state transition table. `terminals` is the list of terminals, and `rules` is the list of rules in the format above.

If you're reading this, please ignore my two first attempts and use the algorithm suggested by D.W.

---
Tags: formal-languages, parsers, stacks
---


title: Graph Coloring Problem

text:
# Question
Title: Graph Coloring Problem
Can solutions to the graph coloring problem be used in the prison system to keep known enemies apart with the goal of reducing violence?

# Answer
> 2 votes
It's unclear exactly what level you're asking the question at.

*In principle*, you could set up a graph where the vertices are prisoners, there's an edge between any two prisoners who need to be kept separate, and each prison corresponds to a colour. *In practice*, there are probably too many prisoners in any reasonably sized country for this to be a computationally tractable approach (though the conflict graph would probably be rather sparse), there are more constraints on the system that would be hard to model in this graph-colouring approach, and two prisoners getting into a fight could cause a re-colouring that might cause a large proportion of the prison population to be moved, which is neither feasible nor desirable.

# Answer
> 0 votes
Yes, in theory, assuming the prison has $n$ separated blocks.

Let each vertex be a prisoner, let each hostile relationship be a graph edge between their two respective vertices and color the graph.

The color of each vertex determines what block the prisoner ends up in, no two prisoners that have a hostile relationship will end up in the same block.

Note that this isn't very useful in practice without other requirements, as for example blocks have limited capacity.

---
Tags: graphs, colorings
---


# Question
Title: Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression
Given an NFA with alphabet $\Sigma = \\{a, b, c\\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression?

The way I solved this problem is to first convert the NFA into a DFA using equivalent classes, and then proceed with the method described here. I feel in this case, that method is very inconvenient, as there are many loops and multiple accepting states. I wrote down all the partial regexps regarding to each accepting state alone, then unioned them together, then eliminated the redundant parts. My answer is $a(a^+ \cup b^\*a \cup c^\*)^+$.

I also tried to eliminate the $\varepsilon$ edges first then start from the "sanitized" NFA, but there were way too many edges in this case, and was very confusing during the process.

Edit: as @DavidRicherby has commented below, converting the NFA to DFA first is not necessary and makes the problem more complex.

# Answer
State elimination method is a good technique, if used properly.

Solving $f\_2$ can be done directly from the given automaton.
$$ f\_2 = ( s \rightarrow q\_1 \rightarrow f\_2 + s \rightarrow q\_2 \rightarrow f\_2 + s \rightarrow f\_1 \rightarrow f\_2)^+ $$ ( Overall Kleene + due to $(f\_2,\epsilon) \rightarrow s$) $$ f\_2 = (a\cdot a^\*\cdot a + a\cdot b^\*\cdot a + (a\cdot c^\*)^+\cdot c)^+ $$ This can be rearranged as $$ f\_2 = (a\cdot a^+ + a\cdot b^\*\cdot a + (a\cdot c^\*)\cdot (a\cdot c^\*)^\*\cdot c )^+$$ $$ = ( a \cdot ( a^+ + b^\*\cdot a + c^\*\cdot (a\cdot c^\*)^\*\cdot c) )^+ $$
Similarly, $f\_1$ can be solved directly from the given automaton as follows $$ f\_1 = ( s \rightarrow q\_1 \rightarrow f\_2 \rightarrow s + s \rightarrow q\_2 \rightarrow f\_2 \rightarrow s)^\* \cdot s \rightarrow f\_1 \cdot (\epsilon + c \cdot \epsilon \cdot f\_1) $$ $$ = ( a \cdot a^+ + a\cdot b^\* \cdot a )^\* \cdot (a\cdot c^\*)^+ \cdot ( \epsilon + c \cdot \epsilon \cdot f\_1) $$

$( \epsilon + c \cdot \epsilon \cdot f\_1)$ represent the two possible transitions from $f\_1$. If the input has been completed scanned, stop at $f\_1$. If not, move to $f\_2$ using $c$, then move to $s$ using $\epsilon$. Then start scanning for $f\_1$ again.

This recursive relationship can be solved by taking $$ r = ( a \cdot a^+ + a\cdot b^\* \cdot a )^\* \cdot (a\cdot c^\*)^+$$ Then $f\_1$ becomes,

$$ f\_1 = r \cdot ( \epsilon + c \cdot f\_1)$$ $$ = r \cdot ( \epsilon + c \cdot ( r \cdot ( \epsilon + c \cdot f\_1) ) )$$ Unravelling this recursion gives us, $$ f\_1 = r + r \cdot c \cdot r + r \cdot c \cdot r \cdot c \cdot r + \space... $$ $$ = r \cdot ( c \cdot r )^\*$$
> 4 votes

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


# Question
Title: Why doesn't this derivation of the margin in a SVM give the correct result?
I'm trying to derive the optimization objective for an SVM (namely $1/\\|w\\|$), but I'm running into a little trouble. I've already read this question, which has certainly offered a lot of insight into the problem, but I would like to know why my own derivation doesn't *quite* work.

So essentially, let's say our support vectors on either side of the decision boundary are $\vec x\_+$ and $\vec x\_-$. Suppose the decision boundary itself is $\vec w\cdot\vec x + b = 0$. We have $\vec w\cdot x\_\pm + b = \pm 1$. Now, the margin $d$ can be calculated as the sum of the distances between the points $\vec x\_\pm$ and the decision boundary. We can use the typical projection formula to obtain

$$ \begin{aligned} d & = \left\\|\vec w\frac{\vec x\_+\cdot\vec w}{\vec w\cdot\vec w}\right\\| + \left\\|\vec w\frac{\vec x\_-\cdot\vec w}{\vec w\cdot\vec w}\right\\| \\ & = \frac{\\|\vec w\\|}{\\|\vec w\\|^2}(|\vec x\_+\cdot\vec w| + |\vec x\_-\cdot\vec w|) \\ & = \frac1{\\|\vec w\\|}(|1-b|+|1+b|) \end{aligned} $$

This is *almost* the correct result, and in fact if we restrict $b\in\[-1, 1\]$, $d$ reduces to $2/\\|\vec w\\|$ as expected. However, in general this can be written: $$ d = \frac{2\max(1,|b|)}{\\|w\\|} $$ So my question essentially is why did I end up with the extra b in the numerator? Does it change the optimization objective at all (I feel like it does)? Is there a reasonable explanation for why we could potentially restrict $b\in\[-1,1\]$?

# Answer
> 1 votes
The first line of your equation for $d$ is incorrect. It should be

$$d = \left\\|\vec w\frac{\vec x\_+\cdot\vec w}{\vec w\cdot\vec w} - \vec w\frac{\vec x\_-\cdot\vec w}{\vec w\cdot\vec w}\right\\|.$$

(Why? The distance between two points $u,v$ is $\\|u-v\\|$, not $\\|u\\|+\\|v\\|$.)

If you continue the derivation from there, you will obtain the result you were expecting.

---
Tags: machine-learning, svm
---


# Question
Title: How would I algorithmically "stretch" polygons on a plane by re-scaling the distances between interior points?
I've been thinking about a computational problem and could use some guidance for how to go about developing an algorithm to solve it.

On a Euclidean plane, I have a polygon A, a set of points A\* bounded by A, another polygon B (that does not intersect A), and another set of points B\* bounded by B. What I want is to create a mapping between points in A\* and B\* (not necessarily one-to-one or onto), re-scale the distances between mapped points (the rescaling can be different for each pair of points), and then "stretch" A and B so that mapped points are still contained within their bounding polygon but are the new distances away from each other. The polygons should maintain their shape to the greatest extent possible.

As a simple example, if A and B were squares of equal size centered along the X axis, A\* consisted of the center point of A, B\* consisted of the center point of B, and I wanted to halve the distance between those two points, I would stretch each polygon along the X axis towards the other by horizontally extending the top and bottom edges, horizontally shift the inner edges towards each other, and leave the outer edge unchanged. The new polygons would look like rectangles that are still centered along the X axis but with each of their center points and inner edges moved a quarter of the original distance towards one another.

Another way of visualizing the transformation is to use the raisin-in-bread analogy https://www.wwu.edu/skywise/hubble\_pudding.html commonly used to explain the expansion of the universe. If the points in A\* and B\* were raisins, the algorithm would show how shapes around those points are distorted if space-time were expanding or contracting between pairs of points.

Ideally, a solution would generalize to any number of polygons with any number of mapped interior points.

Thanks

# Answer
> 1 votes
You might try using the spring model: https://en.wikipedia.org/wiki/Force-directed\_graph\_drawing. Or, you could use optimization methods. Build an objective function $\Psi$ that is a sum of penalty terms. For each pair of mapped points $a^\*,b^\*$ that you are hoping will be at distance $c\_{a^\*,b^\*}$, you have a penalty term $(d(a^\*,b^\*) - c\_{a^\*,b^\*})^2$. Also, for each point $a^\*$, add a penalty term that is zero throughout most of the interior of $A$, but increases when you get close to the boundary of $A$ and rises to $+\infty$ for all points outside $A$. Finally, find an arrangement of points that minimizes this objective function. You could then apply any of a number of optimization methods to do this, such as gradient descent or others. Stress majorization may be useful.

---
Tags: algorithms, graphs, computational-geometry, planar-graphs
---


# Question
Title: How to implement a maximal munch lexical analyzer by simulating NFA or running DFA?
I'm planning to implement a lexical analyzer by either simulating NFA or running DFA using the input text. The trouble is, the input may arrive in small chunks and the memory may not be enough to hold one very long token in the memory.

Let's assume I have three tokens, "ab", "abcd" and "abce". The NFA I obtained is this:

And the DFA I obtained is this:

Now if the input is "abcf", the correct action would be to read the token "ab" according to the maximal munch rule and then produce a lexer error token. However, both the DFA and the NFA have state transitions even after "ab" has been read. Thus, the maximal munch rule encourages to keep on reading after "ab" and read the "c" as well.

How do maximal munch lexers solve this issue? Do they store the entire token in memory and do backtracking from "abc" to "ab"?

One possibility would be to run the DFA with a "generation index", potentially multiple generations and multiple branches within generation at a time. So, the DFA would go from:

```
{0(gen=0,read=0..0)},

```

read "a",

```
{1(gen=0,read=0..1)},

```

read "b",

```
{2+(gen=0,read=0..2,frozen), 2+(gen=0,read=0..2), 0(gen=1,read=2..2)},

```

read "c",

```
{2+(gen=0,read=0..2,frozen), 3(gen=0,read=0..3)},

```

read "f",

```
{2+(gen=0,read=0..2,frozen)}.

```

Then the lexer would report state 2+, and since there is no option to continue, would report an error state. Not sure how well this idea would work...

For "abcd", it would work like this:

```
{0(gen=0,read=0..0)},

```

read "a",

```
{1(gen=0,read=0..1)},

```

read "b",

```
{2+(gen=0,read=0..2,frozen), 2+(gen=0,read=0..2), 0(gen=1,read=2..2)},

```

read "c",

```
{2+(gen=0,read=0..2,frozen), 3(gen=0,read=0..3)},

```

read "d",

```
{2+(gen=0,read=0..2,frozen), 4+(gen=0,read=0..4,frozen), 4+(gen=0,read=0..4), 0(gen=1,read=4..4)}.

```

Now of these, it's possible to drop the first (there is a longer match) and the third (there are no state transitions out), leaving:

```
{4+(gen=0,read=0..4,frozen), 0(gen=1,read=4..4)}.

```

Then the lexer would indicate "match: 4+" and continue reading input from state 0 using generation index 1.

Is this idea of mine, running DFAs nondeterministically, how maximal munch lexical analyzers work?

# Answer
> 3 votes
There are two ways to handle this issue:

1. The most common implementation (the one used in lex, flex and other similar scanner generators) is to always recall the last accept position and state (or accept code). When no more transitions are possible, the input is backed up to the last accept position and the last accept state is reported as the accepted token.

If you're trying to do streaming input, you will need a fallback buffer to handle this case.
2. Alternatively, if the scan reaches an accepting state but another transition is available, we can start performing two scans in parallel: one on the assumption that the transition will be taken, and the other on the assumption that it will not. The second thread may need to fork again, although there is a maximum number of forks, as with generalised LR parsing. In this model, we need to keep a buffer of possible "future" tokens which will be processed if the optimistic thread fails.

I don't know of a practical implementation of the second strategy in a general purpose scanner generator, although there are some papers about how you might do it. Apparently it can be done in time and space linear to the size of the input, which is (in theory) better than the quadratic time consumption of backtracking.

However, it is pretty rare that you find a token grammar which needs to allow unrestricted backtracking. The most common cause of unrestricted backtracking is failing to take into account the fact that things like quoted strings might not be correctly terminated in an incorrect program, so you end up with just the rule:

```
["]([^"]|\\.)*["]   { Accept a string }

```

instead of the pair of rules

```
["]([^"]|\\.)*["]   { Accept a string. }
["]([^"]|\\.)*      { Reject an unterminated string. }

```

(Maximal munch will guarantee that the second rule will only be used if the first rule cannot match.)

So while the second strategy may have some theoretical appeal, it seems to me that it's of little practical use. Flex even has some options which will help you to identify rules which could backup on failure, and this can help you craft your lexical grammar to avoid the problem. It's not always easy to eliminate 100% of backing up (although it often is, and if you manage to do so, flex will reward you by generating a faster lexer), but it's pretty rare to find a lexical grammar which requires more than a few characters of back-up, and the cost of a small fallback buffer is really not worth worrying about, in comparison with the complexity of the alternative (which, of course, also needs extra memory.)

I have seen intermediate strategies for particular grammars. If you know your grammar well enough, you could hand-build the speculative tokenisation in order to avoid backing up. I've seen that, years ago, in SGML lexers which eliminate the rescan of `>` following a tagname by including a redundant rule which recognised a tag immediately followed by a `>` and handled both tokens at once. That must have saved a few cycles, but it's hard to believe that it really made a huge difference, and the difference would likely be even less significant today. Still, if you are the type who obsesses about saving every possible cycle, you could do it.

---
Tags: finite-automata, nondeterminism, lexical-analysis
---


# Question
Title: Karp hardness of searching for a matching cut
Follow-up question in the series:

Karp hardness of searching for a matching erosion

Karp hardness of searching for a matching split

> **Maximum Matching Cut** problem
>
> **Input**: An undirected graph $G(V, E)$ and an integer $k$
>
> **Output**: **YES** if there exists $M \subseteq E$ such that $M$ is a matching of size $k$ (i.e. $k$ edges) and also a cut, **NO** otherwise

What is the complexity of this problem? (Turing completeness was established, what can we tell about its Karp hardness?)

---

*An edge cut is a subset of $E$ the removal of which would increase the number of connected component of $G$, and for each edge in the set, its two endpoints are in (two) different components.*

# Answer
You can reduce the problem without cardinality constraint to the problem with cardinality constraint.

For an instance $G=(V,E)$ of the problem without cardinality constraint, simply add $m\>|V|/2$ isolated edges as well as $2m$ new vertices. Now there is a matching cut in the old graph if and only if there is a matching cut of size $m+1$ in the new graph.

---

Edit: One can also add an edge $(u,v)$ for each newly added edge $(u,x)$ and a fixed vertex $v$ in the previous graph to make $G$ connected. The conclusion is the same.
> 2 votes

# Answer
*This is not supposed to be an answer (eventually, being satisfied enough with the literature and my own's new result, I accept this). But, I wanna mention a very **closely related** result. Namely, without the requirement of cardinality $k$, the problem is NP-complete.*

However, using their result, it is immediately that our problem is **Turing-complete** for $\mathrm{NP}$. The poly-time Turing reduction just query our problem (as an oracle) of every possible $k$.

The ***Maurizio duo*** of ***Roma Tre*** showed our problem (without the cardinality requirement) to be $\mathrm{NP}$-complete in the paper titled "The Complexity of the Matching-Cut Problem" (pdf file)

What makes their hardness proof not guarantees the cardinality requirement $k$ is that the cardinality of the matching cut inside each clause-gadget (the **A**, **B**, **C**, **D**, **E**, **F** cut types in **Table 1** in the paper) can have cardinality of $4$ or $6$. So, we cannot include any cardinality indication $k$ to the produced instance.

---

**UPDATE**: There is also literature proof that Maurizio duo's hardness can be proven *even when restricted to bipartite graphs of bounded diameter*. Though, it is unclear how bipartiteness can help in our problem. Link to the latest article on this topic: https://arxiv.org/pdf/1804.11102.pdf

---

**UPDATE**: xskxzr's answer finally settle down Karp hardness for this problem. Strictly speaking, literature notion of a matching cut requires that the given graph to be connected and the resulted graph to be split into exactly $2$ connected components. If more than two components are allowed. Then, based on the idea of xskxzr, I have managed to extend the construction of Maurizio duo of Roma Tre. Just extend the False chain and True chain to the left (or right, it does not matter) but the new vertices only have single edges link (not doubly linked) and each pair (one in the true chain, one in the false chain) is connected by $3$ edges with $2$ new nodes in between. Then, we can extend these two chains to a long enough length, to safely produce a required cardinality $K$. Since to separate the two chains, we can cut through the "middle" edges and finally when "nearly" reaching $K$, cut $2$ edges that link to the further new vertices. It seems to be difficult to reduce under the requirement of connectedness and a clean cut (exactly into $2$ components).
> 1 votes

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


# Question
Title: How to find a function in Lambda Calculus?
Yesterday I have been trying to complete this exercise. I have to find: $$ ((map)l)t \simeq \lambda k \lambda x ((k)(t)t\_1)....((k)(t)t\_n)x $$

where $$l=\lambda k \lambda x ((k)t\_1)....((k)t\_n)x$$ And $t$ is a generic Lambda term. I tried but without success. Maybe it will be something like that : $$map=(\lambda a \lambda b (\lambda s \lambda d((b(st))d)))$$ Thank you in advance to all will answer

# Answer
In your attempt,

$$map=(\lambda a \lambda b (\lambda s \lambda d((b(st))d)))$$

$a$ plays the role of $l$, $b$ the role of $t$, $s$ the role of $k$, and $d$ the role of $x$.

So, $b(st)d$ should actually play the role of $l(kt)x$, but here we see some mismatch: $b$ does not represent $l$, $a$ does that. Also, we can not use $t$, but must use $b$ instead.

Hence, the correct answer seems to be $a(sb)d$. We get (using the standard notational shortcuts)

$$map=(\lambda a b s d.\\, a(sb)d)$$

Try to check whether $map\\, l\\, t$ does $\beta$ convert to the intended term.

Your original idea, namely using $kt$ instead of $k$, seems to be the right intuition, as far as I can see.
> 1 votes

---
Tags: lambda-calculus
---


title: BST representation of Hash Tables

text:
# Question
Title: BST representation of Hash Tables
I'm reading this book Cracking Coding Interview. In this book author is speaking about BST representation of Hash Tables.

I googled a lot for BST Representation of Hash Table. Code in C++ but didn't find any link or example. Can someone help me with the implementation. I'm really confused how to represend Key-Value pairs on BST. And what if there are collisions etc.

All, I found was comparison b/w BST and HasTables:

1. https://stackoverflow.com/questions/22996474/why-implement-a-hashtable-with-a-binary-search-tree
2. https://www.geeksforgeeks.org/advantages-of-bst-over-hash-table/

# Answer
> 4 votes
What the author means by implementing a HashTable as a BST is simply implementing a BST with $insert(), \space delete() \space and \space search()$ with slight modifications

1. The node of the BST would have the following structure. $Node \space := (Key,Value)$.
2. Insert a key-value pair by performing comparisons on the keys of two different pairs.
3. Avoids nodes with redundant keys i.e. before insertion, if a node in the BST with the same key value exists, do not insert it. Else if no node with the same key exists, insert the key-value pair.
4. No change in delete function.
5. Search returns $null$ if no node's key matches, else return the value associated with the key which was searched.

Then use these functions assuming that these perform the corresponding operations on a HashTable.
Using a self-balancing BST would give $O(log\space n)$ time complexity for all the three functions defined above. And iterating through all the key-value pairs would simply mean doing an in-order traversal of the BST.

---
Tags: hash-tables, binary-search-trees
---


# Question
Title: Karp hardness of searching for a matching split
## UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (*UTC is now 17 Sep 01:57*)

This is yet another follow-up question in the series:

Karp hardness of searching for a matching cut

Karp hardness of searching for a matching erosion

In this question, we further restrict the notion of a matching erosion (which is already a restricted notion of a matching cut). Formally, our definition is as follows.

Given an undirected graph $G(V, E)$, a **matching split** $M=(A, B)$ is a partition of $V$ into two disjoint subsets, i.e. $A\cap B = \emptyset \land A\cup B = V$ that satisfies the following conditions:

* $G\[A\]$ and $G\[B\]$ are two disjoint induced subgraphs
* The edge set of the cut $M = \\{uv\in E\vert u\in A \land v \in B\\}$ is a matching (here, we abuse the notation a little bit, $M$ is both the partition $(A, B)$ and the edge set of the matching cut)
* Each vertex $u\in A$ is incident to exactly one edge in $M$
* Each vertex $u\in B$ is incident to exactly one edge in $M$

Clearly, we should have $|A|=|B|=|V|/2$, hence the name of this concept.

Our decision problem **Matching Split** naturally asks whether a given graph $G$ has a matching split.

Our question is: What is the complexity of deciding **Matching Split**?

# Answer
> 3 votes
It is NP-complete. Clearly it belongs to NP. To prove its NP-completeness, we'll reduce not-all-equal 3-satisfiability (NAE3SAT) to this problem.

Given an instance of NAE3SAT with $n$ variables and $m$ clauses, construct a graph as follows:

1. For each **literal** $l$, construct a **complete** graph with $m+1$ vertices $v\_0(l),\ldots,v\_m(l)$.
2. For each variable whose positive and negative literals are respectively $l\_i$ and $l\_j$, add an edge between $v\_0(l\_i)$ and $v\_0(l\_j)$.
3. For each clause $c\_i=l\_i^1\vee l\_i^2\vee l\_i^3$, add the following structure:

In addition, for each literal $l$ other than $l\_i^1,l\_i^2,l\_i^3$, add a new vertex $v\_i'(l)$ and an edge between $v\_i(l)$ and $v\_i'(l)$.

Now we assert that the instance of NAE3SAT is satisfiable if and only if the graph has a matching split.

If the instance of NAE3SAT is satisfiable, consider a valid truth assignment. If $l$ is a truth literal, we put $v\_i(l)$'s into $A$ and $v\_i'(l)$'s (if exists) into $B$ for all $i=0,\ldots,m$, otherwise we put $v\_i(l)$'s into $B$ and $v\_i'(l)$'s into $A$. In addition, for the structure corresponding to $c\_i$ (we assume $l\_i^1$ and $l\_i^2$ are truth literals while $l\_i^3$ is a false literal without loss of generality), we put $v\_i^{12}, v\_i^{123}$ into $A$ and put $v\_i^{23}, v\_i^{31}, v\_i^{122331}$ into $B$. We can see this partition is a matching split.

If the graph has a matching split, we can observe firstly that $v\_0(l),\ldots,v\_m(l)$ should be put into the same part since they make up a complete graph (assume $m\ge 2$ without loss of generality). In addition, if $l\_i$ and $l\_j$ correspond respectively to the positive and negative literals of the same variable, $v\_k(l\_i)$ and $v\_k(l\_j)$ should be put into different parts otherwise $v\_0(l\_i)$ or $v\_0(l\_j)$ has no neighbor in the other part. If the positive literal corresponding to a variable is put into $A$, we assign the variable to True, otherwise we assign it to False. Note for each clause $c\_i$, $v\_i(l\_i^1), v\_i(l\_i^2)$ and $v\_i(l\_i^3)$ cannot be put into the same part otherwise $v\_i^{123}$ has either no neighbor or $3$ neighbors in the other part. Hence this assignment is a valid assignment for the instance of NAE3SAT.

---

Edit: One can simply add edges among $v\_0(l)$'s to make the graph connected. For example, if the clauses are $l\_1\vee l\_2\vee l\_3$ and $l\_4\vee l\_5\vee l\_6$, one can simply add an edge between $v\_0(l\_3)$ and $v\_0(l\_4)$. The idea is that for a valid assignment, if we flip all the values of variables involved in one connected component, the assignment is still valid. In the example, this means we can always assume $v\_0(l\_3)$ and $v\_0(l\_4)$ are put into the same part.

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


# Question
Title: Not able to find any pattern for $4T(n/2)+n^2 n^{1/2}$
I have tried my best but I'm not able to find any pattern for the $n^2n^{1/2}$ part. This question must be solved iteratively and I get totally clueless after two iteration.s I've to find tight bound in big-O.

# Answer
> 1 votes
Here is what happens when you expand the recurrence: $$ \begin{align\*} T(n) &= n^{5/2} + 4(n/2)^{5/2} + 4^2(n/2^2)^{5/2} + 4^3(n/2^3)^{5/2} + \cdots \\ &= n^{5/2} \left(1 + \frac{4}{2^{5/2}} + \left(\frac{4}{2^{5/2}}\right)^2 + \left(\frac{4}{2^{5/2}}\right)^3 + \cdots \right). \end{align\*} $$ Since $4/2^{5/2} = 1/\sqrt{2} \< 1$, the large bracketed expression converges, and so the answer is $T(n) = \Theta(n^{5/2})$.

# Answer
> 1 votes
\begin{equation} T(n) = 4T(\frac{n}{2}) + n^{\frac{5}{2}} = 4^2T(\frac{n}{2^2}) + 4(\frac{n}{2})^{\frac{5}{2}} + n^{\frac{5}{2}} \end{equation} On the $k^{th}$ iteration, we get \begin{equation} T(n) = 4^kT(\frac{n}{2^k}) + \sum\limits\_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}} \end{equation} which terminantes at $k = \log\_2 n$ The part $$4^kT(\frac{n}{2^k}) = O(4^{\log\_2 n}) = O(n^2)$$ The sum part could be arranged as \begin{equation} \sum\limits\_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}} = n^{\frac{5}{2}} \sum\limits\_{i=0}^{k-1} 4^i (\frac{1}{2^i})^{\frac{5}{2}} = n^{\frac{5}{2}} \sum\limits\_{i=0}^{k-1} \Big( \frac{4}{2^{\frac{5}{2}}} \Big)^{i} = n^{\frac{5}{2}} \frac{1- \big(\frac{4}{2^{\frac{5}{2}}}\big)^k}{1 - (\frac{4}{2^{\frac{5}{2}}})} \end{equation} where the last equality comes from realizing that we have a geometric series. Notice that \begin{equation} \frac{4}{2^{\frac{5}{2}}} = (\sqrt{2})^{-1} \end{equation} So \begin{equation} \sum\limits\_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}} = n^{\frac{5}{2}} \frac{1 - (\sqrt{2})^{-k}}{1 - \frac{\sqrt{2}}{2}} \end{equation} But algorithm terminates at $k = \log\_2 n$ so \begin{equation} \sum\limits\_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}} = O( n^{\frac{5}{2}} \frac{1 - (\sqrt{2})^{-\log\_2 n}}{1 - \frac{\sqrt{2}}{2}} ) = O\Big( \alpha n^{\frac{5}{2}} (1 - (\sqrt{2})^{-\log\_2 n}) \Big) \end{equation} where $\alpha = \frac{1}{1- \frac{\sqrt{2}}{2}}$ But \begin{equation} (\sqrt{2})^{-\log\_2 n} = \frac{1}{(\sqrt{2})^{\log\_2 n}} = \frac{1}{2^{\log\_2 \sqrt{n}}} = \frac{1}{\sqrt{n}} \end{equation} So \begin{equation} \sum\limits\_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}} = O( n^{\frac{5}{2}} \frac{1 - (\sqrt{2})^{-\log\_2 n}}{1 - \frac{\sqrt{2}}{2}} ) = O\Big( \alpha n^{\frac{5}{2}} (1 - \frac{1}{\sqrt{n}}) \Big) = O( n^{\frac{5}{2}}) \end{equation} So \begin{equation} T(n) = \underbrace{4^kT(\frac{n}{2^k})}\_{O(n^2)} + \underbrace{\sum\limits\_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}}}\_{ O( n^{\frac{5}{2}})} = O( n^{\frac{5}{2}}) \end{equation}

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Approximately sorting integers by many criteria
Given $k$ functions $f\_0, f\_1...f\_k$, a large dataset of size $n$, is there an algorithm that will "approximately" sort the dataset according to all of the functions so that "most" items of the dataset end up close to where they should be if they were sorted by any one of the functions alone.

More formally, if we have the functions $R\_k(i)$ which gives the rank of item $i$ if the dataset were sorted with $f\_k$, and $R'(i)$ which gives the actual rank of the item, we can define the statistic: $$r\_k = 1 - \frac{6\sum\_{i=0}^n{(R'(i) - R\_k(i))^2}}{n(n^2-1)}$$ (this is the Spearman rank correlation coefficient of the actual against predicted positions)

*Is there an algorithm which will increase the total $r = \sum\_{i=0}^k{r\_i^2}$, either by outright maximising $r$, or some kind of convergent process which can increase $r$ to its maximum?*

Obviously, sorting according to just one of the functions will give $r \> 0$ but can we do better than this?

I am not really concerned with running time, but anything better than the naive $O(n!)$ of going through all the permutations and computing $r$ would be good.

The motivation for this is to improve branch prediction while searching a large dataset without using any extra space.

# Answer
> 2 votes
I don't know if there is an efficient algorithm that will always produce the optimal solution. I would suggest looking at heuristics that hopefully will often work well, even if they don't come with guarantees. One plausible approach would be to use simulated annealing, or some other form of local search. At any point, you can pick a pair of random indices $i,j$ and consider would happen to $r$ if you swap the items at those two locations; then the simulated annealing algorithms describes the conditions under which you apply that swap vs not. Repeat until convergence. There are no guarantees this will give the global optimum -- it get stuck in a local optimum -- but it could be worth a try.

---

If you are OK with maximizing $\sum\_i r\_i$ instead of maximizing $\sum\_i r\_i^2$, the following might work. You might be able to reduce this to the assignment problem and then apply a standard algorithm for the assignment problem. In particular, for each item $i$ and each rank $j \in \\{0,1,2,\dots,n\\}$ create an edge from item $i$ to rank $j$ whose cost is $\sum\_k 6(j-R\_k(i))^2/n(n^2-1)$. Then, use an algorithm for the assignment problem to find an assignment that assigns a unique rank to each item. The sum of the costs of the selected edges will be equal to $k-\sum\_i r\_i$, so minimizing the sum of the costs will maximize $\sum\_i r\_i$. Assigning each item to a unique rank is equivalent to sorting the items; you just put the items in order of their rank. The assignment problem ensures that no two items will receive the same rank, and every item will receive some rank.

I'm not sure if this works or not. At one point I thought this would work; then at another point I thought it wouldn't work (but I can't remember why not); and now I'm thinking again that this should work, and give a polynomial-time algorithm to find the exact solution for maximizing $\sum\_i r\_i$. As you can see, I've gotten myself totally mixed up here, so I don't trust my thought process. Double-check all of my reasoning here before placing any reliance on it. (Even if this doesn't give the optimal answer, it's also possible that it provides a useful initialization for simulated annealing.)

---
Tags: algorithms, sorting
---


# Question
Title: What makes a proof assistant a proof assistant?
You open a code editor, define a syntax with lambdas, a few primitives. Then you invent some nice computation rules, some cool typing rules, and write a corresponding interpreter and "type checker". Congratulations! You just built a proof assistant! Now you can formalize all of mathematics on it! Or can you? After all, what makes the thing you built a valid "proof assistant"? What constitutes a "type checker"? As far as I'm concerned, you could have actually implemented Tetris, claimed that blocks are terms, their shapes are types, and the game loop is the computation rule. Who has authority to argue you're wrong?

When it comes to implementing a "programming language", the definition is much more clear. Just invent a syntax, a set of reduction rules and prove your thing Turing-complete. Then it is as good as a programming language is expected to be. When it comes to implementing a proof assistant, I have no idea. Sure, there are common things I see present in proof assistants, so, intuitively, I know what they are. They have lambdas and the corresponding dependent function space, they have inductive datatypes and their introductions and eliminations, and they must be consistent, which mean at least some type is uninhabited. But what if my "proof assistant" has no lambdas nor datatypes? It could have for example just combinators. I don't have a precise definition of what makes a "type theory" a "type theory".

**What, formally, makes a program a valid proof assistant, in the same sense that Agda/Coq are? What is a precise and complete definition of a type theory? And what one must do to "justify" his syntax, reduction and typing rules?** I'm making this specifically because, while I feel like I can, given enough time, implement something like A Cosmology of Datatypes, I do not feel the freedom to make any change, even minimal, to whatever the author did, because I do not know what justifies those things he did.

# Answer
I would expect a proof assistant to provide:

1. a syntax to express some mathematical *statements*
2. a syntax to express a *proof* of one of those statements
3. a computational process to "check" that a proof of a statement is indeed valid (returns success or failure, or maybe does not return at all)

Finally, for such a proof assistant to be trustworthy, it should come with a justification of the fact that when its checking process says that a proof of a statement is valid, then indeed this statement is valid in the usual mathematical sense -- there exists a mathematical proof that mathematicians will accept.
> 8 votes

# Answer
I would think a proof assistant is something which can represent proofs and validate the reasoning is correct. The underlying logic/type theory just determines which reasoning can be represented and validated.

I like your example of Tetris, perhaps it is a proof assistant for a limited subset of geometry, which checks a proof of "these shapes of blocks with these orientations form a solid row of blocks" or something like that
> 5 votes

---
Tags: terminology, type-theory, proof-assistants
---


# Question
Title: What is the fastest algorithm to check whether input table is a group?
Given an input table with binary operation $\circ$. I want to check whether given input table represents a group or not.

I need to verify the four axioms of a group.

1. The identity I can find it by just scanning the first row of the given table. -----$\mathcal{O}(|G|)$ running time.
2. Find the closure operation ie.e for any $x,y \in G$, I need to show that $x \circ y \in G $.------$\mathcal{O}(|G|^2)$
3. An inverse of an element.----$\mathcal{O}(|G|^2)$ Running time.
4. Associativity operation. -----$\mathcal{O}(|G|^3)$

Which gives me a $\mathcal{O}(|G|^3)$ running time algorithm to check whether the input table corresponds to some group.

**Question** : What is the fastest algorithm to check whether the input table is a group?

Model of computation is RAM, which computing $x \circ y$ takes constant time.

# Answer
> 4 votes
There is a non-trivial randomized algorithm that can solve this in $O(n^2 \log (1/\delta))$ time, where $\delta\>0$ is the desired error probability. See

Verification of Identities. Sridhar Rajagopalan and Leonard J. Schulman. SIAM Journal on Computing, 29(4), pp.1155-1163.

---
Tags: algorithms, algebra
---


# Question
Title: Are the languages $\{w\in \{a,b\}^* : \#_a(w) > \#_b(w) \}$ and $\{w\in \{a,b\}^* : \#_a(w) \neq \#_b(w) \}$ context free?
So at the beginning I was aiming at $L\_{a\neq b} = \\{w\in \\{a,b\\}^\* : \\#\_a(w) \neq \\#\_b(w) \\}$. But figured out that is would be better to first deal with: $L\_{a\>b} = \\{w\in \\{a,b\\}^\* : \\#\_a(w) \> \\#\_b(w) \\}$, due to the fact that $L\_{a\>b} \cup L\_{b\>a} = L\_{a\neq b}$.

My attempts so far for $L\_{a\>b}$ - I proved that this language is pump-able: Choosing $N=2$ For $z\in L$ contains only $a$s the pump it pretty basic, on the other hand words contain $b$s: $\\#\_b(z) \> 0 \Rightarrow \\#\_a(z) \> \\#\_b(z) \>0 $ so $z$ must include the couple $ab$ or $ba$ as a sub string, so $ z= \gamma ab\delta \Rightarrow \gamma|a|\varepsilon|b|\delta$ is a valid splitting, and $\gamma a^ib^i\delta\in L$ because the relation between $a$'s and $b$'s appearances is preserved.

So I was hoping this language might be context free and tried to form a Grammar which generates the language, However I didn't succeed in it, due to the fact that a general word of the form: $a^{i\_1}b^{j\_1}a^{i\_2}b^{j\_2}...a^{i\_n}b^{j\_n}$ when $i\_k,j\_k \in \mathbb{N}\cup\\{0\\}$ satisfies $\sum i\_k \> \sum j\_k$ and I am having hard time dealing with cases in which $i\_l \<j\_l$ (for example $aaaababb$ when the second pair is $abb$).

I don't know whether I may proceed from my best attempt, yet, in case $ z = a^{i\_1}b^{j\_1}a^{i\_2}b^{j\_2}...a^{i\_n}b^{j\_n}$ satisfies $i\_k \> j\_k \forall k\in \[n\]$ The grammar $A\rightarrow a | AA|AAB|BAA , B\rightarrow b$ with A as the initial term, should work (I didn't formally prove it so I might be wrong).

I also tried to work with closure properties but couldn't even find an idea to start with...

# Answer
Here is a hint. Given a word in $L\_{a\gt b}$, if you remove $ab$ or $ba$ from it repeatedly until you cannot any more, what kind of word will you end up with?

Here is an almost complete answer.

> The language $L\_{a\gt b}$ is similar to the language where the number of "a"s is equal to the number of "b"s, except there can be arbitrary number of extra "a"s at any position and there must be at least one extra "a" somewhere.
> Here is its context-free grammar:
> $\quad S \to TaT$
> $\quad T \to TT|bTa|aTb|aT|\epsilon$
> As a part of a proof that the above grammar generates $L\_{a\gt b}$, let us show that $T$ stands for a word that has no less "a"s than "b"s. $T$ can only generate such kind of word, since whenever a "b" is included, an "a" is included. Now suppose $Z$ is such a word that is not empty. There are two cases.
> If $Z$ starts with a "b", let us walk through the symbols in $Z$ from its beginning, counting how many "a"s and how many "b"s along the way. So initially we have zero "a" and one "b". At some point of this walk, we will count an equal number of "a"s and "b"s since $Z$ has no less "a"s than "b"s. That means $Z=bXaY$ for some words $X$ and $Y$, where $bXa$ has the same number of "a"s and "b"s and where $Y$, the remaining part, must have no less "a"s than "b"s. Note that both $X$ and $Y$ are shorter than $Z$.
> The other case is when $Z$ starts with an "a", that is, $Z=aW$ for some word $W$. If $W$ has no less than "a"s than "b"s, we are in good condition since $W$ is shorter than $Z$. Otherwise, $W$ has (exactly one) less "a"s than "b"s. There are two subcases. If $W$ ends with a "b", then $Z=aUb$, where $U$ has no less "a"s than "b"s and $U$ is shorter than $Z$. Otherwise, $W$ ends with an "a". Now let us walking through symbols of $W$ from its end, counting the number of "a"s and the number of "b"s along the way. At some point of our walk, we will count an equal number of "a"s and "b"s. That means $W=UV$ for some word $V$ that has the same number of "a"s and "b"s. So $Z=aUV$, where $aU$ must have no less "a"s than "b"s. Note that both $U$ and $V$ are shorter than $Z$.
> The preceding two paragraphs shows that $Z$ must comes from two or one shorter word that also has no less "a"s than "b"s by the production rule of $T$. Since $T$ can be replaced by the empty word $\epsilon$, we see that $T$ can generate all words that has no less "a"s than "b"s.

---

**Exercise**
Is the language $L\_{a\gt b\gt c} = \\{w\in \\{a,b,c\\}^\* \vert \\#\_a(w) \> \\#\_b(w) \> \\#\_c(w)\\}$ context free?
> 2 votes

---
Tags: context-free, formal-grammars
---


# Question
Title: Decidability of language L = { n : ∃x∈N, n = 3x+2 }
I've recently came across this language and I don't know if my hint for proving its class is correct or not.

$$L = \\{ n : \exists x \in N, \\,n=3x+2 \\} $$$n$ is in binary format.

I think $L$ is decidable and as proof I was considering using a canonical enumerator of $\\{0,1\\}^\*$.

For each word $x$ printed by the enumerator, my algorithm would compute $3x+2$ and halt if the result was equal or greater to the provided input. If equal, then accept, if greater, then reject.

I would like someone to confirm if I'm correct, pointing me in the right direction if I'm not.

# Answer
Yes, your approach is correct.

The description of your algorithm would be clearer if it also mentions the following.

* The algorithm rejects the empty word immediately.
* That canonical enumerator of $\\{0,1\\}^∗$ enumerates all positive integers in increasing order.
* If $3x+2$ is smaller than the input then the result will be ignored and the enumerator will keep going.

Another algorithm that decides the language would be subtracting 3 from the input number and checking the result repeatedly. If the result is 2, it accepts. If the result is negative, it rejects. It also rejects the the empty word immediately.
> 0 votes

---
Tags: computability
---


# Question
Title: What are the implications of Lean not having the type `Set`?
In Coq we have an impredicative base type, called `Prop`, and a predicative base type, called `Set`, both of type `Type 0`.

On the other hand, in Lean we only have an impredicative base type. We do not have an equivalent to `Set`. Instead we use directly `Type 0`(a synonym of `Sort 1`).

What are the implications of this design decision?

# Answer
In Coq `Set` behaves basically like the smallest possible `Type`. Unlike Coq however, Lean lets you select the "level" of the type manually, such as `Type 9` (or `Sort 10`), something which is not allowed in Coq - meaning that you do not need `Set` in Lean, you can just use `Type 0` (or just `Type`, or `Sort 1`) instead as it is basically the same thing. I should also note that in Lean `Prop` is the same as `Sort 0` (or `Sort`) (which does not have large elimination) and `Type n` (for `n : nat`) is the same as `Sort (n + 1)` (which has large elimination).

TL;DR: `Type` (with no "arguments") is the `Set` of Lean
> 2 votes

---
Tags: type-theory, proof-assistants, coq
---


# Question
Title: Difference between delayed branches and out-of-order execution
I have been reading about instruction pipeline and I stumbled upon the term delayed branches. From what I have understood, delayed branches will keep the pipeline busy, by executing instructions, regardless of the outcome of the branch. This will avoid the usages of `NOP` instructions.

What I do not understand is, how is it it different than Out-of-order execution? In the following example, which I just made up:

```
1    MOV eax, 5
2    MOV ecx, 6
3    MOV ebx, 2
4    CMP eax, ecx
5    JG label1
6    SUB ecx, ebx
7    CALL someFunc
8 label1:
9    SUB eax, ecx
10    CALL someOtherFunc

```

if I have understood delayed branches, before the decision is made, whether the jump to label1 will occur, the instructions on line 6 and 7 will be loaded in the pipeline. But isn't this exactly out-of-order execution?

# Answer
> 2 votes
I suppose you could view branch delay slots as a very special sort of out-of-order execution, but this isn't usually what we mean when we talk about out-of-order execution: generally, we're referring to a CPU that has a more general mechanism to detect when instructions can be re-ordered. In addition, usually out-of-order execution takes care to avoid changing the semantics/behavior of the instructions. In contrast, a branch delay slot does change the behavior of the instructions (because it affects whether the instruction after the branch is executed or not).

# Answer
> 2 votes
The "normal" way to execute code goes like this: There is a program counter (PC). The processor executes the instruction pointed to by the program counter. If that instruction is an unconditional branch, or a conditional branch and the condition is true, then the program counter is set to the destination of the branch. Otherwise, the program counter is increased by the length of the instruction.

With out-of-order execution, it seems to the programmer as if everything happened exactly the "normal" way. But internally, the processor can re-order instructions, as long as the observed behaviour is unchanged. An example: You have three instructions: Read X from memory, add X to Y, set Z to 0. Since "Read X from memory" takes a long time, and "add X to Y" must wait until X has been read, the processor executes "set Z = 0" before "add X to Y". But the behaviour that the programmer observes is the same. If they check what the value of Y is, that check is itself an instruction that waits until "add X to Y" is executed, so the value will look fine.

Delayed branches don't work like that. They *change* the semantics of the code in a defined way. Where I said earlier "if the instruction is a conditional branch and the condition is true, the program counter is set to the destination of the branch", that is not true. Instead, the program counter is set to the destination of the branch *after the next instruction has been executed*.

With delayed branches, instructions are still executed *in order*, but the meaning of "in order" has changed. If you have instructions (A, B, C, conditional branch, D, E, F) and the instructions at the destination of the conditional branch are X, Y, Z then instead of the usual order A, B, C, X, Y, Z the order is A, B, C, D, X, Y, Z. And these instructions are executed in order (they might actually be executed out of order, but except for the difference in speed you wouldn't notice).

---
Tags: cpu, cpu-pipelines
---


# Question
Title: Is there a difference between using $n$ and $\Theta(n)$ in recurrences?
Is there a difference between $T(n)=2T(n/2)+n$ and $T(n)=2T(n/2)+Θ(n)$ when using the master theorem? I've seen it both ways and am a little confused. (Looking for the answer $nlogn$).

# Answer
A recurrence of the form $$ T(n) = 2T(n/2) + \Theta(n) $$ is really a shorthand for a recurrence of the form $$ T(n) = 2T(n/2) + f(n), \text{ where } f(n) = \Theta(n). $$

Let us consider a recurrence of this form, and let us suppose that $an \leq f(n) \leq bn$, where $a,b \> 0$. Consider the more general recurrence $$ T\_c(n) = 2T\_c(n/2) + cn, $$ with the same initial values as the $T(n)$ recurrence. You can prove by induction on $n$ that $$ T\_a(n) \leq T(n) \leq T\_b(n). $$ Therefore, if you can show that $T\_c(n) = \Theta(n\log n)$ for all $c$ (where the hidden constant could depend on $c$), then it would follow that also $T(n) = \Theta(n\log n)$.
> 2 votes

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Solving $$f(x, k) = f(x, k-1) + f(x-1, k-1) + \dots + f(1, k-1)$$ in terms of $x$
I'm having trouble determining the complexity of an algorithm. Let's say the number of operations of my algorithm is described by $$f(x, k) = f(x, k-1) + f(x-1, k-1) + f(x-2, k-1) + \dots + f(1, k-1)$$ where $f(x, 1) = x$

How can I describe the growth of $f(x)$ in terms of

1. $x$
2. $k$
3. $x$ when $k=x-1$

For 1), I believe $f(x, k)$ would be exponential in $x$ as $k$ can be taken to be a constant which would reduce the above equation to being similar to

$$f(x) = f(x-1) + f(x-2) + \dots + f(1) $$

Similarly, for 2), I believe $f(x, k)$ would be exponential in $k$ as I would need to take $x$ as a constant which would lead to the below equation

$$f(k) = xf(k-1) $$

Need help with 3) and also validating my thinking for 1) and 2)

# Answer
The answers to all three questions become easier once we proved the following formula for all positive integer $k$ and $x$. $$ f(x,k) = \frac{x(x+1)(x+2)\cdots(x+k-1)}{k!}$$ Proof: The formula is easily seen to be true for $k=1$ and all positive integer $x$.

Assume the formula is true for some positive integer $k$ and all positive integer $x$. Then, $$\begin{align} &f(x, k+1)\\ &=f(x, k) + f(x-1, k) + f(x-2, k) + \dots + f(1, k)\\ &=\frac1{k!}(x(x+1)(x+2)\cdots(x+k-1) + (x-1)x(x+1)(x+2)\cdots(x+k-2)\\ &\quad\quad+\cdots+1\cdot2\cdots k\\ &=\frac1{k!}\left(\frac{x(x+1)(x+2)\cdots(x+k)-(x-1)x(x+1)\cdots(x+k-1)}{k+1}\right.\\ &\quad\quad+\frac{(x-1)x(x+1)\cdots(x+k-1)-(x-2)(x-1)x\cdots(x+k-2)}{k+1}\\ &\quad\quad+\cdots\\ &\quad\quad+\frac{2\cdot3\cdots(k+1)-1\cdot2\cdots k}{k+1}\\ &\quad\quad+\left.\frac{1\cdot2\cdots k}{k+1}\right)\\ &=\frac1{k!}\frac{x(x+1)(x+2)\cdots(x+k)}{k+1}\\ &=\frac{x(x+1)(x+2)\cdots(x+(k+1)-1)}{(k+1)!}\end{align}$$

By mathematical induction on $k$, the formula is true for all positive integer $k$ and $x$.

---

Here are the answers to your three cases.

1) For fixed $k$ and $x\to\infty$, $$f(x,k)=\frac{x^k}{k!}\frac xx\frac{x+1}x\cdots\frac{x+k-1}{x}\sim\frac{x^k}{k!}$$ That is, $f(x,k)=\Omega(x^k)$.

2) For fixed $x$ and $k\to\infty$, by Stirling's approximation, $$\begin{align}f(x,k)&=\frac{(x-1+k)!}{(x-1)!k!}\\ &\sim\frac1{(x-1)!}\frac{\sqrt{2\pi(x-1+k)}\left(\frac{x-1+k}{e}\right)^{x-1+k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}\\ &=\frac1{(x-1)!}\sqrt\frac{x-1+k}k (x-1+k)^{x-1}\left(\frac{x-1+k}{k}\right)^k\frac{1}{e^{x-1}}\\ &=\frac1{(x-1)!}\sqrt\frac{x-1+k}k\left(\frac{x-1+k}{k}\right)^{x-1}k^{x-1}\left(1+\frac{1}{\frac k{x-1}}\right)^{\frac k{x-1}(x-1)}\frac{1}{e^{x-1}}\\ &\sim\frac1{(x-1)!}k^{x-1}e^{x-1}\frac{1}{e^{x-1}}\\ &=\frac{k^{x-1}}{(x-1)!}\end{align}$$ That is, $f(x,k)=\Omega(k^{x-1})$

3) Let $k=x-1$ go to infinity, again by Stirling's approximation, $$f(x,k) = \frac{(2k)!}{k!k!}\sim \frac{\sqrt{2\pi2k}\left(\frac{2k}{e}\right)^{2k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}\sqrt{2\pi k}\left(\frac{k}{e}\right)^{k}}=\frac{2^{2k}}{\sqrt{\pi k}}$$ That is, $f(k+1,k)=\Omega(k^{-1/2}2^{2k})$.
> 3 votes

# Answer
You can write your recursion as \begin{equation} \begin{split} f(x,k) &= \sum\limits\_{i\_1=1}^x f(i\_1,k-1)\\ &= \sum\limits\_{i\_1=1}^x \sum\limits\_{i\_2=1}^{i\_1} f(i\_2,k-2)\\ &= \vdots \\ &= \sum\limits\_{i\_1=1}^x \sum\limits\_{i\_2=1}^{i\_1} \ldots \sum\limits\_{i\_{k-1}=1}^{i\_{k-2}} f(i\_{k-1},1)\\ &= \sum\limits\_{i\_1=1}^x \sum\limits\_{i\_2=1}^{i\_1} \ldots \sum\limits\_{i\_{k-1}=1}^{i\_{k-2}} i\_{k-1}\\ \end{split} \end{equation} We know that from Faulhaber's formula \begin{equation} \sum\limits\_{i\_{k-1}=1}^{i\_{k-2}} i\_{k-1} = \frac{1}{2}O(i\_{k-2}^2) \end{equation} So \begin{equation} f(x,k) = \sum\limits\_{i\_1=1}^x \sum\limits\_{i\_2=1}^{i\_1} \ldots \sum\limits\_{i\_{k-2}=1}^{i\_{k-3}} \frac{1}{2}O(i\_{k-2}^2) \end{equation} Also \begin{equation} \sum\limits\_{i\_{k-2}=1}^{i\_{k-3}} O(i\_{k-2}^2) = \frac{1}{3}O(i\_{k-3}^3) \end{equation} If you keep doing this, you'd get \begin{equation} f(x,k) = \frac{1}{2 \times 3 \times 4 \times \ldots \times (k-1) } \sum\limits\_{i\_1=1}^x O(i\_1^{k-1}) = \frac{1}{2 \times 3 \times 4 \times \ldots \times (k-1) \times k} O(x^k) = \frac{1}{k!} O(x^k) \end{equation}
> 3 votes

# Answer
For $k \geq 1$, define $$ T\_k(z) = \sum\_{n=0}^\infty f(n,k) z^n, $$ where we define $f(0,k) = 0$ (which agrees with the definition for $k=1$).

Since $f(n,1) = n$ for all $n$, we get $$ T\_1(z) = \sum\_{n=0}^\infty nz^n = z\sum\_{n=0}^\infty nz^{n-1} = z \frac{d}{dz} \sum\_{n=0}^\infty z^n = z \frac{d}{dz} \frac{1}{1-z} = \frac{z}{(1-z)^2}. $$ For $k \> 1$, we have $$ T\_k(z) = \sum\_{n=0}^\infty f(n,k)z^n = \sum\_{n=0}^\infty \sum\_{m=0}^n f(m,k-1) z^n = \sum\_{m=0}^\infty f(m,k-1) \sum\_{n=m}^\infty z^n = \\ \sum\_{m=0}^\infty f(m,k-1) z^m \sum\_{n=0}^\infty z^n = \sum\_{m=0}^\infty f(m,k-1) \frac{z^m}{1-z} = \frac{T\_{k-1}(z)}{1-z}. $$ A short induction shows that $$ T\_k(z) = \frac{z}{(1-z)^{k+1}}. $$ You can now consider the bivariate generating function $$ S(z,w) = \sum\_{n=0}^\infty \sum\_{k=1}^\infty f(n,k) z^n w^k = \sum\_{k=1}^\infty w^k T\_k(z) = z \sum\_{k=1}^\infty w^k (1-z)^{-k-1} = \\ \frac{z}{1-z} \sum\_{k=1}^\infty \left(\frac{w}{1-z}\right)^k = \frac{zw}{(1-z)^2}\frac{1}{1-w/(1-z)} = \frac{zw}{(1-z)(1-z-w)}. $$ From here you can in principle deduce all asymptotic properties. It is also easy to extract the exact formula, since the coefficients of $\frac{1}{(1-z)^k}$ are known.
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: Why must a function with polymorphic type `forall t: Type, t->t` be the identity function?
I am new to programming language theory. I was watching some online lectures in which the instructor claimed that a function with polymorphic type `forall t: Type, t->t` be the identity, but did not explain why. Can someone explain to me why? Maybe a proof of the claim from first principles.

# Answer
The first thing to note is that this isn't necessarily true. For example, depending on the language a function with that type, besides being the identity function, could: 1) loop forever, 2) mutate some state, 3) return `null`, 4) throw an exception, 5) perform some I/O, 6) fork a thread to do something else, 7) do `call/cc` shenanigans, 8) use something like Java's `Object.hashCode`, 9) use reflection to determine if the type is an integer and increment it if so, 10) use reflection to analyze the call stack and do something based on the context within which it is called, 11) probably many other things and certainly arbitrary combinations of the above.

So the property that leads to this, parametricity, is a property of the language as a whole and there are stronger and weaker variations of it. For many of the formal calculi studied in type theory, none of the above behaviors can occur. For example, for System F/the pure polymorphic lambda calculus, where parametricity was first studied, none of the above behaviors above can occur. It simply doesn't have exceptions, mutable state, `null`, `call/cc`, I/O, reflection, and it's strongly normalizing so it can't loop forever. As Gilles mentioned in a comment, the paper Theorems for free! by Phil Wadler is a good introduction to this topic and its references will go further into the theory, specifically the technique of logical relations. That link also lists some other papers by Wadler on the topic of parametricity.

Since parametricity is a property of the language, to prove it requires first formally articulating the language and then a relatively complicated argument. The informal argument for this particular case assuming we're in the polymorphic lambda calculus is that since we know nothing about `t` we can't perform any operations on the input (e.g. we can't increment it because we don't know if it is a number) or create a value of that type (for all we know `t`=`Void`, a type with no values at all). The only way to produce a value of type `t` is to return the one that is given to us. No other behaviors are possible. One way to see that is to use strong normalization and show that there is only one normal form term of this type.
> 32 votes

# Answer
The proof of the claim is quite complex, but if that's what you really want, you can check out Reynolds' original paper on the topic.

The key idea is that it holds for *parametrically polymorphic* functions, where the body of a polymorphic function is the same for all monomorphic instantiations of the function. In such a system, no assumptions can be made about the type of a parameter of polymorphic type, and if the only value in scope has a generic type, there's nothing to do with it but return it, or pass it to other functions you've defined, that can in turn do nothing but return it or pass it.. .etc. So in the end, all you can do is some chain of identity functions before returning the parameter.
> 15 votes

# Answer
With all the caveats that Derek mentions, and ignoring paradoxes that result from using set theory, let me sketch a proof in the spirit of Reynolds/Wadler.

A function of the type:

```
f :: forall t . t -> t

```

is a family of functions $f\_t$ indexed by type $t$.

The idea is that, to formally define polymorphic functions, we should not treat types as sets of values, but rather as relations. Basic types, like `Int` induce equality relations--e.g., two `Int` values are related if they are equal. Functions are related if they map related values to related values. The interesting case is polymorphic functions. They map related types to related values.

In our case, we want to establish a relation between two polymorphic functions $f$ and $g$ of the type:

```
forall t . t -> t

```

Suppose that type $s$ is related to type $t$. The first function $f$ maps type $s$ to a value--here, the value itself is a function $f\_s$ of the type $s \to s$. The second function maps type $t$ to another value $g\_t$ of the type $t \to t$. We say that $f$ is related to $g$ if the values $f\_s$ and $g\_t$ are related. Since these values are themselves functions, they are related if they map related values to related values.

The crucial step is to use the Reynolds' parametricity theorem, which says that any term is in a relation with itself. In our case, the function `f` is related to itself. In other words, if `s` is related to `t`, $f\_s$ is also related to $f\_t$.

We can now pick any relation between any two types and apply this theorem. Let's pick the first type as the unit type `()`, which has only one value, also called `()`. We'll keep the second type `t` arbitrary but non-empty. Let's pick a relation between `()` and `t` to be simply one pair `((), c)`, where `c` is some value of the type `t` (a relation is just a subset of the cartesian product of sets). Parametricity theorem tells us that $f\_{(\\,)}$ must be related to $f\_t$. They must map related values to related values. The first function $f\_{(\\,)}$ doesn't have much choice, it must map the only value `()` back to `()`. Therefore the second function $f\_t$ must map `c` to `c` (the only values related to `()`). Since `c` is completely arbitrary, we conclude that $f\_t$ is $id\_t$ and, since `t` is completely arbitrary, `f` is `id`.

You can find more details in my blog.
> 10 votes

# Answer
EDIT: A comment above has provided the missing piece. Some people are deliberately playing with less-than-turing-complete languages. I explicitly don't care about such languages. A really usuable not-turing-complete language is a crazy hard thing to design. The whole rest of this expands on what happens trying to apply these theorems to a full language.

False!

```
function f(a): forall t: Type, t->t
    function g(a): forall t: Type, t->t
       return (a is g) ? f : a
    return a is f ? g : a

```

where the `is` operator compares two variables for reference identity. That is, they contain the same value. Not an equivalent value, same value. Functions `f` and `g` are equivalent by some definition but they aren't the same.

If this function is passed itself it returns something else; otherwise it returns its input. The something else has the same type as itself therefore it can be substituted. In other words, `f` is not the identity, because `f(f)` returns `g`, whereas the identity would return `f`.

For the theorem to hold it has to assume the ridiculous ability to reduce

```
function cantor(n, <z, a>) : forall t: t: Type int, <int, t> -> <int, t>
    return n > 1 ? cantor((n % 2 > 0) ? (n + 1) : n / 2, <z + 1, a>) : <z, a>
return cantor(1000, <0, a>)[1]¹

```

If you're willing to assume that you can assume the much easier type inference can be handled.

If we try to restrict the domain until the theorem holds we end up having to restrict it awfully far.

* Pure Functional (no mutable state, no IO). OK I can live with that. A lot of time we want to run proofs over functions.
* Empty standard library. meh.
* No `raise` and no `exit`. Now we're starting to get constrained.
* There is no bottom type.
* The language has a rule that allows the compiler to collapse infinite recursion by assuming it must terminate. The compiler is allowed to reject trivial infinite recursion.
* The compiler is allowed to fail if presented with something that can't be proved either way.² Now the standard library can't take functions as arguments. Boo.
* There is no `nil`. This is starting to get problematic. We've ran out of ways to deal with 1/0.³
* The language can't do branch type inferences and does not have an override for when the programmer can prove a type inference the language cant. This is pretty bad.

The existence of both of the last two constraints has crippled the language. While it is still Turing complete the only way to get general purpose work out of it is to simulate an inner platform that interprets a language with looser requirements.

¹ If you think the compiler can deduce that one, try this one

```
function fermat(z) : int -> int
    function pow(x, p)
        return p = 0 ? 1 : x * pow(x, p - 1)
    function f2(x, y, z) : int, int, int -> <int, int>
        left = pow(x, 5) + pow(y, 5)
        right = pow(z, 5)
        return left = right
            ? <x, y>
            : pow(x, 5) < right
                ? f2(x + 1, y, z)
                : pow(y, 5) < right
                    ? f2(2, y + 1, z)
                    : f2(2, 2, z + 1)
    return f2(2, 2, z)
function cantor(n, <z, a>) : forall t: t: Type int, <int, t> -> <int, t>
    return n > 1 ? cantor((n % 2 > 0) ? (n + 1) : n / 2, <z + 1, a>) : <z, a>
return cantor(fermat(3)[0], <0, a>)[1]

```

² The proof that the compiler can't do this depends on blinding. We can use multiple libraries to ensure the compiler can't see the loop at once. Also, we can always construct something where the program would work but could not be compiled because the compiler can't perform the induction in available memory.

³ Somebody thinks you can have this return nil without arbitrary generic types returning nil. This pays a nasty penalty for which I have seen no effective language that can pay it.

```
function f(a, b, c): t: Type: t[],int,int->t
    return a[b/c]

```

must not compile. The fundamental problem is runtime array indexing doesn't work anymore.
> -3 votes

---
Tags: programming-languages, type-theory
---


# Question
Title: Given the regular set $S = a^*ba^*ba^*$, is the set $S'$ of all first thirds of strings in S (with length divisible by 3) regular?
I have no idea how to approach this problem, could I get at least a hint on how to go about proving/disproving this?

I've tried the pumping lemma but I don't think it applies here. I've also tried reasoning about closure properties, but I think my reasoning is faulty. My thought process so far is a string (with length divisible by 3) that is in L can be denoted as a regular expression. As such, the machine M for L can be broken down into M1, M2 and M3, each a machine for handling the first, middle and last thirds of the string. M2 would therefore be the machine corresponding to J, so J is regular.

# Answer
The first step is figuring out the language of first thirds of $S$. Let us denote this language by $L$. A good starting point is to consider the language $P$ of *prefixes* of $S$, since clearly $L \subseteq P$. The language $P$ is easy to find: it is $$ a^\*ba^\*ba^\* + a^\*ba^\* + a^\*. $$ With some work, you can show that $L$ and $P$ are rather close to each other, and so $L$ is regular. Details left to you.

---

More generally, if $S$ is *any* regular language, then the language $L$ of all first thirds of words in $S$ is *always* regular. The easiest proof of this is via NFAs. You can take it as a challenge, or look up material on the very similar operation of taking the first *half* of all words in a regular language.
> 4 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: How to find closed form solution of linear recursion using recursive tree method
I want to be able to find closed form runtime solution for recursive insertion sort which looks something like this

$$T(n)=\begin{cases} 1 &\text{if }n=1,\\ T(n−1)+3n &\text{if }n\>1. \end{cases}$$

However, I am confused about how to plot a tree. I know how to find runtime using tree if problem is divided into half. But here problem is just reduced by one. How does it work?

# Answer
Expanding the recursion, we get $$ \begin{align\*} T(n) &= 3n + T(n-1) \\ &= 3n + 3(n-1) + T(n-2) \\ &= 3n + 3(n-1) + 3(n-2) + T(n-3) \\ &= \cdots \\ &= 3n + 3(n-1) + 3(n-2) + \cdots + 3(2) + T(1) \\ &= 3n + 3(n-1) + 3(n-2) + \cdots + 3(2) + 1. \end{align\*} $$ Therefore $$ T(n) = 1 + \sum\_{m=2}^n 3m. $$ You take it from here.
> 2 votes

---
Tags: recurrence-relation
---


title: Master's theorem

text:
# Question
Title: Master's theorem
Is Master's theorem applicable on $T(n) = 2 T(\frac{n}{2})+n\log n$ ?

I got this doubt from here:

https://gateoverflow.in/227814/introduction-to-algorithms

# Answer
> 1 votes
Yes, Master's theorem is applicable to equations of type:

> $$T(n) = aT(\frac{n}{b}) + \Theta(n^k log^pn)$$

where $a \geq 1$, $b \gt 1$, $k \geq 0$ and for some real number p.

This is slightly modified and we can apply it more easily. The results are as follows:

1. if $a \gt b^k$, then $$T(n) = \Theta(n^{log\_ba})$$
2. if $a = b^k$, then

a) if $p \> -1$, $$T(n) = \Theta(n^{log\_ba} log^{p+1}n)$$

b) if $p = -1$, $$T(n) = \Theta(n^{log\_ba} loglogn)$$

c) if $p \< -1$, $$T(n) = \Theta(n^{log\_ba})$$
3. if $a \< b^k$, then

a) if $p \geq 0$, $$T(n) = \Theta(n^klog^pn)$$

b) if $p \< 0$, $$T(n) = O(n^k)$$

---
Tags: recurrence-relation
---


# Question
Title: Using software to calculate the complexity of an algorithm
I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some resources where I can learn to calculate the complexity of an algorithm?

Secondly, is there some software that calculates the space and time complexity for an algorithm? I have seen that cyclomatic complexity can be calculated by software.

# Answer
Depending on your background, the CLRS book is a solid introduction. I think in the very first chapter, they walk you through of how to analyze a simple algorithm in terms of both correctness (showing the algorithm really solves the problem) and complexity (how many steps the algorithm performs). There are lots of other books out there some other people might prefer more.

In general, there is no software that does this for you. Coming up with right invariants etc. is somewhat of an art requiring insight and experience. Read more about complexity theory, and you'll discover some inherit impossibilities and problems related to automating such analysis.
> 7 votes

# Answer
It is entirely possible with simple curve fitting exercises, which could be automated. Bearing in mind Juho's answer, some estimate must be better than no estimate whatsoever. And some estimate is certainly possible for many algorithms, especially those that don't have many major decision branches and always halt such as cryptographic ones, compression, etc.

1. Code your algorithm.
2. Provide a test framework around it that can feed in different values of $n$.
3. Run the algorithm and time it's execution for each $n$.
4. There are only a few generic complexities to choose from if you are not too concerned with a perfect analysis. A good example set is simply listed on the relevant Big $O$ Wikipedia page. And any analysis must be better than none.
5. Iterate through the generic $O$ formulae, curve fitting and choose the best fit using your favourite fitting technique. Some experience and black magic may be useful in pruning the set.

This may not be academic computer science, but that's how the military, economics, engineering and politics works in this world. Monte Carlo simulation is exactly this type of analysis. The following simple example from Wikipedia is another:-

We see that the run time is approximated to $O((log(n)^2)$ which is polylogarithmic time. The specificity of the example is important. It's entirely possible that this approximation would be impossible to compute algebraically due to the overwhelmingly complex architecture of a Pentium 3 processor.

Reiterating, something is better than nothing and this example proves that automated complexity analysis is not only possible, but can be rather simple.
> -1 votes

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


title: What is a hyper property?

text:
# Question
Title: What is a hyper property?
I am reading the paper Foundations and tools for the static analysis of Ethereum contracts, by Grischenko et al. Sometimes the authors speak about hyper properties (e.g. Section 5). What exactly is a hyper property in this context?

# Answer
A trace is a (finite or infinite) sequence of program steps. (Some works only consider finite traces, or only infinite ones.)

A property is a set of traces. E.g. all those traces where variable $x$ is never negative.

A hyperproperty is a set of sets of traces. E.g. the sets of traces $T$ where each trace in $T$ is finite.

Some complex security goals can not be described as a property. Non-interference, for instance, can not be checked on a single trace, but only on the set of all the possible traces a given system can generate during execution.
> 4 votes

---
Tags: static-analysis
---


# Question
Title: What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?
In these notes about quantum computation by Scott Aronson, he explains that the computation classes $\mathsf{BPP}$ is contained in $\mathsf{BQP}$, but that they are not equal, and

> So, the bottom line is that we get a problem -- Simon's problem -- that quantum computers can provably solve exponentially faster than classical computers. Admittedly, this problem is rather contrived, relying as it does on a mythical "black box" for computing a function f with a certain global symmetry. Because of its black-box formulation, Simon's problem certainly doesn't prove that $\mathsf{BPP} \neq \mathsf{BQP}$. What it does prove that there exists an oracle relative to which $\mathsf{BPP} \neq \mathsf{BQP}$. This is what I meant by formal evidence that quantum computers are more powerful than classical ones.

What does he mean by an *oracle* separation?

My understanding of an oracle for a Turing machine is one that solves the halting problem. Surely that can't be the case here?

# Answer
No, an oracle is a black box that solves a problem in a single step. The problem that it solves can be any problem, it doesn't need to be the halting problem.

What Scott is saying is that there is some black box that a BQP machine with it can do more than what a BPP machine can do with it. However, it doesn't mean that without that black box BQP is more powerful than BPP.

A simpler case is P vs. NP. By Baker, Gill, and Solovay's result there is a black box that P with that black box is not equal to NP with that black box. But it doesn't tell us much about what should be the answer to P vs. NP.
> 15 votes

# Answer
An *oracle* is just a theoretical device which will provide the answer to a given class of decision problems in a single step. We say that a decision problem is in $BPP$ *relative to the oracle* if a turing machine (or whatever model of computation you are using) with access to the oracle can answer the decision problem in a polynomial amount of time with bounded probability of error. Similarly, a problem is in $BQP$ relative to the oracle if a quantum turing machine with access to the oracle can answer the decision problem in a polynomial amount of time with bounded probability of error.

This is closely related to the notion of oracle you know. An oracle which can solve the halting problem is a (very powerful) example of an oracle. Usually when one is talking about such an oracle, one wants to know what problems are in $R$ relative to the oracle, i.e. are computable by a turing machine with access to the oracle.
> 6 votes

# Answer
It depends.

If $\mathrm{BPP} = \mathrm{BQP} = \mathrm{EXP} = \mathrm{EXP}^\mathrm{NP}$, then any oracle separation result would necessarily go beyond $\mathrm{ELEMENTARY} = \cup\_{k} k-\mathrm{EXP}$.

Indeed, $\mathrm{BPP}^\mathrm{EXP} = \mathrm{BQP}^\mathrm{EXP} = \mathrm{PP}^\mathrm{EXP} = \mathrm{EXP}$. Going further, we also have $\mathrm{BPP}^\mathrm{EEXP} = \mathrm{BQP}^\mathrm{EEXP} = \mathrm{PP}^\mathrm{EEXP} = \mathrm{EEXP}$. And so on, and on, *ad astra*.

So, with current mathematical arsenal, we can only hope to construct a separating oracle with at least some **non-elementary logic**.

On the other hand, if $\mathrm{BPP} \neq \mathrm{BQP}$ holds, then a trivial separating oracle exists, namely $\emptyset$.
> 3 votes

---
Tags: complexity-theory, quantum-computing, oracle-machines
---


# Question
Title: what’s wrong with this quantum key distribution scheme?
I’m reading about the BB84 quantum key distribution scheme, and I’m surprised that it’s conceptually more complicated than seems necessary to me. What’s wrong with this conceptually simpler scheme?

1. Alice chooses two random strings $x,y \in \\{ 0,1\\}^{2n}$
2. Alice encodes $x$ into qbits, choosing the basis in which to encode the ith qbit according to whether $y\_i$ is 0 or 1.
3. Alice sends the qbits to Bob (Bob himself doesn’t generate any random strings).
4. Once Bob confirms to Alice (on an insecure but authenticated channel) that he’s received the qbits, Alice sends $y$ to Bob (on an insecure but authenticated channel).
5. Bob decodes all the qbits using $y$. He then chooses $n$ bits at random from $x$, and sends these $n$ classical bits to Alice (using the insecure channel), together with an encoding of which bits he picked.
6. Alice confirms whether the first $n$ qbits are indeed the same as the first $n$ bits in $x$. If they are, then they know that Oscar didn’t observe the qbits, and they use the other $n$ bits as the key. If one of them is not the same, they know that Oscar meddled with the process.

Does this work?

# Answer
No, not really. The main problem with this protocol is that it is less practical than BB84.

# Less practical

Bob is a benign party. To measure a q-bit, you need to know what basis to measure it in before you can measure it (e.g., before you can measure a photon, you need to have your measurement apparatus set up in the appropriate basis). Ordinarily, we'd like to measure it as soon as we receive it. Your protocol doesn't allow that.

Your protocol requires Bob to receive the q-bit and then decide later what basis to use to measure it. That means Bob will need some way to store the q-bit for later measurement. There might be a way to do that (e.g., put the photon into a long delay loop), but it will probably increase complexity and expense.

It's not reasonable to expect legitimate parties to have to do that just to communicate. And in any case, BB84 doesn't require parties to jump through those hoops. So your scheme is less practical than BB84.

---

Side note on security:

With your protocol, it is important that step 4 (including Bob's confirmation) be over an authenticated channel. Without that, there is a security problem.

BB84 provides the following security property: if the final reconciliation phase is done over an authenticated channel (not necessarily secret; it can be public communication; but it does need to be authenticated), and if the parties don't abort, then the resulting secret will be known only to Alice and Bob. In particular, no adversary -- not even an active man-in-the-middle attacker -- can arrange to learn the secret.

Your protocol doesn't offer that guarantee, if step 4 happens over an insecure channel. With your protocol, there's a trivial way that a man-in-the-middle can arrange to learn the secret, with zero chance of being detected. When Alice sends the q-bits, the adversary Mallet intercepts and stores them. Mallet then sends a confirmation that the q-bits were received to Alice (pretending that this came from Bob). When Alice sends $y$, Mallet intercepts and learns $y$. Now Mallet decodes all the q-bits using $y$, and learns $x$. In the second phase, Mallet encodes $x$ into new q-bits and sends those q-bits to Bob (pretending they came from Alice). When Bob responds that he has received them, Mallet sends $y$ to Bob (pretending it came from Alice). Now Bob will decode his q-bits, obtain the same value $x$, send back some of the bits of $x$ to Alice, everything will match, and both Alice and Bob will think that they have obtained a secure key -- but Mallet actually knows that secret key, since Mallet has learned $x$. This attack works even if steps 5 and 6 are done over an authenticated channel.

I suspect it suffices to require step 4 to also go over an authenticated channel (I'm not 100% sure; that would require proof; but it looks like it to me).
> 4 votes

---
Tags: quantum-computing
---


# Question
Title: what is actually a circular array and representation
There are two ways to implement a circular array either take a new array of size `2N` where N is the size of the initial array and copy initial array twice into that new array

```
array = [1,2,3,4,5]
new_array = [1,2,3,4,5,1,2,3,4,5]

```

Or we can use (i % N) where N is the size of the array, i is the index of that element

```
for(var i = 0; i < N + i; i++)
{
    console.log(arr[i%N])
}

```

What does exactly circular array mean? Is a normal array while representing?

# Answer
Circular array is just a fixed size array. We call it circular just because we define the operations on the array in such a manner that its limited size can be utilized again and again and it apparently appears that we are traversing the array in clockwise or anti-clockwise way.

The best example for understanding the circular array is a Queue. We can implement Queue with the help of a circular array. In a Queue we insert at the end and delete from the front.

Suppose you have an array of size 5. Let say we implement Queue using this array. We will have two pointers - one for the **front** of Queue and one for the **rear** of Queue. Initially front and rear both will point at index 1. We may do let's say 3 insertions in the beginning. Rear pointer would point at index 3 and front would point index 1 at this moment (consider 1-based indexing).

Now let say we make 2 deletions and now front is 3 and rear is 3. At this moment we have 2 array positions vacant in the front of array. We can use this space again rather than reallocating an array once rear reaches the end of the array. What we can do to utilize these spaces again, is to introduce the **circularity**, which when rear or front reaches the end of the array re-indexes the rear to 1th index. Since we have changed the index from last index to the first index, we say that the array is circular (apparently in a clockwise manner).

The idea to re-allocate an array and copy the original array twice is totally wrong. The % operation lets you re-index the pointer once you have reached the end of array (e.g. 6%5 = 1). The approach with the mod operation is the correct approach to implement a circular array.

**EDIT**

I have added an image which will help you:
> 7 votes

---
Tags: arrays
---


# Question
Title: What would remain of Quantum Computing if quantum states were real numbers?
This question is motivated by my attempt to understand quantum computing and the source of its computational power.

Quantum statest are described by complex numbers. That is, 1 qubit is described by 2 complex numbers, one for each state (actually 1 complex number, due to the constraint and the invariance).

Quantum phenomena are explained by the fact that quantum states consists of probability amplitutes (complex numbers) rather than actual probabilities (real numbers).

My question is, **what if we would consider an alternative "pseudo-quantum" system, the states of which, unlike classical physics, still consist of a distribution over classical states, only it is now real-valued rather than complex-valued.** What would remain of quantum computing (or "pseudo-quantum computing")?

One thing that would remain is that the number of dimensions in the system would still exponentially increase w.r.t. the number of pqubits (pseudo-qbits), which as far as I understand is one source of the power of quantum computing. That is, it would allow correlations/entanglement, contrary to classical computing, but I am not sure if this actually matters for comoutational power.

# Answer
The gate set Hadamard + Toffoli is universal for quantum computation \[1\] and only uses real number coefficients (some negative). So all quantum algorithms can be run without involving imaginary numbers.

That being said, you will pay some representation overhead if you stick with just H+Tof. For example, you need an extra ancilla qubit and essentially every encoded operation will act on this qubit. This creates a false dependency between most operations, preventing parallelism and locality.

\[1\]: https://arxiv.org/abs/quant-ph/0301040
> 4 votes

---
Tags: quantum-computing
---


title: Solving Recurrences Using Master Method

text:
# Question
Title: Solving Recurrences Using Master Method
Using the Master Method, I need to prove (True, or False and why) the following (3) recurrences:

1. $T(n) = 3T(\frac{n}{2}) + n = \Theta(n\ln(n))$
2. $T(n) = T(\sqrt{n}) + 1 = \Theta(n^2)$
3. $T(n) = 2T(\frac{n}{3} + 1) + n = \Theta(n\ln(n))$

I understand the Master Method (I think, largely from: https://stackoverflow.com/questions/13430256/understanding-master-theorem) and from my CLRS Text.

Problem 1: Would be case 1, but I don't understand how to use it in this case? What would my ɛ be in this case to perform the logarithmic function? I know that ultimately, my time complexity will be $\Theta(n^{1.58})$, but I don't know how to prove that without knowing ɛ

Problem 2: I have no idea.

Problem 3: I believe this is false, because this can be rewritten as $T(n) = 2T(\frac{4n}{3}) + n$, which would be Case 2, and therefore give me a time complexity of $\Theta(ln(n))$.

This is my first time taking anything this granular with algorithms, and despite reading CLRS and looking at videos online, I am a bit lost, and would appreciate any help. Thanks in advance.

# Answer
1) $T(n) = 3T(\frac{n}{2}) + n \in \Theta(n\ln(n))$

a = 3, b= 2 and f(n) = $\Theta(n)$

$n^{\log\_b a} = n^{\log\_2 3} \> n^{\log\_2 2} = n = f(n) \therefore f(n) \in \Theta(n^{\log\_2 3})$

(Case 1) Proved False

2) It is not in the Master Theorem format $T(n) = aT(\frac{n}{b}) + f(n) \therefore$

It is not possible to say if the statement is true or false using the Master Theorem

3) $T(n) = 2T(\frac{n}{3}+1) + n = 2T(\frac{n+3}{3}) + n \in \Theta(n\ln(n))$

a = 2, b= 3 and f(n) = $\Theta(n)$

$n^{\log\_b a} = n^{\log\_3 2} \< n^{\log\_3 3} = n = f(n) \therefore$

Case 3.

Now we could check if it is the case that $T(n) \in \Theta(f(n))$, but we don't need to, because the only way it would be $\Theta(n\log n)$ was if it was case 2.
> 1 votes

---
Tags: algorithms, time-complexity, recurrence-relation
---


# Question
Title: Time complexity of function vs return value
I came across following problem:

> Find the time complexity of below recurrence relation:
>
> $T(n)=\begin{cases} & 2T(n/2)+C; & n\>1\\ & C;&n=1 \\ \end{cases}$

The solution was given as follows

> $\begin{align} T(n) & = C+2C+4C+...nC\\ & = C (1+2+4+...+2^k) \\ & = C \left(\frac{1(2^{k+1}-1)}{2-1}\right) \\ & = C (2^{k+1}-1) \\ & = C (2n-1) \\ & = O(n) \\ \end{align}$

I feel above gives order of return value, but not the order of computation involved.

This function makes two recursive calls with argument $n/2$. Each of these two make another two recursive calls, making total 4, with argument $n/2/2=n/4$. Each of these four make another two recursive calls, making total 8, with argument $n/2/2/2=n/8$. And so on. Thus this form complete binary tree. This tree terminates when $n/2^h=1$. That is, when $2^h=n$.
$\therefore $ Height of binary tree $h=\log\_2n$. And the order of computation will be, number of nodes in the complete binary tree for height $h$ which equals $2^{h+1}-1=2^{\log\_2n+1}-1=O(2^{\log\_2n})$.

Am I correct with this final time complexity and the overall interpretation (of first being the time complexity of the return value and the one which I came up with, the time complexity of computation involved)?

# Answer
The question is ill-posed. Recurrence relations don't have time complexities.

* Recurrences have solutions.
* Algorithms have running times.
* Problems have time complexities.
> 1 votes

# Answer
Here is a correct version of your original problem.

> Find the time complexity **of an algorithm which takes $T(n)$ time/operations to finish when the input size is $n$**, where $T(n)$ satisfies the below initial condition,
>
> $$T(1) = C$$ and the below recurrence relation, $$T(n) = 2T(n/2)+C\ \text{ if } n\>1$$ for some constant $C\>0$.

Another correct version would be "Find the asymptotics in term of big $O$ or $\Omega$ notation for the function $T(n)$ that ...".

My answer is based on the above editions of the your original problem.

Your question and much more beyond have been answered in more generality in this reference question and answer and in particular, by the first case of the master theorem.

Assume throughout this answer and the question that $n$ is a positive integer and "/" is the integer division when it is applied to two positive integers as in Python/Java/C/C++/C#. Without these assumptions, $T(1.5)$ and $T(3)$ may not be defined.

Here is a correct computation. Suppose $2^h\le n\lt 2^{h+1}$ for some nonnegative integer $h$. \begin{align} T(n) & = 2T(n/2) + (2^1-1)C\\ & = 2(2T(n/4) +C)+ (2^1-1)C\\ & = 2^2T(n/2^2) + (2^2-1)C\\ & \cdots\\ & = 2^hT(1) + (2^h-1)C\\ & = (2^{h+1}-1)C\\ & = \Omega(n) \end{align} The last equality stands from the fact that $Cn\le (2^{h+1}-1)C\lt 2Cn$.
> 3 votes

# Answer
You could also use the Master Theorem

$T(n) = aT(\frac{n}{b})+f(n)$

In your case, a = 2, b = 2 f(n) = $\Theta(1)\therefore$

$f(n) = n^0, 0 \< \log\_2 2\therefore$ Case 1 and

$T(n) \in \Theta(n^{\log\_2 2})= \Theta(n)$
> 0 votes

---
Tags: time-complexity, recurrence-relation, recursion
---


title: Store - Order Problem

text:
# Question
Title: Store - Order Problem
Lets there are n stores.

A customer order x items. All the stores might not have all the items from the order.

So find the store/combination of stores that can serve the order request such that the combination that contain least number of stores.

Edit:

Example: Lets say there are 4 stores. User is ordering item 1, 3, 6, 7

Store 1 sells item 1, item 6 Store 2 sells item 1, item 2, item 3, item 4, item 5 Store 3 sells item 6, 7, 8, 9, 10 Store 4 sells item 5, item 7

The combinations of stores that can fulfil the orders { 2, 3 } , { 1, 2, 4}

So optimal solution in this case is {2,3}

P.S: I was asked this question in an interview. What would be the algorithm that would fit into the problem?

# Answer
Your problem is essentially the same as *set cover*, a classical NP-complete problem.

In set cover, we are given sets $S\_1,\ldots,S\_n$ together covering a universe $U$, and the problem is to find the smallest subset that still covers $U$. The only difference between this and your problem is that you want to cover some $V \subseteq U$. You can get the classic formulation by intersecting all sets with $V$.
> 2 votes

---
Tags: algorithms
---