# Question
Title: Floating point normalised numbers in binary
Many text books state that for a binary floating point representation in a computer byte, that if the mantissa is normalised, then a positive number must start with 01 from the left or a negative number with 10 from the left.This is nothing to do with IEEE standard but a common statement in English A level computing books. (A levels are the school leaving exams in most of the UK, and some other countries.)

They then ask you to spot normalised representations:

1) 100000000

2) 011111111

3) 110000000

In the rule above 1 and 2 would be normalised but not 3.

Why does it have to be 10 and 01? How is this rule derived?

# Answer
I'm assuming you're talking about IEEE754. Unless I'm missing something, your book is wrong.

Every number in IEEE754 is represented as normalized (starting with a 1), unless your number is subnormal. A number is only subnormal if the mantissa is minimal (all zeroes). Since the first bit is the sign bit, $10$ could be the start of a subnormal number.

For example $10000000000000000000000000000001$ is the subnormal number $-2^{-149}$.
> 3 votes

# Answer
In answer to the OP, and looking around Tony Piper I found this page:

http://www.teach-ict.com/as\_as\_computing/ocr/H447/F453/3\_3\_4/floating\_point/miniweb/pg10.htm

Essentially, a non-normalised 8 bit floating point is represented like:

```
Sign  Integer  Fraction  Exponent
 0     111       .0       010

```

The largest number this can represent is 111.1 with a 111 exponent which is 7.5 x 2^7, but fractionally you can only represent 0.5 any other fraction is not possible because you have only provided 1 bit in this scheme.

A Normalised floating point is represented as:

```
Sign  Integer  Fraction  Exponent
 0      1       .110        010

```

3 fractional bits instead of 1. The integer part can only be a 1 or a zero. The largest number that can be represented is 1.111 x 2^7 which is not that much less than the 7.5 x 2^7 above. And yet we can now represent 0.001 binary which is 1/8.
> 3 votes

# Answer
Historically, floating point binary formats have varied from machine to machine. For example, some put the exponent on the left and the mantissa on the right, and some use sign and magnitude instead of twos complement. It wasn’t until 1985 that the Institute of Electrical and Electronics Engineers agreed on the standard format used in most of today’s computers, the IEEE 754 standard. This website goes into some detail...

http://www.quadibloc.com/comp/cp0201.htm

The format you’re expected to know about if you sit an A level computer science exam in the United Kingdom illustrates the fundamental principles of floating point binary. You will be told how big the register is, how many bits have been allocated to the mantissa, and how many bits have been allocated to the exponent; both are usually in two’s complement. For example, you might be given an 16 bit register, with a 10 bit mantissa and a 6 bit exponent, both in two’s complement. Chances are, there is no such processor, but who’s to say that one day somebody might not design one like that, for a very specific purpose.

The objectives of normalisation are to maximise the precision of floating point numbers, and to achieve an unambiguous representation. This in turn simplifies processing when performing arithmetic with floating point numbers.

To achieve the most accurate representation of a positive number, for a given size mantissa, there should be no leading 0s to the left of the most significant bit.

0.000001001 000000 When normalised becomes 0.100100000 111011

All normalised positive numbers therefore start with 01

To achieve the most accurate representation of a negative number, for a given size mantissa, there should be no leading 1s to the left of the most significant bit.

1111100100 000011 When normalised becomes 1001000000 111111

All normalised negative numbers therefore start with 10

You should try converting both normalised and un-normalised forms of the same number back into base 10. You will get the same result.

Take a look at this

https://www.youtube.com/watch?v=5OuRbAsME1w
> 3 votes

---
Tags: floating-point, number-formats
---


# Question
Title: When using a hash and a collision occurs and linear probing is used how is that item found again
How is the search for the item supposed to find the specific item if the data is all clumped together and all the search is given is the output of the hash function. I don't understand how it knows which of the pieces of data is the one that corresponds to the key if linear probing has been used so it could be any of a number of pieces of data? Thanks for any help

# Answer
> 1 votes
Any given equality function over the objects. You're asking if an *object* is in a hash table, and it is if there is an object that is "equal" to the given object.

And remember that object equality implies hash equality.

# Answer
> 0 votes
In linear probing, The hash function only points to the bucket in the hash table that is the starting index for the search. So say item $x$ after hashing has a hash value of $h(x)$. This is just the starting index of the bucket. If the data at hash bucket $h(x)$ is not equal to the data, we incrementally search $h(x)+1, h(x)+2,....$ till either the data is found or an empty slot if found.

---
Tags: hash-tables
---


title: Time complexity of BFS with min heap

text:
# Question
Title: Time complexity of BFS with min heap
Given a matrix of size m x n, I am trying to traverse it using BFS from top left corner to bottom right corner. Instead of using a normal queue for BFS, I am using a min heap. For each cell, I am inserting the adjacent values (top, left, right, bottom) in a min heap. I am specifically trying to understand how big the heap would grow. I know that BFS traversing would cost me O(mn) and each heap insertion would cost me O(logk) where k is the size of the heap. Here I am trying to figure out how big can be k. e.g

```
[
[1,2,3,4,5],
[2,3,4,1,3],
[4,3,2,1,4]
]

```

My thoughts are that at max there can be m x n elements in the heap. So the overall complexity can be O(mnlogmn). But when I run through some examples, I think not everything will be in the heap all the time. A single cell can at max insert 2 elements (other 2 would have been inserted by some other cell already). So based on the examples I am thinking that it should be O(mnlog(m+n))

# Answer
> 0 votes
Yes. Both bounds are valid. There's not much difference between the two bounds.

There are certainly at most $mn$ items in the queue at any time, as there are only $mn$ possible items. Consequently, the running time is at most $O(mn \log(mn))$.

By analyzing how BFS visits nodes and the size of the "fringe", one can show that the size of the fringe is most $m+n$. In particular, the fringe is a path that goes from somewhere on the top of the matrix to somewhere on the left of the matrix, by going only down, left, or diagonally down-and-left (but never right or up). Thus the fringe can include at most $m+n$ cells. This means that at every stage, the size of the heap is at most $m+n$, so $O(mn\log(m+n))$ is also a valid upper bound on the running time.

These two bounds are pretty close, so either is a reasonable upper bound on the running time.

Caveat: there are multiple heap data structures, with different running times for the heap operations. This answer assumes you are using a heap data structure where inserting into a heap containing $k$ items can be done in $O(\log k)$ time.

---
Tags: graphs, algorithm-analysis, runtime-analysis, graph-traversal, heaps
---


# Question
Title: Amdahl's law of processors (infinite processors to test limits of speedup)
My processor noted that an **infinite number of processors will allow me to test how much speedup I can achieve.**

I am not exactly sure how this applies.

For instance, let's say I have a program that takes $1000$ seconds to execute and is broken into 4 phases(A, B, C, D). If two of the phases are $50%$ parallelizable and the other $2$ are not parallelizable at all, how can I apply the concept that I have infinite available processors to figure out how much maximum speed up I can achieve?

I attached numbers to my example, but a generic one would be just as helpful.

If I am to strictly just apply Amdahl's law, I'd say the answer is just $1/(1-0.5) = 2$ times faster.

# Answer
Don't think of it as "you've been given infinity processors." Think of it as "you can have as many processors as you want, but of course after a certain point more professors won't help, so find out how fast you can make it run with the optimum number of processors."
> 1 votes

---
Tags: parallel-computing
---


# Question
Title: What is `wasted space` parameter and why is it O(n) for a linked list
I'm reading a book on data structures and there is a comparison between linked list, array and dynamic array. The parameter name is *wasted space*. Here are the values:

\begin{array}{cc} \text{Linked list} & O(n)\\ \text{array} & 0 \\ \text{dynamic array}& O(n) \end{array}

What is the wasted space parameter and why is it $O(n)$ for a linked list?

# Answer
> 3 votes
Different people seem to define "wasted space" in different ways. Some authors define it as any space in a data structure that's not used to store actual data; others define it as space that could be used to store data but isn't being so used at the moment.

So, in the first definition, a linked list has $O(n)$ wasted space because every entry of the list contains some piece of data but also a pointer, so a constant fraction of the space taken up by the data structure is "wasted". (I think this is a silly definition of "waste": the space taken up by the pointers isn't wasted; it's an overhead.) In the second definition, a half-full hash-table has 50% wasted space (again, $O(n)$).

---
Tags: data-structures, arrays, linked-lists
---


# Question
Title: How does CFS prevent a long sleeping task from occupying the CPU?
The Completely Fair Scheduler executes the task that has so far received the least share of CPU time and is thus the most 'disadvantaged'. So if a task sleeps for a really long time, say 3hrs, how does CFS prevent this task from being executed for the next like 3hrs (to adapt its CPU share to the much larger values of the other tasks)?

Or does CFS do so at all? Or did I get something wrong?

Thanks in advance :)

# Answer
> 1 votes
Just found it out by myself:

each time CFS places a new/old task into the rbtree it does not reuse its old runtime but rather assigns a new one: `se->vruntime = max(se->vruntime, vruntime)` where `vruntime` is the current minimum virtual runtime.

That is basically what is expressed through "sleeper fairness": each task gets a fair share of CPU time, no matter whether it is running or not.

---
Tags: process-scheduling
---


# Question
Title: Insertion and deletion complexities for a linked list and array
I have the following table that compares different operation complexities for a linked list and array:

```
                        Linked List |   Array   |   Dynamic Array
Deletion at ending      O(n)        |   O(1)    |   O(n)
Insertion in middle     O(n)        |   O(n)    |   O(n)
Deletion in middle      O(n)        |   O(n)    |   O(n)

```

Can anyone please explain why:

1. Deletion for Dynamic Array is `O(n)`?
2. Insertion and deletion in middle for all data structures is `O(n)`?

Thanks

# Answer
1. The array may need to be reallocated if there are too many free cells, and this costs $O(n)$ (non-amortized)
2. For arrays, the array portion which comes after the affected element must be moved one position left or right, so that's $O(n)$. For lists, it depends. If you have the pointer to the previous cell w.r.t. the inserted/deleted one, this can be done in $O(1)$. If you don't, and you only have the pointer to the list head, then you have to scan the list -- half the list, on average, will be scanned, costing $O(n)$.
> 1 votes

---
Tags: data-structures, arrays, linked-lists
---


title: Optimal insertion of edges for a graph

text:
# Question
Title: Optimal insertion of edges for a graph
I am working on a problem which could be reduced to a graph optimization problem as below.

* A set of colored nodes is given.
* The edges are to be inserted between the nodes.
* A node can have only 4 edges at max.
* A table provides rules for profit contribution from the edges.

Eg.,

+ An edge connecting red to red: profit is 10
    + An edge connecting red to blue: profit is 20
* The total number of colors is typically around 20 to 30, but it can go as high as 50. Correspondingly the table for profit(edge) would be a long list but it won't list all possible combinations. The profit for edges not specified in the table is assumed zero.

The problem is to optimize the connections (edges) such that the total profit is **maximized**.

I am wondering if this problem, maybe in some other way, is known. If so, please provide any pointers that might be of help. Thanks.

