# Question
Title: What will a given CPU architecture do in the event that we were to invert all of the instruction bits to a given instruction?
Given an arbitrary CPU - Architecture and its instruction set... What would be the outcome of the given inverted instruction within that Architect?

For simplicity, let's use an 8-bit CPU architecture that has an 8-bit Bus design where that bus is used for both addressing and data transfer operations. A single instruction or micro instruction will act on an 8-bit string of binary digits per clock cycle. Each clock cycle may consist of 3,4,or 5 micro instructions before incrementing the instruction register for the next full instruction to be processed. These would account for the `Fetch`, `Decode`, and `Execute` phases of a single CPU clock cycle instruction.

The following is a mock-up only to demonstrate or illustrate my curiosity and concern while designing the layout of a given `ISA`(Instruction Set Architecture)...

Here we have the range of possible instructions from `[0000 0000, 1111 1111]` which are all of the possible permutations that this arbitrary CPU-Architecture's Machine Language can support. We could use **Ben Eater's** 8-bit Bread Board CPU and its `ISA` as an example... You can find that here along with other useful videos from his YouTube channel: Comparing C to Machine Language, and Programming 8-Bit Computer. With his given implementation, the first 4 bits are used to define the `instruction` and the second 4 bits are used for `data` {either memory address or immediate value}...

Now to my question: Given a specific instruction word and its accompanying data field, what would be the resulting outcome if we invert all of the instruction bits?

First, I know that this would be independent on each Architecture's `ISA` design implementation... Second, I'm just curious to what the ramifications would be when designing your own specifications in that, would it be possible to carefully design and layout your bit fields per instruction in a manner that you could have a special invert operation, that would automatically invert a given instruction where that inversion would produce the opposite or inverse effect of the given incoming instruction? Now, the inversion won't necessarily happen to the entire instruction string that includes all 8-bits, but only to the bit-fields that pertain to the instruction type while preserving the data field... For example:

* If we have an Add instruction, the invert op would turn this to a Sub...
* If we have an And instruction, the invert op would turn this to an Or instruction...
* If we have either a Bit Shift Logical Left or Bit Shift Arithmetic Left, the invert op would respectively turn these into Bit Shift Logical/Arithmetic Right operations...
* And so on...

Would such a design be possible to have perfect symmetry within it's ISA?

*-Note- I don't know if this is the correct StackExchange site for this question... if it is not please don't down vote it due to being irrelevant and be kind enough to point me in the right direction letting me know where the appropriate site for this question would be.*

# Answer
> 1 votes
If you are decoding instructions using logic based on individual bits in the opcode, this "inversion' scheme is probably counter productive. If the opcodes are decoded using a simple table lookup of the "value" of the opcode, then the actual pattern of the opcode is just arbitrary and the inversion scheme is just as valid as one based on the alphabetic order of the mnemonics.

For stack based machine, variable length opcodes could be more valuable, shorter opcodes for push, pop, and any immediate value instructions to give more space for address or data bits.

Self-modifying code has been out of fashion for decades, so being able to flip the meaning by inverting the bits would seem to have no utility.

---
Tags: computer-architecture, assembly
---


# Question
Title: How to prove the class of regular languages is closed under 3MAJ?
Let $\Sigma$ be some alphabet. We define the following operation on the set of all languages over $\Sigma$.

The operation $\mathrm{3MAJ}(L\_1, L\_2, L\_3)$ takes in three languages $L\_1$, $L\_2$ and $L\_3$ and outputs the language of all words that are members of the majority of the input languages. Formally: $$\mathrm{3MAJ}(L\_1, L\_2, L\_3) = \\{w \in \Sigma^\*\mid\text{ at least two out of the }L\_1, L\_2, L\_3\text{ contain }w\\},$$ where $\Sigma^\*$ is the set of all words over $\Sigma$. How to prove that the class of regular languages is closed under the operation 3MAJ?

# Answer
> 6 votes
**Hint:** prove that $3MAJ(L\_1, L\_2, L\_3) = (L\_1 \cup L\_2\cap L\_3) \ \cap \ (L\_2 \cup L\_1\cap L\_3) \cap \ (L\_3 \cup L\_1\cap L\_2)$.

# Answer
> 2 votes
Let's consider 3 regular languages $L\_1$, $L\_2$ and $L\_3$. By Kleene's theorem, there exist 3 DFA $\mathcal{A}\_1 = (Q\_1, \delta\_1, q\_1, F\_1)$, $\mathcal{A}\_2 = (Q\_2, \delta\_2, q\_2, F\_2)$ and $\mathcal{A}\_3 = (Q\_3, \delta\_3, q\_3, F\_3)$ that recognize respectively $L\_1$, $L\_2$ and $L\_3$. Let $\mathcal{A} = (Q, \delta, q\_0, F)$ an automaton defined by:

* $Q = Q\_1\times Q\_2\times Q\_3$;
* $q\_0 = (q\_1, q\_2, q\_3)$;
* $\forall (q, q', q'') \in Q, \forall a \in \Sigma, \delta((q, q', q''), a) = (\delta\_1(q, a), \delta\_2(q', a), \delta\_3(q'', a))$ which means you read a word in all three automata simultaneously;
* $F = Q\_1\times F\_2\times F\_3 \cup F\_1\times Q\_2\times F\_3 \cup F\_1\times F\_2 \times Q\_3$

Then $L(\mathcal{A}) = 3MAJ(L\_1, L\_2, L\_3)$ (I leave the formal proof to you). That proves that regular languages are closed under $3MAJ$ operation.

---
Tags: regular-languages
---


title: Tournament Scheduling Problem

text:
# Question
Title: Tournament Scheduling Problem
I am trying to design an algorithm to compute the solution to this problem.

Given a list of n tournaments with a name, start\_date, end\_date, latitude and longitude, find the list of p tournaments in chronological order with the least total travel distance when a person has to travel from one tournament to the next to the next.

A valid list of tournaments (called a tour) is where there are no overlaps in dates. The sports person travels from one tournament to the next along the straight line between the 2 coordinates.

I have a working solution but it uses too much memory.

I start by building a graph where nodes are tournaments and edges are the straight line distances between the coordinates of a node and a child\_node. Each node has child nodes representing only tournaments which occur after it.

I then define a tour as a list of these nodes.

I start with a previous\_tours list (containing tours of length i) and a current\_tours list (containing tours of length i + 1). The previous\_tours list is initialised with tours of length 1, which is just n tours each with one of the nodes.

Then to calculate the current\_tours list, I loop through the previous\_tours list and for each tour (current\_tour) I get the last\_node in the tour. Then for each child\_node in last\_node, I copy the current\_tour and append the child\_node to the end of the tour and add each copy to the current\_tours list. This calculates all possible tours of length 2 as nodes only have child nodes occuring after it. The distance between the last\_node coordinates and the child\_node coordinates is added to the tours total travel distance. I then set previous\_tours to current\_tours.

I repeat this until I have all possible tours of length p. Then I loop through this list to find the one with the least total travel distance.

This is giving me the correct answer, but I am giving it a list of 120 tournaments and trying to calculate the best tour of length 4 and it uses around 5GB of memory when I implemented it in C++

I was thinking of just adding in a heuristic at each iteration to cut down the number of possible tours.

Does anyone know a more efficient way of getting this result without using a heuristic in that way?

# Answer
> 1 votes
The chronological order constraint actually makes this problem much easier to solve than D.W. thought. It means that we can orient edges in the graph from earlier to later tournaments (reflecting the fact that we cannot travel back in time), and wind up with a DAG (cycle-free directed graph). The problem can be solved optimally in $O(pn^2)$ time and $O(pn)$ space (so, at most a few milliseconds and KB for your problem size) using dynamic programming.

Let $f(v, i)$ be the length of the shortest $i$-vertex path that ends at vertex $v$. The goal is to compute $f(v, p)$ across all vertices, and pick the $v$ that minimises the function among all of them.

**The shortest $i$-vertex path ending at vertex $v$ must be the result of extending (by one edge, to $v$) the shortest length-$(i-1)$ path to one of $v$'s predecessors:**

$f(v, i) = \min\_{u:uv\in E} f(u,i-1)+d\_{uv}$

where $E$ is the set of all edges in the graph and $d\_{uv}$ is the distance between $u$ and $v$.

Naturally we also have $f(v, 1) = 0$ for all $v$. So, we can compute all these function values and store them in a 2D array as follows:

* Initialise $f\[1\]\[v\] = 0$ for all $v$.
* For $i$ from 2 to $p$:
    + For each $v$ in $V$:
        - Set $x = \infty$.
        - For each predecessor (in-neighbour) $u$ of $v$:
            * Set $x = \min(x, f\[i-1\]\[u\] + d\_{uv})$.
        - Set $f\[i\]\[v\] = x$.
* Set $z=v\_1$.
* For each $v$ in $V\setminus \\{v\_1\\}$:
    + If $f\[p\]\[v\] \< f\[p\]\[z\]$ then set $z=v$.

After running this, we know the *lengths of* all shortest paths of $i$ vertices or less ending at each vertex, and that the shortest overall path of $p$ vertices ends at vertex $z$. To find an actual shortest path ending at vertex $z$, we can trace backwards through the matrix looking for predecessor entries that satisfied the $\min$ condition:

* Set $i=p$.
* While $i\>0$:
    + Output the current vertex, $z$.
    + Set $x = \infty$.
    + For each predecessor (in-neighbour) $u$ of $z$:
        - If $f\[i-1\]\[u\] + d\_{uz} = f\[i\]\[z\]$:
            * $u$ is the previous tournament on some optimal path ending at $z$, so set $z=u$, decrease $i$ by 1 and jump to the top of the while loop.

This will output the tournaments in reverse order, but that can be easily fixed.

---
Tags: scheduling
---


# Question
Title: Generating Combinations from a set of pairs without repetition of elements
I have a set of pairs. Each pair is of the form (x,y) such that x,y belong to integers from the range `[0,n)`.

So, if the n is 4, then I have the following pairs:

```
(0,1) (0,2) (0,3)
(1,2) (1,3)
(2,3)

```

I already have the pairs. Now, I have to build a combination using `n/2` pairs such that none of the integers are repeated (in other words, each integer appears at least once in the final combination). Following are the examples of a correct and an incorrect combination for better understanding

```
 1. (0,1)(1,2) [Invalid as 3 does not occur anywhere]
 2. (0,2)(1,3) [Correct]
 3. (1,3)(0,2) [Same as 2]

```

Can someone suggest me a way to generate all possible combinations, once I have the pairs.

# Answer
> 16 votes
One direct way is a recursive procedure that does the following on each invocation. The input to the procedure is a list of pairs that have already been chosen and a list of all the pairs.

1. Compute the smallest number not already covered by the input list. For the first invocation, this will be 0 of course, because no pairs have been chosen.
2. If all the numbers are covered, you have a correct combination, print it out and return the the previous step. Otherwise, the smallest number that is uncovered is the target we will aim for.
3. Search through the pairs looking for a way to cover the target number. If there is none, then just return to the previous level of recursion.
4. If there is a way to cover the target number, pick the first way and recursively call the entire procedure again, with the pair just picked add to the list of chosen pairs.
5. When that returns, look for the *next* way to cover the target number with a pair, without overlapping a previously chosen pair. If you find one, pick it and again recursively call the next procedure.
6. Continue steps 4 and 5 until there are no more ways to cover the target number. Go through the entire list of pairs. When there are no more correct choices, return to the previous level of the recursion.

The way to visualize this algorithm is with a tree whose paths are sequences of non-overlapping pairs. The first level of the tree contains all the pairs that contain 0. For the example above, the tree is

```
           Root
             |
     ----------------
     |       |       |
   (0,1)   (0,2)   (0,3)
     |       |       |
   (2,3)   (1,3)   (1,2)

```

In this example all the paths through the tree actually give correct collections, but for example if we left out the pair (1,2) then the rightmost path would have only one node and would correspond to the search in step 3 failing.

Search algorithms of this type can be developed for many similar problems of enumerating all objects of a particular type.

---

It was suggested that perhaps the OP meant that *all* pairs are in the input, not just a set of them as the question says. In that case the algorithm is much easier because it's no longer necessary to check which pairs are allowed. It's not even necessary to generate the set of all pairs; the following pseudocode will do what the OP asked. Here $n$ is the input number, "list" starts out as an empty list, and "covered" is an array of length $n$ initialized to 0. It could be made somewhat more efficient but that's not my immediate goal.

```
sub cover {
  i = 0;
  while ( (i < n) && (covered[i] == 1 )) {
   i++;
  }
  if ( i == n ) { print list; return;}
  covered[i] = 1;
  for ( j = 0; j < n; j++ ) {
    if ( covered[j] == 0 ) {
      covered[j] = 1;
      push list, [i,j];
      cover();
      pop list;
      covered[j] = 0;
    }
  }
  covered[i] = 0;
}

```

# Answer
> 10 votes
You can solve it iteratively. Suppose you have all solutions $S\_n$ for the range $\[0,n)$. Then you can easily construct the solutions $S\_{n+2}$ from $S\_n$. The size grows extremely quickly with $n$, so it may be good to write a generator rather than to hold all the sets in memory, see Python example below.

```
def pairs(n):
    if (n%2==1 or n<2):
        print("no solution")
        return
    if (n==2):
        yield(  [[0,1]]  )
    else:
        Sn_2 = pairs(n-2)
        for s in Sn_2:
            yield( s + [[n-2,n-1]] )
            for i in range(n/2-1):
                sn = list(s)
                sn.remove(s[i])
                yield( sn + [ [s[i][0], n-2] , [s[i][1], n-1] ] )
                yield( sn + [ [s[i][1], n-2] , [s[i][0], n-1] ] )

```

You can list all pairs by calling

```
for x in pairs(6):
   print(x)

```

# Answer
> 6 votes
**Update**: my earlier answer dealt with bipartite graphs, which the OP was NOT asking about. I'm leaving it in for now, as related info. but the more pertinent information relates to perfect matchings in nonbipartite graphs.

In this regard, there's a nice survey by Propp that outlines progress (till 1999). Some of the ideas in that article, and the related links, might prove to be useful. the TL;DR is - it's tricky :)

*--- Start of old answer*

Note that what you're asking to do is enumerate all possible perfect matchings on a bipartite graph. There are many different algorithms for doing this, and in particular one of the more recent ones is from ISAAC 2001.

The basic idea is to find one perfect matching by using network flows, and then repeatedly modify this by using alternating cycles (see any algorithms textbook chapter on network flows for more information).

# Answer
> 4 votes
Every pair you pick eliminates two rows from which you can not pick anymore. This idea can be used to setup a recursive algorithm (in Scala):

```
def combine(pairs : Seq[(Int,Int)]) : Seq[Seq[(Int, Int)]] = pairs match {
  case Seq() => Seq()
  case Seq(p) => Seq(Seq(p))
  case _ => {
    val combinations = pairs map { case (a,b) => {
      val others = combine(pairs filter { case (c,d) =>
        a != c && a != d && b != c && b != d
      })

      others map { s => ((a,b) +: s) }
    }}

    combinations.flatten map { _.sorted } distinct
  }
}

```

This can certainly be expressed in a more efficient way. In particular, the idea of not having to consider whole rows for combinations is not used by the call to `filter`.

# Answer
> 4 votes
While there are already many lovely ansewers to the question, I think it would be nice to point out the basic, general, trick behind them.

**It is much easier to generate unique combinations if you can have a total ordering of the elements to be combined**. This way, uniqueness is guaranteed if we only allow sorted combinations. It is not hard to generate the sorted combinations either - just do the usual brute force enumeration search, but at each step only pick elements larger then the ones already picked at each step.

The extra complication in this particular problem is the desire to get only the combinations of length n/2 (the maximal length). This is not hard to do if we decide on a good sorting strategy. For example, as pointed out in Carl Mummet's answer, if we consider a lexicographical sort, (top-down, left-right in the diagram in the question) we derive the strategy of always taking the next element so that its first digit is the smallest still unused number.

We can also extend this strategy if we want to generate sequences of other lengths. Just remember that whenever we pick a next element whose first number is not the smallest one available we rule out one or more rows of elements from appearing on the sorted subsequence, so the maximum length of the prermutation decreases accordingly.

# Answer
> 3 votes
I am not sure if this is what you are asking but as I understand, you have all $n \choose 2$ unordered pairs of $\[n\] = \\{1, \cdots, n\\}$ and want to count the list of all pairs that cover the set $\[n\]$ where $n$ is an even number. We can think of this as edge-coverings of $K\_n$, the complete graph on $n$ vertices.

Moreover the question seems to assume that each number in $\[n\]$ appears only once in the list. In which case, we are only looking at the coverings which are perfect matching. The number of matching in a graph is equal to the permanent of its adjacency matrix. So we need to compute $\mathsf{Perm}(K\_n)$.

It is known that permanent is $\mathsf{\\#P\text{-}complete}$, but this is in general case. For $K\_n$ there are $\frac{n!}{2^{\frac{n}{2}}}$ such lists.

The easiest way to generate all of these is to fix one perfect matching and then apply a permutation of $\[n\]$ but this will generate many duplicates.

# Answer
> 1 votes
Using list comprehensions works giving a one-line body function:

```
def pairs(n):
    return [[a,b] for a in range(n) for b in range(a,n) if a != b]

```

which returns the expected \[\[0, 1\], \[0, 2\], \[0, 3\], \[1, 2\], \[1, 3\], \[2, 3\]\] for n=4

---
Tags: algorithms
---


title: Arrow notation?

text:
# Question
Title: Arrow notation?
can someone explain what the following notation is?

```
For j <- 1 to n
    Legal <- True

```

I've seen these in various places, including wikipedia articles. It seems to be a specific notation, but I don't know the name and can't find much of anything on it.

Can someone explain what it is, where it's used, if it's in widespread use, and maybe provide a link to a reference or somewhere I can learn the language/symbols and their meaning?

# Answer
> 12 votes
In general, there are no standards for pseudo-code. Everybody can design their own pseudo-code however they want to. Normally, an author should define the conventions they use for their pseudo-code.

Unfortunately, pseudo-code is often used without documenting it, under the assumption that it will be "obvious" to the reader what the code means. As you have discovered, what is and isn't obvious to the reader obviously depends on the reader!

In my case, the snippet you posted is obvious to me, because I am used to programming languages that use the  operator symbol in the same way: Scala, Haskell, historic Smalltalk.

Arrows *generally* are used to indicate that "some thing" is "flowing" in the direction of the arrow. A rightwards arrow typically means "goes to" in the sense of a mapping or a function. A leftwards arrow typically means "becomes" or "let" or "draws from". However, arrows can also indicate message sends or receiving messages. You have to be aware of the context.

This code looks like it is simple imperative structured programming code, so the "assignment" meaning is the more likely interpretation, but if this where pseudo-code for some process calculus, an asynchronous, concurrent, parallel, or distributed algorithm or data structure, or something along those lines, it could likely also mean "blocks until it receives a message" or something like that.

In this particular case, the two leftwards arrows have slightly different, but strongly related meaning:

The second one simply means "`Legal` becomes `True`", so this is a form of assignment. (This assignment syntax was actually used by historic Smalltalk versions.)

The first one also means assignment, but it is interpreted to mean that `j` takes *all the values* on the right-hand side, one after the other. In other words, this is a `FOREACH` iterator loop. (Scala actually uses the leftwards arrow in precisely this meaning in its `for` comprehensions.)

# Answer
> 8 votes
Left arrows often mean assignment or modification. This pseudo-code can be interpreted as

"For j from 1 to n, the variable Legal is given the value True"

Check this page: https://en.wikipedia.org/wiki/Pseudocode#Common\_mathematical\_symbols

# Answer
> 3 votes
This notation, and others such as `:=`, is a reaction against the use of `=` for assignment, which some computer scientists find deplorable, due to that symbol's role as a pure relation in mathematics.

There is an anecdote I recall from very long ago about some famous computer scientist, perhaps Dijkstra, having become outraged during some seminar lecture and loudly yelling out *"becomes! becomes!"* at the point when the presenter had written or projected an "a = b + c" expression which he then began reading out loud as "a **equals** b plus c".

That `<-` symbol is "becomes". It's intended to thwart being read as "equals" and any confusion which that might entail.

Here is a true story of my own: he first time I had ever seen a computer program, which was written in line numbered BASIC and contained a few lines of variable assignments, I was really puzzled because I thought that this was a system of equations being declared for the machine to solve! "But how on Earth can X be equal to X + 1??!" I thought.

# Answer
> 2 votes
I think this is often used in pseudo-code to distinguish between equality and assignment because different languages have different rules for how this works. For example, = can be an assignment or copy in c++ and javascript has a table of rules on how equality checks works. The point of pseudocode is not to depend on language conventions and to attempt to be unambiguous in what the code does.

---
Tags: notation
---


# Question
Title: Why mod operation can be used as hash function
I'm new here, and I'm currently trying to understand why mod operation can be used as a hash function.

For example, consider the function $h(x)=x\mod 2^{256}$, where $x$ can be a string of any length. The book says that this function will return a fixed size of 256 bits. To my understanding, $h(x)$ will return an integer in the interval $\[0,2^{256})$, which can be expressed in 256 bits. My question is that, suppose $x$ is $5$, then $h(x)=5$, which can also be expressed in 3 bits (101). How do we guarantee that the output will be the size of $256$ bits? (I am just new to computer science and apologize if the question is too elementary).

# Answer
> 1 votes
The output of the function can always be expressed as a 256-bit value. The value 5 is expressed as 00000...000101 (some 0's omitted).

---
Tags: hash
---


title: Programming Language Hierarchy

text:
# Question
Title: Programming Language Hierarchy
I know that Assembly is the lowest level of the stack besides machine code, but are the languages above it all considered "high level languages" or is there a hierarchy amongst these languages. For instance, are C++, Ruby, and Python all "high level languages"?

# Answer
> 1 votes
High Level languages are all languages that are able to be written in code that is easy to read. High level languages will use words that are easily read and understood and because of this, the code is very different from low level code. Code written in these languages has to be compiled and assembled into code that the computer can directly understand. This resulting code will be the low level language/code that you are referring to.

Examples:

High Level: C++, Java, C# Low Level: Assembly, Machine code

# Answer
> 3 votes
There are supposedly generations of languages. According to Wikipedia:

First generation: Machine language.

Second generation: Low-level programming languages such as assembly language.

Third generation: Structured high-level programming languages such as C, COBOL and FORTRAN.

Fourth generation: Domain-specific high-level programming languages such as SQL (for database access) and TeX (for text formatting)

The fifth generation was supposed to be developed by Japan's fifth generation project in the 1980s but didn't really go anywhere. Some people consider constraint-based languages to be fifth generation (Wikipedia).

There is also a supposed hierarchy of language power, expressed by Paul Graham as the "Blub Paradox" in his essay Beating the Averages. In this controversial approach, languages such as Basic and Cobol are low in the hierarchy, Python and Perl would be in the middle, and Lisp would be at the top.

# Answer
> 1 votes
Perhaps a better way to try to understand which languages come from where is a directed graph on a timeline (like a family tree ).

Shameless Plug

# Answer
> -1 votes
This picture shows the hierarchy:

Machine Language is the lowest. It is the most understandable by computer.

High level language is the highest. It is the most understandable by human so far.

---
Tags: programming-languages
---


# Question
Title: Las Vegas algorithm for finding 00000 in bit string
> **Problem 1:** Consider the following problem: given a binary string $w=a\_1a\_2\cdots a\_n \in\\{0,1\\}^\*$, decide whether $w$ contains 00000 as a substring (i.e., where $w$ contains five consecutive 0's). There is an obvious $O(n)$-time algorithm. You will investigate the hidden constant factor, concerning the number of bits that need to be examined (i.e., the number of $a\_i$'s that need to be evaluated) to solve this problem.
>
> 1. (10/100 points) First argue that every deterministic algorithm solving this problem needs to evaluate $\Omega(n)$ bits in the worst case.
> 2. (30/100 points) Prove that for a sufficiently large constant $c$, for any string $a\_1 \cdots a\_c$ of length $c$ that does not contain 00000, there must exist two indices $i,j \in \\{1,\ldots,c\\}$ with $a\_i=a\_j=1$ and $2 \leq |i-j| \leq 5$.
> 3. (60/100 points) Design a Las Vegas randomized algorithm solving this problem (with zero error probability) that evaluates an expected $\alpha n + o(n)$ number of bits for any input, for some constant $\alpha$ strictly smaller than $1$. (You do not need to optimize the constant $\alpha$.)

Above is a question some friends and I have looked at to prepare for a qualifying exam and is itself from a past qualifying exam. Parts 1 and 2 are fine but what we are having troubles with is part 3. I think the idea behind this problem is to imagine that evaluating some bit $s\_i$ is really expensive, so we would like to get the right answer while minimizing how many of these bits we evaluate. That said, there is some ambiguity to us about whether we (1) care about the number of *distinct* bits we evaluate or (2) the total number of times we evaluate any bit. Clearly if we were worried about the latter, we could just store the result of the bit evaluation and avoid doing an expensive evaluation again, but we are not sure. For now, I assume the latter case and specifically that if we want the value for the same bit twice, we assume we need to evaluate it each time and incur $2$ units to the cost we are trying to minimize.

---

Now I have some idea for this problem and to help explain my idea, let us consider a simple deterministic algorithm with the pseudocode written below. We will loop from the start of the string to the end, checking all meaningful 5 bit substrings. If we ever find a $1$ bit as we loop over a 5 bit substring, we know that substring cannot be $00000$ but if we start at the bit right after that $1$ bit, there might be one. Thus, we update our new starting point to the position right after that $1$ bit and then start back up again from there.

On input $s$:

1. set $i \leftarrow 1$
2. while($i \leq (n-4)$):
    * set $b \leftarrow \text{true}$
    * for($j = 0$ to $4$):
        + if( $a\_{i+j} = 1$ ):
            - $i \leftarrow (i+j+1)$
            - $b \leftarrow \text{false}$
            - break for loop.
    * if( $b = \text{true}$ ):
        + return **TRUE**
3. return **FALSE**

My idea for a Las Vegas algorithm was to do the same algorithm but slightly modify it by making the inner loop performed in random order, making the pseudocode now be

On input $s$:

1. set $i \leftarrow 1$
2. while($i \leq (n-4)$):
    * set $b \leftarrow \text{true}$
    * for($j = 0$ to $4$ *in random order*):
        + if( $a\_{i+j} = 1$ ):
            - $i \leftarrow (i+j+1)$
            - $b \leftarrow \text{false}$
            - break for loop.
    * if( $b = \text{true}$ ):
        + return **TRUE**
3. return **FALSE**

The positive thing going for this algorithm is that if there exists a $1$ bit in the 5 bit substring we are looking at in the inner loop, we will find it in at most $3$ loop iterations in expectation. However, if I define a bit string $s$ to be $$s = 100001 100001 100001 \cdots 100001$$ then the algorithm should require looking at $6$ bits (potentially some of the same ones multiple times) in expectation to get past each $100001$ substring. This implies on this input we will go to see the value of $n$ bits (the number of distinct bits seen may be less) in expectation before we answer the question of if $00000$ is contained in $s$. Thus, this algorithm does not seem sufficient.

Does anyone have any thoughts on how to approach this problem or think we should actually be worried about the number of distinct bits we evaluate? If yes to the latter, then I could potentially see other ways to tackle this problem.

# Answer
Let $c$ be the constant from part 2, and assume for simplicity that $n$ is divisible by $c$ (otherwise, query the first $n \bmod c$ bits).

Partition the string into intervals of length $c$, and go over them one by one in an arbitrary order. The order doesn't need to be random – you can go over them from left to right.

For each interval $I$, choose a pair $(i,j)$ out of all pairs $i,j \in \\{1,\ldots,c\\}$ at distance $j-i \in \\{2,\ldots,5\\}$, and query the points $I\_1,\ldots,I\_i,I\_j,\ldots,I\_c$. If $I\_i=I\_j=1$, then there is no need to query the points $I\_{i+1},\ldots,I\_{j-1}$, otherwise do query them. If the interval contains 00000, immediately halt, answering Yes.

After going through all intervals, check whether the string contains 00000 (the unqueried points make no difference here), and answer accordingly.

According to part 2, if an interval $I$ doesn't contain 00000, then with probability $p \geq 1/4c$ the chosen pair $(i,j)$ will satisfy $I\_i = I\_j = 1$, and in this case we query at most $c-1$ out of the $c$ points. If it does contain 00000, then we query all points, and immediately halt. This shows that on average, we query at most $(1-1/4c^2)n + 2c$ points (taking into account the case in which $n$ is not divisible by $c$).
> 2 votes

---
Tags: algorithms, algorithm-analysis, strings, randomized-algorithms
---


# Question
Title: Is the time complexity of the Fibonacci sequence O(fib(n))?
I started watching SICP lectures and am totally new to computer science. SICP. LEC 1B: Procedures and Processes; Substitution Model

I don't know why the time complexity of the Fibonacci sequence is O(Fib(n)). So, I googled about it,

he says

> There's a thing that grows exactly at Fibonacci numbers. It's a horrible thing. You wouldn't want to do it. The reason why the time has to grow that way is because we're presuming in the model-- the substitution model that I gave you, which I'm not doing formally here, I sort of now spit it out in a simple way-- but presuming that everything is done sequentially. That every one of these nodes in this tree has to be examined. And so since the number of nodes in this tree grows exponentially because I add a proportion of the existing nodes to the nodes I already have to add one, then I know I've got an exponential explosion here.

Can anybody please explain what he's saying?

# Answer
$\DeclareMathOperator{\fib}{fib}$If you choose to calculate $\fib(n)$ by using the naive recursion formula, then you need $\Theta (\fib(n))$ additions, and since the numbers involved grow to $c\cdot n$ bits for a not very large constant $c$, it will take $\Theta(n \cdot \fib(n))$ operations. (I may be wrong here because most of the numbers involved may be much smaller than $c \cdot n$ bits).

If you are reasonably clever and calculate $$\fib(0), \fib(1), \fib(2), \dots, \fib(n),$$ then you have $n$ additions of $c \cdot n$ bit numbers, which takes $\Theta(n^2))$ operations.

You can use matrix exponentiation to calculate $\fib(n)$ faster for large $n$, I'd estimate something like $M(n)$ where $M(n)$ is the time for an $n$-bit multiplication.

Most important is that for maybe $n = 100$ or $n = 200$, your computer has not a chance to calculate $\fib(n)$ using the naive recursive algorithm within your lifetime, while the simple method of calculating consecutive values will find the same result within microseconds on a newish smartphone.
> 4 votes

---
Tags: time-complexity
---


# Question
Title: Brute force method to solve the 0-1 knapsack problem
I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following:

* If the brute force method can solve the problem with 20 items in 1 second - how many items can it solve in one day (2^16 s)?

I know that the time complexity of brute force is big O(2^n). But still I don't see how I can solve this.

# Answer
> 3 votes
As O(2^n) says adding one item will double computation time, giving the fact that one day equals 2^16 seconds, you more or less answered the question yourself.

A method solving a problem with 20 items in 1 second will will solve a problem with 20 + 16 = 36 items in a day.

Wow, downvote for the right answer, that's nice! So let us elaborate on this:

## Calculation 1

As we know worst-case runtime for 20 items is 1 second, there is no need to experiment and guess the constant factor (c) as suggested in another answer.

Instead we can get it by simple calculation:

`1 second = c * 2^20 => c = 1/2^20 = 2^-20`

The equation we still have to solve, to find out, with how many items we can expect an answer in a day is:

`1 day =~ 2^16 seconds = c * 2^n = 2^-20 * 2^n`

multiplied by `2^20` on both sides we end up with:

`2^36 = 2^n`

Which we might logarithmize on both sides, if we don't see, that `n=36` directly.

qed.

## Calculation 2

After verification of the answer 36, let's take a closer look at the alternative suggested - experimenting with 40 and 80 items\*.

\[\*: at least before the author changed from these numbers to n\_1 and n\_2\]

**Expermient 1 - 40 items**

For 40 items the algorith will take 2^20 times the time it takes for 20 items, and as such:

`2^20 = 1048576 s = 17476 min = 291 h = 12 days`

While waiting those 12 days for our calculation to complete, let's take a look at our second suggestion.

**Expermient 2 - 80 items**

For 80 items we will have to deal with 2^60 times the time it takes for 20 items:

`2^60 = 1152921504606846976 s = 19215358410114116 min = 320255973501901 h = 13343998895912 days = 36558901084 years`

As scientists estimate the age of our universe to be something around 13.7 * 10^9 years our result of something like 36.5 * 10^9 years seems to be rather ambitious.

Good luck waiting anyways.

## naive c * 2^n Algorithm

There were doubts wether such an algorithm exists, so here a sample brute-force algorithm working in c * 2^n.

Written in pseudo code, so familarity with a specific programming language should not be required.

```
# let w[1], ... , w[n] be the weights of the items
# let v[1], ... , v[n] be the values of the items
# let maxWeight be the capacity of the knapsack

bestValue := 0

function solve(n, currentWeight, currentValue) {

    if n = 0 and currentWeight <= maxWeight and currentValue > bestValue:
        bestValue := currentValue

    if n = 0: return

    # don't pack this item
    solve(n-1, currentWeight, currentValue)
    # pack this item
    solve(n-1, currentWeight + w[n], currentValue + v[n])
}

solve(n, 0, 0)

print bestValue

```

Assignments and comporisons made in `solve` all run in O(1).

Recursion depth is n with 2 recursive calls in each run, resulting in 2^n runs total.

Runtime is thus not only bound by O(2^n), but also of the form c\*2^n as requested.

qed.

## Answering still open questions

... taken from the comments section

> 1) How do you check a solution candidate in O(1) time? 2) Even the most naive algorithm may find a witness early and abort. 3) How do you make the jump from some abstract, unspecified combinatoric measure to runtime (in seconds)?

