# Question
Title: What is the difference between modulo and modulus?
Throughout my education in computer science, I feel like I've heard the terms "modulo" and "modulus" used interchangeably. It looks like even Wikipedia claims that "modulo" is "sometimes called 'modulus'" (see the first sentence of the page on 'modulo').

I've looked into this issue a little and it seems that **"modulo"** finds singular use in modular arithmetic (e.g. "19 and 64 are congruent modulo 5"). In addition, I've seen the symbol `%` be referred to as "modulo."

Meanwhile, **"modulus"** appears to have several definitions, including "absolute value" and "constant factor" as well as referring to the "5" in "modulo 5."

Is it ever correct to use these terms interchangeably in the context of computer science? Are they simply different types of words that represent the same idea (such as "run" and "runner")? Are there important differences in other disciplines?

Bonus: Etymologically, what gave rise to these two terms?

# Answer
> 26 votes
"modulo" is an operator. For instance, we might say "19 and 64 are congruent modulo 5".

"modulus" is a noun. It describes the 5 in "modulo 5". We might say "the modulus is 5".

No, the two should not be used interchangeably. It would be incorrect to say "19 and 64 are congruent modulus 5". It would also be incorrect to "the modulo is 5".

See also https://en.wikipedia.org/wiki/Modular\_arithmetic and https://en.wikipedia.org/wiki/Modulo\_operation. Both define the word "modulus", and as far as I can see they use it correctly.

# Answer
> 2 votes
My knowledge in Latin and etymology is very limited, but, 'modulus' is a Latin word, and the form 'modulus' is singular, nominative. 'moduli' is its plural form, again in the nominative case. Finally, 'modulo' is its ablative case. I believe that 'a is congruent to b *modulo m*' literally means something like 'a is congruent to b *in the modulus m*'.

English declension is very simple, but it wasn't always like that. And, it seems that in old times, when you import a foreign word into English, you import not only the standard, singular nominative form, but also all other forms. Some of Latin or Greek plural forms are remaining in modern English, although their uses seem to be declining. But in older times, not only plural forms, but also other cases were sometimes used. I think the word 'modulo' in math is a very rare remaining active usage of the Latin ablative case in English.

---
Tags: terminology, modular-arithmetic
---


# Question
Title: Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?
I claim to have solved the travelling salesman problem as follows.

(You will have to be familiar with djikstra's algorithm for this.)

1) I am about to start using djikstra's algorithm on any given road network but,

2) The end node is not known for now, regardless, I just begin from any arbitrary node, assuming I will be given the end node at some later point in time or I will claim it myself.

3) At each step of djikstra's algorithm you stop me, I claim the last node I currently am to be the end node I was looking for. Also at each step I disregard the roads that has been travelled already for that particular path.

4)Whenever I get stopped, I am at the shortest path I can be from my initial node to the current node by virtue of djikstra's algorithm (end node from djikstra's perspective)

5) I continue the process unless I start to reach to every node.

6) There is only a final node remaining, I go there and still, the path I have chosen is shortest path possible from initial node to that node, and I have travelled all the nodes possible.

7) I return to the initial node, travelling through all the nodes with shortest path possible.

Question: why I haven't solved the travelling salesman problem?

P.S. please comment if my argument is not clear enough I will try to refine it. There is clearly a gap in my understanding of the theory and I want to understand what it is. I don't have enough CS experience to pose a question algorithmically.

# Answer
> 3).. . Also at each step I disregard the roads that has been travelled already for that particular path.

In order to do that, you must be running Dijkstra on a graph with exponentially more vertices than the input graph.
> 3 votes

# Answer
Your algorithm builds a tree, not a single path.
> 0 votes

---
Tags: algorithms, np-complete, shortest-path, np, traveling-salesman
---


# Question
Title: Is logical address generated by CPU and MMU same if Physical and Virtual address space are same?
The system has same physical and virtual address space i.e. 32-bit. Are the logical address generated by CPU and address generated by MMU same?

# Answer
> 0 votes
It can be but not necessarily.

The MMU can be setup to translate adresses. There is nothing stopping you from having swapping physical adresses between, say, two logical segments and still have the same amount of logical and physical adresses. Sounds a bit unusual to me, but not impossible.

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