# Answer
> 1 votes
Let your vertex set be $\\{v\_1, \dots, v\_n\\}$. If $n\leq5$, just add all possible edges. Otherwise, create a new graph with vertices $\big\\{v\_{i,j}\mid i\in\\{1, \dots, n\\},\ j\in\\{1, 2, 3, 4\\}\big\\}$, and edge set $\\{v\_{i,j}v\_{k,\ell}\mid i\neq k\\}$. You're looking for a minimum-weight perfect matching in that graph. (Which is the same thing as a maximum-weight matching in the graph where you multiply all the costs by $-1$). This can be done in polynomial time, even though the graph isn't bipartite.

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Insertion of n consecutive keys in an initially empty B-Tree
Consider this question ( 18.2-4 of CLRS) which states that:

Suppose that we insert the keys ${1,2,...,n}$ into an empty B-Tree with minimum degree 2. How many nodes does the final B-tree have?

My approach:
We add each element one by one. We'll need 3 elements at first (namely *1,2 and 3*), after which the $4th$ element will cause a split. This split is a root node split.
A normal node split results in one extra node.
A root node split results in 2 extra nodes.
Thus after the 4th element we have 3 nodes in total. Now, as we keep on adding more elements to the B-tree, we can see a pattern in splitting. 3 lower level splits initially produce a higher level split, and then each higher level split will require 2 splits only. Since we've to approximate only, we can disregard the initial 3 split condition and go on with the 2 lower level splits to produce an upper level split.
Notice that there is atleast a split at the insertion of these elements: $4,6,8,10,12...... $
That are all even numbers leaving 2.
Thus total such splits are $n/2$
Total higher level splits are thus:$n/4$
Total splits for the higher level than the previous one: $n/8$
Thus the total splits until the $nth$ element is inserted in the B-Tree is:
$n/2+n/4+n/8+......$
Which results in $n$. This is more than expected. I've made two approximations here:
1) Number of higher level splits is equal to half of the immediate lower level splits.*This increases our answer.*
2) Some starting elements don't contribute to the splits.
Maybe these are the reasons why the answer is coming more. I can't enumerate these values exactly. Finding these values exactly would help me very much. Any help appreciated.
Moon

# Answer
We know that every node except the root must have at least t−1=1 keys, and at most 2t−1=3 keys. The final tree can have at most n−1 nodes when n≥2. Unless n=1 there cannot ever be n nodes since we only ever insert a key into a non-empty node, so there will always be at least one node with 2 keys. Next observe that we will never have more than one key in a node which is not a right spine of our B-tree. This is because every key we insert is larger than all keys stored in the tree, so it will be inserted into the right spine of the tree. The fewest possible number of nodes occurs when every node except the deepest node in the right spine has 2 keys and the deepest node in the right spline has 3 keys. So at height 1, 1 nodes, at height 2, 3 nodes, …, at level h, 2h−1 nodes. In this case, n =2^(h+1)−1 where h is the height of the B-tree, and the number of nodes in B-Tree is #nodes = 2^(h+1)−2−h = n−lg(n+1). So for any n, the final B-Tree must have n−⌊lg(n+1)⌋≤#nodes≤n−1 (if n≥2).
> 1 votes

---
Tags: trees
---


title: Shortest path with positive edge cycle

text:
# Question
Title: Shortest path with positive edge cycle
When reading about shortest paths in Cormen . I came across this paragraph which says that 'shortest path cannot contain' positive edge path even. But I don't understand the logic behind their explanation

> Can a shortest path contain a cycle? As we have just seen, it cannot contain a negative-weight cycle. Nor can it contain a positive-weight cycle, since removing the cycle from the path produces a path with the same source and destination vertices and a lower path weight. That is, if p {vo,v1,v2,.... vk} is a path and c = {vi; v(i+1)....vj) is a positive-weight cycle on this path (so that vi = vj and w(c) \> 0), then the path pnew = {v0,v1,.... vi, v(j+1) , ... vk} has weight w(pnew) = w(p)-w(c) \< w(p), and so p cannot be a shortest path from v0 to vk.

The original snip from the book is here.

Could someone explain why it is so ? I don't understand because any way removing an edge will cause the path length to decrease right ? why are they seeing removing positive edge cycle as different ?

For eg in the following diagram

How are they removing cycle and connecting vi and v(j+1) ?

# Answer
> 2 votes
They are just saying that if $P$ is a shortest path, in $P$ there are not **positive** cost cycles, since removing the cycle would led to a smaller cost (and so to a better path).

Consider your example and suppose we want the shortest path beween $s$ and $v\_k$, let $P=(s,v\_1,\color{red}{v\_i},\color{red}{v\_{i+1}},\color{red}{v\_{j-1}},\color{red}{v\_i},v\_{i+1},v\_{j-1},v\_{j+1},v\_k)$.

Removing the cycle from $P$ we obtain $P'=(s,v\_1,v\_i,v\_{i+1},v\_{j-1},v\_{j+1},v\_k)$ where $cost(P')=cost(P)-6$, so to a better path in terms of cost.

---
Tags: graphs, algorithm-analysis, shortest-path
---


# Question
Title: adder in logisim using only 2-input-NAND gates
I want to build an adder in logisim only with 2-input-NAND gates. The adder consists of 2 inputs (1 x constant 1 and 1 x arbitrary number) and an output.

The first thing which came into my mind is a 8-bit full adder but maybe there is an easier solution for this (because of the constant 1). Has anyone an idea? THX

# Answer
If I understand your question right, you want to build an incrementor.

First you need to build a halfadder. If you do not can or want to design it, you can ask logisim to do it.

choose project/analyse circuit. add two inputs (a,b) and two outputs (o,c).

then fill in the logic table for the half adder.

a b | o c
...............
0 0 | 0 0
0 1 | 1 0
1 0 | 1 0
1 1 | 0 1

then push build circuit and check both options (2 input gates only and nand only)

logisim wil build the circuit:

then you can connect 8 halfadders to build a 8 bits incrementor.
> 2 votes

# Answer
Here is a half-adder using NAND gates:

The way it works is by imitating an `and` gate on the bottom and an `xor` gate on the top. The trickiest part of understanding the diagram, I think, is the idea of putting the same input twice into a `nand` (such as just before the `Sum` output). When you stick two of the same input into a `nand` gate, you reduce yourself to two input possibilities: `1, 1`, and `0, 0`. This causes NAND to behave as a `not` gate.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Verification condition in case of array theory
As far as i can understand the problem of checking safety property, can be reduce to solving for inductive invariants in VC's and there is following parts to it:

1. Generate VC's from the program.
2. Solve it: If user provide inductive invariants just check the Validity of the whole VC formula.
3. Inferring problem : simultaneously solve the VC's taking these predicates as uninterpreted function that make all the VC's valid.

How hard the problem of checking 2. (User provide the inductive invariant) in the case of array theory? For example: Array sorting.

# Answer
Sure, if the user provides inductive invariants, you can try to check the validity of the verification conditions. However, this remains undecidable, as it requires checking the validity of a formula in first-order logic (with quantifiers and array expressions), and that's undecidable.

It might be feasible often enough in practice to be useful, especially since we might hope that programmers have a reason why their code is correct and won't write code that requires overly complex reasoning to prove correct. But in general, it is undecidable.
> 2 votes

---
Tags: arrays, automated-theorem-proving, loop-invariants, smt-solvers
---


# Question
Title: Is this grammar really LL(1) while not being LR(1)?
$S \rightarrow S$, $L(G) = \\{\\}$

**LL(1) analysis:**

We estabilish $FIRST(S)$ to be empty and $FOLLOW(S)$ to be $\\{\\$\\}$. $FIRST(S)$ doesn't contain ε, so the parse table looks like this:

```
+---+---+
|   | $ |
+---+---+
| S |   |
+---+---+

```

and correctly rejects any input including ε.

**LR(1) analysis:**

We start with the initial state 0:

$S' \rightarrow \bullet S \[\\$\]$

calculate its closure:

$S' \rightarrow \bullet S \[\\$\]$

$S \rightarrow \bullet S \[\\$\]$

and the only transition, which leads to state 1 on S:

$S' \rightarrow S \bullet \[\\$\]$

$S \rightarrow S \bullet \[\\$\]$

State 1 has a reduce/reduce conflict.

Now, obviously there must be something I'm missing, since LL(k) grammars are a proper subset of LR(k) grammars. Would anyone care to point out the error?

# Answer
I've just consulted a parsing book, and it indeed requires that $S \Rightarrow^+ S$ be impossible, if $S$ is the starting symbol, before a grammar is considered $LR(k)$. As you said yourself, this is not required for a grammar to be $LL(k)$.

Usually, it is implicitly assumed grammars 'behave' when we make statements about them, such as $LL(k) \subset LR(k)$. For instance, $S \Rightarrow^+ S$, absence of symbols not derivable from $S$, and absence of symbols not deriving terminal strings are all properties of 'well behaved' context free grammars.

If we assume these things, we are spared some weird oddities of context-free grammars: for example, if we have some grammar with starting symbol $S$, by adding a nonterminal $T$ and productions $T \to \epsilon$, $S \to T S$, we can force the grammar to have infinitely many parse trees for every string in the language it represents. In contrast, if we do assume 'well behaved' grammars, we are guaranteed only finitely many parse trees exist for any input.
> 6 votes

# Answer
The book I have been consulting starts with the assumption: "let $G$ be a grammar without useless symbols". I could not immediately see where that is necessary in the analysis, but obviously your variables are useless, they do not generate terminal strings.

You are right, I could find no explicit note of that fact in the Rosenkrantz and Stearns paper you cite. Only in one of the constructions they note (page 229 top) "Remove all the symbols \[..\] and all productions \[..\] which cannot be used in deriving a terminal string \[..\]". But that is in the LL(1) analysis.

(originally posted as comment, as it is low on technical detail; moved following the suggestion by Yuval)
> 5 votes

# Answer
I did not see why we should consider a useless grammar such as

S ::= S

Are there meaningful implications? The easy thing we can do is to require that we should "remove all useless symbols and production rules before generating LL and LR parsers."
> -1 votes

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


# Question
Title: Finding the maximum bandwidth along a single path in a network
I am trying to search for an algorithm that can tell me which node has the highest download (or upload) capacity given a weighted directed graph, where weights correspond to individual link bandwidths. I have looked at the maximal flow problem and at the Edmond-Karp algorithm. My questions are the following:

1. Edmond-Karp just tells us how much throughput we can get (at the sink) from source to sink if any of the paths were used. Correct?
2. Edmond-Karp does not tell us which path can give us the maximum flow. Correct?

# Answer
> 5 votes
A very simple approach for question 2 is the following. Sort the edges by capacity. Remove the edge with lowest capacity, and check if there is still a path from $s$ to $t$. If there is, move on the edge with the second lowest capacity, and so on.

At some point, we will disconnect $s$ from $t$ by removing an edge of capacity $c$. Now, we know that $c$ is the maximum capacity of a single path from $s$ to $t$.