**ad 1**: O(1) time candidate check in the pseudo code example takes place in line 9:

`if n = 0 and currentWeight >= maxWeight and currentValue > bestValue:
 bestValue := currentValue`

**ad 2**: It indeed **may**

... if you are lucky or at least not very unlucky. Nevertheless there is no guarantee.

**ad 3**: The "jump" to computation time in seconds takes into account the trustworthyness of the information that

> the brute force method can solve the problem with 20 items in 1 second

... (on a specific machine) given in the exercise, reading "*the problem*" as a synonym for the *0-1 knapsack problem*, which, at least as I read it, should include all problem instances, even the ones taking worst-case time.

# Answer
> 4 votes
You can't. Landau notation does not hold enough information.

* You don't know the constant factor(s).
* With only $O$, you don't have a *lower* bound.
* It's only a *worst-case* bound; different runs with the number of items can have wildly different runtimes.
* Such bounds only hold *in the limit*, that is even $\leq c \cdot 2^n$ may not hold for those $n$ you can realistically run the algorithm for.
* The quantity bounded is *not* runtime but some abstract measure.

In particular, effects like operation reordering, memory hierarchy and branch mispredictions routinely skrew with runtimes.

The best you can do is *assume* that the runtime behaves like $\approx c \cdot 2^n$, run experiments with $n\_1$ and $n\_2$ items and estimate the constant factor -- then it's simple rule of three. But given all the caveats listed above, the prediction is unlikely to be worth much.