# Question
Title: Automata with minimal number of states using reverse
So, by the Bzozowski theorem, if A is DFA det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an DFA which is NOT minimal (the min. automata have 2 states ) but det(rev(A)) is the same automata (obviously det(rev(det(rev(A))) is also the same). Can you tell me what am I doing wrong ? Tnx.

# Answer
Your initial automaton has two final states. Its reverse should have two initial states. You wanted to avoid that, and added a new initial state.

The proper construction just uses the two initial states. The determinization algorithm can handle that.
> 1 votes

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


title: Coefficients in cost function in A-star

text:
# Question
Title: Coefficients in cost function in A-star
I'd like to expand on this question :

https://stackoverflow.com/questions/52420788/why-does-the-a-star-algorithm-need-gn

Dijkstra's algorithm uses cost function $f(n) = g(n)$ whereas A\* uses cost function $f(n) = g(n) + h(n)$, with $g(n)$ being the cost of the path from the start node to node $n$, and $h(n)$ is a heuristic function that estimates the cost of the cheapest path from node $n$ to the goal.

It is clear from the linked question's answer that A\* needs its $g(n)$ function in the cost function. My question however is the following. Can one use the cost function :

$f(n) = \alpha g(n) + (1-\alpha)h(n)$

for some alpha $0\<\alpha\<1$ ?

I ask because in some cases I observed it can be much faster to prioritize (through a coefficient) estimated cost over already traversed cost. I am not sure however if this still results in an optimal path?

EDIT : multiplying the heuristic $h(n)$ by some alpha $0\<\alpha\<1$ is allowed, since this operation still underestimates if $h(n)$ already did (which is necessary to obtain the resulting optimal path). I am more concerned about the multiplying of $g(n)$.

# Answer
> 1 votes
For A\* to get the optimal path it requires that $f(n) \leq g(goal)$. In other words that the heuristic underestimates the cost from the node to the goal.

Multiplying a valid hueristic with $0 \lt\alpha\lt 1$ will not violate this requirement.

Multiplying $g(n)$ is not allowed because you can end up with $f(goal) = \alpha g(goal) \< f(n)$ which would violate the requirement for getting the optimal path.

# Answer
> 0 votes
This question has been answered here :

https://stackoverflow.com/questions/57974474/coefficients-in-cost-function-in-a-star/57978082#57978082

As user Harold states :

> The global scale factor of f, assuming it is a positive scale, does not matter, because f is only used in a relative sense. Numbers scaled by some positive scale stay in the same order.
>
> Therefore, f(n) = αg(n) + (1-α)h(n) may be rewritten as f'(n) = f(n)/α = g(n) + ((1-α)/α)h(n), which is not equal but equivalent. So while you are interested in scaling g, effectively that is equivalent to scaling h anyway, after factoring out the global scale.
>
> The effect is scaling the heuristic by some amount, which is OK only as long as (1-α)/α ≤ 1 (so: α ≥ 0.5), and otherwise leads to the same trouble as usual with an inadmissible heuristic.

---
Tags: algorithms, search-algorithms, a-star-search
---


# Question
Title: How is the problem, {⟨G⟩|G has no triangle} in Logspace?
I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-tuples in the tape, then how come my solution is limited to log-space?

As far as my understanding, listing all the 3-tuples in the tape would need $\binom{n}{3}$ combinations, and hence, $O(n^3)$ space.

I am not able to find the flaw in my understanding, grateful ever for the hint.

P.S. This reference is from our course slide:

> Let $L$ be the language $\\{⟨G⟩ \\: | \\: G\text{ has no triangle}\\}$. Then $L$ can be recognized in log-space as follows: On the work tape, the machine $M$ can write all 3-tuples of the vertices of $G$. For each tuple written, the machine checks if there is a triangle passing through those vertices. If all tests fail, then $M$ accepts, otherwise $M$ rejects. The space used by $M$ is enough to store three vertex identifiers, therefore $L$ is in log-space.

# Answer
You don't need to **first** write **all** 3-tuples and **then** check, for each of them, whether it induces a triangle.

You can just enumerate the 3-tuples **one at a time** and reject as soon as you find one that induces a triangle. If you reach past the last 3-tuple then the graph contains no triangle and you can accept.
> 17 votes

# Answer
```
FOR x := 1 TO n DO
    FOR y := 1 TO n DO
        FOR z := 1 TO n DO
            IF E(x,y) && E(y,z) && E(z,x) THEN REJECT
ACCEPT

```

Each of the variables `x`, `y` and `z` requires $\Theta(\log \texttt{n})$ bits to store an integer between $1$ and $\texttt{n}$.
> 19 votes

---
Tags: graphs, turing-machines, space-complexity
---


# Question
Title: Efficient algorithm to filter off points from a point cloud
I have a master point cloud, which essentially just a list of points with `{x,y}` coordinates.

The point cloud is HUGE ( like, it can contain more than 1 million points). The problem now is that I have another (sub)set of point clouds, and I need to check whether the points inside the second point clouds are the same with any of the points in the first point clouds, and then remove them from the list.

The characteristics of the second point cloud:

1. The second point cloud points are usually clustered in a corner of the first point cloud ( but not always).
2. None of the points from the second point cloud will lie outside of the first point cloud ( the first point cloud always contain every single point of the second point cloud)

The naive algorithm will be something like this:

```
   public static List<Point> FilterPoints(Lis<Point> master, List<Point> subset)
   {
    var FilteredPoints = new List<Point>();
    for(int i=0; i< subset.Count; i++)
    {
        var isContained = false;
        for(int j=0; j< master.Count; j++)
        {
          if(subset[i].X==master[j].X && subject[i].Y==master[j].Y)
          {
              isContained = true;
              break;
          }
        }
        if(!isContained)
        {
           FilteredPoints.Add( master[i]);
        }
      }
     return FilteredPoints;
}

```

But is there anyway to improve over the above naive algorithm in terms of speed, given the known characteristics of the both point clouds?

PS: I've also asked about how to make use of C# language characteristics( if any) in order to improve the speed for the above algorithm at SO.

# Answer
> 2 votes
You should use a set data structure for your subset-list. This would allow querying if it contains a given point in constant time.

Your function, as python-like pseudocode:

```
def FilterPoints(master, subset):
    # take the list and convert it to a set ( O(|subset|)
    subset_set = set(subset)
    # iterate through master and and the points that are not in subset O(|master|)
    filtered_list = [p for p in master if p not in subset_set]
    return filtered_list

```

Some points:

* If master is larger than subset, the algorithm will be $\mathcal O(|master|)$
* The equivalent of set in C# should be HashSet

# Answer
> 2 votes
If you really do want to test points for *equality*, then oerpli's solution is ideal. Any standard dictionary data structure will do the job.

However, for completeness, if you need to match points within some small distance (e.g. maybe these are floating point and you're reading one of them from an ASCII file where you can't guarantee precision), then you can use some kind of spatial index instead. Insert one set of points into the index, and then query it with the other set of points.

Something like k-d trees, quadtrees, or R-trees is probably easiest. If the coordinates are bounded, you could also use a space-filling curve approach such as geohash.

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


# Question
Title: Can you have simple unit tests for complicated function?
Can you have simple unit tests for complicated function? For example: Turing test for AI.

Do you always can find simple unit tests for any complicated enough function / algorithm?

# Answer
The Turing test would make a very poor unit test because (a) it is difficult (impossible ?) to automate and (b) the evaluation of the test output to produce a pass or fail result is subjective. In fact, it might not even be possible to devise useful unit tests (in the usual sense) for strong AI - how would unit tests distinguish between true AI and a program that simply responded by rote ?

But simple unit tests for other complicated functions are certainly possible. As long as the function produces output that can be objectively evaluated then you can write unit test cases for it. For example, a Travelling Salesman Problem solver could be a very complicated program, but a unit test plan is very simple:

(a) test edge cases - 0 cities, 1 city, 2 cities

(b) test some simple cases with known solutions e.g. 3 cities in scalene triangle, 4 cities at corners of a rectangle, solved examples from TSPLIB
> 0 votes

# Answer
In the case of the travelling salesman problem, you can easily write unit test that find _ some\_ bugs but not all: construct an instance and find a solution. Then increase some distance between cities that are part of the optimal solution and solve again. The shortest distance should not become less. And then you repeat.

An algorithm that doesn’t find an optimal solution ( when it is supposed to) would likely find solutions that are sometimes less and sometimes more close to optimal. So if you give it instances where the optimal value should have non- decreasing values a non- optimal solution might produce decreasing values sometimes.
> 0 votes

---
Tags: complexity-theory, software-testing, turing-test
---


# Question
Title: maximum flow with all or nothing through each edge
Consider a maximum flow problem, where each edge has a small integer capacity. Now, I want a solution that for each edge uses the entire capacity, or no flow through that edge at all. To avoid the subset-sum problem, the capacities are small. Is this solvable in polynomial time or is it NP-Complete?

# Answer
> 3 votes
Your problem is NP-hard. There is a reduction from Independent Set to its decision version.

Consider an instance $G=(V,E)$ of Independent Set, you construct a network with vertices $\\{s,t\\}\cup V\cup V'$ where each vertex in $V'$ corresponds to a pair of vertices in $V$. For example, if $V=\\{1,2,3\\}$, then $V'=\\{v\_{12},v\_{23},v\_{13}\\}$. Then we construct the edges as follows:

* For each vertex $x\in V$, add an edge $(s,x)$ with capacity $|V|-1$.
* For each vertex $v\_{xy}\in V'$, add two edges $(x,v\_{xy})$ and $(y,v\_{xy})$. Both edges have capacity 1.
* For each vertex $v\_{xy}\in V'$ where $(x,y)\in E$, add an edge $(v\_{xy},t)$ with capacity 1.
* For each vertex $v\_{xy}\in V'$ where $(x,y)\notin E$, add two edges $(v\_{xy},t)$ with capacity 1 (if multiple edges are not allowed, we can add another two vertices $u\_1,u\_2$ and add two paths $v\_{xy}\rightarrow u\_1\rightarrow t$ and $v\_{xy}\rightarrow u\_2\rightarrow t$, which has the same effect).

Now $G$ has an independent set of size $k$ if and only if the constructed network has a flow of value $(|V|-1)k$.

# Answer
> -1 votes
Consider the following decision problem.

Determine if the network N has a flow of size at least k, but with the restriction that some (fixed pre-determined) edges must either have 0 flow, or be at maximal capacity.

This problem is NP-complete, I have a proof written up here (arxiv).

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


# Question
Title: Fitting a polynomial to a set of points or to a skeleton
## Available data

Available to me is a set of points which can be represented as shown in image 1:

Also available to me is a non-continuous path derived from this data. It is not important how this non-continuous path is obtained. It is however important, that it roughly represents a curve I intent to approximate. This non-continuous path is shown in image 2:

## Goal

I want to approximate this data using a polynomial of either second or third degree. Examples of these approximations are shown in images 3, 4:

## Problem / question

Now I am looking for a way to obtain the red curve. Some details confuse me, where my knowledge is likely to be simply lacking. For example, how to fit a polynomial, when technically what I require is not a function, at least not in this coordinate system, because there will be situations where an **x** value is being assigned two **y** values.

I thought of possibly using the ends of my path to define a new x-axis, but I consider this approach faulty. Another consideration are Splines.

How should I go about obtaining this red curve from the non-continuous path (preferred) or from original data? What sources should I look into?

Apologies if this is an already answered question which I suspect it might be. However I have been issuing search queries for this without success, hence my question.

# Answer
You can try fitting a multi-dimensional polynomial regression. It seems that for your data, a two dimensional regression model should be fine: $$ (a)x^2 + (b)x + (c)y^2 + (d)y + (e)xy + (f) $$

In python for example, you can fit a proper model using:

```
import numpy as np
from sklearn.preprocessing import PolynomialFeatures

X = np.array([ [x0,y0], [x1,y1], ...  ])
poly = PolynomialFeatures(2)
poly.fit_transform(X)
poly = PolynomialFeatures(interaction_only=True)
poly.fit_transform(X)

```
> 2 votes

---
Tags: image-processing, polynomials
---


title: Distinct Binary Heaps

text:
# Question
Title: Distinct Binary Heaps
I have $n$ elements out of $n-1$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it.

*My analysis* : I started with $n$ distinct elements. Since root is fixed( maximum element) we can choose $l$(found using deducting total elements from elements in penultimate level) from remaining $n-1$ elements and recursively choose for Left Sub-tree and Right Sub-tree.

Recurrence Relation :

> $T(n)={n-1 \choose l} * T(l) * T(r)$

Now for $n-1$ distinct elements(given), for root we have $2$ options i.e. maximum elements and we can recurse as above for left and right sub-tree. But since the repeated element is also there I am not able to figure out exact way to do so.

Eg: $A=\[2,6,6\] =\>$ There are 2 distinct max heaps $ =\> \[6,2,6\] , \[6,6,2\]$

I am unable to think of the way to find out the number of max heaps in this case. Can someone think of algorithm/recurrence relation to find so ?

# Answer
If the duplicate element is the maximum element, the answer is the same as when all numbers are distinct. Let's say the duplicate element is $a\_1, a\_2$. Even though they are the same, we can treat it as $a\_1 \> a\_2$, and then remove the duplicate heaps where the only difference is the exchange of $a\_1, a\_2$, but that is not possible because $a\_1$ is always at the root. So no duplicates found.

If the duplicate element is the minimum element, the problem gets more interesting. Let $S(n)$ be the number of max heaps such that the minimum element is duplicated, and $T(n)$ be the number of max heaps such that there are no duplicates. We already know that

$$T(n) = {{n-1}\choose {l}} \times T(l) \times T(r)$$

with base case $T(1) = 1$.

For the duplicate case, we have 3 cases. We can put them both into the left subtree, both into the right subtree, or one in each subtree. Hence, the recursion is

$$S(n) = {{n-3}\choose {l-2}} S(l) T(r) + {{n-3}\choose {r-2}} T(l) S(r) + {{n-3}\choose {l-1}} T(l) T(r)$$

with base case $S(1) = 0, S(2) = 1, S(3) = 1$.
> 1 votes

---
Tags: algorithms, binary-trees, recursion, heaps
---


# Question
Title: Time complexity for balancing an unbalanced binary tree
The question here is that: There is an unbalanced binary tree with n-nodes. What is the time complexity to balance the tree?

The solution I thought of involved solving using Recursion where for the worst-case I took a maximally unbalanced tree like this

And then try to balance this using rotations.

But I cannot come up with an expression which will give O(log(n)) time complexity.

Can I get some help in solving this? I am stuck on how to approach this problem.

# Answer
Do an inorder traversal of the BST...and store it in an array the array will be sorted. next construct a balanced binary search tree from this array. 1) Get the Middle of the array and make it root. 2) Recursively do same for left half and right half. a) Get the middle of left half and make it left child of the root created in step 1. b) Get the middle of right half and make it right child of the root created in step 1.

Time Complexity of both inorder traversal and AVL tree construction is O(n).
> 1 votes

# Answer
I don't think that it is possible to balance a tree in logarithmic time:

* An algorithm has to determine somehow, when it is finished
* In this case, establishing that the tree is balanced is necessary
* This operation alone is $\mathcal O(n)$ (count the height of left/right subtree)

Therefore, $\mathcal O(n)$ will be a lower bound for your algorithm and there are multiple ways to construct binary trees in linear time, so take either one of them.
> 1 votes

---
Tags: data-structures, binary-search-trees
---


title: Deadlocks in operating System

text:
# Question
Title: Deadlocks in operating System
Consider a system with 6 processes, where each process needs 2 copies of Resource R. The maximum units of R required to cause deadlock is ??

# Answer
For a system to be in deadlock it must not be able to proceed. A process may be not started, complete, waiting for a resource, processing a resource, or be deadlocked.

It's normal for a process to have to wait for a resource, so deadlock only arises if it is shown that the resource can never be made available. For the information given, and absent the specification any of the other conditions, then I think the answer must be 1.

Perhaps the question needs to be more explicit with respect to its constraints.
> 1 votes

# Answer
I am assuming you know the $4$ conditions required for the system to be in deadlock.

Now let's consider there are $n$ processes in the system $P\_1, P\_2, P\_3, …… , P\_n$ where

> Process $P\_1$ requires $x\_1$ units of resourc $R$
>
> Process $P\_2$ requires $x\_2$ units of resource $R$
>
> Process $P\_3$ requires $x\_3$ units of resource $R$
>
> .....
>
> Process $P\_n$ requires $x\_n$ units of resource $R$

So for deadlock to exist, in worst case,the number of units that each process holds = One less than its maximum requirement.So we can say that for system in deadlock,

> Process $P\_1$ holds $x\_1 -1$ units of resource $R$
>
> Process $P\_2$ holds $x\_2 -1$ units of resource $R$
>
> Process $P\_3$ holds $x\_3 -1$ units of resource $R$
>
> .....
>
> Process $P\_n$ holds $x\_n -1$ units of resource $R$

Now, to break the deadlock,we just need one more unit of resource $R$ in the system. This is because that unit would be allocated to one of the processes and it would get execute and then release the resources held by it which can be used by other processes.

From here, we can say

Maximum number of units of resource $R$ that ensures deadlock

> $= (x\_1-1) + (x\_2-1) + (x\_3-1) + …. + (x\_n-1)$
>
> $= ( x\_1 + x\_2 + x\_3 + …. + x\_n ) – n$
>
> $= \sum\_{x=1}^nx\_i\ – n$

Now in your question, $n=6$ and $x\_i = 2$. Putting in the values of $x\_i$ and $n$

> $= 2+2+2+2+2+2 - 6$
>
> $=6$