This algorithm takes time $O(m^2)$, since the connectivity check can be made in time $O(m)$, and we can remove each edge at most once.

Now you can find the actual path (there might be many) of maximum capacity, by finding any $s$-$t$ path in this reduced graph.

When considering node-capacity, remember to change your graph to support that.

# Answer
> 2 votes
Given a path, just iterate along it and find the node with highest capacity.

Distilled from the comments, let us consider this more interesting question:

> Given a network of nodes $N$ connected by links $E$ with limited bandwidths $b : E \to \mathbb{N}$, find a path from $s$ to $t$ with maximum bandwith.

In other words, you are looking for an $s$-$t$-path $p = (s, v\_1, \dots, v\_k, t)$ that maximises

$\qquad \displaystyle B(p) := \min\ \\{ b(s,v\_1), b(v\_k, t) \\} \cup \\{b(v\_i,v\_{i+1} \mid i = 1, \dots, k-1\\} $

among all $s$-$t$-paths.

It is noteworthy that cycles do not change path bandwith $B$, so we can restrict ourselves to minimal paths in this respect, that is look at $B$-optimal spanning trees.

Note furthermore that among all $B$-optimal paths, there is (at least) one that has the subpath-optimality property we know from the shortest path problem, that is that all partial paths of an optimal paths are optimal (for the nodes they connect). It does not hold for all $B$-optimal paths¹, but that is not a problem: what we need to know is that there *is* a $B$-optimal path that can be constructed from a concatenation of $B$-optimal paths. Therefore, we can restrict ourselves to considering only such (partial) paths.

With this we have collected enough justification for a greedy strategy similar to Prim's algorithm: starting in $s$, successively choose edges with maximum bandwith among those edges incident to already visited nodes (that do not connect two already visited nodes). This will discover only $B$-optimal paths and therewith a $B$-optimal $s$-$t$-path (if $t$ is reachable from $s$).

This runs in time $O(|N|^2)$.

---

1. Consider this graph:

<sup>\[source\]</sup>

All $s$-$t$-paths are optimal, but those that go via the lower node have non-optimal subpaths.

# Answer
> 0 votes
This can be done in O(VlogV + E) time by doing a simple modification to Dijkstra

key(Node n) = single path max flow from s to n

Update Key: if p is the predecessor of n Key(n) = min(Key(p), edge(p, n))

This is because for all paths P=(s, a\_2, ... a\_m-1, a\_m)

Max flow in path P= min( capacity(a\_m-1, a\_m), Max flow in P-{a\_m} )

This works because single path max flow to x = max( Max flow in path all paths P from s to x )

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: String distance metric for possibly truncated words
I am looking for the optimal string distance metric to indicate similarity/difference between possibly truncated words. For example, I would like to find the distance metric between the name "Richard" and possible variations of it (and other names as well)

Variations: Richard | Rihcard | Richard Smith | Rich? | R?ard | ?rd | Joe

, where "?" stands for truncation. For example, the metric should indicate smaller distance between "Richard" and "?rd" or "Richard Smith" than "Richard" and "Joe".

I would really appreciate any help.

# Answer
> 3 votes
It is quite hard to propose an *"optimal"* string distance metric, especially when the specification is only specified by an example.

There are many possibilities for you to try:

1. Levenshtein or Edit distance (wiki): allows insertions, deletions and replacements.
2. Hamming distance (wiki): allows only replacements.
3. Episode distance: allows only insertions.
4. Longest Common Subsequence (LCS) distance (wiki): allows only insertions and deletions.
5. Damerau–Levenshtein distance (wiki): allows insertion, deletion, or substitution of a single character, or a transposition of two adjacent characters.
6. Smith Waterman similarity (wiki), Needleman–Wunsch similarity: determining similar regions between two strings.

The paper "A Guided Tour to Approximate String Matching" is also informative.

---

By the way, *Mathematica* contains most of the distance metrics listed above as built-in functions. For example, to calculate the edit distances:

```
Map[EditDistance["Richard", #] &, {"Richard", "Rihcard", "Richard Smith", "Rich", "Rard", "rd", "Joe"}]

```

You get:

```
{0, 2, 6, 3, 3, 5, 7}

```

This result meets your requirement of `the metric should indicate smaller distance between "Richard" and "?rd" or "Richard Smith" than "Richard" and "Joe".` Be prudent, however.

# Answer
> 2 votes
I know this is an old question, but since Google brought me here, maybe it will bring some future beings here as well...

I would recommend using the Jaro-Winkler Distance which is defined in terms of the Jaro Distance $d\_j$, the common prefix length of the two strings $l$ (bounded by some maximum value, let's say $b$), and a prefix scaling factor $p$. It is important that you select the parameters $b$ and $p$ such that their product does not exceed one.

$d\_{jw} = d\_j + lp(1-d\_j) = lp + d\_j(1-lp)$

Conceptually, it's probably easiest to think of it as a convex combination (weighted average where the weights sum to one) of the Jaro distance and one with weights $1-lp$ and $lp$, respectively. Thus we see that it is important to bound $lp$ to the range $\[0, 1\]$, otherwise this expression is no longer a convex combination, so we may obtain values outside the range of the Jaro distance: $\[0, 1\]$.

Obligatory note about the word **metric**: when we speak of string distance metrics in general, the word "metric" doesn't carry its formal mathematical definition, but rather its basic English definition: "a means by which to measure something."

---
Tags: strings, string-metrics
---


# Question
Title: Using amplification lemma to decrease error probability gives 0 as divisor
I am attempting to work through an example of how to select an error bound, and then determine the number of simulations necessary by the amplification lemma to obtain the desired error bound. I have probabilistic Turing machine $M$ with an error probability of $.5$. I'd like an error bound of $.25$, so I will bound the error probability by $2^{-t}$, where $t=2$. According to my textbook, I need to choose a $k$ such that $k \ge t/f$, where $f=-log\_2(4e(1-e))$, where $e$ is the error probability. As $M$ has an error probability of $.5$, $e=.5$. Substituting into the equation gives: $-log\_2 (2(.5))=-log\_2(1)=0$. The problem is when I go to select a $k$ such that $k \ge t/f$, I get $0$ as a divisor. Are there other restrictions on the calculation? Or, am I just doing something wrong?

# Answer
> 2 votes
If the Turing machine has an error probability of $1/2$, the Turing machine is useless and you cannot amplify to reduce the error bound.

Consider: if you just ignore the input and flip a coin and use that to decide whether to accept or reject, you get an error probability of $1/2$ -- yet that is an obviously useless procedure. A Turing machine with an error probability of $1/2$ is no better than that.

Here's another way to see why it's hopeless. One standard method of amplification is to run the Turing machine multiple times and take a majority vote. Suppose we run the Turing machine 3 times, and take a majority vote. What is the probability that the outcome of the majority vote is correct? It's not hard to see that this probability is $1/2$ -- no better than running the machine once. (Why? Each time you run the Turing machine, it is either correct or incorrect. Since you run it 8 times, there are 8 cases: CCC, CCI, CIC, CII, ICC, ICI, IIC, III, where C = correct and I = incorrect. If the Turing machine's error probability is $1/2$, all 8 of those cases are equally likely. The majority vote after 3 runs will be correct in the cases CCC, CCI, CIC, and ICC; thus, the majority vote is correct with probability $4/8 = 1/2$.) The same thing happens no matter how many times you run the Turing machine.

To get amplification, you need the error probability to be strictly less than $1/2$.

---
Tags: turing-machines, probability-theory, probabilistic-algorithms
---


title: Finding a unambiguous grammar

text:
# Question
Title: Finding a unambiguous grammar
As an exercise we were supposed to find a grammar $G$ that generates language $L(G) = \\{w \in \\{a,b\\}^\* \mid |w|\_a = |w|\_b\\}$. That was not so hard, I found a grammar which I think is correct:

$S \longrightarrow bA \mid aB$

$A \longrightarrow a \mid aS \mid bAA$

$B \longrightarrow b \mid bS \mid aBB$

Though then I found out that this grammar is ambiguous.

So the question is, is there any context free grammar generating language $L$ that is not ambiguous? I've read that there is no algorithm to determine whether a grammar is ambiguous. So if there is such grammar, how can we prove it is? Or is there any way to transform my grammar $G$ to become unambiguous?

# Answer
You can get an unambiguous grammar by thinking of words in $L$ as walks that start and end on the Y axis; each $a$ corresponds to a move $\nearrow$, and each $b$ corresponds to a move $\searrow$. Each such walk can be decomposed into segments of the form $\nearrow \cdots \searrow$ and $\searrow \cdots \nearrow$ which only touch the Y axis at the endpoints. Moreover, this decomposition is unique.

In turn, in a walk of the form $\nearrow \cdots \searrow$, the $\cdots$ part is itself a concatenation of walks of the same form, and this decomposition is unique. Alternatively, if you convert $\nearrow \mapsto ($ and $\searrow \mapsto )$, then walks of the form $\nearrow \cdots \searrow$ become valid strings of balanced parenthesis, surrounded by a pair $()$.

Putting everything together, we get the following unambiguous grammar: $$ \begin{align\*} &S \to AS \mid BS \mid \epsilon \\ &A \to a X b \\ &X \to AX \mid \epsilon \\ &B \to b Y a \\ &Y \to BY \mid \epsilon \end{align\*} $$ Actually proving that this grammar generates $L$ and that it is unambiguous is tedious, and left to you.
> 3 votes

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


title: Is $K(b|a) \geq 1$ if $a\neq b$?

text:
# Question
Title: Is $K(b|a) \geq 1$ if $a\neq b$?
Since $K(a|a) = 0$, is $K(b|a) \geq 1$ when $a\neq b$, as we need at least one bit to distinguish between $K(a|a)$ and $K(b|a)$? If not true in general, is it true if $a$ and $b$ are elegant programs?

# Answer
> 2 votes
Whether $K(a|a) = 0$ could depend on your universal computer. The only thing you can say in general is that $K(a|a) \leq C$ for some constant $C$ independent of $a$.

You can arrange for a universal computer for which $K(a|a) = 0$ for all $a$, and then indeed $K(b|a) \> 0$ for all $b \neq a$, since there is only one program whose length is zero, and given $a$ it generates $a$.

---
Tags: kolmogorov-complexity
---


# Question
Title: Correct name for a recursive descent parser that uses loops to handle left recursion?
This grammar is left recursive:

```
Expression  ::= AdditionExpression

AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

MultiplicationExpression    ::=
    Term
        | MultiplicationExpression '*' Term
        | MultiplicationExpression '/' Term

Term    ::=
    Number
        | '(' AdditionExpression ')'

Number  ::=
    [+-]?[0-9]+(\.[0-9]+)?

```

So in theory, recursive descent won't work. But by exploiting the properties of the grammar that each left-recursive rule corresponds to a specific precedence level, and that lookahead of a single token is enough to choose the correct production, the left-recursive rules can be individually parsed with while loops.

For example, to parse the AdditionExpression non-terminal, this pseudocode suffices:

```
function parse_addition_expression() {
    num = parse_multiplication_expression()
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            num += parse_multiplication_expression()
        else if (current_token == MINUS)
            num -= parse_multiplication_expression()
        else {
            unget_token()
            return num
        }
    }
    return num
}

```

What is the correct name for this type of parser? This informative article only refers to it as the "Classic Solution": https://www.engr.mun.ca/~theo/Misc/exp\_parsing.htm

There must be a proper name for this type of parser.

# Answer
It is just an LL(1) parser implemented with recursive descent.

Starts with:

```
AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

```

apply left-recursion removal to get an LL(1) grammar:

```
AdditionExpression  ::=
    MultiplicationExpression AdditionExpressionTail

AdditionExpressionTail ::=
        | '+' MultiplicationExpression AdditionExpressionTail
        | '-' MultiplicationExpression AdditionExpressionTail

```

write the corresponding functions:

```
function parse_AdditionExpression() {
    parse_MultiplicationExpression()
    parse_AdditionExpressionTail()
}

function parse_AdditionExpressionTail() {
    if (has_token()) {
        get_token()
        if (current_token == PLUS) {
            parse_MultiplicationExpression()
            parse_AdditionExpressionTail()
        } else if (current_token == MINUS) {
            parse_MultiplicationExpression()
            parse_AdditionExpressionTail()
        } else {
            unget_token()
        }
    }
}

```

remove tail recursion:

```
function parse_AdditionExpressionTail() {
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            parse_MultiplicationExpression()
        else if (current_token == MINUS)
            parse_MultiplicationExpression()
        else {
            unget_token()
            return
        }
    }
}

```

inline:

```
function parse_AdditionExpression() {
    parse_MultiplicationExpression()
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            parse_MultiplicationExpression()
        else if (current_token == MINUS)
            parse_MultiplicationExpression()
        else {
            unget_token()
            return
        }
    }
}

```

and you have just to add the semantic processing to get your function.
> 11 votes

# Answer
You want to look into LL($k$) parsing. The Wikipedia article is mostly useless, but it's basically recursive descent with $k$ symbols lookahead.

There is also LL($\*$) which permits unbounded lookahead.

See here for a comprehensive overview on how powerful this class of parsers is.
> 5 votes

---
Tags: reference-request, formal-grammars, recursion, parsers, left-recursion
---


title: Time required for mod operation

text:
# Question
Title: Time required for mod operation
> Let $x,y,n$ be $1234567809, 12345, 9087654321$. My laptop can perform 1 64-bit mod operation in 1 microsecond. Estimate the number of seconds needed for each of the following:
>
> 1. Find $x^y \pmod{n}$
> 2. Find $t$ such that $x^t \equiv 2672633475 \pmod{n}$.

I guess around 10^45 digits, am I right and how do I calculate time from here?

# Answer
Hint: If you want to calculate $1234567809^{12345}$ modulo 9087654321, you do *not* start by calculating $1234567809^{12345}$. After every operation, you reduce the result modulo 9087654321.

Hint 2: You can calculate $x^{12345}$ with about 25 multiplications, not 12345.

Hint 3: Probably less than 10 seconds for the last question if you find factors of n first, and use brute force and a tiny bit of maths (but that answer won't do you any good if you can't find that tiny bit of maths).
> 2 votes

---
Tags: modular-arithmetic
---


# Question
Title: Sorting in sub-quadratic time and logspace simultaneously
On a standard computing model that reflects reality for *sequential* processing, such as a RAM machine with penalized access time for growing memory, can a comparison sort algorithm work in both logspace yet sub-quadratic time?

Standard algorithms for sorting are O(n\*log(n)) time yet I've found that once these programs are restricted to only read-only input, write-only output, and pointers for indexing into the I/O, they seem to suddenly require quadratic time.

Another question on cstheory prompted answers giving model-independent lower bounds for famous complexity classes such as NP requiring a product of time and space resources to be nearly quadratic. Does that same argument apply here to non-trivial problems in L?

# Answer
The following paper proves that any comparison-based sorting algorithm must satisfy $TS = \Omega(n^2)$, where $T$ is the running time and $S$ is the amount of read-write space used.

Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa. A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. Journal of Computer and System Sciences, vol 22 pp.351--364, 1981.

In particular, if $S = O(\log n)$, then $T = \Omega(n^2/\log n)$, i.e., if you have only logarithmic space, then the running time has to be nearly quadratic.
> 0 votes

---
Tags: complexity-theory, sorting
---


# Question
Title: Finding lowest "pass" between two points on a map?
(I expect that the hard part of this question is getting the right language for the problem. My attempts at searching for an answer didn't get anything useful, which suggests to me that whatever they are, I'm not using them!)

Consider a map where each x,y coordinate has an associated "height" value. If we have two points (each of which is at a local minimum height) on this map, we can consider the set of all possible paths between those two points. Each path has a maximum height along the path; call this the "pass height" of the path. I'm interested in the minimum value of the pass height over the set of possible paths.

I'm calling this a "lowest pass", because in real maps, these paths with minimum height are the passes through the mountains.

What is an algorithm that will allow me to determine this minimum pass height? I'd be happy either with an algorithm that assumes a discrete grid of finitely-spaced points, or an algorithm that approximates the solution on a continuous surface with numerical iteration of some sort.

I'd also particularly like a solution that will work in a high-dimensional space, but one in 2-space would be a good start.

# Answer
> 3 votes
A simple solution to this would be to implement it as any normal pathfinding algorithm (say, A\*), but then render in your map any height over a threshold as impassable, and any height under the threshold as passable, and then continuously run the pathfinding algorithm for threshold heights between the minimum cell height and the maximum cell height. The first time you can path from start to end is the lowest possible height.

This has some performance implications for maps with a large difference between highest and lowest points, but you use a search algorithm other than a linear search to find the upper and lower bounds and close in on the boundary.

Many pathfinding algorithms are already generalised to n-dimensions, so to generalise this is simply the case of picking the correct dimension to use as the varying threshold. Essentially, for a map of n dimensions (say, a 2D map + height), you path find in that many dimensions with the height being made into a passable/impassable cost.

---
Tags: algorithms
---


# Question
Title: Can a turing machine calculate word's length?
I want to understand how a turing machine that will accept only words of length bigger than 100 will look like. My idea: it will copy a word and move to the right 100 times. If non of the cells was empty it will accept. Furthermore if it is true I can also conclude that it is decidable .

If there is no problem with my assertions so far, how will a turing machine that prints the number of letters in a word will look like? is it possible as well?

# Answer
Replace every character in the input string with a $1$; you then have the length of the string in unary notation. Then convert the unary representation to your favorite base $b$ by successive division by $b$.
> 1 votes

# Answer
If the target length 100 is fixed, and not an input of the TM, you can simply create a TM with 100 states (beyond the starting and final states), and use those states to effectively "count" up to 100.

Hence, you can just scan the tape once, moving right. If within 100 steps, you find the end of the input, you reject. If after 100 steps the end of the input was not met, you can accept.
> 1 votes

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


# Question
Title: Dijkstra’s in a graph with negation of edges
Let say I have a directed graph G with positive edges and I create a new graph, G', by replacing the weight of each edge by the negation of its weight in G. If for a given source vertex *s*, I compute all shortest path from *s* in G' using Dijkstra’s algorithm. Will the resulting paths in G’ be the longest (i.e., highest cost) simple paths from *s* in G. True or false? And please, justify.

# Answer
The answer is FALSE.

Contradicting example: (starting from S)

Running Dijkstra on the following graph will not find the longest path from S to D (S-\>A-\>B-\>C-\>D). Due to removing node C from the queue too soon (before the relaxation of node B), hence prev(D) = E.

Please follow the correctness argument of Dijkstra's algorithm, which relies heavily on the edge weights being positive.

In addition, longest path problem is computationally hard. (NP-Hard).
> 3 votes

---
Tags: algorithms, graphs
---


title: Huffman Coding vs LZW Algorithm

text:
# Question
Title: Huffman Coding vs LZW Algorithm
I'm trying to understand comparisons between the two. Is there ever a case where is it better to use Huffman Coding over LZW? Could the compression ratio for Huffman ever surpass that of LZW?

Thanks!

# Answer
In a gist LZW is about frequency of repetitions and Huffman is about frequency of single byte occurrence.

Take the string 123123123.

(The following is an oversimplification but will make the point) LZW will identify that 123 is repeated three times and essentially create a dictionary of codes for sequences. It will esentially say when I say A I mean 123 here is AAA (or three bytes).

Huffman will detect the frequency of bytes (let's assume the text above is ASCII or UTF-8 (which will make ABC all single byte code points), so A=3, B=3, C=3 and there are no other items, so I can use 1.5 bits (well a 1 and 2 bit combo) to represent all characters. So let's say A=0, B=10, C=11. Huffman will encode the text ABCABCABC as (in bits) 010110101101011 (or 15 bits) or since we are usually limited to bytes 2 bytes.

What if we used Huffman on the LZW result?

Well AAA can be represented with a single bit (Let's choose 0) so 000 (3 bits or 1 byte rounding up).

The unfortunate part here is that Huffman and LZW require some info to decode so it won't quite be as awesome as sending a 0 and saying go decode with Huffman, then LZW, but in essence this combination results in very good compression results with real-world payloads that aren't already compressed (A JPG or ZIP file is unlikely to be compressible with this, but a .docx, xml doc, txt file, etc (the longer and more verbose and repetitive the better) will do. awesome!

If you look at the characteristics of the algorithms and have awareness of the data you will see that order of algorithms and repetition may well make a difference. Think of a doc 1TB in size of all "A"s and apply the above and think what would do better. Frankly a naive SingleByteUsageEncoder would do best as the minimal info here is what char how many times. Huffman would max out at approximately 1/8 (1 byte to one bit) LZW would do muuuuuuuch better. However if you had a doc with ever possible permutation of a sequence of letters then generally Huffman would do better. I think if you think carefully about this you will recognize that LZW is generally more helpful, but combos often achieve best results (assuming your goal is smallest size, not best performance).
> 9 votes

# Answer
LZW is dictionary-based - as it encodes the input data, it achieves compression by replacing sub-strings that have occurred previously with references into the dictionary.

If phrases do not repeat (the data is a stream of symbols in more or less random order), LZW isn't going to be able to compress the data very well.

By contrast, Huffman Coding could still compress the data significantly if certain symbols (characters or bytes) occur more frequently than others.
> 6 votes

---
Tags: algorithm-analysis, lempel-ziv, huffman-coding
---


# Question
Title: Induction rules for reflexive, transitive closure
I'm trying to solve an exercise on inductive definitions, the premiss is:

---

Let $\to$ be a relation on $A$ and $\to^\*$ its reflexive, transitive closure, which is defined by following two rules:

1. $a \to^\*a$ (reflexive)
2. ${a \to^\*b \quad b \to c \over a \to^\*c }$ (step)

---

The questions are:

1. What are the induction rules for $\to^\*$?
2. Show that $\to^\*$ is reflexive.
3. Show that $\to^\*$ is transitive.

The first question startles me, I view ${a \to^\*b \quad b \to c \over a \to^\*c }$ as the induction rule. Is this the complete answer?

And can I show the reflexivity with ${a \to^\*b \quad b \to a \over a \to^\*a }$?

# Answer
> 4 votes
Here's a fully formal articulation in the language of Agda. First, inductive rules correspond to indexed families.

```
data Star {A : Set}(R : A → A → Set) : A → A → Set where
    Refl : {a : A} → Star R a a
    Trans : {a b c : A} → Star R a b → R b c → Star R a c

```

Here the `Refl` data constructor corresponds to your first rule, and the `Trans` data constructor corresponds to your second rule. `R` represents $\to$, so `Star R` corresponds to $\to^\*$. The induction rule corresponds to the eliminator for the data type, i.e. roughly the fold on that type (though things are a bit more complicated in a dependently typed language).

```
ind : {A : Set}{R : A → A → Set}{P : A → A → Set}
    → ({a : A} → P a a) → ({a b c : A} → P a b → R b c → P a c)
    → {a b : A} → Star R a b → P a b
ind r t Refl = r
ind r t (Trans s x) = t (ind r t s) x

```

This says that if you give me some binary relation $P$ and you show that $\forall a \in A. P(a,a)$ holds and $\forall a,b,c\in A. P(a,b)\land R(b,c) \Rightarrow P(a,c)$ (i.e. when $P(a,b)$ and $R(b,c)$ hold, then $P(a,c)$ holds) then I can provide you a proof of $P(a,c)$ whenever $R^\*(a,c)$ holds, where $R^\*$ is the reflexive, transitive closure of $R$.

Question 2 is completely trivial. The formal proof of the statement is `Refl`. Question 3 is not much harder. It's asking to show that if $a \to^\* b$ and $b \to^\* c$ then $a \to^\* c$, while the inductive rule only gives the case when $b \to c$ in a single step. Obviously, we just need to recursively apply the single-step rule. This leads to the following code:

```
trans : {A : Set}{R : A → A → Set}{a b c : A} → Star R a b → Star R b c → Star R a c
trans r Refl = r
trans r (Trans s x) = Trans (trans r s) x

```

For your purposes, you should probably define the equivalent of `trans` in terms of the induction rule, i.e. in terms of `ind`. I'll leave that as a very simple exercise.

# Answer
> 3 votes
1. No. Induction rules for this case look like this:

~~Let $P$ be some property of relations on $A$ (you already know some examples of such properties: symmetry, transitivity, etc.). To show that $P(\rightarrow^\*)$ holds~~ Let $P$ be some binary relation on $A$. To show that $P(a, b)$ holds whenever $a \rightarrow^\* b$, it should be enough to prove something that only mentions $\rightarrow$ and $P$, but not $\rightarrow^\*$. What? Namely, there will be 2 premisses, one corresponding to "reflective" and another to "step".
2. Well, first you'd need to prove that $a \rightarrow^\* b$ and $b \rightarrow a$ hold for any $a$ and $b$, and of course you can't. The puzzling thing is that the proof is utterly trivial. Does it maybe say "transitive" instead?

---
Tags: logic, proof-techniques, first-order-logic, induction
---


# Question
Title: Lower bound on worst case pancake number?
Given n pancakes, for each permutation we can compute the minimum number of pancake flips. If we take the maximum over all possible permutations, we get the worst case pancake number $P\_n$.

I think I can prove that $P\_n \geq n$. My argument is that I can start from the sorted pancake, and do a "anti-sorting" of the pancake by first flipping at position n, then position at n-1, n-2, etc.

For example, the case of n=5 would yield 34251.

Sorting such a pancake would take at best n steps.

Am I doing something wrong?

# Answer
I assume that you are talking about the Pancake sorting (wiki) problem. Your argument for $P\_n \ge n$ is rather informal.

The paper "Bounds for Sorting by Prefix Reversal (1979)" gives the lower bound $P\_n \ge n$ in the Introduction section. Better lower bounds are also mentioned in this paper.

This paper "Pancake Flipping Is Hard" (2011) proves that determining the minimal number of moves for a given stack is NP-hard.
> 3 votes

---
Tags: sorting, lower-bounds
---


# Question
Title: Dijikstra implementation in books subtly different
I was reading about Dijkstra algorithm and was referring two books 1) Introduction to Algorithms by Cormen Section 24.3 2) Algorithm design by Kleignberg Section 4.4

And found a subtle difference in their way of show Dijkstra algorithm

book 1:

```
Dijkstra(G, w, s)
Initialize(G,s) d(s) = 0 initialize others to inf
S = {}
Q = G.V
while Q not equal to {}:
    u = Extract-Min(Q)
    S = S U {u}
    for each vertect v belonging to G.Adj[u] // all edges emanating from u
        Relax(u,v,w)

```

Note : the word in for each loop : **G.Adj\[u\]**

original snip from book

book 2:

```
Dijkstra(G, w, s)
Initialize(G,s) d(s) = 0 initialize others to inf
S = {}
Q = G.V
while S not equal to V:
    Select node v that is not yet added to S with at least one edge ***from S*** for which
         d'(v) = min of (d(u) + le)  // computed over all edges that
                                     // emanate from all possible
                                     // nodes in S
    Add v to S and make d(v) = d'(v)

```

Note : the word in for each loop : **from S**

original snip from book

Only I find one difference.

in book1 they are computing the neighbors of only the recently added node u. and in book2 they are computing neighbors of entire set S (see the highlighted portion "from S") (and that is not in S).

Yes, both works.

But why is there two implementations of Dijstra algorithm. Any reason why each book has adopted a different way ? Why should we do from entire S when we can easily do from last computed node as that is the one with the last node in the longest of the shortest path and that will decide everything ? Am I missing something ?

# Answer
> 1 votes
Usually algorithms are specified in a somewhat high level format. Later one might fine tune some of the implementation details to get the complexity right. Usually we call the various implementations all Dijkstra's algorithm. (And yes, I consider those implementation details, even though we are not coding in a specific language.)

* How do we store the distances so that we easily find the one with shortest distance from the start node?
* How do we store the graph: adjacency lists or adjacency matrix?
* It might be a good idea to compute 'temporary' distances for nodes not yet completed, so that we do not have to look at *all* edges between nodes that are completed and those that are not yet completed.

In the special case of Dijkstra's algorithm the type of graphs we consider might influence the implementation details. We might choose a certain type of priority queue when the graphs are sparse or not.

---
Tags: algorithms, graphs, algorithm-analysis, shortest-path
---


# Question
Title: Regular Languages in $ \mathsf{\text{}NC^1}$
**Theorem** : To prove $ \mathsf{\text{} Regular} \subseteq \mathsf{\text{}NC^1}$.

To prove the theorem stated above we need some theorems and definitions given below :

**Barrington Theorem** : A branching program of constant width and polynomial size can be easily converted (via divide-and-conquer) to a circuit in $\mathsf{\text{}NC^1}$.

Proof Idea of Barrington Theorem is like small depth boolean circuit implies small group program and small group program implies small branching program.

**Monoid** : In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

I google and find out a research paper but not able to understand much (some of the things that I have understood I have written above). A high level proof idea or an resource to prove the theorem stated above will be helpful.

# Answer
> 4 votes
Let $L$ be a regular language. Take some DFA $\langle q\_0, Q, \delta, F \rangle$ that accepts $L$. There is a constant size circuit whose input is a symbol $\sigma$, and whose output is the function $q \mapsto \delta(q,\sigma)$. In other words, if $Q = \\{q\_1,\ldots,q\_m\\}$, then in input $\sigma$, the circuit computes the sequence $\delta(q\_1,\sigma), \ldots, \delta(q\_m,\sigma)$.

There is another constant size circuit whose inputs are two functions $f,g\colon Q \to Q$ (such as the outputs of the circuit above), and whose output is their composition $q \mapsto f(g(q))$. As before, we encode the inputs and outputs as sequences of $m$ states.

Given $n$, construct a circuit that computes whether a given input word $\sigma\_1 \ldots \sigma\_n$ belongs to $L$ as follows. Assume by simplicity that $n = 2^t$.

* Compute the functions $q \mapsto \delta(q,\sigma\_1), \ldots, q \mapsto \delta(q,\sigma\_n)$ using the constant size circuit from the first paragraph.
* Compute the functions $q \mapsto \delta(q,\sigma\_1\sigma\_2), \ldots, q \mapsto \delta(q,\sigma\_{n-1}\sigma\_n)$ using the constant size composition circuit from the second paragraph.
* Compute the functions $q \mapsto \delta(q,\sigma\_1\sigma\_2\sigma\_3\sigma\_4), \ldots, q \mapsto \delta(q,\sigma\_{n-3} \sigma\_{n-2} \sigma\_{n-1} \sigma\_n)$ using the constant size composition circuit.
* Continue in the same way for $t-2$ more levels, until you compute the function $\varphi$ given by $q \mapsto \delta(q, \sigma\_1\ldots\sigma\_n)$.
* Using a constant size circuit, determine whether $\varphi(q\_0) \in F$.

This circuit has depth $O(\log n)$ and size $O(n)$, and moreover it is uniform in $n$. This shows that $L \in \mathsf{NC^1}$.

---
Tags: complexity-theory, regular-languages, reference-request, circuits
---


# Question
Title: A question about an input in a Halting Problem proof
Here is my Halting Problem proof, that largely mirrors other (non-diagonalizing) proofs that I've seen.

1. $H(p,i)$ returns $1$ if program $p$ halts on input $i$.
2. $H(p,i)$ returns $0$ if program $p$ does not halt on input $i$.
3. Let $f(t,t)$ be an interface for any program that returns a $0$ or a $1$.
4. $g(x)$ is $0$ if $f(x,x)$ is $0$, infinite loop if $f(x,x)$ is $1$
5. Now use $H$ in place of $f$:

***4b.*** *(modified)* $g(x)$ is $0$ if $H(x,x)$ is $0$, infinite loop if $H(x,x)$ is $1$

6. Run $g(g(i))$ which runs $H(g(i),g(i))$ If $H(i,i)=0$, then $g(i) = 0$ If $H(i,i)=1$, then $g(i)$ is undefined
7. If $g$ halts, then $H(g(i),g(i))$ must return $1$ (line 1).

*But then $g$ won't halt. (line 4b)*
8. If $g$ doesn’t halt, then $H(g,g)$ must return $0$ (line 2).

*But if $H(g(i),g(i))$ is $0$, then $g$ halts. (line 4b)*

My issue is with $g(g(i))$. I understand that the idea of the proof is to feed the machine into itself, but what, exactly, is the contents of the $i$?

# Answer
It is an unspecified input. Halting program proofs show that, for any given program that one claims can solve the halting problem, there exists an input for which it does not. The proofs typically do not try to find what that input actually is, merely to prove that one must exist.
> 1 votes

# Answer
In $g(\mathtt{g})$, $\mathtt{g}$ is an encoding of $g$ as a program. As such, it needs no concrete arguments.

As it happens, the proof shows that not all functions that can be defined can be encoded as programs. In this particular case, while $g$ exists, $\mathtt{g}$ does not.
> 1 votes

---
Tags: computability, undecidability, proof-techniques, halting-problem
---


# Question
Title: Can we count the number of inversions in time $\mathcal{O}(n)$?
It is possible to find the total number of inversions by $\mathcal{O}(n\log{}n)$ running time (extension of merge-sort algorithm for example).

Is there more asymptotically efficient way to do it? $\mathcal{O}(n)$? Or is there any proof that’s not possible?

# Answer
There are $o(n\log n)$ algorithms in the RAM model. Dietz gave an $O(n\log n/\log\log n)$ algorithm in his 1989 paper *Optimal algorithms for list indexing and subset rank*, and Chan and Pătraşcu gave an $O(n\sqrt{\log n})$ algorithm in their 2010 paper *Counting inversions, offline orthogonal range counting, and related problems*. Chan and Pătraşcu also gave an $O(n)$ algorithm for finding a $1+\epsilon$ approximation, for any $\epsilon\>0$.

If you only allow comparisons, then there is an $\Omega(n\log n)$ lower bound, see this question on cstheory.
> 3 votes

---
Tags: complexity-theory, asymptotics, lower-bounds, permutations
---


# Question
Title: Can a 1-tape turing machine simulate a stack?
Is it possible to simulate a stack-based machine using a 1-tape turing machine? I cannot wrap my head around it as turing machines do not provide mechanisms such as pointers.

I failed to find any examples or explanations. If it is possible, how?

# Answer
Machines that have *only* a stack are called *pushdown automata*. They are less powerful than Turing machine, so yes: TMs can simulate stacks.

Turing machines are a fairly simplistic model of computation, which can make programming in them hard. Try to start with simple things; for instance, implement a counter. If you feel ambitious, try implementing the basic building blocks of (Turing-complete) imperative programming as Turing machines. This should convince you, then, that TMs *are* as powerful as any other¹ model.

As for your question, you don't need pointers for a stack. TM tapes have a *direction*, and you can easily label cells by introducing special alphabet symbols; the TM can then move over the tape and look for these labels. It's all a matter of encoding.

---

1. Ignoring hyper-computation.
> 3 votes

# Answer
In addition to what @Raphael said, it's very easy to actually do it. Just make a rule for your Turing Machine that every time it moves left, it will also write null. *Voilà!* You have made a Pushdown Automata.
> 3 votes

---
Tags: turing-machines, computation-models, stacks
---


# Question
Title: Why each function may be computed with circuit with 2^n gates?
> Why each function may be computed with circuit with 2^n gates ?

I am trying to understand this thing, but I can't. In particular why function constant $1$ requires $2^n$ gates. For me, it should be simple to return $1$ regardless of input.

# Answer
> 2 votes
The meaning of the statement is that each function can be computed with *at most* $2^n$ gates; it doesn't anything about the *minimal* number of gates needed to compute any function.

That said, you can always add dummy gates to increase the number of gates in your circuit without changing the function it computes. For example, you can replace one of the inputs $x\_i$ to $x\_i \lor x\_i$ to increase the number of gates by 1.

---
Tags: complexity-theory, computability, circuits
---


# Question
Title: How to construct a sequence of polynomial-time Turing machines
I know that similar questions have been asked before but I still wasn't able to find answers to all my questions.

In many proofs in complexity theory we use an enumeration of some $T(n)$-time Turing machines. For simplicity, let's consider polynomial-time TM's. I want to know exactly how we construct such an enumeration.

I know that the following observations are important:

* TM's correspond to the natural numbers: each binary sequence (natural number) encodes some Turing machine (if we have a sequence that does not encode a valid TM, we say that it is a trivial machine that halts and rejects on all inputs immediately)
* Every TM's is represented by infinitely many strings/natural numbers, because we allow the encoding to end with any number of 0's (that do not matter for the encoding).

So if we want to obtain an enumeration of TM's that halt in polynomial time for some input $x \in \\{0,1\\}^n$, we can let each TM of our enumeration of all TM's (the natural numbers) run on input $x$, but then with a counter and an extra tape. If the TM hasn't halted in $n^i + i$ steps, with $i$ the length of the sequence that encodes the TM, we remove it from our enumeration. Because every TM is represented by an infinite number of strings, we now have any TM that runs in time $O(n^c)$ for some $c$.

Please tell me if this is not correct.

My confusion lies here: we need TM's that run in polynomial time for all inputs. Do we need to go over all possible inputs? There are only finitely many inputs of length $n$, but how are we sure that some TM does not use more than polynomial time for a larger input? Or is this some trivial consequece from the deterministic nature of Turing machines?

# Answer
> 3 votes
The simplest way is to use *timed Turing machines*. We enumerate pairs $\langle T\_i, P\_j \rangle$, where $T\_i$ goes over all Turing machines, and $P\_j$ goes over all polynomials. The machine corresponding to $\langle T\_i, P\_j \rangle$ simulates $T\_i$ for $P\_j(n)$ time steps, and then stops it (unless it already halted).

This is better than your solution, since you have to verify that the given Turing machine runs in time $P(n)$ for some given polynomial, a task which is uncomputable.

---
Tags: complexity-theory, turing-machines, time-complexity
---


# Question
Title: How can languages that are E-complete have sub-exponential size circuits?
The question whether there exist languages in $\mathsf{E}$ that require circuits of size $\Omega(2^{\delta n})$ for some $\delta \> 0$ is open, and this would imply some derandomization results.

Suppose we have a language $L$ which is complete for $\mathsf{E}$. Then, how can $L$ have sub-exponential size circuits? If $L$ has a circuit of size $s(n)$ where $s(n) = o(2^n)$, then we can construct a machine $M$ which evaluates the circuit in time polynomial in $s(n)$ on any input $x$, which implies that $L \in DTIME(poly(s(n))$, which we know cannot happen because of the time hierarchy theorem.

Obviously, I must be missing something here, otherwise why is this such an important and open question?

# Answer
What you're missing is that it might be hard to construct the circuits. In order for your algorithm to simulate the circuit, it needs to know the circuit, but since the circuit depends on $n$, you can't hard-code it — you'll need to hardcode an infinite number of circuits.

To give a simpler example, consider the following language: $$ \\{ x : \text{The $|x|$th Turing machine halts on the empty input} \\}. $$ This is an uncomputable language which has constant size circuits.

What could *not* be the case is that some language in $\mathsf{E}$ has *uniform* subexponential circuits, for a suitable notion of uniformity (given $n$, you need to be able to construct the circuit in time subexponential in $2^n$). Your argument would work then, since the algorithm would be able to construct the circuit in subexponential time.
> 2 votes

---
Tags: complexity-theory, circuits
---


title: Isolation lemma

text:
# Question
Title: Isolation lemma
Here is a link to the isolation lemma. Please refer to the statement and Spencer's proof at the given link.

https://en.wikipedia.org/wiki/Isolation\_lemma

In its statement, shouldn't there be a condition $N\>=n$ since the probability is defined as $1-n/N$? Also, is it not required that the intersection of all sets in a given family of subsets is null? Otherwise, for $x$ that lies in every set of a given family, how can the threshold for $x$ be calculated as described in Spencer's proof?

# Answer
> 1 votes
You are asking two questions. To answer your first question, if $N \leq n$ then $1-n/N \leq 0$, so the statement is vacuous (every probability is always non-negative). The isolation lemma is only interesting when $N \> n$. Note that the claim isn't that the probability of isolation is *exactly* $1-n/N$, but rather that it is *at least* $1-n/N$.

Regarding your second question, if some $x$ is common to all sets, then you can just ignore it (the condition holds iff it holds for the system with $x$ removed from all sets). This means that the statement should actually hold with the larger probability $1-(n-1)/N$.

---
Tags: complexity-theory
---


title: Broadcasting on a dynamic grid

text:
# Question
Title: Broadcasting on a dynamic grid
We are given a $n \times n$ grid, where each node can maintain a single "active" edge with one of its 4 neighbors at each time step. The active edge of each node changes periodically clockwise or anticlockwise, in the sense that if, for example, at time $t$ node $v$ has an active edge with its upper neighbor, and it rotates clockwise, at times $t+1$, $t+2$ and $t+3$ it will maintain an active edge with its right, lower and left neighbors, respectively.

at time $t=0$ node $(i,j)$ holds a message, and at each time step a node that has already received the message can transfer it through an active edge to one of its neighbors, **if that neighbor also maintains this edge as active at this time step**.

I am looking for sufficient conditions (initial active edges configurations and rotation direction of all the nodes) such that the message can be transmitted to all nodes in the grid. It's clear this is predetermined by the initial conditions, and depends upon the connectivity of a graph G' that represents them (where neighboring nodes that both maintain an edge as active at some time step are connected in G'). Given that G' it's possible to find total broadcasting time by graph traversal (BFS). The main question is how to know if two edges share an active edge at some time step (given that their behavior is cyclic).

Thanks!

# Answer
> 2 votes
Here is how to analyze a starting configuration to determine whether the message will be able to eventually reach all nodes in the grid.

Consider two adjacent nodes $u,v$. We'll say that these two nodes are *connected* if at some point during the first four time steps, node $u$'s active edge points to $v$ and node $v$'s active edge points to $u$. In other words, nodes $u,v$ are connected if one (or both) of the following two conditions holds:

1. In the initial configuration, $u$'s active edge points to $v$ and $v$'s active edge points to $u$.
2. $u$ rotates in the opposite direction as $v$.

Construct an undirected graph $G$ with one vertex per node in the cell, and an edge $(u,v)$ between two vertices iff they are *connected* (per the above definition). Then a necessary and sufficient condition for the message to be able to reach all nodes in the grid is that the graph $G$ must be connected.

---

It's also possible to use this kind of analysis to determine the shortest time necessary before the message reaches all nodes, with running time linear in the size of the graph.

In particular, we can build a directed graph $G'$ with one vertex $(i,j,k)$ per cell $(i,j)$ and value $k \in \\{0,1,2,3\\}$. (We will interpret $k$ as the time, modulo 4.) This graph has a directed edge $(i,j,k) \to (i',j',k+1 \bmod 4)$ if $(i,j)$ is adjacent to $(i',j')$ and $(i,j)$'s active edge points to $(i',j')$ at time $k$ and $(i',j')$'s active edge points to $(i,j)$ at time $k$.

Now we use breadth-first search to find the shortest path from $(i\_0,j\_0,0)$ to every other vertex, where $(i\_0,j\_0)$ is the cell where the message starts. We define

$$f(i,j) = \min\\{d((i\_0,j\_0,0),(i,j,k)) : k=0,1,2,3\\}$$

where $d(u,v)$ is the length of the shortest path from vertex $u$ to vertex $v$ in $G'$. Finally, $\max\_{i,j} f(i,j)$ is the shortest time necessary for the message to reach all nodes. The running time of this algorithm is $O(mn)$, i.e., it runs in linear time (linear in the size of the input).

---
Tags: graphs, discrete-mathematics, agent-based-computing
---


# Question
Title: How is algorithm complexity modeled for functional languages?
Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case in pure functional languages. The Haskell list takes linear time for access. Modifying a node in a tree involves making a new copy of the tree.

Should then there be an alternate modeling of algorithm complexity for functional languages?

# Answer
> 34 votes
If you assume that the $\lambda$-calculus is a good model of functional programming languages, then one may think: the $\lambda$-calculus has a seemingly simple notion of time-complexity: just count the number of $\beta$-reduction steps $(\lambda x.M)N \rightarrow M\[N/x\]$.

But is this a good complexity measure?

To answer this question, we should clarify what we mean by complexity measure in the first place. One good answer is given by the *Slot and van Emde Boas thesis*: any good complexity measure should have a polynomial relationship to the canonical notion of time-complexity defined using Turing machines. In other words, there should be a 'reasonable' encoding $tr(.)$ from $\lambda$-calculus terms to Turing machines, such for some polynomial $p$, it is the case that for each term $M$ of size $|M|$: $M$ reduces to a value in $p(|M|)$ $\beta$-reduction steps exactly when $tr(M)$ reduces to a value in $p(|tr(M)|)$ steps of a Turing machine.

For a long time, it was unclear if this can be achieved in the λ-calculus. The main problems are the following.

* There are terms that produce normal forms (in a polynomial number of steps) that are of exponential size. Even writing down the normal forms takes exponential time.
* The chosen reduction strategy plays an important role. For example there exists a family of terms which reduces in a polynomial number of parallel β-steps (in the sense of optimal λ-reduction), but whose complexity is non-elementary (meaning worse then exponential).

The paper "Beta Reduction is Invariant, Indeed" by B. Accattoli and U. Dal Lago clarifies the issue by showing a 'reasonable' encoding that preserves the complexity class  of polynomial time functions, assuming leftmost-outermost call-by-name reductions. The key insight is the exponential blow-up can only happen for 'uninteresting' reasons which can be defeated by proper sharing. In other words, the class **P** is the same whether you define it counting Turing machine steps or (leftmost-outermost) $\beta$-reductions.

I'm not sure what the situation is for other evaluation strategies. I'm not aware that a similar programme has been carried out for space complexity.

# Answer
> 23 votes
> Algorithm complexity is designed to be independent of lower level details.

No, not really. We always count elementary operations in some machine model:

* Steps for Turing machines.
* Basic operations on RAMs.

You were probably thinking of the whole $\Omega$/$\Theta$/$O$-business. While it's true that you can abstract away some implementation details with Landau asymptotics, you do *not* get rid of the impact of the machine model. Algorithms have very different running times on, say TMs and RAMs -- even if you consider only $\Theta$-classes!

Therefore, your question has a simple answer: fix a machine model and which "operations" to count. This will give you *a* measure. If you want results to be comparable to non-functional algorithms, you'd be best served to compile your programs to RAM (for algorithm analysis) or TM (for complexity theory), and analyze the result. Transfer theorems may exist to ease this process.

# Answer
> 1 votes
Instead of formulating your complexity measure in terms of some underlying abstract machine, you can bake cost into the language definitions itself - this is called a *Cost Dynamics*. One attaches a cost to every evaluation rule in the language, in a compositional manner - that is, the cost of an operation is a function of the cost of its sub-expressions. This approach is most natural for functional languages, but it may be used for any well-defined programming language (of course, most programming languages are unfortunately not well-defined).

---
Tags: algorithm-analysis, runtime-analysis, computation-models, functional-programming
---


# Question
Title: Does a computation tree for a probabilistic Turing machine have to be a binary tree?
Ever example of computation on a probabilistic Turing machine that I have read uses only a binary tree to show the computational branches of a probabilistic Turing machine. I know that an NTM may use as many branches as needed during a computation, so is this also the case for a PTM? Or is a PTM limited to only binary branching?

# Answer
There are many ways to think of how a probabilistic Turing machine works. One way is to imagine that it has the ability to flip a fair coin (sample a random bit) at any point. In that case, it's reasonable to imagine a binary tree, where each branch corresponds to a coin flip -- the fact that we are choosing a random bit / flipping a 2-sided coin is why it is a *binary* tree. Another way to think of a probabilistic Turing machine is that it has an additional input tape that is full of random bits. There you could imagine a binary tree, which each branch corresponds to another bit on that additional input tape.

Typically probabilistic Turing machines can sample a random bit, i.e., a random number from the set {0,1}. If you want a random number from a different range, you must emulate that by repeatedly sampling random bits and doing something with them.
> 1 votes

---
Tags: turing-machines, probabilistic-algorithms
---


# Question
Title: Faster algorithm to search in a set of strings
Suppose that we are given a pattern $p$, which is a set of characters (order doesn't matter). We are also given a set of strings $A$. I want to find all of the strings in $A$ whose characters are all contained in $p$ (without taking the order of these characters into consideration), i.e., to find all $s \in A$ such that every character in $s$ is also in $p$.

The algorithm that I use is to loop every string in $A$ first, and, then, loop every character in each string, so the time complexity is $O(nm)$. My question is: is there any faster algorithm? Bit operation or matrix is ok.

Here is an example:

```
Pattern "abcdef"

Set A  {a, b, ac, ag, bde, cbd, daf, cg, abzdef, d}

Desired results : a, b, ac, bde, cbd, daf, d

Filtered: ag, cg, abzdef (as g,z don't belong to the original string "abcdef")

```

# Answer
> 4 votes
You only need to read the strings in set $A$ and the characters in pattern $p$ once. You can store each character of $p$ in a hash table* for (expected) constant time lookup, and, then, perform a linear scan in $A$ to obtain the desired result. The running time of this solution is $O(n+m)$, where $n$ is the length (i.e., the total number of characters) of $A$ and $m$ is the length of $p$.

* A solution that is more space-efficient than the hash table (and guarantees constant time lookup) is to use a bit array $P$ to store pattern $p$. This array will be indexed by the *ASCII* values of all possible characters that you want to consider in your application; for instance, $P$ will have 26 index positions in the case of the English alphabet: one per distinct character. The $i$-th bit of $P$ will be set to $1$ if the $i$-th character appears in $p$, and to $0$ otherwise. Thus, you can scan $A$ in linear time and discard every string that contains at least one character $c$ such that $P\[v\_c\]=0$, where $v\_c$ is the *ASCII* value of $c$.

# Answer
> 0 votes
Mario Cervera's proposed structure is asymptotically the best you can do( O(n) ).
However there is a faster data structure for practical sets of Strings(such as the English words).
It is called a **binary decision diagram**.
Basically you create a binary tree 26 (size of alphabet) nodes deep. At the first level you have a node with value = 'a' and pointer to left and right subtree. In the left tree you store words containing 'a', in the right those that do not. next level is 'b' and so on... Then you traverse the tree in a special way to get all words that match the query. I have implemented this in Java, PM me if you want to see the source.

---
Tags: algorithms, search-algorithms, strings
---


# Question
Title: Isomorphism of finite dimensional polynomial algebras over finite fields
For a prime power $q$, consider polynomials $f\_1,f\_2 \in \mathbb{F}\_q\[x\]$. Then, do we have an efficient way of checking whether there exists an algebra isomorphism between:

$$\frac{\mathbb{F}\_q\[x\]}{\langle f\_1 \rangle} \text{and} \frac{\mathbb{F}\_q\[x\]}{\langle f\_2 \rangle},$$

and computing one such isomorphism if it exists?

I think an intermediate step will be to factorise $f\_1$ and $f\_2$ into products of irreducible polynomials over $\mathbb{F}\_q$, which can be done efficiently using Cantor-Zassenhaus algorithm. Any hints on how to proceed?

# Answer
As you mentioned, you can factor $f\_1$ and $f\_2$ in polynomial time. Consider the multiset $D\_1$ of degrees of the factors of $f\_1$, and the multiset $D\_2$ of degrees of the factors of $f\_2$. If $D\_1 \ne D\_2$, they are not isomorphic. If $D\_1 = D\_2$, they are isomorphic. That takes care of determining whether they are isomorphic.

Computing an isomorphism explicitly is harder. Let me focus first on the case where $f\_1,f\_2$ are squarefree, for ease of exposition. Note that if $f = g\_1 \times \cdots \times g\_m$, then we have a sort of Chinese remainder theorem:

$$\mathbb{F}\_q\[x\]/\langle f\rangle \cong \mathbb{F}\_q\[x\]/\langle g\_1 \rangle \times \dots \times \mathbb{F}\_q\[x\]/\langle g\_m \rangle.$$

Consequently, by matching factors of same degree, you can reduce the problem to the case where $f\_1,f\_2$ are irreducible and $\deg f\_1 = \deg f\_2$ (in the squarefree case). Then both fields are isomorphic to $\mathbb{F}\_{q^n}$, where $n= \deg f\_1$.

Finding an isomorphism explicitly (if $f\_1 \ne f\_2$ and $\deg f\_1 = \deg f\_2$) looks related to the discrete log problem over $\mathbb{F}\_{q^n}$. The discrete log problem is believed to be hard in general: the fastest algorithms currently known have a subexponential running time, and it is conjectured that there is no polynomial-time algorithm. In particular, it looks related to the Diffie-Hellman problem, and in most fields the Diffie-Hellman problem is probably as hard as the discrete log problem. I don't know of a reduction from discrete log or Diffie-Hellman to prove that finding an isomorphism is as hard as those problems, but I suspect there might be some relationship.

I do know that if you can compute the discrete log efficiently in $\mathbb{F}\_{q^n}$, then you can exhibit an explicit isomorphism: pick a generator $g$ for the first field, and a generator $h$ for the second field; the isomorphism sends $g \mapsto g'$, and sends $g^k \mapsto h^k$, so given $x$, we compute the discrete log $k$ of $x$ to base $g$, then $x$ maps to $h^k$.

There's lots written about the discrete log problem in such finite fields. For the case where $q$ is small and $n$ is large, see for example https://crypto.stackexchange.com/q/228/351 and https://crypto.stackexchange.com/q/22332/351.

What about when $f\_1,f\_2$ are not squarefree? Then I think the problem is at least as hard. We can reduce to the case where $f\_1 = p\_1^e$ and $f\_2 = p\_2^e$, where $p\_1,p\_2$ are irreducible and $\deg p\_1 = \deg p\_2$. Then I think it might be possible to use Hensel lifting, though I haven't thought through the details. In particular, here is what happens with the discrete log. Consider the case where $e=2$. Let $g=a\_1 p\_1 + b\_1$ be a generator of $\mathbb{F}\_q\[x\]/\langle p\_1^2 \rangle$. Note that

$$g^k = (a\_1 p\_1 + b\_1)^k = k a\_1 p\_1 + b\_1^k.$$

Therefore, to compute the discrete log of $x = a\_2 p\_1 + b\_2$, it suffices to first find $k\_0$ such that $b\_1^{k\_0} = b\_2 \pmod{p\_1}$ (which is the squarefree case of the discrete log considered above), then find $k$ such that $k \equiv k\_0 \pmod{q^n-1}$ and $k \equiv a\_2/a\_1 \pmod{q^n}$, where $n = \deg p\_1$. Such a $k$ can be found through the Chinese remainder theorem; you end up with $k = k\_0 q^n - (a\_2/a\_1) (q^n-1)$. This shows how to compute the discrete log in $\mathbb{F}\_q\[x\]/\langle p\_1^2 \rangle$ if you know how to compute the discrete log in $\mathbb{F}\_q\[x\]/\langle p\_1 \rangle$. I think the same will apply to any $e\>1$, not just $e=2$.
> 1 votes

---
Tags: algorithms, factoring, polynomials, algebra
---


# Question
Title: What is the whole picture of the NP-hardness proof of Super Mario Bros?
I am reading the NP-hardness proof of Super Mario Bros. in the paper "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta.

I can get the basic idea of the proof framework presented in Section 2.1. I think I also understand the Start gadget, Finish gadget, Variable gadget, Clause gadget, and Crossover gadget individually used in this proof. See the figure below.

However, I failed to **plug these gadgets into the proof framework to construct a complete instance/scenario of Super Mario Bros**. Specifically,

1. In the Variable gadget, Mario chooses the path to *fall down*. Then Mario goes to some Clause gadget where it hits the item block *from below* to release a Star. I don't understand how the Variable gadgets are connected to the Clause gadgets so that the orientations (*fall down* vs. "from below") fit together?
2. In the Clause gadget, the Firebar is on the right side. However, in the proof framework, the Check path goes from right to left. How can Mario pick the Star as desired in this case?
3. Where should the Crossover gadgets be plugged in the proof framework? Are the circles between the paths from the Variables to Clauses crossover?

# Answer
### Graph Connection and Gadget Orientation

Short answer to your first question is to use graph algorithms to compute gadget assembly. Erik mentions this briefly. Keep in mind the gadgets don't necessarily have to be oriented as shown above. You could rearrange the gadgets however you wish as long as you retain the edge connections and entrance/exits of the graph.

The idea of "falling down" from a variable is so that there is no way to get back up to it. After you fall down there could be a tunneling system or corridor that allows Mario to get to the bottom side of a clause and hit the question box from below.

### Right-to-Left Check Path

You could use the mirror (about the y-axis) of the clause gadget to achieve the capability of going right to left. This would be true for any of these gadgets as long as you kept the entrances and exits hooked up properly using tunnels. You do not gain or lose anything from going right to left versus left to right in SMB. They would be equal movements and since the whole level is on the screen at one time, we are not restricted from going right to left.

### The Crossover Gadget

The crossover gadget is placed where edges intersect (edges between literal and clause). This is because SMB is a 2-dimensional game and thus the graph using all these gadgets must be planar. The crossover gadget will then act as a vertex where the two intersecting edges can safely connect and not interfere with each other. They will not interfere because if you enter top left, you can only leave top right and if you enter bottom left you can only leave top center. More on the planarity and edge interference here.

Importantly, the crossover gadget is directional. You can only go left to right through the gadget once. This means the edges must also be directional. Whenever you see an edge from literal to clause there are really two directional edges; (literal -\> clause) and (clause -\> literal). Which results in there being four crossover gadgets whenever the two directional edges cross with two other directional edges. Erik explains more in the video at 1h1m20s (It won't allow me to link to it because this is my first post).
> 2 votes

---
Tags: complexity-theory, reductions, np-hard, 3-sat
---


# Question
Title: Having trouble proving vertex cover greedy algorithm
So this is my first time posting, but I don't know where else to go. I've spoken with several PHD and Masters students and they referred me here. I've been looking at the Vertex Cover problem and came up with an algorithm to find the optimal minimum. I've tried this on several graphs as examples and it's found the optimal every time. Could someone please help me prove that either this finds the optimal for all VC problems or if there is a counter example disproving it? Thanks in advance.

Given Graph G = (V,E), find minimum Vertex Cover

1. Sort the vertices by the number of edges associated; greatest to smallest **O(nlogn)**
2. While there are unmarked edges in E: **O(V)**
    1. Select the vertices with the highest edge count (total), put vertex in set S, and mark it’s associated edges **O(V\*E)**
    2. Break ties by prioritizing the vertices with the fewest marked edges. If a tie still exists, handle arbitrarily.
    3. Skip vertices that have no unmarked edges.
3. For each vertex in S, in the order they were added:
    1. Remove vertex from set S and update edge markings. If any associated edge becomes unmarked, reselect vertex and remark the edges. Otherwise, remove vertex from S (nobody wanted them anyways ) **O(V\*E)**
4. Return S

Algorithm runs in **O(V\*E)**. The edge markings can be maintained in a VxV table.

# Answer
I had initially missed parts 2.3 and 3.

If I'm not still missing something, then your algorithm can find a non-optimal cover for the hexagon, and necessarily finds a non-optimal cover for  $K\_{3,3}$ minus one edge. (Those are both connected balanced-bipartite graphs, so each half of their bi-partitions is a three-vertex vertex cover.)

The hexagon's vertices all have degree two, so "highest edge count (total)"  won't do anything, and your algorithm will fall back on 2.2 for each loop through 2. Your algorithm's initial choice for the hexagon doesn't matter, and its next choice will be an arbitrary one of the three vertices in the hexagon's opposite half. If your algorithm chooses the middle of those three  (i.e., the opposite vertex), then its next choice won't matter and part 2 will finish by choosing an arbitrary one of the vertices in the remaining unmarked edge. If its last choice is the one that is opposite from its next-to-last choice, then S will be the four vertices vertices from two opposite edges, which is a minimal vertex cover, in which case part 3 can't remove anything.

$K\_{3,3}$ minus one edge has four vertices with degree three and no vertices with higher degree.Those four vertices are each adjacent to a degree-two vertex, so will all be put into S. Due to the removed edge, putting those four in will result in there being no unmarked edges. Since *only* that edge was removed, S is a minimal vertex cover, so part 3 can't remove anything from it.
> 2 votes

---
Tags: algorithms, graphs, np-complete, np-hard, np
---


title: Trouble understanding Grammar Rules

text:
# Question
Title: Trouble understanding Grammar Rules
I am totaly new to theoretical computer science, so I am sorry if I get the terminology wrong:

I was reading the definition of a grammar, what I didn't get was the formal definition of the production rules: Let V be the set of Variables and sigma the alphabet. Let P be the set of Rules or productions. Formal: $P \subset (V \cup\sum)^+\times (V \cup\sum)^\*$.

I saw an example with G = ({P}, {0,1}, A, P) with the set of rules A:

1.P $\to \epsilon$

2.P $\to 0$

2.P $\to 1$

4.2.P $\to 0P0$

Now my question: How can the last rule (no 4) exist? It is not an element of the subset of the cartesian product mentioned above.

# Answer
> 1 votes
$(V\cup\Sigma)$ represents the set of variables (like $P$) and terminals (like $0$).

$(V\cup\Sigma)^\*$ represents all finite strings (including the empty string) that can be made from variables and terminals (like $0P0$ or, $01P10PP0P0$, for instance). The expression $(V\cup\Sigma)^+$ is almost the same, but excludes the empty string.

Functions are essentially matchings so can be represented by a Cartesian product $(x, f(x))$, so in your definition, a production in $(V\cup\Sigma)^+\times(V\cup\Sigma)^\*$ is a pairing from nonempty strings to strings, like the ones you gave. Others would include

* $V\rightarrow \epsilon$ (the empty string is often denoted by $\epsilon$ or $\lambda$).
* $S\rightarrow 01001$, or even
* $aT\rightarrow TbT$

---
Tags: formal-grammars, notation
---


# Question
Title: Finding a function f(n) which will bring T(n) runtime to O(log^4(n)) (Interview question)
I am having trouble finding the solution to this interview-like question:

> $T(n)$ is given as:
>
> $$T(n) = \begin{cases} 1 & n \leq c, \\ 2T(f(n))+1 & n \> c, \end{cases}$$
>
> where $c$ is some constant.
>
> Find a function $f(n)$ so that $T(n) = \Theta(\log\log\log\log n)$.

# Answer
I'm solving the case where $c=1$. Doing it for arbitrary $c$ is made in a similar fashion.

Let take $f(N) = 2^{2^{2^{\sqrt{\frac{\log^{\[3\]} N}{2}}}}}$. so that for every integer $N$ we have : $$T\left(2^{2^{2^N}}\right) = 2 T\left(f\left(2^{2^{2^N}}\right)\right)+1 = 2 T\left( 2^{2^{2^\sqrt{N/2}}} \right)+1.$$

I'm assuming in your question that you are only interested in functions $f$ that are increasing over $\mathbf{N}$. Let prove that $T(N) = \Theta(\log^{\[4\]} N)$, that is proving that there exists two positive constants $A,B$ such that for sufficiently big $N$, $$ A\log N \leq T\left(2^{2^{2^{N}}}\right) \leq B\log N.$$

Let assume the last inequality holds up to some $\sqrt{N}\>1$, with constant $A=1$ and some $B \> 1$. Then $$f\left(2^{2^{2^N}}\right) = 2 T\left( 2^{2^{2^\sqrt{N-1}}} \right)+1,$$ and so by hypothesis: $$\log N = 2 \log\sqrt{N/2} +1 \leq T\left(2^{2^{2^N}}\right) \leq 2 B\log\sqrt{N/2}+1 = B \log N +1-B \leq B\log N.$$

We can then conclude by induction, jumping by successive squaring, using the increasing property of $T$ to fill the gaps.
> 1 votes

---
Tags: complexity-theory, runtime-analysis
---


# Question
Title: Modeling tiling problems as SAT problems
I read that tiling problems can be modeled as satisfiability problems (2-SAT?), but the author did not explain how. Is this true? What would be an example?

By a "tiling problem" I mean you have a matrix and have to fill it up according to some constraint. For example, you might have to fill the matrix with a particular shape, or the values in the matrix have to adhere to some constraint. For example, imagine a partially filled matrix and the rule is that you have to fill it with values that are one more or one less than the adjoining values, or something like that.

# Answer
One example of a tiling problem that was successfully attacked by reducing it to a SAT instance was rectangular grid coloring. In "Extremely Complex 4-Colored Rectangle-Free Grids: Solution of Open Multiple-Valued Problems" the authors describe how they tackled 17x17, 17x18, and 18x18 grid colorings using a SAT solver plus some previous knowledge of grid coloring theory to pare down the search space.
> 2 votes

# Answer
It's possible that you're talking about Wang tiles. Imagine that you have to fill up a matrix with tiles that cannot be rotated. Each side of each tile is a given color. If two tiles are placed next to each other (share an edge), they must have the same color along that edge.

While the color vs number aspect is not important, this differs from your requirement in that each side has a different color (whereas you are talking about only a single number per spot). So far as I can tell, this difference is fundamentally important.

If you want to obtain NP-hardness, I believe you need further constraints (such as having colors along the border of the matrix). However, with this slight extension, it seems that this can fairly easily be proven by extending the undecideability result for Wang tiles; this mathoverflow answer discusses this a bit.
> 1 votes

---
Tags: satisfiability, modelling, constraint-satisfaction, tiling
---