# Answer
> 0 votes
There are two problems if the only things you know are "the time is O (2^n)" and "the problem is solved in 1 second for n = 20": One, big-O only gives you information for large n. You don't know what's large. You might have a problem that can be solved in exactly 1 second for any n ≤ 1 billion, and $2^{n-1,000,000,000}$ seconds for any larger n. Two, big-O gives an upper bound. Your time could be n/20 seconds for every n; n/20 is in O(2^n) but you can solve quite large problems in a day.

You can make a more or less educated guess that the execution time is $c * 2^n$ seconds for some unknown c, then you can calculate that $c = 2^{-20}$ and that 36 items give you an execution time of $2^{16}$ seconds. But that is a calculation based on a guess, and you need to be aware of that. You would want more than one data point to see how good your guess about the execution time is.

---
Tags: algorithms, efficiency, knapsack-problems
---


title: Issue with the Halting Problem

text:
# Question
Title: Issue with the Halting Problem
***For clarity, I'll claim the supposed impossible program to be 'Code X'.***

Something doesn't seem to make sense about the proof against Code X:

Consider a code that halts if you input oranges, but doesn't if you input apples. The answer to whether it halts is in this very obvious case is that 'it depends'. So either this is a much more simple proof or the Halting problem excludes input-dependant codes (or assumes a pre-determined input). I'll stick with the latter.