So the maximum units of $R$ required to cause deadlock is $6$
> 0 votes

---
Tags: deadlocks
---


# Question
Title: Finding the last substring in lexicographical order in O(n) time
> Given a string s, return the last substring of s in lexicographical order.
>
> Example 1:
>
> Input: "abab" Output: "bab" Explanation: The substrings are \["a", "ab", "aba", "abab", "b", "ba", "bab"\]. The lexicographically maximum substring is "bab".

More specifically, I am looking for an accompanying proof/intuition. I can find many solutions, but none provide a proof of their technique and I cannot convince myself.

source: https://leetcode.com/problems/last-substring-in-lexicographical-order/

# Answer
> 1 votes
Consider a string of 100 million characters with say 100 z’s in between plus a huge number of the characters a to y (and no character lexicographically after z). Find an algorithm that would often give you the correct result in O(n), actually with at most 2n comparisons. Find out why this algorithm doesn’t always run in O(n), then figure out what you can do about it to still run in O(n). For example, if you have a million repetitions of zabcdefabcdef.

# Answer
> 1 votes
Greedily keep track of the lexicographically last character and all characters following it. It will take $2n$ comparisons at most as @gnasher suggested.

The rules are as follows where `str` is the input string:

* Keep track of current best (lexicographically last) string `last`. Initially it is the first character of `str`.
* For `i` in the range `[1, length(str)]`:

+ Let `k` be an offset equal to `0` initially.
    + For `j` in the range `[0, length(last) + 1]`:

    1. If `str[i + k]` is less than `last[j]` or `j = length(last)` then append `str[i, i + k]` to `last`. Set `i = i + k + 1` and break this loop.
        2. If `str[i + k]` is greater than `last[j]` then set `last = str[i, i + k]`. Set `i = i + k + 1` and break this loop.
        3. If `str[i + k]` is equal to `last[j]` then `k++` and continue this loop.
* Return `last`.

It runs in $O(n)$ but may take $~2n$ comparisons because we have to scan back through `last`, although we never scan an index in `str` more than twice.

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


title: Safety property vs Liveness property

text:
# Question
Title: Safety property vs Liveness property
If i take a safety property $SP$ and a liveness property $LP$, is it true that the result of their intersection is a safety property (and not a liveness property) ? Why ?

Thanks

# Answer
> 1 votes
No, it is not. If you have a look at the Decomposition theorem for example, then you will find, that there are properties you cannot express as neither a SP or LP, but as an intersection of a SP and LP.

There exist such SP and LP, that their intersection is a safety property. For example the property of all possible traces, the result is again the property of all possible traces. Which incidentally is the only property that is both safety and liveness.

---
Tags: software-verification, model-checking
---


# Question
Title: How to prove that ($56n^2+106n+48)(\log(264n^2+200)) = Θ(^2\log n)$
I understand that essentially we have to prove that

$$c\_1(n^2\log n)\le (56n^2+106n+48)(\log(264n^2+200)) \le c\_2(n^2\log n)\\,.$$

I am confused on how to simplify this further? And correctly find a c value.

# Answer
> 2 votes
For all $n\geq 1$, $56n^2+106n+48\> 56n^2\> n^2$ and $\log (264n^2+200)\> \log 264n^2\>\log n$, so $$(56n^2+106n+48)\log(264n^2+200) \> n^2\log n\\,,$$ i.e., you can take $c\_1=1$.

Also for all $n\geq 1$, $56n^2+106n+48\leq 56n^2+106n^2+48n^2 = 210n^2$ and, for all $n\geq 200$, $264n+200 \< 265n$ so $\log(264n^2+200) \< \log 265n^2 = 2\log n + \log 265$. For all $n\ge 265$, $2\log n + \log 265\leq 3\log n$. Therefore, for all $n\geq 265$, $$(56n^2+106n+48)\log(264n^2+200) \< 630n^2\log n\\,,$$ i.e., you can take $c\_2=630$.

# Answer
> 0 votes
It's sometimes more convenient to work with the limit definitions.

To prove the statement, you can break it down into proving that $f(n) = O(g(n))$ and that $f(n) = \Omega(g(n))$. In your case, it's straightforward to compute $\lim\_{n \to \infty} f(n)/g(n)$. I believe that this will turn out to be a positive three-digit constant less than infinity and greater than zero, and we'll be done.

# Answer
> 0 votes
$c\_1 = 56$ works for all n.

Let n \>= 265, then 200 \<= $n^2$, $264n^2 + 200 \<= n^3$, the logarithm is less than 3 log n, $56n^2 + 106n + 48 \<= 56n^2 + n^2 + n^2 = 58n^2$, so you can pick $c\_2 = 58\*3 = 174.

---
Tags: algorithms, runtime-analysis, big-o-notation
---


# Question
Title: Why does a Turing Machine need at least two states?
I read in some text book ( either ullman or peter linz) that a turing machine must have at least two states. I don't understand why?

For example if we want to build a Turing Machine for the empty language then we can start in state $q\_o$ (accept state). We will define only one transition for epsilon on which the input would be accepted. However if the input is something else then since we have not defined any transition we would enter dead configuration.

what's the problem with this approach?

# Answer
> 4 votes
TL;DR: technically, there need to be an accepting and rejecting state and they need to be different; but it's not a big deal and, at an intuitive level, one-state machines work just gine.

---

A Turing machine is typically defined to be a tuple $M=\langle Q, \Sigma, \Gamma, \delta, q\_0, q\_\mathrm{acc}, q\_\mathrm{rej}\rangle$ where the items are the state set, input and tape alphabets, the transition function (or relation for a nondeterministic machine), and the initial, accepting and rejecting states, respectively.

The accepting and rejecting states must be distinct because the machine cannot simultaneously accept and reject. Therefore, there must be at least two states.

In principle, you might want to define a Turing machine that has only one state: the initial state would be the accepting state and there'd be no rejecting state, or vice-versa. There's nothing morally wrong with that but it would make the definition more complicated. Instead of saying "A Turing machine has distinct accepting and rejecting states", you'd have to say "A Turing machine either has distinct accepting and rejecting states, or it has just one state which is either the accepting state or the rejecting state." That's more complex, and it doesn't buy you anything, so people don't do it.

But note that this isn't really an important point. You can perfectly well think of Turing machines with just one state and it won't hurt you in any way, unless you try to write down a formal definition. Any machine that you want to think of as having one state, you can easily rewrite as having two states: just add the second state, which will be inaccessible.

# Answer
> 2 votes
Under most definitions, a Turing machine can have only one state. Maybe the authors of the book wanted to require at least two states because it makes their presentation easier for some reason.

Small details like this are irrelevant when it comes to complexity theory. We are not interested in the "implementation details" of our model of computation.

# Answer
> 1 votes
Possibly you are remembering that, while there are computable functions that cannot be computed by a one-state machine, every computable function can be computed by a machine with two states? (This maybe should be a comment but I lack the reputation.)

# Answer
> 0 votes
There is something to be gotten out of the computation.

Either you interpret the final tape contents (and you stop by the "HALT" command, not by going into an accept state, which you do not have), or you distinguish two states (accept, reject), or stopping means accept (again by HALT, no accept state) and running forever means reject.

The halting problem is decidable in any case. Lit.: Y. Saouter, https://hal.inria.fr/inria-00074105/document

---
Tags: formal-languages, turing-machines
---


# Question
Title: Neural network for PDE: Should we train the PDE using more initial and boundary data at the beginning?
I was trying to solve a partial differential equation (PDE) using a neural network. The solution to the PDE is not unique unless the boundary condition is determined.

In my case, the neural network takes $(x, y)\in \[0, 10\]\times\[0, 10\] = A$ and outputs a scalar. Suppose at the beginning of the training, I only sample from the middle of $A$, which will give us a neural network that satisfies the PDE except for the boundary condition. Then we sample from the boundary of $A$.

My question is, will it be costly to train using the algorithm above? My guess is yes since we have to drag that solution to somewhere else based on the boundary condition, causing large change to the output value. And intuitively, it's better to construct the solution on the boundary first to make the foundation of the solution correct.

I know that we can test it by experiments, but I'm more interested in a theoretical explanation, e.g., why / why not will it be costly to update parameters of the neural network after the boundary data get considered?

# Answer
There is sadly very little theory that is useful for predicting the behavior of neural networks. Also, their effectiveness tends to be dependent on the particular workload/task you are trying to solve it. While I know it's not what you were hoping to hear, I suggest that you try it in empirical experiments.
> 1 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: Which of the following sequences could not be the sequences of nodes examined in a binary search tree?
Suppose that we have numbers between $1$ and $1000$ in a binary search tree and want to search for the number $363$. Which of the following sequences could not be the sequences of nodes examined

```
a) 924,220,911,244,898,258,362,363$

b) 925,202,911,240,912,245,363

c) 2,399,387,219,266,382,381,278,363

d) 935,278,347,621,299,392,358,363

e) 925, 202, 911, 240, 912, 245, 363

```

I know that $d$ and $e$ are not valid sequences, my professor told us so. I know it has something to do the range between jumping from node to node, which has something to do with the following property of **BST's**

Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $y.key \geq x.key$.

I just don't see it, been trying to simulate the path sequence with no clear breakthrough.

# Answer
> 2 votes
Actually the test is quite easy. If you consider the subsequence of numbers greater than the final number $363$, this sequence is supposed to decrease.

Thus, in the case of $e: 925, 202, 911, 240, 912, 245, 363$, the subsequence is $925, 911, 912, 363$ and we see the problem.

Why is that so? If we see a number $x$ larger than the target $363$, we are supposed to move to the left subtree of $x$ where *all* numbers will be smaller than $x$. Thus also all numbers we will see from there will be smaller. As a consequence the numbers larger than $363$ will decrease.

Similarly, the numbers smaller than $363$ will increase. That is why $d$ fails: $278,347,299,358,363$.

# Answer
> 1 votes
I know this is old but in response of @Trey here's the analysis.

We know that in BST you either go to left Subtree$(target \> root)$ or Right Subtree $(target \< root)$. In this process you can say that you will only search values between two ranges that depends on which path you want to proceed.

Here is a short Algorithm to describe it:

> Let CurrentNode be the root and target is the element you want to find.
>
> 1. Initialize MaxValue= INT\_MAX, MinValue=INT\_MIN.
> 2. CurrentNode-\>value should be within \[MinValue,MaxValue\]. If not then it's not BST.
> 3. If CurrentNode-\>value == target you return it.
> 4. Else if CurrentNode-\>value \> target we go to left subtree and update MaxValue = CurrentNode-\>value.
> 5. Else CurrentNode-\>value \< target we go to right subtree and update MinValue = CurrentNode-\>value

Let's convert this algorithm to array of elements (sequence given can be seen as array of elements):

> 1. Initialize MaxValue= INT\_MAX, MinValue=INT\_MIN.
> 2. For each element in sequence :
>
> a. CurrentElement should be within \[MinValue,MaxValue\]. If not then it's not a valid sequence.
>
> b. If CurrentElement == target you it is a valid sequence and end the algorithm.
>
> c. Else if CurrentElement \> NextElement (we go to left subtree) so update MaxValue = CurrentElement.
>
> d. Else if CurrentElement \< NextElement (we go to right subtree) so update MinValue = CurrentElement

Let's run it on $1$ wrong case : $\[ 925, 202, 911, 240, 912, 245, 363\]$

> $Initialize Range = \[-65535,35535\]$ $1. target = 363 , CurrentElement = 925 , NextElement = 202, Range=\[-65535 , 65535\]$
>
> > Here $CurrentElement \> NextElement =\>$ go left $=\> Range = \[-65535,925\]$
>
> $2. target = 363 , CurrentElement = 202 , NextElement = 911, Range=\[-65535 , 925\]$
>
> > Here $CurrentElement \< NextElement =\>$ go right $=\> Range = \[202,925\]$
>
> $3. target = 363 , CurrentElement = 911 , NextElement = 240, Range=\[202 , 925\]$
>
> > Here $CurrentElement \> NextElement =\>$ go left $=\> Range = \[202,911\]$
>
> $4. target = 363 , CurrentElement = 240 , NextElement = 912, Range=\[202,911\]$
>
> > Stop as $CurrentElement$ is outside $=\> Range = \[202,911\]$

---
Tags: data-structures, binary-search-trees
---


# Question
Title: A regular expression for all strings that have exactly one double letter in them?
Why is the answer `(b + /\)(ab)*aa(ba)*(b + /\) + (a + /\)(ba)*bb(ab)*(a + /\)`? I'm confused and I request guidance

# Answer
> 5 votes
It took me a while to understand that your alphabet $\Sigma$ is $\\{a,b\\}$ and by `/\` you meant the empty word $\epsilon$.

Your regular expression is the union of two sub-expression, namely:

* `(b + /\)(ab)*aa(ba)*(b + /\)` ; and
* `(a + /\)(ba)*bb(ab)*(a + /\)`.

The first one (resp. second one) matches all the words that contain exactly one double letter, and that double letter is "a" (resp. "b"). Since the two sub-expression are similar (just swap "a" and "b"), I will only describe the first of the two.

A word $w$ that matches the first sub-expression contains exactly one occurrence of "aa" and no occurrence of "bb", and can then be decomposed as $$w = x \circ \\, aa \\, \circ y,$$ where "$\circ$" denotes concatenation and:

* $x$,$y$ are strings that contain no double letters;
* $x$ does not end with "a" (as otherwise you would have 3 consecutive "a"s in $w$).
* $y$ does not start with "a".

We are then left with the task of finding a regular expression for $x$ and $y$. Let's consider $y$ first. Either $y = \epsilon$, or it must start with a $b$. Moreover, since no two characters in a row can be the same, $y$ is just an alternation of "b"s and "a"s. This can be expressed as $(ba)^\*$ if $y$ has even length (i.e., if it ends with an $a$), and as $(ba)^\*b$ if $y$ has odd length.

Therefore we can write the following regular expression for $y$: $(ba)^\* + (ba)^\*b$ and, by factorizing the common prefix, $(ba)^\*(b+\epsilon)$.

The argument for $x$ is analogous, with the exception that $x$ is either $\epsilon$ or it must *end* with a "b". With a similar reasoning we get: $x = (ab)^\* + b(ab)^\* = (b + \epsilon)(ab)^\*$.

Substituting our regular expression for $x$ and $y$ back into the formula for $w$ we obtain:

$$ w = x \circ \\, aa \\, \circ y = \underbrace{(b + \epsilon)(ab)^\*}\_x \\; aa \\; \underbrace{(ba)^\*(b+\epsilon)}\_y . $$.

---
Tags: automata, finite-automata
---


title: Encoding row types

text:
# Question
Title: Encoding row types
I'm working on a type system with extensible records, similar to ones explained in "A Polymorphic Type System for Extensible Records and Variants - Benedict R. Gaster and Mark P. Jones" and "Extensible records with scoped labels - Daan Leijen",

I already have a working implementation but I followed a completely different path for implementation(for example, I didn't use kinds, instead I used different variables with different types, this also helped me add arbitrary properties to variables, like absent label list). Now I want to implement it like explained in this two papers,

And the problem is, I can't see how can fields and rows with "absent" specifiers can be implemented. Both papers using a simple type constant for record update operations, but types or kinds are not allowing specifying field labels, or absent field names in row variables.

So can anyone help me understand how can field labels and absent fields can be specified in simple kind/type system explained in these two papers?

Thanks in advance.

EDIT: To clarify things,

Here's a language of kinds and types described in papers mentioned above: (in haskell syntax)

```
data Kind = KStar | KRow | KFun Kind Kind

data Type = TCon Typeconstant
          | TVar Typevar
          | TAp Type Type -- type application

```

What I meant to say was I couldn't see a way to encode row types with this language. ie. there is no way to encode type of this function:

```
row_extend r = r.a = 10

```

Because there is now way to tell in types that this function adds or updates 'a field with label `a`'.

I can't give types to record operations in this language(given as Haskell code above).

# Answer
> 2 votes
In the Gaster and Jones paper, rows are encoded using type application of a few type constants, most notably row extension. Your implementation needs to have the following constructors in `Typeconstant`:

```
data Typeconstant = Arrow | EmptyRow | Rec | Var | RowExtension Label

```

Absence of labels is handled using predicates in qualified types:

```
data QualifiedType = QualifiedType [(Type {- where kind is Row -}, Label)] Type
data TypeSchema = TypeSchema [(Typevar,Kind)] QualifiedType

```

Assuming row extension creates a copy of the object, then the type of `row_extend` in your example is

```
forall rec:row. (rec\a) => Rec rec -> Rec {a:int|rec}

```

which would be encoded as

```
rowExtendType = typeSchema where
  typeSchema = TypeSchema [("rec",KRow)] qualifiedType
  qualifiedType = QualifiedType [(TVar "rec", Label "a")] func
  func = TAp (TAp (TCon Arrow) input) output
  input = TAp (TCon Rec) (TVar "rec")
  output = TAp (TCon Rec) (TAp (TAp (RowExtension (Label "a")) (TCon IntType)) (TVar "rec"))

```

---
Tags: type-theory, type-inference, type-checking
---


# Question
Title: Let L be any non-empty language over an alphabet Σ. Show that $L^2$ ⊆ $L^3$ if and only if λ ∈ L
I have this question in my Theoretical Computer Science class on the topic of Automata and Formal Languages.

$$ λ ∈ L \iff L^2 ⊆ L^3$$

I thought of showing it by proving the contrapositive but I was only able to complete half of the proof (since it is a bidirectional proof) and on top of that I am not even sure it is correctly written in a formal form.

I wanted to prove that if

$$λ ∉ L \implies L^2 \nsubseteq L^3$$

But since it is a bidirectional proof, I must also show that

$$L^2 \nsubseteq L^3 \implies λ ∉ L$$

right?

This is what I have so far:

1) $λ ∉ L \implies L^2 \nsubseteq L^3$

$ \lambda \notin L \implies \forall w \in L, n\_o(w) \geq 1$
$ L^2 = L * L \implies \forall w\_2 \in L^2, n\_o(w\_2) \geq 2 $
$ L^3 = L * L * L \implies \forall w\_3 \in L^3, n\_o(w\_3) \geq 3 $
$\forall w\_3 \in L^3 \land \forall w\_2 \in L^2, n\_o(w\_3) \> n\_o(w\_2)$
$ \therefore L^2 \nsubseteq L^3$

So first of all, is this correct?

Secondly, how would I go about showing the second part of my proof where
$$L^2 \nsubseteq L^3 \implies λ ∉ L$$

Thank you!

# Answer
> 1 votes
I'm assuming by $\lambda$ you mean the empty word and by $n\_0(w)$ the length of a word.

The proof for the first part is not correct: You argue that every word in $L^2$ has length at least $2$ and every word in $L^3$ has length at least $3$. From that it does not follow that every word in $L^3$ is longer than every word $L^2$, because there could also be a word of e.g. length $3$ in $L^2$. Consider for example $L = \\{a\\}^\star \setminus \\{ \lambda \\}$, that is, the set of all non-empty $a$-sequences. You have $a \in L$ and $aa \in L$, thus $aaa = a \cdot aa \in L^2$, but also $aaa = a \cdot a \cdot a \in L^3$.

Instead, what you want to say is that there is a word of minimal length $n$ in $L^2$, and because every word in $L$ has length at least one, the shortest word in $L^3$ has length at least $n+1$.

More formally: Let $\lambda \notin L$. Thus $\forall w \in L: n\_0(w) \> 0$. Pick $w \in L^2$ such that $n\_0(w)$ is minimal. Assume $w \in L^3$. Since $L^3 = L^2 \cdot L$, it follows that $w = u \cdot v$ for $u \in L^2$ and $v \in L$. Since $n\_0(v) \> 0$, it follows $n\_0(w) \> n\_0(u)$. But then $n\_0(w)$ is not minimal. Contradiction.

For the second part: Assume $L^2 \not \subseteq L^3$ and $\lambda \in L$. Thus there is $w \in L^2$ such that $w \notin L^3$. But since $L^3 = L^2 \cdot L$, it follows $w = w \cdot \lambda \in L^3$. Contradiction.

# Answer
> 0 votes
Let w be the shortest word in L with length l. Then the shortest word in $L^2$ has length 2l, but the shortest word in $L^3$ has length 3l. If l ≥ 1 then the sets are different.

Now assume L contains the empty string. $L^3$ is the set of all strings that can be created by taking an element of $L^2$ and adding an element of L. Among many others, this includes all strings that can be created by taking an element of $L^2$ and adding the empty string - which is all the elements of $L^2$.

---
Tags: formal-languages
---


# Question
Title: How to sort a large list of elements where everything is sorted but k elements?
Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?

# Answer
Here is an $O(k \log k + n)$ Algorithm. Assuming we are dealing with an ascending order. We assume $A$ is a linked list, an hence removing elements can be done in constant time. Given an array instead, we can preprocess it in linear time building a linked-list out of it.

```
Let A be a given list of n elements.
Let B be an empty array.
For x in A do
- Let y be the element following x.
- As long as y < x then
- - Add x to B.
- - Add y to B.
- - Remove x from A.
- - Remove y from A.
- - If x was the first element,
- - - then break from the inner loop.
- - Set x to the previous element of x.
- - Set y to the following element of y.
Sort B with any efficient sorting algorithm.
Unify A and B in the array C efficiently.
Return the array C.