How can Code X be inputted into itself if it requires an input (remember that the above analysis tells us that Code X only works for code that's not input dependent)?

And even if you can reason past that, what if Code X requires that the code it's testing needs to be run a (finite) number of times before making its verdict as to whether it halts or not?

# Answer
> 0 votes
The proof for the halting problem is as follows:

Let us assume towards contradiction that such 'Code X' exists, we will call it $H$. Notice that $H$ is a program, and we can write down its code. Basically, its just a piece of text - unless we give it meaning.

We want to show that we cant give it meaning, in some meaningful way. Since we assumed that it is the code that solves the halting problem, the "correct" meaning for $H$ is to accept when it receives text that corresponds to some code and an input to that code, and it would halt.

Now, we want to look at another program, $A$ that accepts one input (and not two like $H$ did) and has the following code:

1. get stuck into an infinite loop if $H(X, X)=true$
2. else, halt

where $X$ is the said input. Consider $A(text(A))$: We run $A$ on its own code!

If $A$ would halt with this input $X=text(A)$, then we know that $H(text(A),text(A))=false$, but from the definition of $H$ it would mean that $A$ would not halt on $text(A)$! A contradiction. A similar argument can be shown if $H(text(A), text(A))=true$, and from this we know that such program $A$ cannot exist, and therefore also $H$ cannot exist.

---
Tags: halting-problem
---


# Question
Title: Way to solve 5-dimentional Linear assignment problem
I faced a problem that looks very hard, the problem is this:

> We have 5 people putting dots on a whiteboard, each person uses colored dots with a different color (there are 5 colors, 1 for each person). My job is to find a cluster of points which contains 3 or more distinct colors. Also, we have some fixed radius $R$, and the distance for each point in a given cluster shouldn't be more than R. Also, there might be points that don't belong to any cluster.

What kind of approach can you suggest? At first, I tried the Multidimensional linear assignment problem, but it seems that this problem is NP-hard, so I want to solve it in a reasonable amount of time (I write code). What kind of solutions can you suggest? Maybe using the fact that this isn't a general problem, I mean we use 2D space where people take action, also there are only 5 people.

# Answer
If you had as much people as number of people in your clusters (each people must have a dot in each cluster) then maybe you could hope for some divide-and-conquer strategy with polynomial runtime, because of greedy-like regularities. For example, in 1D and with 3 people only, after sorting the points along the axis a greedy sweeping algorithm yields an optimal solution ; with some tweaks maybe this kind of ideas could work in higher dimensions. But with some people who can not be part of a specific cluster, this doesn't seem to work anymore.

If I were you, I'd look for approximation algorithms (good ones are known for the 3d matching). Maybe some of them can yield good approximation factors with your problem's structure.
> 1 votes

---
Tags: algorithms
---


# Question
Title: How to find an array of probabilities that give equal products
I'm trying to figure out if there is an algorithm which can solve the following:

Given an array of randomly generated values, for example: $$\[54.6, 1.96, 5.0, 31.31\]$$

Find an array of equal length, in this example $\[x\_1, x\_2, x\_3, x\_4\]$ such that:

$$54.6 \cdot x\_1=1.96\cdot x\_2=5.0\cdot x\_3= 31.31\cdot x\_4$$

and

$$x\_1 + x\_2 + x\_3 + x\_4 = 1.0$$

Any suggestions for an algorithm to solve this?

# Answer
Let the array be $a\_1,\ldots,a\_n$, which we assume are positive. The condition $a\_i x\_i = a\_j x\_j$ implies that $$ x\_i = \frac{a\_n}{a\_i} x\_n. $$ Since the $x\_i$ must sum to $1$, $$ 1 = \sum\_{i=1}^n \frac{a\_n}{a\_i} x\_n \Longrightarrow x\_n = \frac{\frac{1}{a\_n}}{\sum\_{i=1}^n \frac{1}{a\_i}}. $$ The formula for $x\_i$ shows that $$ x\_j = \frac{\frac{1}{a\_j}}{\sum\_{i=i}^n \frac{1}{a\_i}}. $$
> 4 votes

# Answer
If you consider an array $\[a\_1, …, a\_n\]$, then an easy way to choose the array $\[x\_1, …, x\_n\]$ is to define $x\_i = \frac{1}{a\_i}$. That way, $\forall i, a\_i\times x\_i = 1$. The problem is that $\sum x\_i$ is not necessarily equal to $1$, but is instead equal to $S = \sum \frac{1}{a\_i}$.

If you now consider $x\_i' = \frac{1}{S\times a\_i}$, then we still have $\forall (i, j), a\_i x\_i' = a\_j x\_j'$, but we also have $\sum x\_i' = \frac{1}{S}\sum \frac{1}{a\_i} = 1$.

Since $S$ is easy to compute, you have what you wanted.

I supposed here that all $a\_i \> 0$.
> 2 votes

---
Tags: algorithms
---


title: Is DISCRETE LOG a NP hard problem?

text:
# Question
Title: Is DISCRETE LOG a NP hard problem?
In cryptography there are two problems which are part of the foundation of modern public key cryptography. Both of them can be solved in polynomial time on quantum computers. I am talking about:

* **FACT**

**Given:** A composite number, i.e. a positiv integer which is the product of some prime numbers: $x = p\_1 \cdot p\_2 \cdot \ldots \cdot p\_n$ You know only $x$.

**Wanted (calculation problem):** At least one factor of this composite number.

**As a decision problem:** For a given $k \le x$: Is there a factor $p\_i \le k$?

*(You just need to solve the decision problem $\log x$ times to solve the calculation problem. So, as long as the complexity of the decision problem is polynomial or harder, both flavors of the problem belong to the same time-class.)*
* **DISCRETE LOG**

**Given:** $x = a^n \mod p$. There $p$ is prime and you know $x$, $a$ and $p$.

**Wanted (calculation problem):** Find $n$.

**As a decision problem:** Is there some $n \le k$ such that $x=a^n \mod p$?

*(Also here you need to solve the decision problem only $\log p$ times to solve the calculation problem.)*

I know, that both problems, as far as we know, are not in the complexity class **P**, i.e. for both problems there is no algorithm know that could solve them in polynomial time on a deterministic Turing Machine.

I know, that both problems can be solved in polynomial time on a non-deterministic Turing machine, which, per definition means, that both of them are in the class **NP**.

Let's suppose, that **P** $\ne$ **NP**. Under this assumption **NP** is partitioned into three sub-classes:

* **P**
All problems which are solvable in polynomial time on a deterministic Turing Machine
* **NPC**
NP-complete.
The subset of **NP** to which all problems in **NP** can be reduced, i.e. the subset of **NP** that is NP-hard.
* **NPI**
NP-intermediate
All problems which are in **NP** but neither in **P** nor in **NPC**.

It is known, that **NPI** is not empty if **P** $\ne$ **NP** (Ladner's theorem). (If **N** $=$ **NP**, then also **NPC** $=$ **P**, which means, that **NPI** must be empty.)

I know, that under the assumption that **P** $\ne$ **NP**, FACT seems to be in **NPI**, since until now nobody could prove that FACT $\in$ **NPC**.

But I could not find similar statements about DISCRETE LOG.

Here are my questions:

* Is DISCRETE LOG know to be in **NPC**? Or is it thought to be in **NPI**?
* If it is in **NPI**:
    + Is there a know algorithm to reduce FACT to DISCRETE LOG?
    + Or is there an algorithm to reduce DISCRETE LOG to FACT?
    + Are they maybe even equivalent, i.e. reduzibel in both directions?

# Answer
No one knows, but:

* It is suspected that neither factoring nor discrete logarithm are NP-complete, but we have no proof. (Evidence for the suspicion: they are in NP $\cap$ coNP. See, e.g., https://cstheory.stackexchange.com/q/159/5038, https://cstheory.stackexchange.com/q/167/5038 for factoring. It's similarly easy to prove that discrete log is in NP $\cap$ coNP; see, e.g., How hard is finding the discrete logarithm?. Moreover, if any problem in NP $\cap$ coNP is NP-complete, it follows that NP = coNP. This would be an unexpected result.)
* It is suspected that there is no polynomial-time algorithm for factoring or discrete logarithm, but we have no proof. (Evidence for the suspicion: we haven't been able to find a polynomial-time algorithm for either, despite a lot of trying.)
* There is no known (classical) reduction between discrete log and factoring. However, I personally wouldn't be shocked if one were found, or if both were found to be instances of some broader problem, or something. For instance, when we find an algorithm technique that works against one, historically often we've been able to adapt it to the other as well. So, they seem to be connected or related in some deep way.
> 8 votes

# Answer
In regards to the relationship between discrete logarithm and factoring, it seems worth mentioning that both problems are special cases of the Hidden Subgroup Problem. Shor's Algorithm, under the covers, is really solving this problem. Here are some references: factorization, discrete log.

The last link also mentions how integer factorization can *tecnically* be reduced to discrete log, though it isn't quite the same situation as standard cryptographic uses of the discrete log (factoring N is the same taking the discrete log modulo N, while cryptographic uses take the discrete log modulo a prime).
> 4 votes

---
Tags: complexity-classes
---


# Question
Title: Oracle that can only definitively say if an instance is unsatisfiable
Assuming I have an Oracle that takes as input a strictly 3SAT Boolean instance and states whether the instance is satisfiable or not. If it says instance is unsatisfiable then the instance is unsatisfiable. If it says instance is satisfiable there is a 57% chance the instance is satisfiable and a 43% chance that is unsatisfiable. The percentages are just an example, essentially oracle is reliable only one way.

Can I use such an Oracle to solve 3SAT instances? If so, how?

# Answer
> 1 votes
**You can use your oracle to construct a process that is guaranteed to be correct, and will most likely be fast.**

The basic idea is that a proof that a formula is unsatisfiable might be huge - but if that's the answer we get, we can trust it. On the other hand, we can easily convince ourselves that the formula is satisfiable by inspecting a satisfying assignment.

As pointed out by Nathaniel, we can get our correctness chances arbitrarily close to 1 by just making a constant number of oracle calls, and answering "satisfiable" only iff all of them say so.

Now the procedure is as follows:

1. Ask the oracle if the formula is satisfiable. If "no", we are done.
2. Substitute $x\_0 = \top$ and $x\_0 = \bot$, and ask for both resulting formulae whether they are satisfiable. If both answers are "no", the originl formula is not satisfiable. If exactly one says "yes", proceed with that formula. If both say "yes", proceed with $x\_0 = \bot$ and keep $x\_0 = \top$ for backtracking.
3. Once values for $x\_i$ for $i \< j$ have been chosen, try $x\_k = \bot$ and $x\_j = \top$. If both substitutions yield "no", go back to back to the last backtracking point. If one says "yes", proceed with that one. If both say "yes", create a backtracking point.
4. Once all variables are instantiated, check whether you have a satisfying assignment. If so, the original formula is satisfiable. If not, backtrack.
5. If you are supposed to backtrack, but there is no backtracking point, the original formula is not satisfiable.

The procedure will never give us a wrong answer. Its worst-case runtime is exponential, but every time we backtrack this is due to our oracle incorrectly answering "satisfiable", which is very unlikely. Using Wolfram Alpha for the calculation, I get that the expected number of backtracks is below 1.4 for a oracle correctness probability of 0.9. It follows that the expected runtime of the procedure is linear.

# Answer
> 1 votes
Edit: I wrongly read the question, therefore the following answer is incorrect. It would be correct if the oracle worked as followed: "if the instance is unsatisfiable, then the oracle always says it is unsatisfiable otherwise, there is a 57% chance the answer is that the instance is satisfiable, and a 43% chance that it is not".

The key here is to repeat the process of asking your oracle to improve the probability of getting the right answer. You know that the way it is constructed, if the oracle states that a formula is satisfiable, then IT IS satisfiable (since it never makes mistakes on non-satisfiable formulas).

For example, with your percentages, if you ask 6 times your oracle if a formula $\varphi$ is satisfiable, it will always give the right answer if $\varphi$ is not satisfiable, and there will be over 99% chance to say that $\varphi$ is satisfiable if $\varphi$ is satisfiable, because it has $0.43^6 \< 1\\%$ chances to say that $\varphi$ is not satisfiable even if it is.

You will never be able to guarantee 100% in both cases, but you can be as close as you want by repeating the question to the oracle.

---
Tags: logic, satisfiability, 3-sat, oracles
---


title: Perfect matching problem

text:
# Question
Title: Perfect matching problem
Suppose you are given two sets of integers L and M both having N elements. The problem is to match each number in L to a number in M. Such perfect matching has some cost given by $\sum\_{i=1}^{N} l\_i\*m\_i$.

I want to find some perfect matching with some given cost. I suspect that this is hard (i.e. NP-complete). Can you solve it quickly? (find an efficient algorithm).

Here is an example: we have three courses, credit hours are 4, 5, 8. Grade points are 4, 3, 2. A solution is a perfect matching between the lists that result in some given GPA.

For this to be computationally meaningful, the largest grade point and largest credit hour are unbounded.

P.S. Yuval hinted the reduction from Subset sum problem. I am interested in hardness proof of strong NP-completeness.

# Answer
This problem is indeed $NP-complete$ as you have suspected. To see this, we will show a reduction from $SubsetSum$.

## The reduction

Let $A,s$ be an instance of $SubsetSum$, where $|A|=n$. We will define $L$ as all the numbers in $A$, in addition to another $n$ zeros. For example, if $A= 4, 5, 8$ then $L=4,5,8,0,0,0$.

Now, we define $M$ to be with $2n$ values, such that we have $n$ ones and $n$ zeros.

The target value will be $s$

## Proof

Such a perfect matching defines us a subset $A'\in A$, that $a\in A'$ iff $1$ is matched with $a$. Since we have $n$ values in $A$, and we have $n$ ones and $n$ zeros in $M$, then each pair of $(0,1)$ in $M$ can be assigned to every pair $(a, 0)$ where $a\in A$, and thus any $a\in A$ can be matched with either $0$ or $1$, contributing to the total sum either $a$ or $0$. Therefore, there is a perfect match if and only if there is a subset with that sum (as the value of the matching is a sum of the subset $A'$).
> 2 votes

---
Tags: algorithms, complexity-theory, time-complexity
---


# Question
Title: If a language consists of an NP and coNP question, do we have to place it in P^NP^NP?
If $x \in L$ only if $x \in A$ and $x \in B$, where A is an NP problem and B is a coNP problem, I cannot place $L \in NP$ or $L \in coNP$ without implying that NP = coNP right?

# Answer
> 2 votes
No, because $A$ isn't necessarily $NP$-complete and $B$ isn't necessarily $coNP$-complete. You'd need both to be true to force the implication $NP = coNP$ by $X$ being a member of both problem classes. In fact $A$ and $B$ could both be in $NP$ **and** $coNP$. E.g. $A$ and $B$ could both be in $P$. $NP \cap coNP$ is not the empty set.

---
Tags: complexity-theory, polynomial-time-reductions
---


# Question
Title: Polynomial kernelization for Set Splitting
In a set system $(U, F)$, $F\subseteq \mathcal{P}(U))$, we say that a function $f: U \to \\{0, 1\\}$ is a *coloring* of $(U, F)$. A set in $F$ is *split* by $f$ if $F$ receives both colors.

The **Set Splitting** problem is defined as follows:

> Given an set system $(U, F)$ and an integer $k \in \mathbb{N}$, does there exists a coloring of $(U,F)$ that splits at least $k$ sets from $F$?

I wish to show that there exists kernel with $2k$ sets and $|U|\in O(k^2)$. So far I have these reduction rules:

**Rule 1:** If there is $x\in U$ s.t. there's no $W\in F$ s.t. $x\in W$, then we can delete $x$ from U and work with a new instance. $(F,U\setminus\\{x\\},k)$.

**Rule 2:** If $W\in F$ is a singleton, then we can remove it and work with $(F\setminus \\{W\\},U,K)$ because such $W$ will never contain two elements of different colors.

**Rule 3:** If $V\in F$ is s.t. $|V|\geq 2$ and $V\cap W$ is empty for each other $W\in F$, then we can color elements in $V$ somehow to satisfy the distinctness and we can lower $k$ by one.

**Rule 4:** From instance $(F,U,k)$ create instance $(F,U\cap \bigcup F,k)$, i.e. we are interested in coloring only the elements that are actually in some set $W\in F$.

Not really sure how to proceed from here. Any hints appreciated.

# Answer
I understood the question as "select a subset of size $2k$ from $F$ such that (there exists coloring for $F$ $\iff$ there exists coloring for the subset)".

As you've said, you can remove all singleton and empty sets. The remaining sets have at least $2$ elements. You can show that *any* $2k$ such sets suffice.

Select $2k$ arbitrary sets with at least two elements. We assume that they have exactly $2$ elements (it's the worst case; the analysis is easy to modify for more than $2$ elements). We use the probabilistic method. For each element, we select the color randomly, and we compute the expected number of sets that have both colors. We show that the expected number of sets with both colors is $k$. Note that this is an expectation over all random colorings. Therefore, there must exist a coloring that gives the value greater or equal to the expectation, i.e. $\ge k$, as required.

Let $\\{S\_i\\}\_{i=1}^{2k}$ be the selected sets. For each set $S\_i$ we introduce indicator variable $I\_i$, which equals $1$ when the set $S\_i$ has both colors, and $0$ otherwise. The expectation above equals $\mathbb E\[\sum\_{i=1}^{2k} I\_i\] = \sum\_{i=1}^{2k} \mathbb E\[I\_i\]$. For set $S\_i = \\{x\_1, x\_2\\}$, with probability $\frac 12$, $x\_1$ and $x\_2$ have different colors. Therefore, $\mathbb E\[I\_i\] = \frac 12$, and the required expectation is $2k \cdot \frac 12 = k$.
> 1 votes

---
Tags: complexity-theory, colorings, parameterized-complexity
---


# Question
Title: Encoding the theorem on friends and strangers in predicate logic
> In every group chat of six (distinct) people on Instagram, there is a group of three (distinct) people such that either:
>
> * everyone in the group are friends
> * everyone in the group are strangers (i.e not friends).
>
> 1. Let $F(x,y)$ be a relation that denotes that $x$ and $y$ are friends on Instagram. Translate the statement into predicate logic.

So I believe this is using the pigeonhole principle.

> 2. Would the statement still be true if Instagram had only 3 users?

I have no idea where to start with the predicate logic.

# Answer
The first part doesn't ask you to *prove* anything. It just asks you to encode the theorem on friends and strangers in predicate logic. Let's build this statement step by step. First, we want to go over all sets of six people: $$ \forall x\_1 \cdots \forall x\_6 $$ We are only interested in the case in which they are all distinct: $$ \bigwedge\_{1 \leq i \< j \leq 6} (x\_i \neq x\_j) \Rightarrow $$ There must be a set of three people which are either all friends or all strangers: $$ \bigvee\_{1 \leq i \< j \< k \leq 6} (F(x\_i,x\_j) \land F(x\_j,x\_k) \land F(x\_k,x\_i)) \lor (\lnot F(x\_i,x\_j) \land \lnot F(x\_j,x\_k) \land \lnot F(x\_k,x\_i)) $$ The second part asks whether the statement remains true if there are only three users. The statement is vacuously true, because then it is impossible to choose a set of six distinct users.
> 1 votes

# Answer
Implication predicates A (x) and B (x)

A(x) ⇒ B(x)

is the union of the set T2 - the truth of the predicate B (x) and the complement to the set T1 of the truth of the predicate A (x).
> 0 votes

---
Tags: logic, predicate-logic
---


# Question
Title: Turing machine to compute $⌈\log_2n⌉$ with 1 tape and unary input/output
I'm trying to figure out how to make the action table for a Turing Machine computing $⌈\log\_{2}(n)⌉$. The input and output shall be unary (meaning $3$ should represent $111$). I can only deal with 1 tape.

Also, I would prefer having 7 transition states, 1 final state, 24 actions and 5 symbols, but any other numbers are fine too. At the end of the computation, the TM head should be at the 1st $1$ from the left, of the output.

For $⌈\log\_{2}(0)⌉$, I would like to have the symbol $N$ on the tape.

I would also like an easy-to-understand explanation, if possible.

# Answer
> 0 votes
One simple approach is *repeated halving*.

Remove a single 1 from the input (if you fail, output N). Then go over the tape in passes. Each pass deletes every other 1 encountered (starting with the first). The number of passes required to delete all 1s is $\lceil \log\_2 n \rceil$. You can count the number of passes as you go.

For example, suppose that $n=6$:

```
111111       Delete the first 1
b11111       Delete every other 1
2b1b1b       Delete every other 1
22bb1b       Delete every other 1
222bbb       Convert back to 1
111bbb       Done

```

The number of passes is $3 = \lceil \log\_2 n \rceil$.

---
Tags: turing-machines
---


# Question
Title: help understanding the recurrence relation of an algorithm
I have the following code which I have to figure out the recurrence relation, but I am having a bit of a trouble understanding what the algorithm does exactly.

```
Interesting-Product(A[1..n])

if n = 1 then return

for i := 1 to n/3   do
    A[i] = A[i]*A[i+(n/3)]

Interesting-Product(A[1..n/3])

 for j := (n/3) + 1 to   2n/3   do
      A[j] = A[j]*A[j+(n/3)]

 Interesting-Product(A[1..n/3])

```

I'm taking an algorithms class and having trouble understanding the code.

# Answer
> 1 votes
Let's try to parse this procedure, which we denote by $P$ for short.

The input to $P$ is an array $A$ of length $n$.

If $n = 1$, then we immediately quit.

Otherwise, we perform $n/3$ multiplications, call $P$ on an array of length $n/3$, perform $n/3$ more multiplications, then call $P$ on the same array of length $n/3$ again.

The procedure isn't doing anything interesting – the exercise is only asking you to express the running time of $P$ as a recurrence relation. We think of the running time of $P$ as a function $T(n)$, where $n$ is the length of the input to $P$. The recurrence relation should just follow the description above, using big O whenever appropriate (this should have been explained in class).

If you're not sure how to work out the recurrence relation, I suggest you review the class material. It would be counterproductive to solve this elementary exercise for you – the goal of such questions is for you to get a handle on the basics, and the only way to accomplish that is for you to actually solve the question on your own.

---
Tags: recurrence-relation, java
---


title: Is $\log(n-1) \in \Omega(\log(n))$?

text:
# Question
Title: Is $\log(n-1) \in \Omega(\log(n))$?
I saw this question Can I simplify log(n+1) before showing that it is in O(log n)? and wanted to know if a similar situation was also true.

Namely, is $\log(n-1) \in \Omega(\log(n))$?

# Answer
> 2 votes
As you have seen, $\log(n+1) \in \mathcal{O}(\log n)$. That means that $\log n \in \Omega(\log( n + 1))$. Now you can change $n$ with $n-1$ and have your answer.

To be more precise, $\log(\alpha n^{\beta} + \gamma) \in \Theta(\log n)$ for any $\alpha, \beta, \gamma \in \mathbb{R}\_{\>0}$.

# Answer
> 2 votes
Having $n-1 \gt \sqrt{n}$, when $n \gt 3$ we can write $$\log (n-1) \gt \log \sqrt{n} = \frac{1}{2}\log n$$ So, taking $N=3$ and $C=\frac{1}{2}\gt 0$ we fulfilled definition for $\Omega$.

---
Tags: time-complexity, big-o-notation
---


# Question
Title: Can inputs in the decision tree model be computed?
The Wikipedia definition of the decision tree model says that it allows the sign functions of certain classes to be computed in constant time (and presumably also memory). My questions, still unresolved by reading the article, are:

1. Can those functions be fed any values computed by the algorithm (including ones of asymptotically larger magnitudes) or just ones from the input array?
2. Do the coefficients in the linear decision trees have to be hard-coded? The article seems to indicate that there are as many of them as elements in the input (and even more, exponential in the maximum allowed degree $d$, for algebraic decision trees), which means they cannot be hard-coded. Or is the $n$ in this fragment different and actually only sums of some fixed number of terms, independent of the input length, are allowed?
3. Regarding point 1, does it make a difference, i.e. can some problems be solved asymptotically faster (or in less memory) when comparisons of differences (or linear combinations, or polynomial functions) of any intermediate computed numbers are allowed? If yes, does the answer change if the numbers fed to the functions can only be $$ of those in the input array?

# Answer
> 2 votes
A decision tree is a special kind of "program" which computes a function, usual from $\\{0,1\\}^n$ to $\\{0,1\\}$. Let's take an example from Wikipedia:

A decision tree is a binary tree. Internal nodes are labeled by functions from a set $\mathcal{F}$ (more on this, later). Leaves are labeled by elements from $\\{0,1\\}$. Each internal node has one child labeled $0$ (the left child in the diagram) and another child labeled $1$ (the right child in the diagram). The binary tree doesn't have to be complete as in the example above.

In order to evaluate the decision tree, you start from the root, evaluate the function written there, and descend to the left child or to the right child accordingly. You continue in this fashion until reaching a leaf, at which point you output the label written there.

The *cost* of a decision tree is its depth, or equivalently, the maximum number of edges in a root-to-leaf path.

The most common choice for the set $\mathcal{F}$ of allowed queries is $\\{x\_1,\ldots,x\_n\\}$. Linear decision trees are decision trees in which $\mathcal{F}$ consists of all linear threshold functions. Alegbraic decision trees of degree $d$ are decision trees in which $\mathcal{F}$ consists of all polynomial threshold functions of degree $d$.

Comparison-based algorithms can also be modeled by decision trees. Here the input is an array of length $n$, the output is a permutation of the positions of the array, and the allowed queries are comparisons.

Decision trees capture some properties of algorithms, and ignore other properties. They are most often used to prove lower bounds on algorithms solving a certain problem. For example, we can represent every comparison-based sorting algorithm as a decision tree. This representation completely ignores how difficult it is to decide what comparison to do next, and how difficult it is to generate the output given the results of past comparisons. Yet the model is useful, since it shows that every comparison-based sorting algorithm must make $\Omega(n\log n)$ comparisons in the worst case, and in particular, must have running time $\Omega(n\log n)$.

Kane, Lovett and Moran constructed linear decision trees of depth $\tilde{O}(n)$ solving the 3SUM problem. In contrast, the 3SUM conjecture states that no RAM-based algorithm for 3SUM runs in time substantially better than $O(n^2)$. This is one case in which the decision tree model isn't able to capture the hardness of a problem.

The main point here is that proving lower bounds on computation time is hard. The only lower bounds we know how to prove are in restricted models, or on a specific type of resource, such as queries in the decision tree model, or communication in the communication complexity model. These models abstract away computation but capture some pertinent properties which suffice for proving meaningful lower bounds in many cases.

We can now answer your questions one by one:

1. The decision tree model is really a family of models, parametrized by the set $\mathcal{F}$ of allowed queries. As a user of the decision tree model, you get to decide which queries you allow.
2. The decision tree model is a non-uniform model. You can use whatever functions from $\mathcal{F}$ that you wish. Unless stated specifically, there is no requirement that there be an efficient procedure that constructs the decision tree for inputs of given length.
3. The most common measure of complexity for decision trees is depth. Another measure of complexity sometimes used is size; in this case, we sometimes allow DAGs (known in this context as branching programs) rather than just (directed) trees. Enlarging the set $\mathcal{F}$ of allowed functions can reduce the complexity.

For the specific case of linear decision trees, it is known that arbitrary weights can be reduced to polynomial weights at the cost of increasing the depth by at most 1, see Goldmann and Karpinski, Simulating threshold circuits by majority circuits. (The models are not the same, but it seems likely that the conclusion still holds.)

Another example where comparing more complicated linear functions can make a large difference is 3SUM. The decision trees constructed by Kane, Lovett and Moran have sparsity 6, while an earlier lower bound of Ailon and Chazelle (cited in \[KLM\]) shows that sparsity 5 cannot achieve depth $\tilde{O}(n)$.

---
Tags: complexity-theory, time-complexity, decision-tree, definitions
---


# Question
Title: In a DBMS what are the implementation details that make set operations faster than cursors?
What are the low level implementation details that make set based operations exponentially faster than iterative processes, like cursors?

At a memory level how does a set operation "touch" the data less than a cursor?

# Answer
Set-based operations *are* iterative at a "low level", and are *not necessarily* any faster to execute than cursors under all circumstances.

The main advantage with set-based operations is that they are well-defined operators which can be analysed algebraically, and the order of operations thus rearranged or simplified by the database engine, or the exact algorithmic implementation altered - not just at the time of writing the query, but possibly later at the time of subsequent executions of the query.

What is "simple" or "fast" here is constantly re-determined by the database engine at runtime based on the statistics it collects about actual whole database performance.

By contrast, there is much less flexibility for the database engine in the case of cursors, and if every action in a database were written as a cursor then overall performance could become abysmal (or the system more recalcitrant to any changes) far sooner than when set-based operations are used which provide the database engine a large latitude for optimisation.

The most straightforward analogy is the performance of a modern optimising compiler for a high-level language, versus writing everything in assembly language, although this does not quite capture the *ongoing* monitoring that a database engine performs.
> 4 votes

# Answer
When operations are made on sets, this is what DBMS engine is optimized to do, all fancy stuff like collecting minimal intersection from queries, order execution, batch reads and possible concurrency kicks in.

Per row query could be executed by multiple threads, splitting work among them, when you create cursor processing must be sequential. By the nature of temporarily created set, it differs from internal structure by allowing iterator-like traversal, so it is effectively new table populated with result. When query is executed all updates are issued, so even not altered data (in the cursor) is updated back, this creates more work - the price for easier result traversal.

No possibility for parallel execution is constant slowdown, creating temporary memory is operation with huge constant, updating results is wasteful, but this creates another passes through data, so slowdown is polynomial with one-thread processing and additional memory management.
> 1 votes

---
Tags: databases, memory-access
---


title: Maximal expansion of a convex polygon

text:
# Question
Title: Maximal expansion of a convex polygon
There is a convex polygon $X$ contained in another polygon $Z$ (which can be non-convex and even have holes). I would like to expand $X$ to a larger convex polygon $Y$ such that:

* $X\subseteq Y\subseteq Z$
* $Y$ is *maximal*, i.e, there is no other convex polygon $Y'$ such that $Y\subsetneq Y' \subseteq Z$

NOTE: $Y$ does not have to have maximum area; it only has to be maximal.

What is an algorithm for finding such $Y$?

# Answer
> 1 votes
**Algorithm**. We maintain a set $S$, which is initially a set of vertices of $X$. Let $CH(S)$ be the convex hull of $S$. We want to find $S$ such that $CH(S) \subset Z$ is a maximal polygon.

We first define operation $extend(s,t)$ which

1. Finds a point $x$ on the ray starting from $s$ and going through $t$ such that $CH(S \cup \\{x\\}) \subset Z$ and $x$ is the farthest from $s$ (i.e. it's the most we can extend the polygon in direction $s \to t$).
2. Add $x$ to $S$.

$extend$ is the only operation we'll use. Therefore, $CH(S) \subset Z$ by construction. We only need to select a sequence of extensions so that $CH(S)$ is maximal.

The algorithm consists of $2$ phases:

1. Let $c$ be any point strictly inside the $X$. For each vertex $v$ of $Z$ (including inner vertices), perform $extend(c, v)$
2. For all edges $(u,v)$ of $CH(S)$, while possible, perform $extend(u,v)$ and $extend(v,u)$.

The following example demonstrates the algorithm (I omit steps which don't modify $S$, but we should try all vertices of $Z$ (including holes' vertices) and all edges of $CH(S)$):

**Proof of maximality**.

Let $x \in Z$ be a point such that $x \in Z \setminus CH(S)$ and $CH(S \cup \\{x\\}) \subset Z$. Let $u \in S$ be a vertex s.t. $(u,x)$ is an edge in $CH(S \cup \\{x\\})$. We can assume that $x$ is arbitrarily close to $u$. It's clear that when $x$ is sufficiently close to $u$, one of two neighbors of $u$ in $CH(S)$ becomes a neighbor of $x$ in $CH(S \cup \\{x\\})$. We call this neighbor $v$. Let $u'$ be another neighbor of $u$, and $v'$ be another neighbor of $v$.

Since we can't extend $(v', v)$ and $(u',u)$, there must exist a vertex $y$ of polygon $Z$ lying strictly between lines $(v', v)$ and $(u',u)$ (it's cumbersome to explain, but it's kind of obvious). Then line $(c,y)$ either intersects $(u,x)$ or $(v,x)$. Let $z$ be the intersection point. Then this point 1) lies outside of $CH(S)$, 2) lies in $CH(S \cup \\{x\\})$ and 3) lies on line $(c,y)$. This means that during phase $1$ we didn't fully extend to $y$, contradiction.

**Complexity**. We first need to estimate the complexity of $extend$. One can do this with a binary search: for a candidate, build a convex hull and check if it lies inside of $Z$. The convex hull can be built in $O(n)$ (since we only need to add one point) and an intersection with $Z$ can be checked in $O(n)$, so the total time is $O(n \log (precision))$. I suspect that it's possible to get rid of binary search and get $O(n)$ or $O(n \log n)$ time.

Now, we need to estimate the number of calls of $extend$. There are $O(n)$ calls of $extend$ in the first phase. In the second phase, each time we successfully perform $extend$ (i.e. the area of $CH(S)$ increases), one of two things happen:

1. A vertex of $CH(S)$ which was not on the boundary of $Z$, now lies on the boundary of $Z$.
2. A vertex of $Z$ which was not on the boundary of $CH(S)$, now lies on the boundary of $Z$.

Since there are $O(n)$ vertices of $Z$ and $CH(S)$ (it can't have more vertices than $Z$), we call $extend$ at most $O(n)$ times.

Therefore, the total running time is $O(n^2 \log (precision))$

---
Tags: computational-geometry
---


# Question
Title: Proving using a SAT solver that KB entails D
Suppose you're given this KB:

$$KB = (A, A ⇒ B, A ⇒ C, B ∧ C ⇒ D)$$

How would you show using a SAT solver that $KB \vDash D$?

# Answer
> 3 votes
TL;DR: Use the SAT solver to search for a counterexample.

To check that $KB \models \varphi$, you need to know whether there is any assignment that is consistent with $KB$ but that does not satisfy $\varphi$. In other words, you need to know whether $KB \land \neg \varphi$ is satisfiable or not. If $KB \land \neg \varphi$ is satisfiable, then you have found a counterexample that demonstrates that $KB \not\models \varphi$. If $KB \land \neg \varphi$ is not satisfiable, then you proven that $KB \models \varphi$ is true.

Now apply that to your specific example.

---
Tags: logic, proof-techniques, sat-solvers
---


# Question
Title: How to simulate two counters using one (FIFO) queue?
How to simulate two counters using one (FIFO) queue? (In terms of algorithms, unary stack.)

# Answer
Queue automata are Turing-complete, so they can simulate any machine, including a two-counter machine.
> 1 votes

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


# Question
Title: Can you add up all the nodes of a special binary tree in polynomial time, in respect to the number of levels?
Let's say you have a binary tree defined by a group $S=\\{a:\[5,6\],b:\[7,67\],c:\[45,12\],...\\}$ (this group is just an example). The binary tree is constructed so that there are two starting parent nodes, $a\[0\]$ and $a\[1\]$. Each of those nodes have two child nodes $b\[0\]$ and $b\[1\]$. Each of those nodes ($b\[0\]$ and $b\[1\]$ from both $a\[0\]$ and $a\[1\]$) have two child nodes, $c\[0\]$ and $c\[1\]$, and so on and so on. To evaluate such a tree, you start at the bottom of the tree, add up the two leaf nodes in each of the last parent nodes, and multiply that by its parent node. This is now the new value of the parent nodes. This process is repeated upwards until you do $a\[0\](b\[0\]+b\[1\])+a\[1\](b\[0\]+b\[1\])$ (remember that $b\[0\]$ and $b\[1\]$ are no longer $7$ and $67$, respectively at this point). Can you do this evaluation in polynomial time, in respect to the number of levels of the tree?

Follow up: Can it still be done in polynomial time if some of the leaf nodes are missing?

EDIT: Here is a picture with what I mean:

# Answer
> 1 votes
No. A complete binary tree has $\ell$ levels and about $2^\ell$ nodes. Any algorithm must examine all nodes to get the correct answer, so the running time has to be exponential in the number of levels.

(A small note of caution: "polynomial time" typically means polynomial in the size of the input, so it could risk some confusion to talk about it as "polynomial time" when you mean a polynomial in the number of levels.)

---
Tags: asymptotics, binary-trees
---


# Question
Title: Compilers: how to find first and follow sets?
I sort of know how to solve the problem but I am not sure how to do it in a systematic way. Could someone provide a step-by-step solution especially for the follow set one? Thanks!

# Answer
> 1 votes
To find the follow of S, I feel that it would be helpful to calculate all the firsts of all the variables as it helps a lot. First, let us see all the rules to find the first as they will be helpful.

```
1. For terminal a, First(a) = {a}.
2. For production A -> a, add 'a' to First(A).
3. For production A -> , add '' to First(A).
4. For production A -> BCD, add First(B) to First(A).
5. For production A -> BCD and  ∊ First(B), add First(CD) to First(A).

```

It would be easier for me to explain if we number all the productions, so we number the productions as follows:

```
1. S -> A(S)B
2. S ->
3. A -> S
4. A -> SB
5. A -> x
6. A ->
7. B -> SB
8. B -> y

```

Now as it is a recursive function, it would be better if we go in cycles to find the answer until we find a cycle in which the answer hasn't changed.

Firstly, find first using all the productions which start with a terminal, i.e. productions 2, 5, 6, 8.

Round 1

```
First(S) : {}, First(A) : {x, }, First(B) : {y}

```

From production 1, First(A) ∊ First(S), therefore add it. Also, as ∊ First(A), add ( to First(S).

From production 3, First(S) ∊ First(A), therefore add it. Also from production 4, as ∊ First(S), add First(B) to First(A).

From production 7, First(S) ∊ First(B), therefore add it.

Round 2

```
First(S) : {, x, (}, First(A) : {x, , (, y}, First(B) : {y, x, , (}

```

Add all the steps performed in round 2, again in round 3.

Round 3

```
First(S) : {, x, (, y}, First(A) : {x, , (, y}, First(B) : {y, x, , (}

```

This is the final outcome. After this, if you perform the steps again, you will get the same values of First.

Now we will find follow. First, let us understand the rules of follow as it will be helpful.

```
1. For start symbol S, add $ to follow(S).
2. For production A -> BC, add follow(A) to follow(C).
3. For production A -> Bb, add b to follow(B).
4. For production A -> BCD, add first(CD) to follow(B).

```

Also, we don't add in the follow.

As S is the start symbol, add $ to Follow(S)(rule 1).

To find other elements of Follow(S), find all the productions where S is in RHS. Here they are 1, 3, 4, 7.

From production 1, add ) to Follow(S)(rule 3), add ( to Follow(A)(rule 3), add follow(S) to follow (B)(rule 2).

```
Follow(S) = {$, )}, Follow(A): {(}, Follow(B): {$, )}

```

From production 3, add Follow(A) to Follow(S)(rule 2).

```
Follow(S) = {$, ), (}, Follow(A): {(}, Follow(B): {$, )}

```

From production 4, add Follow(A) to Follow(B)(rule 2) and add First(B) to Follow(S)(Rule 4)

```
Follow(S) = {$, ), (, x, y}, Follow(A): {(}, Follow(B): {$, ), (}

```

From production 1 again, add Follow(S) to Follow(B)(rule 2)

```
Follow(S) = {$, ), (, x, y}, Follow(A): {(}, Follow(B): {$, ), (, x, y}

```

Now we have found first and follow of all the variables. The actual solution might not be this big. I have tried to explain everything so it's a bit bigger. Hope you liked and understood the solution.

---
Tags: compilers, parsers
---


# Question
Title: Show that moving one symbol to the end still makes a regular language
# Question

For any string $\sigma$ over alphabet $\Sigma$, we define the operation $\texttt{MOVE}$ as following

> For $\sigma = aw$ ($a \in \Sigma, w\in \Sigma^\*$), $\texttt{MOVE}(\sigma)=wa$

This is equivalent to moving the starting symbol to the end. For example, $\texttt{MOVE}(10110)=01101$.

Show that for a regular language $L$, the language $\texttt{MOVE}(L) = \\{\texttt{MOVE}(\sigma): \sigma \in L\\}$ is also regular.

# My Attempt

After reading this post, I know I could prove a language $L$ is regular by showing that $L$ could be expressed as a DFA, NFA, or regular expression.

I tried different (vaguely related) directions

* I have proved that: if $L$ is regular, then its reverse $L^R$ is also regular. However, in terms of $\texttt{MOVE}(L)$, only one symbol is reversed while the order of others is preserved.
* $\texttt{MOVE}(L)$ seems to be related to converting between left and right quotients. But I do not how to proceed as quotients are defined upon two languages rather than one.

$$ L\_1/L\_2 = \\{w\vert \exists x: x\in L\_2 \wedge wx \in L\_1\\}\\ L\_1\backslash L\_2 = \\{w\vert \exists x: x\in L\_2 \wedge xw \in L\_1\\} $$

Except these attempts, I do not know how to approach this problem. It would be great if anyone provide some pointer for me.

# Answer
Consider a DFA for the original language with states $Q$, initial state $q\_0$, final states $F$, and transition function $\delta$. We construct an NFA for the new language which operates roughly as follows:

* It first guesses the initial symbol $a$.
* It then reads the word $w$.
* A state is accepting if $wa \in L$.

To implement this, the set of states will be $\Sigma \times Q$, that is, the set of pairs $(a,q)$ where $a \in \Sigma$ and $q \in Q$. The initial states are $(a,\delta(q\_0,a))$. A state $(a,q)$ is final if $\delta(q,a) \in F$. Finally, the transition relation is $\delta((a,q),b) = (a,(q,b))$.

---

You can solve this in many other ways. One of the simplest is using closure properties. Let $a^{-1}L = \\{w \in \Sigma^\* : aw \in L\\}$, which is a quotient $L \setminus \\{a\\}$ per your definition. Then $$ \texttt{MOVE}(L) = \sum\_{a \in \Sigma} (a^{-1}L)a. $$ You can even implement this using regular expression. Given a regular expression for $L$, construct a regular expression for $a^{-1}L$ using the following rules:

* $a^{-1} \emptyset = a^{-1} \epsilon = \emptyset$.
* $a^{-1}a = \epsilon$ and $a^{-1}b = \emptyset$, where $b \neq a$ is a symbol.
* $a^{-1}(r\_1+r\_2) = a^{-1}r\_1+a^{-2}r\_2$.
* If $r\_1$ doesn't generate $\epsilon$ then $a^{-1}(r\_1r\_2) = (a^{-1}r\_1)r\_2$.
* If $r\_1$ does generate $\epsilon$ then $a^{-1}(r\_1r\_2) = (a^{-1}r\_1)r\_2 + a^{-1}r\_2$.
* $a^{-1}(r^\*) = (a^{-1}r)r^\*$.

You can determine whether $r$ generates $\epsilon$ recursively. Denoting this predicate by $E$,

* $E(\emptyset) = E(a) = F$, $E(\epsilon) = T$.
* $E(r\_1+r\_2) = E(r\_1) \lor E(r\_2)$.
* $E(r\_1r\_2) = E(r\_1) \land E(r\_2)$.
* $E(r^\*) = T$.

This gives a mechanical procedure to compute a regular expression $a^{-1}r$ satisfying $L\[a^{-1}r\] = a^{-1}L\[r\]$. We can then define $$ \texttt{MOVE}(r) = \sum\_{a \in \Sigma} (a^{-1}r)a, $$ which satisfies $L\[\texttt{MOVE}(r)\] = \texttt{MOVE}(L\[r\])$.
> 5 votes

---
Tags: formal-languages
---


# Question
Title: Is there an optimization algorithm that could help match the maximum number clients to servers with constraints?
How do you go about solving the following problem that tries to match the greatest number of clients with servers with constraints? I'm trying to identify an algorithm or simulation that could help me solve this problem as optimally as possible.

Assume you are given a 2d map of servers and clients randomly scattered. Each server can handle a certain radius of clients but never two clients that are near each other (this is the constraint). While it makes sense for a server to handle all the clients near it, some clients may need to be handled by another server nearby. Picking which of those clients should be handled by another server (potentially farther but still in reach) such that the maximum number of clients can be handled is the objective.

Not all clients necessarily can be handled, but the problem should be able to match the most number of clients with servers possible, and the constraint must be upheld.

# Answer
> 1 votes
The problem is NP-hard. Consider the following special case: there is only one server, and its radius is infinite (or very large). Then your problem becomes the problem of finding an independent set in a planar graph. That problem is known to be NP-hard. Since a special case of your problem is NP-hard, then your problem must be at least as hard in the general case.

There are many ways to deal with NP-hard problems. Probably one reasonable approach is to formulate your problem as integer linear programming, and then solve with an off-the-shelf ILP solver. Another approach is to formulate it as an instance of SAT (with a pseudoboolean constraint/cardinality constraint for counting the number of clients that are serviced), and solve with an off-the-shelf SAT solver, like Z3 (which has good support for pseudoboolean constraints).

---
Tags: optimization, constraint-satisfaction
---


# Question
Title: What is wrong with this proof that proves that 0*1* is not a regular language?
*I know why cases 1 and 2 are wrong because our language can have different numbers of 0's and 1's. But I'm not sure how case 3 can be proved wrong for our language.*

Exercise 1.30: Describe the error in the following “proof” that $0^{∗}1^{∗}$ is not a regular language. (An error must exist because $0^{∗}1^{∗}$ is regular.)

> The proof is by contradiction. Assume that $0^{∗}1^{∗}$ is regular. Let p be the pumping length for $0^{∗}1^{∗}$ given by the pumping lemma. Choose s to be the string $0^{p}1^{p}$. You know that s is a member of $0^{∗}1^{∗}$, but Example 1.73 shows that s cannot be pumped. Thus you have a contradiction. So $0^{∗}1^{∗}$ is not regular.

Example 1.73:

> Let B be the language $\\{0^{n}1^{n}|n ≥ 0\\}$. We use the pumping lemma to prove that B is not regular. The proof is by contradiction. Assume to the contrary that B is regular. Let p be the pumping length given by the pumping lemma. Choose s to be the string $0^{p}1^{p}$. Because s is a member of B and s has length more than p, the pumping lemma guarantees that s can be split into three pieces, s = xyz, where for any i ≥ 0 the string $xy^{i}z$ is in B. We consider three cases to show that this result is impossible.
>
> 1. The string y consists only of 0s. In this case, the string xyyz has more 0s than 1s and so is not a member of B, violating condition 1 of the pumping lemma. This case is a contradiction.
> 2. The string y consists only of 1s. This case also gives a contradiction.
> 3. The string y consists of both 0s and 1s. In this case, the string xyyz may have the same number of 0s and 1s, but they will be out of order with some 1s before 0s. Hence it is not a member of B, which is a contradiction.

> Thus a contradiction is unavoidable if we make the assumption that B is regular, so B is not regular. Note that we can simplify this argument by applying condition 3 of the pumping lemma to eliminate cases 2 and 3. In this example, finding the string s was easy because any string in B of length p or more would work.

*This question is from the book 'Introduction to the Theory of Computations' by Michael Sipser, exercise 1.30*

# Answer
The pumping lemma states that if $L$ is regular then there exists a constant $p$ such that any word $w \in L$ of length at least $p$ can be decomposed as $w = xyz$ so that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, and (iii) $xy^iz \in L$ for all $i \geq 0$.

The pumping lemma does *not* state that any decomposition which satisfies properties (i),(ii) also satisfies property (iii).

The pumping lemma only guarantees that *some* decomposition which satisfies all three properties exists.

In your case, you can take $p = 1$. If $w = 0^n1^m$ for $n \geq 1$, then you can take the decomposition $x = \epsilon$, $y = 0$, $z = 0^{n-1} 1^m$. If $w = 1^m$ for $m \geq 1$, then you can take the decomposition $x = \epsilon$, $y = 1$, $z = 1^{m-1}$.
> 2 votes

# Answer
The cases 1 and 2 don't work because unlike the language in example 1.7.3, your language allows strings with different number of 0's and 1's.

Therefore you have no contradiction and no proof that the language is irregular.
> 1 votes

---
Tags: pumping-lemma
---


# Question
Title: How to express complexity of two functions considering it is the same in big O notation
I have two functions. `a` and `b`.

Both have linear complexity `O(n)`.

```
fcn a (items)
    loop items -> item
        ...

```

```
fcn b (items)
    loop items -> item
        ...

    loop items -> item
        ...

    loop items -> item
        ...

```

Though `b` obviously takes 3 times longer to run than `a` for the same input.

**Is there any other notion / technical way to express the difference?**

Or is it normal to say "it takes 3 times longer but still O(n) in time so w.e, let's move on"

# Answer
Big O notation is oblivious to this difference. This is one of its downsides.

One reason we use big O notation in the first place is that the exact running time depends on the system used to run the algorithms. It is meaningless to say that a given algorithm takes X instructions, since X depends on the CPU, the compiler, and so on. However, in some cases we can find a proxy for the running time which is meaningful to look at.

The prototypical example is the number of comparisons in a comparison-based sorting algorithm. In many cases, number of comparisons is a good proxy for the overall running time, and this is a "dimensionless" quantity which is meaningful to compare across algorithms.

Another option is to implement your algorithms as efficiently as possible, and then compare their running time empirically. In a practical paper, this is a very reasonable thing to do.

In your particular case, you can just say that algorithm B invokes algorithm A three times, and consequently is three times slower. This is not reflected in big O notation, but is quite precise and meaningful.
> 2 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Is this clique algorithm in polynomial time correct or might it have another time complexity?
I came up with the idea finding a k-clique through starting at a small s-clique (like 1-,2- or 3-clique) and use it to find every s+1 Clique iterative. I had some trouble finding the Time Complexity and I am not sure where I might have went wrong.

First I will show the algorithm, argue about its correctness and then what I tried on finding the time complexity.

So given a Graph $G = (V,E) $ and $n = |V|$ and $m = |V|$ and the case of k \> 3 we would use the following algorithm:

* Find every 3-Clique first in $O(n^3)$ (using three for loops for checking every possible triangle) and using hashing whether a triangle was already added or not.
* Now we have the set $M := \\{(i,j,k) | i,j,k \in V \land (i,j), (i,k), (j,k) \in E \\}$ of triples of all disting 3-cliques.
* Next we use the list of 3-Clique to search for 4-Clique through looking at every adjacent node $l$ of of every triple $(i,j,k)$. If one the the adjacent nodes is connected to all $(i,j,k)$ so that $(l,i),(l,j),(l,k) \in E$ we have found a 4-Clique.
* We proceed this process for every s-Clique with $s \in \\{4,...,k \\} $ usingal found $s-1$ clique

For the correctness of the algorithm it should be enough to show by induction that every s-clique consists of s-1 possible (s-1)-cliques. So once we have all s-1-clique it is easy to find every s-clqiue, since we just have to check every adjacent node of the s-1-clique for a connection with every node in the s-1-clique.

I tried to estimate the time complexity the following way:

* Worst Case Complexity is finding a n-Clique in $G$. So this means we have $ m = n(n-1) $
* We would have to do $(n - 3)$-Loops for finding every s-clique in the sth loop.
* In every loop we have less n s-clique where every s-clique might have maximum $s(n-1)$ adjacent nodes to look at.
* Since we have less then n s-clique this would mean looking at $n\*s(n-1)$ possible edges for finding a new s-clique.

This would sum up to $O(n^5)$ using gauss sum for every s-clique, but this would mean clique is in P and this seems a little bit to easy to be true.

# Answer
> 6 votes
Your analysis of the time complexity is wrong. Specifically this statement:

> In every loop we have less n s-clique where every s-clique might have maximum s(n−1) adjacent nodes to look at.

In fact you can have up to $\binom{n}{s}$ $s$-cliques.

You approach is essentially enumerating all cliques of size up to $k-1$. So you cannot hope to have a running time better than $\Omega\left( \sum\_{s=1}^{k-1} \binom{n}{s} \right)$.

---
Tags: complexity-theory, time-complexity, polynomial-time, clique
---