```

If an element $x$ is greater than the following element $y$, then at least on of them must be one of the $k$ elements, because else they must be sorted. Hence, we do not remove more than $2k$ elements from $A$. Since with each visit of the inner-loop except for the last one, we remove two elements from the array, and since we do not remove in total more than $2k$ elements, the total number of visits of the inner loop is at most $2k+n$. The size of $B$ is at most $2k$, since it only has the elements removed from $A$. Using quick-sort, we can sort $B$ in running time $O(k \log k)$ (note that $B$ is an array and not a list). Unifying two sorted arrays/lists in a new sorted list can be achieved in linear time using sliding-window. The total running time is $O(n + 2k + k \log k + n + k) = O(k \log k + n)$.
> 2 votes

# Answer
If you start with a sorted array, and then k array elements are modified, the best would be to keep track of the array indices of the modified elements as they are modified, extract them into a separate array and sort them, then merge both arrays.
> 0 votes

---
Tags: algorithms, sorting, arrays
---


# Question
Title: I want to know where there is the flaw in my argument
I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable.

$L: \\{\langle M\rangle: M\space is\space a\space TM\space and\space |L(M)| \ge3\\}$

Now thinking intuitively I conjectured that this language is semi-decidable. We can say yes when the input does belong to $L$. But, we can not say no when the input does not belong to $L$.

Now, I formulated following reduction from complement of halting problem $\overline{HP}$ which is not semi-decidable (non $RE$).

$\overline{HP}: \\{\langle M, w\rangle : M\space is\space TM\space and\space it\space does\space not\space halt\space on\space string\space w.\\}$

$\tau(\langle M,x\rangle) = \langle M'\rangle$.

$M'$ on input $w$ works as follows. It erases w, puts $M$ and $x$ on its tape, and runs $M$ on $x$ and accepts if $M$ doesn't halt on x. Otherwise it rejects.

---

Proof of validity of reduction:

$\langle M,x\rangle \in \overline{HP} \implies M\space does\space not\space halt\space on\space x \implies M'\space accepts\space all\space inputs\space \implies|L(M')| \ge 3\implies M' \in L$

$\langle M,x\rangle \notin \overline{HP} \implies M\space does\space halt\space on\space x \implies M'\space rejects\space all\space inputs\space \implies|L(M')| \< 3\implies M' \notin L$

---

According to above reduction $\overline{HP}$ should be recursively enumerable$(RE)$ which it is not. So, $L$ should not be $RE$ but it indeed is $RE$. So, my reduction must be flawed.

Please point out where I messed up.

# Answer
> 0 votes
> accepts if $M$ doesn't halt on $x$

That's not something a Turing machine can do in general: informally, keep in mind that accepting has to happen at some finite stage while we can't in general tell that a program isn't going to halt in finite time (which is why HP is undecidable).

Your $M'$ is implicitly treating a co-r.e. event (non-halting) as r.e. (so that it can wait for it to occur and, when it does, halt and accept).

---

It's worth noting that we can do this *with $HP$ as an oracle*, and this shows (correctly) that $L$ is r.e. over $HP$. But we have to be careful about what exactly that means. At first glance we might think that "r.e. over $HP$" implies r.e., since $HP$ itself is r.e., but when a set is presented as an oracle we get *both* positive and negative information about it. So r.e. over $HP$ \- that is, the domain of some $HP$-computable partial function - is not the same as r.e.: for example, $\overline{HP}$ is r.e. over $HP$.

This is a good example of how we have to keep track of the various different reducibilities we might be using, with the relevant ones here being Turing versus many-one: in the context of this question we're interested in many-one reductions but oracles correspond to Turing reducibility.

---
Tags: turing-machines, reductions, undecidability, halting-problem
---


# Question
Title: Advantage of Stack-Based Allocation for Local Variables
While learning stack allocation, I came across this paragraph in the textbook (Programming Language Pragmatics - 3rd Edition):

> Even in a language without recursion, it can be advantageous to use a stack for local variables, rather than allocating them statically. In most programs the pattern of potential calls among subroutines does not permit all of those subroutines to be active at the same time. As a result, the total space needed for local variables of currently active subroutines is seldom as large as the total space across all subroutines, active or not. A stack may therefore require substantially **less memory** at run time than would be required for static allocation.

I would appreciate if anyone could explain how stack allocation would save memory when used for allocating local variables. I tried reading this many times. But I can't understand the author meant.

# Answer
Consider the following program:

```
f1();
f2();

```

If local variables are allocated statically, there's a space in memory that's reserved for the local variables of `f1`, and a separate space for the local variables of `f2`. If `f1` needs $n\_1$ bytes of memory for its local variables and `f2` needs $n\_2$ bytes, the program above needs $n\_1 + n\_2$ bytes.

If local variables are allocated on a stack, the same stack space is first used for the local variables of `f1`, then reused for the local variables of `f2`. The program only needs $\max(f\_1, f\_2)$ bytes of memory.

With more functions in a program, the amount of static memory grows linerarly with the number of functions and the size of their local variables. The amount of stack memory only grows as fast as the depth of the call chain.

In addition, static allocation does not permit recursion or concurrency: if `f1` is already active, you can't invoke it again since the second invocation would overwrite the local variables used by the first invocation. Stack allocation does.

Stack allocation has been standard practice since the very early days of computers.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: Concrete example of Vertex Cover to Subset Sum reduction
In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem, mostly to prove Subset Sum is NP-Complete. I also see a reduction in the line of - ***A graph G has VC of size k if and only if there is a subset S that sums exactly to t***. However, not able to find out (understand) exactly what is this t. I think providing a concrete example will help many like me. Request any one to provide a concrete graph with |VC| 3 or something manageable, and then show exact value of t i.e. what would be the exact instance of subset sum problem. Finally, explaining/clearly mentioning elements of S would be of great help.

# Answer
> In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem...

We do?

> ... mostly to prove Subset Sum is NP-Complete.

There's no particular reason to go down that route. Karp \[1\] defined the Knapsack problem as: given $a\_1, \dots, a\_r, b\in\mathbb{Z}$, is there a set $S\subseteq \\{1, \dots, r\\}$ such that $\sum\_{i\in S}a\_i=b$? This is one variant of what is now called Subset Sum. If you prefer to define Subset Sum such that $b$ is always zero, we'll come back to that in a minute.

Karp shows that Subset Sum is **NP**-complete by the chain of reductions $$\text{SAT}\leq \text{3SAT} \leq \text{Chromatic Number}\leq\text{Exact Cover}\leq\text{Subset Sum}\\,.$$ In particular, the reduction from Exact Cover to Subset Sum produces an instance where the $a\_i$'s and $b$ are all positive so, if you want to define Subset Sum as "is there a subset whose total is zero?", you can set $a\_{r+1}=-b$.

Since Subset Sum and Vertex Cover are both **NP**-complete, there is clearly a reduction between them. However, you shouldn't expect that there's a "nice" reduction where a small VC instance naturally transforms into a small Subset Sum instance that makes you say, "Aha, now I understand." And that applies to most pairs of **NP**-complete problems. In complexity theory courses, we teach the simple, intuitive reductions, usually between problems that are somehow similar, or between SAT or 3SAT and a problem that isn't about Boolean formulas. That can give the impression that there's a natural reduction between any pair of **NP**-complete problems; in reality, there usually isn't.

---

\[1\] Richard M. Karp, *Reducibility among combinatorial problems*. In *Complexity of Computer Computations*, Plenum Press, 1972. (PDF)
> 4 votes

---
Tags: np-complete, reductions, polynomial-time-reductions
---


# Question
Title: Decidability of the language of all deterministic LBA where all states are reachable
I have a exam task with 3 parts. (b) is no problem. I got a solution for (a) but the way (c) is asked makes me wonder if I even understood (a)

*(a)* L := { \< A \> | A is a DFSA, where all states are reachable }. Is L decidable? Why or why not?

*(b)* M is a DLBA and k is the input length. There exists a function g(M,k) which returns the maximum number of steps a DLBA can possibly do, which halts on an input the size of k. Why?

*(c)* L' := { \< M \> | M is a DLBA, where all states are reachable }. Show that L' is **semi-decidable**. Use g(M,k) from (b)

---

**My solution:**

(b) Limited amount of configurations. I get that.

For example how I understand (a): L is a language and every word of L is the encoding of a FSA. But only FSAs where every state can somehow be reached from the starting state or is the starting state.

So is it decidable?

My answer: Yes, for any word w you could check if its a valid FSA-encoding, if not: reject, if it is: Construct a FSA from this encoding and check if you can reach all states like this:

```
Mark the starting state;
Repeat until no new marked states:
   Mark all states you can reach from the marked states.
Check if all states are marked.
Reject or Accept

```

**My Question:**

Is (c) just semi-decidable and how do I use g(M,k) to show this? Because I would think I could solve (c) exactly like (a) and show that it is decidable (which would mean it is also semi-decidable)

**Edit:** Hi, if you give me a downvote I would appreciate a comment on how to improve my questioning. I know it is a long post but I just try to lay out how I understand questions like this to be solved so you can correct me if I have key misunderstandings. I now reduced the amount of questions I asked and the length of my post.

# Answer
> 0 votes
After days of constantly refreshing this page in hope for an answer today I woke up and my very first thought might be it.

If all states are reachable and it is deterministic this means there has to be a set of inputs where every state will once be reached.

semi-decidable Algorithm:

```
Validate if DLBA-Encoding and reject if not;     # returns 'no' on bogus
k = 0;
Repeat until every state has been at least once been reached {
   For every possible input w for the DLBA of the length of k {
      Simulate DLBA with w for g(M,k) steps while keeping record of the reached states;
   }
   k++;
}
return 'yes'

```

It will accept if all states are reachable

It will reject if not a valid DLBA-Encoding

It will run forever if valid DLBA but not all states are reachable

I figured out, that DLBAs can have states where there are a series of transitions leading from the starting state to those but they still can never be reached. So just looking at transistions isn't enough

---
Tags: formal-languages, semi-decidability, linear-bounded-automata
---


# Question
Title: Are models of computation closed under composition?
It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^\*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or concatenation, or the Kleene star. And those questions seem natural to me, because they're essentially questions about the power of a model of computation that can decide precisely the languages in $C$. However, it seems just as natural to me - perhaps even more natural - to ask whether such a class is also closed under composition.

Here's what I mean by that. If I fix some subset $\mathcal{C} \subseteq \mathcal{P}(\Sigma^\*)$ of "decidable" languages relative to some model of computation, for any (finite) $\Sigma$, then I have also fixed some subset $\mathcal{F} \subseteq B^A$ of computable functions, for any languages $A, B$ \- because each function $f : A \rightarrow B$ can be viewed as a function $\bar{f} : A \times B \rightarrow \\{0, 1\\}$. Given that, I would expect that for any reasonable model of computation, if $f : A \rightarrow B$ and $g : B \rightarrow C$ are computable, then $g \circ f : A \rightarrow C$ should be as well. Put in terms of the corresponding languages, I'd expect that if $L\_f = \\{(a, b) \in A \times B : f(a) = b\\}$ and $L\_g = \\{(b, c) \in B \times C : g(b) = c\\}$ are decidable, then $L\_{g \circ f} = \\{(a, c) : \exists b \in B s.t. f(a) = b \wedge g(b) = c\\}$ should be decidable as well.

This seems to me like a natural question to ask of any class of languages. Is it in fact a reasonable question? If not, why? If it is, is there a better way to frame it, one that would make it more clear what we're demanding?

# Answer
> Given that, I would expect that for any reasonable model of computation, if $f : A \rightarrow B$ and $g : B \rightarrow C$ are computable, then $g \circ f : A \rightarrow C$ should be as well.

Let's say our model is quadratic time computation. If $f$ is the function which maps a string of length $n$ to a string of $n^2$ zeroes, then $f$ is computable in our model, but $f\circ f$ is clearly not.

> I'd expect that if $L\_f = \\{(a, b) \in A \times B : f(a) = b\\}$ and $L\_g = \\{(b, c) \in B \times C : g(b) = c\\}$ are decidable, then $L\_{g \circ f} = \\{(a, c) : \exists b \in B s.t. f(a) = b \wedge g(b) = c\\}$ should be decidable as well.

This is a bit of a weird definition since $L\_f$ can be much easier than $f$ (e.g., let $f(a)$ be the function that outputs a prime factorization of $a$). $F\_l$ is poly-time while it is not known that $f$ is. Let's make $f$ also take an additional input $i$, and then let $f(a,i)$ output the number $i$ together with a factorization of $a$. If we then make $g$ output the $i$th bit of the factorization we end up with $L\_f$ and $L\_g$ being poly-time computable but $L\_{f\circ g}$ being as hard as factorization.
> 1 votes

---
Tags: formal-languages, computability, closure-properties
---


# Question
Title: Reducing from NPC to Co-NPC => NP = Co-NP?
In my lecture we learned:

`If X is NPC and X in Co-NP => NP = Co-NP`

Would it be enough to prove `NP = Co-NP` if I reduce a problem just in one direction (from NPC to Co-NPC) in polynomial time?

Or would it be necessary to show this for both directions?

# Answer
> 1 votes
# In short

yes

# Proof

Let's assume $X$ is NP-complete and $X$ is in co-NP.

We show that $NP \subseteq coNP$ and viceversa.

## \[$NP\subseteq coNP$\]

Because $X$ is NP-complete $=\>$ for each $L\in NP$ we can found a polytime function $f$ that $s\in L$ iff $f(s)\in X$.

But $X$ is in coNP $=\>$ for the *polityme reduction closure* of coNP, $L\in coNP$ too $=\>$ $NP\subseteq coNP$

## \[ $coNP \subseteq NP$ \]

let $B\in coNP$ $=\>$ $B^c \in NP$ $=\>$ $s\in B^c$iff $f(s)\in X$ $=\>$ $s\in B$ iff $f(s) \notin X$ $=\>$ $s\in B$ iff $f(s) \in X^c$

but because $X \in coNP$ $=\> X^c \in NP$ and for *polityme reduction closure* of $NP$ $=\> B \in NP$ $=\>coNP\subseteq NP$

So $NP=coNP$ under this assumptions.

# Answer
> 0 votes
Ok I think I got it know.

If I could reduce a NP-complete problem to a coNP-complete problem every problem in NP can be reduced to every coNP-complete problem and it would show that NP is a subset of coNP.

Because every problem A in coNP has a complement co\_A in NP

A in coNP =\> co\_A in NP =\> co\_A in coNP =\> A in NP

=\> every Problem in coNP is in NP

=\> NP = coNP

If there is a NPC problem that can be reduced to coNPC =\> NP = coNP

**Edit:** I wrote this while the other answer was given

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Maximize Reward with Cost Limit in a Fully Obserable Environment
I recently encountered a coding interview question which is broken down as follows.

You are given an array **N** which consists of pairs **n** which consist of a reward and a cost.
You are also given **m** which is the maximum cost you can incur.

Find the subset of **N** in which the sum of the reward is maximized and the sum of the cost does not exceed **m**.

# Answer
This is the Knapsack Problem in disguise. It is an NP-hard problem so do not expect a polynomial time algorithm. However, it has a pseudopolynomial time algorithm (it is polynomial in the instance size and value of the biggest occurring number) and thus has a FPTAS.

Your comment describes a 2-approximation of the problem if you take the maximum of "your solution" and the biggest reward.
> 1 votes

---
Tags: algorithms
---


title: How to prove NP-hardness from scratch?

text:
# Question
Title: How to prove NP-hardness from scratch?
I am working on a problem of whose complexity is unknown. By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use.

Finally, I have decided to go for the most primitive method -- Turing Machines.

Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might've messed up with the terminology here).

So, assuming that there are no problems to perform an NP-hardness reduction, how does one prove that a problem is NP-hard? Are there any publications that does this?

I also want to add that I know how to perform an NP-hardness reduction. However, the problem that I am tackling is a "localized" geometric problem, that it does not allow me to model any given instance of 3SAT, 3-coloring, vertex cover, etc.

The immediate question comes to mind: "what if the problem is polynomial time solvable?"
Well, that is also a possibility, but I want to exhaust everything before I move onto designing an algorithm.

# Answer
The only two methods I've seen are (a) a reduction or (b) direct proof (as in the proof of the Cook-Levin theorem). It is almost universally the case that a reduction is easier than a direct proof. Therefore, I suggest you keep trying to find a reduction, and consider other reduction partners. There are lots and lots of problems known to be NP-complete; perhaps you can find one that is a more suitable partner than 3SAT.

Possibly useful: How do I construct reductions between problems to prove a problem is NP-complete?.
> 4 votes

# Answer
> Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might've messed up with the terminology here)

That's not odd at all: it's because no such proof exists. Anything that can be computed can be computed by a deterministic Turing machine. Any proof that no *polynomial-time* deterministic Turing machine can decide some problem in $\text{NP}$ would constitute a proof that $\mathrm{P}\neq\mathrm{NP}$, resolving the biggest open problem in computer science. There are proofs that polynomial-time deterministic Turing machines can't decide certain classes of $\text{NP}$-hard languages: see the time hierarchy theorem. However, if $\mathrm{P}\neq\mathrm{NP}$ then, it is a consequence of Ladner's theorem that there are problems that cannot be solved by polynomial-time deterministic Turing machines but which are not $\text{NP}$-hard.

To me, the fact that you considered this as an approach, and that you think there are no problems to reduce from (as distinct from no *convenient* problems), suggests that you don't fully understand what $\text{NP}$-hardness is. I suggest you check out our reference question on the subject.
> 3 votes

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


# Question
Title: How to generate Deterministic finite automaton for given language
**Problem:** Write a program which generates Deterministic finite automaton which accepts given language. Language is defined with alphabet and start/end sub strings.

For example: Alphabet={a,b,c}; start sub string="ab"; end sub string="cb"

I need to construct DFA which will accept strings of kind: {abcb, abaacb, abcabcb...}.

**Question:** What algorithm should I use to write function which will construct DFAs for this set of problems.

# Answer
First, you have to build the regular expression recognizing your language $L$. It should look like this where $p\_1,...,p\_k$ are the start sub strings and $s\_1,...,s\_l$ are the end sub strings and $\Sigma$ is your alphabet: $(p\_1 | ... | p\_k) \Sigma^\* (s\_1 | ... | s\_l)$

In your example, your regular expression is $ab \Sigma^\* cb$. Using the Thompson construction, you get a NFA that accepts $L$. This can be transformed into a DFA with the power set construction. As a last step you could minimze the DFA if necessary.

I am not sure if there would be a benefit to use a specialized construction, especially since all the algorithms mentioned above have been implemented and optimized for quite some time.

By the way, a "start substring" is called a *prefix*, the "end sub string" *suffix* and a "substring" *infix* in automata theory.
> 0 votes

---
Tags: algorithms, automata, finite-automata
---


# Question
Title: Books on finite languages and automata theory with examples, problems and solutions
Can you suggest me a good book with illustrative examples and problems with solutions for finite languages and automata theory?

I tried Hopcroft's but it has mostly theory and not many problems with solutions.

Thanks! :)

# Answer
> 2 votes
Try this question to get an idea. I think the classical ones at universities are the one from Sipser and Hopcroft's one. For Hopcroft I would really look for the old version if you are mathematically inclined. They removed a lot of proofs in new versions.

For specific examples of problems you'll get solutions here and there over the Internet. It is good not to have a straight look to the solution and having the solution very near can be very tempting at times.

While looking for books to get an idea of what's on them I like this Internet library. Then you can always buy the book on paper or borrow it from your University library.

Hope this helps.

**Some books with solutions: (under construction)**

Hopcroft's et alii. solutions to their book.

Apparently, Sipser's book contains solutions after each chapter.

# Answer
> 1 votes
Here are some which contains more solved examples :

1. An Introduction to Formal Languages and Automata by Peter Linz.
2. Automata and Computability by Dexter C. Kozen.

# Answer
> 0 votes
I know its been a while since this question has been asked, but I think that ***Problem Solving in Automata, Languages, and Complexity by Ding Zhu Du*** is the best book for, surprisingly, *problem solving*!

It contains plentiful examples for DFA, NFA, using pumping lemma to prove irregularity, proving regularity of weird languages which seem to be irregular and complicated!

Its available as PDF for free on internet, I hope it's legal!

---
Tags: automata, finite-automata
---


title: Unique property of a full binary tree

text:
# Question
Title: Unique property of a full binary tree
I read a statement that was unclear to me, and was hoping to get some clarification.

It said that given a full binary tree with $n \> 2$ leaves, there exists some internal node such that one third to two thirds of all $n$ leaves in the tree are its descendants.

From my understanding, I know each internal node in a full binary tree has 2 children. That said, the whole tree has $2n - 1$ nodes, which means $n - 1$ of them are internal nodes (not leaves).

I can come up with drawn examples where this is always the case, but I am not sure how to formally reason it. Any help would be greatly appreciated.

# Answer
> 1 votes
Let $T$ be a tree rooted at $r$ with $n \> 2$ leaves, and let $\ell(u)$ denote the number of leaves in the subtree of $T$ rooted at node $u$.

Initially let $v=r$, then proceeds as follows:

1. If $\ell(v) \le \frac{2n}{3}$ then return $v$.
2. Otherwise, let $u$ be one of the children of $v$ with the largest $\ell(u)$, set $v=u$ and repeat from the first step.

Notice that, for every $v$ considered by the algorithm:

* $v$ is not a leaf (hence step 2 is well-defined). If $v$ were a leaf, then the parent $w$ of $v$ (which always exists) would satisfy: $2 \le \frac{2n}{3} \< \ell(w) = 2 \ell(v) = 2$, a contradiction.
* $\ell(v) \> \frac{n}{3}$. This is clearly true when $v=r$. For $v \neq r$, let $w$ be the parent of $v$. Since $\ell(w) \> \frac{2n}{3}$, we must have $\ell(v) \ge \frac{\ell(w)}{2} \> \frac{2n/3}{2} = \frac{n}{3}$.

The algorithm must terminate (at each iteration the depth of $v$ increases), therefore the returned vertex $v$ is not a leaf and satisfies both $\ell(v) \> \frac{n}{3}$ (by the above property) and $\ell(v) \le \frac{2n}{3}$ (by the condition of step 1).

This proof is constructive and shows that $v$ can be found in $O(n)$ time (you can find all the values $\ell(v)$ with a postorder visit).

---
Tags: graphs, data-structures
---


# Question
Title: Is it true that for every genetic algorithm there exists a non-genetic algorithm that achieves the same results more efficiently?
And if it is not true, what are the problem classes or characteristics for which genetic algorithms are superior?

# Answer
What you might have heard could have been a formulation of a No Free Lunch Theorem. Loosely, those results say that you can either have an optimization algorithm that does fairly well on many problems, or really well on some problems, but not both.

Genetic Algorithms are rather broad classes of optimizers, so you can typically apply them to many types of problems with decent results, but for specific problems there will typically be more efficient algorithms that only work for this type of problem.
> 3 votes

---
Tags: efficiency, genetic-algorithms
---


# Question
Title: Runtime complexity of a brute force factoring algorithm? (in terms of bits)
Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the asymptotic running time for the brute force factoring algorithm?

# Answer
It is $(\lfloor \sqrt{N} \rfloor-1) \cdot O(n^2) = O(\sqrt{N} \log^2 N) = O(2^{\frac{n}{2}} n^2)$ in the worst case: for each of the $O(\sqrt{N})$ choices of the dividend you perform a division of two numbers of at most $n$ bits.

(When you factor $N$ you might repeat some of the divisions, but these can be safely ignored since there can be at most $n$ repeated divisions, for a total complexity of $O(n^3) = o(2^{\frac{n}{2}} n^2)$.)

Notice that this is the best bound we can get for your question under reasonable hypotheses. Indeed, if the complexity of dividing two n-bit numbers is also $\Omega(n^2)$ and you apply the brute-force algorithm on a prime $N$:

$$ \sum\_{i=2}^{\lfloor \sqrt{N} \rfloor} T(\log N, \log i) \ge \sum\_{i=\lceil \sqrt{N}/2 \rceil}^{\lfloor \sqrt{N} \rfloor} T\left(\frac{1}{2}\log N - 1, \frac{1}{2}\log N - 1\right) = \Omega(\sqrt N) \cdot \Omega(\log^2 N) = \Omega(\sqrt{N} \log^2 N), $$

where $T(i,j)$ is the time it takes to divide a $i$-bit integer by a $j$-bit integer and I am assuming that $T(i,j)$ is non-decreasing w.r.t. $i$ and $j$.
> 1 votes

# Answer
Dividing a 128 bit number by a 64 bit number can be done in constant time. If N is a prime that doesn't fit into 128 bit then the algorithm won't finish in your life time :-) Dividing two n bit integers can be done in O (n log n) for large n.

But assuming that you use brute force division that *does* use $O (n^2)$ operations for a division, then you should just ask yourself how many divisions you will perform in the worst case (N is prime or the product of two primes close to $N^{1/2}$), and multiply by the number of operations per division.

You also need to be a bit more careful with the description of your algorithm: 121 is not divisible by any integer between 2 and the square root of 121. Similar, 86 is not divisible by any integer between 2 and the square root of 86.
> 0 votes

---
Tags: complexity-theory, time-complexity, asymptotics, factoring, big-o-notation
---


# Question
Title: What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element?
Consider the recursive `quick sort` with `random pivoting` i.e. each time a random pivot element is chosen uniformly. When this randomized algorithm is being applied to an array with `n` distinct element, what is the `probability` that the `smallest` and the `greatest` element will be `compared` during run of the algorithm.

# Answer
> 1 votes
It is $2/N$ : the probability of picking the smallest or the biggest as pivot. If you choose one of them, they will be compared. If you choose any other, then the smallest and the biggest elements will be put in different partitions, and thus will not be compared.

---
Tags: algorithms, sorting, randomized-algorithms, quicksort
---


title: Is LOG(L) Regular?

text:
# Question
Title: Is LOG(L) Regular?
For a language L $\subseteq$ $\Sigma$* , define LOG(L) = { u $\epsilon$ $\Sigma$* | $\exists$ v s.t. |v| = $2^|$$^u$$^|$ and uv $\epsilon$ L}. Show that if L is regular so is LOG(L).

---

I was trying to come up with some finite state automaton for LOG(L) but can't find any. Please give some hint.

# Answer
> 0 votes
Yes, it is regular. It is complicated.

Create an FSA for L.

For each pair of states (Si, Sj) find the set of possible counts of symbols that could lead from Si to Sj. This set can be described in a finite way, it has the form of some constants ci, plus if there is a cycle involved, n\*k + di for some fixed k and some constants di, and all n ≥ 0. Example: If you can get from state S3 back to S3 with a cycle of length 3 and another cycle of length 5, then the number of symbols processed is (0, 3, 5, 6, n\*1 + 8).

For each state Si, find the possible set of possible counts of symbols that could reach an accepting state.

Since we accept strings of length k when L contains a string of length k + 2^k, we can now determine the possible numbers of symbols processed to enter state Si, which would lead to an accepted string of length k + 2^k.

So we have the same FSA, but it needs to accept a string in state Si if we have entered Si with the right number of symbols.

We then modify the FSA so you can enter a state Si only with the right number of symbols, and that's it.

---
Tags: automata, regular-languages
---


# Question
Title: General algorithm to find a minimal branching program
Given a general branching program, is there an algorithm which can find an equivalent branching program $P$ of minimal length. That is $|P| \leq |P'|$ for all equivalent branching program $P'$.

If not, are their some specific cases where this algorithm exists?

# Answer
> 1 votes
I'm assuming you mean branching programs in the sense of generalized binary decision diagrams (see here).

Now the question is whether by "length", you mean "size" or "depth". I will answer the "size" version here, as you will most likely mean that (and the depth version has some intricacies).

We can represent a smaller solution in space not larger than the input size. Furthermore, checking two branching programs to be equivalent is a problem contained in the complexity class co-NP.

Hence, we can define an algorithm in $\Sigma^P\_2$ (see here) for finding if there exists a smaller equivalent branching program by letting it first *guess* a smaller solution, and then *verify* it to be correct using the co-NP equivalence checking oracle.

Note that this may not be an algorithm that is complexity-theoretically optimal. However, the existence of this algorithm answers your question with a "yes".

---
Tags: finite-automata
---


# Question
Title: How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?
Consider cellular automaton rules for a two-dimensional universe with two states, where a cell's new state can depend on its previous state and the states of the cells in its Moore neighborhood. Such a rule can be modeled as a function that takes as input a 3 by 3 matrix of bits, and outputs a bit.

Such a rule can be represented easily using a string of 512 bits representing the output for each of the $2^{3 \times 3}$ input states. Since this representation is bijective, a rule can also be randomly generated by sampling 512 bits.

However, it is sometimes preferable for reasons of aesthetics and comprehensibility that the output of the rule be the same when the input matrix is rotated or flipped horizontally or vertically. The rule for Conway's Game of Life is an example of a function satisfying this restriction.

Given a function $r : 2^9 \to 2$ which does not necessarily obey this restriction, we can obtain a function that does by mapping the input to the lexicographically smallest matrix obtainable by reflecting or rotating it before passing to $r$. However, this provides little insight into the questions I am interested in:

* How many functions obey this restriction?
* How can they be compactly representing using a bit string?
* How can they be efficiently randomly generated?

# Answer
> 1 votes
I won't go into the details of your specific case but try to answer the general problem.

In the unrestricted case there is a mapping from each of the $n$ (=512) input states to one of 2 output states and you want to restrict the function as follows:

* Create a partitioning of the initial $n$ input states into subsets.
* Your adapted function maps each of these subsets to an output

Proceed as follows:

* Enumerate all input states from 1 to $n$ (this is then the index of that state)
* Write a function $f(i)$ that generates all rotations/symmetric versions of an input state $i$ and take the lowest index of that set
* Partition the set $1..n$ according to $f$, i.e. if $f(x) = f(y)$, they are in the same class. The result is a pairwise disjoint set of sets, where each set consists of 'similar' input states that should therefore also have the same output.
* Let $P$ be the number of these sets.

Answering your questions should then be easy:

1. You could assign each of the $P$ sets an arbitrary output to get a unique function. $\Rightarrow 2^P$ functions
2. A bitstring of length $P$
3. Generate random integers (with more than $P$ bits each) and take the last $P$ bits.

a. Maybe consider the distribution of values generated by your RNG, i.e.: are the last $P$ bits uniformly (or whatever you desire) distributed?

# Answer
> 1 votes
You seem to be looking to enumerate (and/or randomly sample from) the set of isotropic two-state two-dimensional cellular automata on the Moore neighborhood.

The general way to this is simply to find all the equivalence classes of the $2^{3\times3}$ possible neighborhoods, where two neighborhoods are considered equivalent if one can be transformed into the other by rotation and/or reflection. Your rule will then be a function from the set of these equivalence classes to the set of single cell states, and the number of such rules (for a two-state automaton) will be $2^N$, where $N$ is the number of these equivalence classes.

As far as I know, there's no obvious "elegant" way to find these equivalence classes other than by a brute force exhaustive search. Fortunately, this tedious work has already been done, and a list of all the $2 \times 51$ equivalence classes can be found e.g. on the wiki page I linked to above.

The page also describes a compact and somewhat human-readable notation developed by Alan Hensel for describing such rules, based on describing each equivalence class using the number of live cells in it (excluding the center cell) and a more or less arbitrary letter denoting the specific configuration of those cells, as shown in the table on the linked wiki page, and quoted below:

For example, using this notation, the rule string `B2-a/S12` describes a rule where dead cells become alive if they have exactly two live neighbors *and those neighbors are not adjacent*, and live cells survive if they have one or two live neighbors in any configuration.

Several programs used for simulating and/or searching for patterns in Game of Life -like cellular automata, such as Golly, can parse rule strings in this notation.

---
Tags: data-structures, optimization, matrices, cellular-automata
---


# Question
Title: How can I show this language is Regular? (Foundations of computing)
Σ(alphabet) contains 3x1 column matrices \[\[0\],\[0\],\[0\]\], \[\[0\],\[0\],\[1\]\] , \[\[0\],\[1\],\[0\]\]... \[\[1\],\[1\],\[1\]\] such that each element in the language is a THREE SET of the columns where the bottom row is the sum of the two top rows

example \[\[0\],\[0\],\[1\]\], \[\[1\],\[0\],\[0\]\] , \[\[1\],\[1\],\[0\]\] is an element of the Language

BUT

\[\[0\],\[0\],\[1\]\], \[\[1\],\[0\],\[1\]\] , \[\[0\],\[0\],\[0\]\] is not an element of the language.

# Answer
Your question was already asked before, but got no answer: How to prove for string of triplets that it is a Regular Language?. I merely summarize the comments given there.

You need to implement binary addition. That is easier when you consider first the language in reverse, the lower bits first.

Standard letters are (in a more intuitive notation) \[00|0\], \[01|1\], \[10|1\], \[11|0\]. In the last case however, we realize that we should take a carry to the next position. This can be solved by adding a special state for that case, and adapting the letters accordingly.
> 2 votes

---
Tags: automata
---


# Question
Title: Concatenate multiple integer arrays such that number of inversions in resulting array is minimal
Given `N` arrays of variable length.

Find a way to concatenate the arrays in such a way that the number of inversions is minimum

An inversion for an array Arr can be defined as,

a pair of indices `(i,j)` such that,

```
i != j

i < j

Arr[i]>Arr[j]

```

I tried to concatenate the arrays on the basis of sum, such that the one with minimal sum goes first and one with maximal sum goes last.

It didn't work out though.

Example:-

```
[14, 18, 18, 20, 16, 6, 11] SUM:- 103

[2, 4, 11, 40, 20, 14, 19] SUM:- 110

[14, 18, 18, 20, 16, 6, 11, 2, 4, 11, 40, 20, 14, 19] Inversions:- 42

[2, 4, 11, 40, 20, 14, 19, 14, 18, 18, 20, 16, 6, 11] Inversions:- 40

```

# Answer
As an exercise to the reader, two lemmas:

> **Lemma 1.** If $a, b$ are strings of symbols with a partial order, and $\text{numinv}$ counts the number of inversions in a string of symbols then $$\text{numinv}(ab) = \text{numinv}(a) + \text{numinv}(b) + \text{crossinv}(a, b)$$ where $$\text{crossinv}(a, b) = |\\{(i,j) \in \\{1,\dots,|a|\\}\times\\{1,\dots,|b|\\} \mid a\_i \> b\_j\\}|.$$
>
> **Lemma 2.** $\text{crossinv}$ has the distributive property over concatenation, that is for strings $a, b, c$ we have
>
> \begin{align} \text{crossinv}(a, bc) &= \text{crossinv}(a, b) + \text{crossinv}(a, c)\\ \text{crossinv}(ab, c) &= \text{crossinv}(a, c) + \text{crossinv}(b, c). \end{align}

You can use the above two lemmas repeatedly to generalize, and see that for a tuple of strings $(x\_1, \dots, x\_n)$

$$\text{numinv}(x\_1x\_2\dots x\_n) = \sum\_{i=1}^n \text{numinv}(x\_i) + \sum\_{i=1}^n\sum\_{j=i+1}^n\text{crossinv}(x\_i, x\_j).$$

Since the first sum is constant for any re-ordering of $x$, we can ignore it for our problem. In fact, if we sort the symbols inside each $x\_i$ you can compute $\text{crossinv}(x\_i, x\_j)$ in $O(|x\_i| + |x\_j|)$ time. So we only need to minimize the second sum by re-ordering $x$.

However, I do believe that this is a difficult problem to solve optimally. A greedy swapping approach won't work. As a counter-example (I apologize for the somewhat length counterexample, it's just one I found during experiments with randomly generated arrays) consider the following array of arrays:

$$(39, 23, 9, 31, 1, 44), (35, 41, 1, 49, 23, 38, 4, 11), (13, 10, 17, 5, 38, 50, 46), (28, 21), (45, 46, 33)$$

This has $102$ inversions when concatenated. The unique optimal concatenation order is

$$(28, 21), (39, 23, 9, 31, 1, 44), (35, 41, 1, 49, 23, 38, 4, 11), (13, 10, 17, 5, 38, 50, 46), (45, 46, 33)$$

with $100$ inversions. However this can't be generated with a simple swap. I've found similar counterexamples for single-symbol substring rotations.

A simple greedy growing approach won't work either. $(41, 3, 31), (16, 11, 47)$ is uniquely optimally ordered, but if we extend this with $(30, 20)$ the unique optimal ordering becomes

$$(16, 11, 47), (30, 20), (41, 3, 31)$$

Which is in no way a simple extension of the previous.

To go even further, Tim shows in this answer that if you view $\text{crossinv}$ as a black box function, and you don't exploit any of its special properties, then this problem is NP-complete and you're doomed to fail. So any efficient optimal algorithm must use some special property of $\text{crossinv}$.

For very large amount of arrays you will probably see the best real-world results using a non-deterministic technique such as genetic evolution to optimize the number of inversions, although this wouldn't guarantee optimality. Or perhaps I'm overestimating this problem's difficulty and someone comes along with a better answer.
> 4 votes

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


# Question
Title: How to partition disagreeable people into compatible groups
We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is grouped with someone they don't like. (If A doesn't like B then A cannot be in a group with B. Each person must belong to exactly one group.)

The incompatibilities between people are given explicitly as unordered pairs of people that cannot be in a group together.

Consider one possible scenario involving 10 people where incompatibility pairs are given as follows:

```
(1,2) (1,6) (1,7) (2,3) (2,6) (2,7) (2,8) (3,4) (3,7) (3,8) (3,9)
(4,5) (4,8) (4,9) (4,10) (5,9) (5,10) (6,7) (7,8) (8,9) (9,10)

```

In this scenario it is unacceptable to form a group consisting of persons \[ 1, 4, 5 \] because of the incompatibility pair (4,5), which means that persons 4 & 5 are incompatible and cannot be in the same group.

For the scenario given above, we can divide people up optimally into groups that all get along, using no fewer than 4 groups. Here is one such way of arranging people into 4 groups.

```
GROUP #1 : [ 1, 3, 5 ]
GROUP #2 : [ 2, 4 ]
GROUP #3 : [ 6, 8, 10 ]
GROUP #4 : [ 7, 9 ]

```

Note, that the groups do not have to have the same number of members, and it is acceptable to have a group consisting of only one individual if necessary. But each person must assigned to a group.

Describe an algorithm, given an arbitrary incompatibility matrix among N people in the form of zero or more incompatibility pairs, to determine a compatible grouping that uses the fewest groups possible.

---

### EDIT: Here's what I have tried so far.

A greedy algorithm:

```
While there are persons not yet assigned to a group.
   Take the lowest numbered unassigned person and create a new group `g` consisting of just them.
   For each person `p` not yet added to a group:
       If they are not incompatible with anyone in the current group `g`:
          Add person `p` to group `g`

```

I have no confidence at all that this would produce the minimal number of groups though.

# Answer
> 2 votes
You are essentially asking this: "Given a graph $G=(V,E)$ where each vertex in $V$ denotes a person and each edge $(u,v) \in E$ means that $u$ is incompatible with $v$, what is the minimum number of colors required to color the vertices of $V$ such that no edge in $E$ has both endpoints of the same color?"

In other words, given any graph $G$ (which can always be realized with a suitable set of incompatibilities), find the chromatic number $\chi(G)$ of $G$.

This is a well-known NP-hard problem. In particular, it is already NP-hard to decide whether $\chi(G) \le 3$. For the special case of $2$ colors, $\chi(G) \le 2$ can be decided in linear time (just check whether $G$ is bipartite, which also gives you the corresponding coloring if that is the case).

However, since you are just asking for an algorithm (no mention of a polynomial-time complexity or even efficiency) you might as well enumerate all existing colorings in $O(3^{|V|} + \dots + \chi(G)^{|V|}) = O(\chi(G)^{|V|})$ time. This can be improved to $O(2.2461^{|V|} )$ time, see: https://epubs.siam.org/doi/10.1137/070683933

Finally, there is simple linear-time greedy algorithm that uses at most $\Delta(G)+1$ colors, where $\Delta(G)$ is the maximum degree of $G$: Examine the vertices of $G$ one at a time, color a vertex with any color that is not already used by any of its neighbors.

This is the relevant Wikipedia page: https://en.wikipedia.org/wiki/Graph\_coloring .

**EDIT**

Your algorithm is iteratively computing maximal independent sets of $G$. Similarly to the greedy algorithm, it will return a coloring with at most $\Delta(G)+1$ colors. To see this, suppose that there is a vertex $v$ of color (group) $\Delta(G)+2$. Then, since $v$ has not been added to any of the first $\Delta(G)+1$ groups, it must have at least one neighbor in each of those groups. This means that the degree of $v$ is at least $\Delta(G)+1$, a contradiction.

Here is a tight example for both algorithms (vertices are examined in increasing order of their label):

# Answer
> 0 votes
If writing an algorithm that finds an optimal solution is too hard, or runs too slow, you can somewhat improve your algorithm.

1. Go through all pairs (a, b). If a dislikes b but b likes a then change that to "b dislikes a". It doesn't change the solution, but it makes it easier to talk about things.
2. Find pairs that *always* fit together. Go through all pairs (a, b). If a likes b, and also likes everyone whom b likes, then remove a from the problem altogether, solve the problem, and add a to b's group. This may reduce the numbers a bit.
3. Whenever you have two or more people in a group, immediately add everyone who likes everyone in the group and who likes everybody whom everybody in the group likes. Adding any such person doesn't increase the total dislike of the group. 1 to 3 are things that you should always do because they are optimal.
4. When you consider the next person to add to the group, find someone who dislikes the minimum number of people not already disliked by the group (increase the total dislike of the group by the smallest possible amount), and of those pick the one who dislikes most people. (Someone who dislikes many people is bad news. So if we can stick that person into a group that already dislikes most of the people that person dislikes, we minimise the damage that person can handle).
5. Run your algorithm repeatedly, taking random decisions instead of just arbitrary ones. Then pick the best output of those runs.

---
Tags: algorithms, optimization, sets, partitions
---


# Question
Title: If you have a DFA M, how do you construct a new NFA that accepts L(M) and {e}?
Suppose you're given a DFA $M$ with a 5 tuple of $(Q, \Sigma, \delta, q\_0, F)$.

How do you construct an NFA that accepts $L(M)$ and $\\{\varepsilon\\}$, the set containing the empty string? I know that a DFA is an NFA.

My thought is that you would simply add a new transition from the start state to the accepting state, which takes epsilon/the empty string.

For example (eps. is epsilon/empty string):

Since I've added an empty string transition, the machine is no longer a DFA, but it is an an NFA.

# Answer
> 3 votes
You've got the right idea, but there's a slight bug. If you add an $\varepsilon$-transition from the start state to all accepting states, then the new machine recognizes a subtly different language. Let $L\_k = \\{w\_1 \cdots w\_k : \exists u\_1, \dots, u\_{k-1} \in L(M) \text{ such that } w\_1 u\_1 w\_2 \cdots u\_{k-1} w\_k \in L(M)\\}$. Note that $L\_1 = L(M)$. This new machine will recognize the union of the $L\_k$, i.e., it recognizes $\bigcup\_{k=1}^{\infty} L\_k$.

Instead, you can create a new state $q\_{\text{empty}}$, add an $\varepsilon$-transition from $q\_0$ to $q\_{\text{empty}}$, and take the new set of accepting states to be $F \cup \\{q\_{\text{empty}}\\}$.

---
Tags: automata
---