title: General method to make circuits?

text:
# Question
Title: General method to make circuits?
I have a subject called computer architecture in university but I don't get a clue of it. We get assignments like: *make a 2-bit two’s complement carry lookahead adder using 3 4-bit adder*.

This is a circuit I have to make in Logisim, however, it's like you need an already deep insight in the subject to be able to make this; insights I don't have (because it's totally new for me).

Is there a kind of method to solve and make these circuits? Using truth tables or anything?

**Note:** I'm not asking for the solution for this specific problem, only for a method or steps-to-take in general, to be able to make any (basic) circuit.

This is the full exercise: http://msdl.cs.mcgill.ca/people/hv/teaching/ComputerSystemsArchitecture/materials/CA2/CA\_Project\_2.pdf (Ex5 if you want more explanation of the problem).

I was able to solve the other 4 by trying very hard and using Google but without actually knowing what I was doing.

So again, I'm not asking for this specific solution, only if there is a general way to solve these kind of assignments using a specific method or steps, eventually explained by using this one example-exercise.

# Answer
Both suggestions in the comments in the OP were excellent and I agree with the users who provided them. I have included these comments below for continuity:

*There is en.wikipedia.org/wiki/Logic\_synthesis but the general way of solving exercises in university is by understanding the material or asking your TAs if you have problems. – adrianN*

*Work with your peers. Students manage to pass the class somehow, so there must be a principled way. The course is designed to impart the mode of thinking which enables you to solve such exercises, but unfortunately the only way to accomplish this is by actually solving the exercises, on your own or together with friends. – Yuval Filmus*

To assist you, look at the Wikipedia pages here and here on digital circuits/adders.

Also, ask your instructor and/or TA for suggestions on a good computer architecture and design book.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Sub-exponential for Subset Sum on the total bit length of the input
Was crawling the internet, and found this in a paper (1)

*"\[...\], a variant of dynamic programming called dynamic dynamic programming has been shown to have a worst-case sub-exponential time complexity of $2^{O(\sqrt x)}$ when the total bit length $x$ of the input set is used as the complexity parameter."*

As I understand this claim violates the Exponential Time Hypothesis, and there has been some answers in the forum clearly stating no such sub-exponential algorithm exists, would be interesting to know what the experts in the area think about the proposed algorithm in terms of worst case complexity.

Direct link to the paper (2) explaining the dynamic dynamic approach.

(1) Thomas E. O’Neil -An Empirical Study of Algorithms for the Subset Sum Problem

(2) Thomas E. O’Neil, Scott Kerlin - A Simple $2^{O(\sqrt x)}$ Algorithm for PARTITION and SUBSET SUM

# Answer
> 1 votes
This doesn't violate the exponential time hypothesis. The exponential time hypothesis says that k-SAT takes exponential time, i.e., $\Omega(2^{cn})$ for some constant $c\>0$. So if you found a $O(2^{\sqrt{n}})$ time algorithm for k-SAT, that would violate the exponential time hypothesis -- but a a $O(2^{\sqrt{n}})$ time algorithm for subset sum does not violate the hypothesis.

---
Tags: time-complexity, np-complete, runtime-analysis
---


# Question
Title: Is there a polynomial algorithm for optimal sorting on trees?
There's the classical problem of sorting numbers in a list with the restriction that you can only swap two neighbouring numbers. It's easy to see that getting an optimal number of needed swaps can be achieved by insertion sort or bubble sort.

We can generalize this problem by changing the underlying structure from a list to a graph. Instead of swapping neighbouring numbers in a list we would be swapping numbers connected by an edge. Formally let's have a graph G=(V, E) with V = {1, ..., N} and an assignment of values f: V -\> {1, ..., N} where f is a bijection/permutation. In order to do a swap we select an edge {u, v} from E and switch f(u) with f(v). Our goal is to sort f (that is achieve a state when f is the identity) in the least number of swaps. My question is whether there is a (polynomial) algorithm for this.

Since working on general graphs seems really difficult from what I've tried let's restrict ourselves to G being a tree. This should be a simpler question because each number has a clear path to its target.

Some observations:

When G is a path graph the problem is the same as sorting a list which is simple.

When G is a complete graph the problem is also simple since we only need to decompose each cycle into transpositions. You can actually look at the general problem as decomposing a permutation into as few transpositions as possible with the restriction of which transpositions you are allowed to use.

As long as the graph is connected there's a lower bound of "sum of all distances to targets"/2 because each swap decreases the distance to target of at most two numbers. The upper bound is "sum of all distances to targets" because we can select a number that wants to be in a non-articulation vertex (or simply leaf in trees) and drag it there. Then we can forget about this vertex and reduce the problem to a smaller graph.

# Answer
> 2 votes
This problem is called Token Swapping, and you can find more information if you search by its name on google.

I couldn't find a proof that it is NP-complete on trees, but I've found a recent paper that gives a 2-approximation algorithm for trees: http://erikdemaine.org/papers/TokenReconfiguration\_FUN2014/paper.pdf

---
Tags: algorithms, graphs, sorting, trees
---


# Question
Title: How to compare the efficiency of two encoding schemes or hypothesis languages?
My question is pretty basic, I'm looking for a named method if you know one, but also proper terminology, further reading, and anything this reminds you of if you don't. (I'm new to this, don't have the right terminology and just need a starting point so I can help myself.)

I'm trying to interpret the vector inputs to a black-box controller (which I can model as finite-state machine). I can see them and they look like a series of symbols but it is too variable (stochastic) to easily define an "alphabet" based on repetition and it isn't clear how the symbols are grouped. In other words it isn't clear whether they use something like block coding where each symbol is the same number of vectors in a sequence, or convolutional coding where symbols can have different numbers of vectors.

The controller operates a linear actuator (it just goes up and down) and the inputs are large vectors from a CNN. It's essentially a pong playing robot. I make predictions by modeling the controller as binary decision tree that maps each putative symbol to an exact position of the actuator. This is very similar to a language induction problem for a finite-state machine. Recall that a finite automaton can be a representation of a regular language. Also recall that finite automaton can characterized in terms of its memory requirements and computational complexity, hence a regular language can too.

1. I know that the controller is optimal. There is no controller which has both less memory and less computational complexity. If I have two guesses at coding schemes and each are able to predict actuator position equally well then I want to pick the coding scheme which implies the least complexity and memory. So how does one go about evaluating the resource requirements of a coding scheme (raw inputs-\> symbols) and grammar (rules about symbols) in combination?
2. I need to keep in mind that I might be wrong that it digitizes its inputs into symbols at all. So what are the signs that it is not digital? (such as, if I divide the symbols into smaller symbols and it still works just as well, ad infinitum, that probably means the symbols are meaningless).

---

If you don't think I've given enough information keep in mind that I don't expect a detailed answer (but I'm happy to offer more). An acceptable answer is something of the form "I think you need to look into \____.", "This sounds like \____ in which case we often use \____.", "This sounds like a paper I read, see \____.", or "The \____ metric compares the level of the difficulty of a task to the number of symbols in the language required to perform that task and tells you how efficient a language is at that task."

# Answer
The answer was just tree depth. What I needed to do was learn about evaluating the complexity of finite automata and how we can use a decision-tree model (decision-tree complexity) to put bounds on the complexity of an automata (analysis of algorithms). So I take my two coding schemes (call them A and B) and I make binary decision tree to predict the output of my system based on the inputs provided by the coding schemes. If both coding schemes A and B are equally useful for predicting the outputs but A requires a tree depth of 15 while B requires a tree depth of 54 then A is "better". This is because our decision-tree model of the system is simpler when using A than when using B and as stated before we strongly believe that our system is as simple as possible.

Of course I also need to include the complexity of the coding scheme itself but that just goes with alphabet size since it is a Nearest Neighbor search.

So it was under my nose, I just needed some context.
> 1 votes

---
Tags: formal-languages, terminology, efficiency, coding-theory, encoding-scheme
---


# Question
Title: Enumerate all maximal subset of a weighted knapsack
Given a knapsack $A$ composed of $(u\_i, v\_i)$-item where $u\_i$ is the item identifier and $v\_i$ is the weight of the item.

I call a *maximal* subset when you consider a subset $S$ of $A$ where the sum $R(S)$ over $v\_i$ in this subset is less or equal than $P\_{max}$ *and* if you try adding any item $(u\_j, v\_j) \in A \setminus S$ (if that's not empty) in $S$, then it'll exceed the $P\_{max}$ limit, that is: $\forall (u\_j, v\_j) \in A \setminus S, R(S \cup \\{ u\_j, v\_j \\}) \> P\_{max}$.

I wrote this Python algorithm to compute such an enumeration:

```
def determine_available(bag, Pmax):
    return [(u, p) for (u, p) in bag if p <= Pmax]

def enumeration(bag, Pmax):
    if Pmax == 0:
        return []

    cur = []
    for v, p in determine_available(bag, Pmax):
        r = Pmax - p

        if not determine_available(bag, r):
            cur.append([v])
        else:
            for pos in enumeration(bag, r):
                cur.append([v] + pos)

    return cur

print(enumeration([(4, 20), (2, 2)], 100)) # for example.

```

Pseudo-code:

```
enumeration (bag: set of available items, Pmax)
     if Pmax = 0
     then return empty list

     current_subsets <- empty list
     for all available and usable item of identifier v, weight p
     do
          r = Pmax - p
          if enumerate(bag, r) is empty
          then add the singleton [v] as a subset in current_subsets
          else
               for all subset of enumerate(bag, r)
                  add in current_subsets: [v] + subset
     done
     return current_subsets

```

Unfortunately, I would like to compute only distinct solutions without removing duplicates after the enumeration. Is there any way to do this?

Bonus question: how to enumerate them in an iterative way?

# Answer
There might be exponentially many such maximal subsets, so there is in general no efficient way to enumerate all of them.

It's not hard to write a recursive algorithm to enumerate all subsets. There are only two cases:

* The subset doesn't contain item 1. It consists of a maximal subset of items 2,3,... that sum to $P\_\max$ or less.
* The subset does contain item 1, plus a maximal subset of items 2,3,... that sum to $P\_\max-v\_1$ or less.

You can enumerate all subsets of the first type with a recursive call to the procedure, and enumerate all subsets of the second type with a second recursive call. The base case: if $P\_\max \le 0$ or $A$ is empty, then the only such subset is the empty set.
> 1 votes

---
Tags: enumeration
---


# Question
Title: Reducibility and Artificial Neural Networks
I have read (here and here ) about the computational power of neural networks and a doubt came up.

There is a way to reduce an ANN to another ANN (not taking into count the training algorithm) ? e.g. Reduce a Recurrent Neural Network to a Multilayer Perceptron, meaning that if I have a trained RNN, I can get a MP that maps the same inputs given to the RNN to the same outputs produced by the RNN.

And if exists an answer to the above question, we can show the equivalence between neural networks, e.g., all problems solved by an Multilayer Perceptron can be solved by a Recurrent Neural Network but the opposite is not true, i.e., $MP \subset RNN$ (I do not know if this is true, is just an example). So, if we obtain this relationship between all neural networks, we can get a neural network $X$ that is more powerful than others, so, we can throw away all other neural networks because $X$ can solve any problem that other NN can. Is this reasoning correct ?

Thanks.

# Answer
Not really. I respect what you're trying to achieve, but I don't think it's possible to achieve what you want, given our current level of knowledge of neural networks.

We already know that convolutional neural networks perform better for some problems, and fully-connected neural networks (what you call MP) work better for other problems. So you can't expect to find that one is always better than the other.

It has been proven that any computable function can be approximated arbitrarily well by some fully-connected neural network. However, the catch in this theorem is that the theorem doesn't tell us how large the neural network needs to be. We already know that sometimes a larger network is more accurate, but is also slower to train, so that's a pretty big caveat in the theoretical result.

And if you want to compare two different network architectures -- say, convolutional vs fully-connected -- then such a comparison won't be useful if it doesn't take into account the size of the network. If you need 1 billion parameters to make a fully-connected network work well, or 1 million parameters to make a convolutional network work well, are they equally good? No, you'll probably prefer the convolutional network. It's not at all clear how to get useful reductions between the two architectures that tells us anything about the *size* of the neural network.

So, no, you're probably not going to get some useful theory this way that says "you can throw away all other architectures other than type X".
> 1 votes

---
Tags: reductions, neural-networks, computation-models
---


# Question
Title: Can deep learning be applied to nonlinear parameter estimation problems?
Suppose $y=f(x,p)$ while $x$ and $y$ are variables and $p$ is the parameter (all in vector form), and $f$ is an explicit nonlinear function. We have:

$$y\_1^{(1)} = f(x\_1^{(1)},p\_1), y\_1^{(2)} = f(x\_1^{(2)},p\_1), ..., y\_1^{(n\_1)} = f(x\_1^{(n\_1)},p\_1)$$

$$y\_2^{(1)} = f(x\_2^{(1)},p\_2), y\_2^{(2)} = f(x\_2^{(2)},p\_2), ..., y\_1^{(n\_2)} = f(x\_1^{(n\_2)},p\_2)$$

$$...$$

$$y\_i^{(1)} = f(x\_i^{(1)},p\_i), y\_i^{(2)} = f(x\_i^{(2)},p\_i), ..., y\_1^{(n\_i)} = f(x\_1^{(n\_i)},p\_i)$$

$$...$$

If given a set of $(x\_i^{(1)},y\_i^{(1)}), (x\_i^{(2)},y\_i^{(2)}), ...$, we can estimate the value of $p\_i$ by means of optimization such as gradient descent or any other algorithms.

My question is : **Can the parameter estimation problem described above, which is conventionally solved by optimization methods, be solved by deep learning?**

Since $f$ is an explicit math formula, a very large training set can be easily generated by sampling $x$ and $p$ from some sort of prior distribution.

The difficulties I met during searching the answer on google:

1. Since DL itself is an optimization problem (or parameter estimation problem), what I found is mainly basic tutorials of DL rather than something directly relevant.
2. A similar question on Quora: How can I apply machine learning to parameter estimation problem in control theory? Is there any example study you can suggest?. The only answer to this question is very brief and only provides a 132-page thesis. I scanned the thesis and found that it seemed to solve a rather complicated image processing problem by reinforcement learning. I'm not sure if it is relevant.
3. A similar question on StackOverflow: Can I do nonlinear regression with deep learning ? How?. But the author tried to use deep learning to find the relationship between $x$ and $y$, which is different from my question: the function $f$ is already known, I just want the $p$.

The intuition of solving parameter estimation by deep learning instead of direct optimization could be:

1. Optimization methods such as gradient descent is prone to find a local optima. Maybe DL will have some magic.
2. In practice, the parameter estimation problem may need to be solved many times for different set of $(x,y)$, which requires speed. So conventional optimization methods may be too slow for this. In a real case that prompts me to ask this question, each parameter estimation takes 0.6s by the `lsqnonlin` function of MATLAB. In contrast, although training a neuron network is time-consuming, getting the output from the input only takes several milliseconds for a pre-trained network.
3. The formula $y=f(x,p)$ may be used in practice for many years and proves to be very effective. The parameter $p$ also has clear physical meanings and can indicate the actual conditions of the system/machine/experiment. Both $x$ and $y$ can be easily obtained. So I want to reserve the formula rather than use a blackbox-like network to predict $y$ from $x$ as most DLs do.

The difficulties I met when solving the problem myself:

1. Suppose the size of the $(x\_i,y\_i)$ set is $n\_i$: $(x\_i^{(1)},y\_i^{(1)}), (x\_i^{(2)},y\_i^{(2)}), ..., (x\_i^{(n\_i)},y\_i^{(n\_i)})$. The problem is: $n\_i$ is not fixed. If $n\_i=5$, we may estimate $p\_i$ with a great error. And if $n\_i=1e6$, we may get a very precise estimation of $p\_i$. But in both case we can get an estimation of $p\_i$ at last. However, multi-layer perceptron (MLP) or convolution neuron network (CNN) both accept fixed number of inputs. If you do image processing, you even need to resize every image to the same size first. It seems that MLP and CNN don't suit for this question.
2. The $(x,y)$ set has no order as time-series. The 1 and 2 in $(x\_i^{(1)},y\_i^{(1)})$ and $(x\_i^{(2)},y\_i^{(2}))$ are just indices, which don't imply that $(x\_i^{(1)},y\_i^{(1)})$ is necessarily before $(x\_i^{(2)},y\_i^{(2}))$. So recurrent neuron network (RNN) doesn't seem to be a natural option.

# Answer
No. Deep learning is not useful or relevant here. Deep learning is for *classification*. You don't have a classification task. Rather, you have an optimization task: find the parameter value $p$ that causes the best match between the given $x$-values and $y$-values.

Deep learning isn't magic sauce that you can apply to anything you might ever think of and expect it to solve your problem. Your question is an instance of the XY problem. There may be suitable methods to speed up optimization, but you'll probably need to ask a new question and tell us something about the structure/properties of $f$ and the typical range of values for $n\_i$.
> 4 votes

# Answer
I am interested in this question as well. And I did some research. It turns out that Tensorflow is able to do the single function optimization using SGD, Adam, etc.

Here is a very detailed tutorial.

http://patwie.com/2017/01/04/optimization\_with\_tf.html

Since the Nonlinear Regression is kind of minimization problem such as minimizing the sum of squared residual, I guess we are able to feed a single objective function of unknown parameters and all the data into Tensorflow to solve the problem.

I have not tried it yet. I will come back with new results.

However, it will not be deep learning or Neural Network anymore.

It just uses the Tensorflow's power to facilitate the optimization.

update:

I did run a model with nonlinear objective function and it works. And then I am thinking that it is a Neural Network with a nonlinear hidden layer.

**1st input layer/data/x -\> 2nd hidden layer/nonlinear f(x, theta) -\> 3rd output layer yhat**

the model is

$$\hat y = f(x, \theta)$$

not a linear model

$$a = wx + b$$

The objective function is the sum of squared error: $\sum\[(y- \hat y)^2\]$.

The Tensorflow use the forward and backward propagation to solve the problem.

We estimate the $\theta$s instead of $w \quad \text{and} \quad b$.

I will MXnet and other packages to see if the idea works as well.
> 1 votes

---
Tags: algorithms, optimization, machine-learning
---


# Question
Title: Is there an approximation algorithm for Minimum Test Collection Problem?
The problem is defined as follows:

**Instance:** A finite set $A$ of "possible diagnoses," a collection $C$ of subsets of $A$, representing binary "tests," and a positive integer $J≤|C|$.

**Question:** Is there a subcollection $C′⊆ C$ with $|C′|≤ J$ such that, for every pair $a\_{i},a\_{j}$ of possible diagnoses from $A$, there is some test $c∈C′$ for which $|{a\_{i},a\_{j}}|∩ c|=1$ (that is, a test $c$ that "distinguishes" between $a\_{i}$ and $a\_{j}$)?

And we know that MTC is $NP$-complete, it has been proved by reducing it to 3 Dimensional Matching problem in the Garey & Johnson's book.

Thanks.

# Answer
> 1 votes
Yes, there are approximation algorithms for this problem.

1. If $k$ is the upper bound of the test case, the authors of http://repository.cmu.edu/cgi/viewcontent.cgi?article=1397&context=tepper constructed a $O(\log{k})$-approximation algorithm
2. Another approximation algorithm of the same complexity is derived here: https://link.springer.com/chapter/10.1007/3-540-44676-1\_13

Hope that helps!

---
Tags: complexity-theory, np-complete, approximation
---


# Question
Title: Physical significance of pumping length in pumping lemma
Would it be possible to explain the physical significance of pumping length $p$ in pumping lemma for regular languages?

Somehow, the physical significance of pumping length $p$ in pumping lemma for regular languages escapes me.

I have explored a number of tutorials and presentations on this topic. The nearest I came to is, at some point, $p$ was assumed to be the number of states in the DFA recognizing the language. But the same presentation at some later point cautioned that $p$ is a property of the language, and *not* of the DFA.

When we prove a language to be not-regular, first of all, we assume it to be regular and thus having a pumping length $p$. We also assume the language to satisfy the conditions of pumping lemma. Later on, we find that the language fails to satisfy the conditions of pumping lemma and hence not a regular one.

So, such languages will not have any pumping length.

But what about regular languages? If I am given a regular language, there are many, just pick any one from this list, $10^\*$, $1\Sigma^\*$, $\Sigma^\* 001$, would it be possible for us to point out the pumping length for that language?

# Answer
First, in the Pumping Lemma as I know it, there is no such thing as *the* pumping length for a language. "For every regular language $L$ there exits a constant $p$ such that for any string $w\in L$ with $|w|\ge p$ ...". In fact, if $L$ satisfies pumping length $p$ then it will also satisfy any pumping length larger than $p$. (This is not completely trivial, the requirements in the dots ... above mention $p$ again.)

So we can call the smallest length $p$ for which the pumping property holds "the" pumping length. This is indeed a property of the language. If I am right the pumping length for $L = a(aa)^\*+b(bb)^\*$ is three. Strings of length 3 and above can be "pumped".

As you observe yourself, every regular language can be pumped (well, that is what the Lemma states). And the proof may use *any* automaton for the language. Whenever a string is at least as long as the number of states in the automaton, its computation must repeat a state, and we can pump. We can use the smallest automaton for the language, to minimize the pumping length. That smallest deterministic automaton is in fact well-defined. Unfortunately this in general still does not fix the (minimal) pumping length. An automaton for $L$ above seems to use at least five states (and actually 6 if it must be deterministic).

But still the property seems tied to the regular language via a certain "minimal" automaton, and the length of strings that ensure repetition of states.

But hey, even non-regular languages might in fact be pumpable: the Pumping Lemma (or better Pumping Property) is not a characterization of the regular languages. See for instance "Languages that satisfy the pumping lemma but aren't regular?" where it is observed that languages of the form $c L\cup \\{ c^k \mid k\neq 1 \\}\cdot\\{a,b\\}^∗$ for *any* $L\subseteq \\{a,b\\}^\*$ have the Pumping Property (for pumping length one or two, I believe). I do not know a "physical" significance in the nonregular case.
> 4 votes

# Answer
Regular languages that are infinite may nevertheless include a finite set of (possibly very large) strings that will not be produced by cycling, or any sort of repetitive pattern. The pumping length allows you to abstract these singularities in the formulation of the pumping lemma.

As it happens, the correctness of the lemma is guaranteed by a pumping length that is bigger than - for instance - the largest non-cycling sequence of transitions of a minimal DFA, but it is not necessary (or particularly interesting) to define it in these terms. As you noted, being regular is a property of the language, not of any particular way of defining it.
> 3 votes

# Answer
Thinking of the pumping length as the size of a DFA recognizing the language is a good intuition. If you want to be more precise, you need to be careful about quantifiers.

**A** pumping length that works in a proof that the language is regular is the number of states in **a** DFA recognizing the language. $p$ is not unique. It's always possible to build a DFA with more states (trivially, by adding unreachable states or separating equivalent dead states, or in more complex ways). And if the pumping property is true for a certain $p\_0$, it's true for all $p$ such that $p \ge p\_0$.

It follows that the minimum pumping length that works for the lemma is smaller or equal to the minimum size of a DFA recognizing the language. The minimum pumping length is sometimes, but not always equal to the minimum DFA size. This is to be expected since the pumping lemma is not an equivalence — a language which is not regular, but for which the pumping property holds, has in a sense a finite pumping length but an infinite minimum finite automaton size. Hendrik Jan gives some examples.

The minimum pumping length is a property of the language, and not of the DFA, since it's about the words that are recognized by the language and not about how these words are recognized. It isn't about a specific DFA recognizing the language, but you could say that it's about the *class* of DFA's that recognize that language.
> 3 votes

---
Tags: formal-languages, pumping-lemma
---


# Question
Title: Advantages of segmented paging over pure paging
As we know segmented paging is an improvement over segmentation and paging but I am having some doubts regarding the memory overhead of these three system.It is clear that segmentation need less memory overhead.But about other two system please confirm these two points.

> number of pages in pure paging=number of pages in segmented paging

In pure paging we have a single page table for each process but in segmentation we have page table for each segment.so I think that after all total number of pages in pure paging is equal to Segmented paging.is this true?

> memory overhead is larger in segmented paging than pure paging

as the number of pages are same,thus total memory requirements will be same but in paging we have a fixed size single page table so some amount of internal fragmention will be there but as in segmented paging there are various size of many segmented page table so can I conclude that amount of frag mention is much more than pure paging and also extra segmentation table is required in this system.
Is my conclusion is true that memory overhead is more in segmented page table?

# Answer
It is difficult to compare directly because memory management will likely be different in segmented paging compared to pure paging. That being said, if we assume the allocations are exactly the same, then segmented has a higher overhead because one needs to keel track of the segments. However the overhead will depend on the number of segments, and there are several possible strategies and it is also hardware dependent. Some processor may support an arbitrary (or at least very high) number of segments whereas some may only support a few (data/code/stack for example).

Also note that segmented paging is not used in any of the major processors these days: ARM does not support it, x86 only supports it in 32-bit and almost no OS uses it.
> 1 votes

---
Tags: memory-management
---


# Question
Title: What is the $4k$ kernelization algorithm for Planar Independent Set?
Chen et al. say that

> The four-color theorem implies a $4k$-kernelization for Planar Independent Det, which is the dual problem of Planar Vertex Cover.

I knew that Vertex Cover has a kernelization with $2k$ vertices. Furthermore, I know that we have a lower bound which is $n/4$ for IS.

But how to get a $4k$ vertex kernel for Planar IS? Is there a general rule that when we transform "primal" program to "dual" program, then we have a factor of 2.

# Answer
The formal problem is:

* Input: A planar graph $G = (V, E)$ and an integer $k$ (the parameter)
* Question: Does $G$ have an independent set of size at least $k$?

**A kernelization algorithm for Planar IS** with $4k$ vertices.

Recall that we can obtain a four-coloring of $G$ in polynomial time. That is, we get a partitioning of your vertex set $V$ into $V\_1, V\_2, V\_3, V\_4$ such that each class is an independent set.

We now distinguish between two cases:

* One class $V\_i$ has size at least $k$. This is a witness and hence $G,k$ is a yes instance, so we may output a trivial yes instance.
* Otherwise, every class has size less than $k$, so $V$ has at most $4k-4$ vertices.

Thus in polynomial time, we may output a graph $G'$ with at most $4k$ vertices such that $G,k$ is a yes instance if and only if $G', k$ is a yes instance.

Notice that *this only holds for planar graphs.* Independent Set is W\[1\]-hard on general graphs.
> 4 votes

---
Tags: parameterized-complexity
---


title: Calculating this sum in $O(n)$ time

text:
# Question
Title: Calculating this sum in $O(n)$ time
Assume that $\forall 1 \leq i \leq n : a\>0, c\_i \> 0 $ where $n \in \mathbb{N}$. I need to show that it is possible to compute this sum in $O(n)$ time:

$$I = \sum\_{(\epsilon\_1,...,\epsilon\_n) \in \\{0,1\\}^n}a^{c\_1 \epsilon\_1 + ... + c\_n \epsilon\_n}$$

(a sum over all binary vectors of length $n$) I notice that in $I$, for any fixed $1\leq i \leq n$, we have that $a^{c\_i\epsilon\_i} = 1$ in $2^{n-1}$ of the times, and $a^{c\_i}$ in the other $2^{n-1}$ of the times. So $I$ can be written as follows:

$$2^{n-1}\cdot a^{c\_1} \cdot \sum\_{(\epsilon\_2,...,\epsilon\_n)\in \\{0,1\\}^{n-1}}a^{c\_2\epsilon\_2}\cdot ... \cdot a^{c\_n \epsilon\_n} + 1 \cdot \sum\_{(\epsilon\_2,...,\epsilon\_n)\in \\{0,1\\}^{n-1}}a^{c\_2\epsilon\_2}\cdot ... \cdot a^{c\_n \epsilon\_n}$$

But coming to expand this for $i=2,...,n$ I immediately realize that this won't turn out to be $O(n)$. I would appreciate some guidance.

# Answer
You can prove this by full induction, which gives you an algorithm, too. The claim is $$I\_n = \sum\_{(\epsilon\_1,...,\epsilon\_n) \in \\{0,1\\}^n}a^{c\_1 \epsilon\_1 + ... + c\_n \epsilon\_n} = (1 + a^{c\_1})(1 + a^{c\_2}) \ldots (1 + a^{c\_n}) $$ The product of the right side can be computed in $O(n)$ steps if the exponentiation requires constant time.

Proof:

1. For $n=1$ the claim is obviously true: $I\_1 = 1 + a^{\epsilon\_1}$.
2. $n \rightarrow n+1$: Let the claim be true for $n$: \begin{eqnarray} (1 + a^{c\_{n+1}})I\_n & = & (1 + a^{\epsilon\_{n+1}})\sum\_{(\epsilon\_1,...,\epsilon\_n) \in \\{0,1\\}^n}a^{c\_1 \epsilon\_1 + ... + c\_n \epsilon\_n} \\ & = & \sum\_{(\epsilon\_1,...,\epsilon\_n) \in \\{0,1\\}^n}a^{c\_1 \epsilon\_1 + ... + c\_n \epsilon\_n} + a^{c\_{n+1}}\sum\_{(\epsilon\_1,...,\epsilon\_n) \in \\{0,1\\}^n}a^{c\_1 \epsilon\_1 + ... + c\_n \epsilon\_n} \\ & = & \sum\_{(\epsilon\_1,...,\epsilon\_n) \in \\{0,1\\}^n,\\ \epsilon\_{n+1}=0}a^{c\_1 \epsilon\_1 + ... + c\_n \epsilon\_n + c\_{n+1} \epsilon\_{n+1}} + \sum\_{(\epsilon\_1,...,\epsilon\_n) \in \\{0,1\\}^n,\\ \epsilon\_{n+1}=1}a^{c\_1 \epsilon\_1 + ... + c\_n \epsilon\_n + c\_{n+1} \epsilon\_{n+1}} \\ & = & \sum\_{(\epsilon\_1,...,\epsilon\_n,\epsilon\_{n+1}) \in \\{0,1\\}^{n+1}}a^{c\_1 \epsilon\_1 + ... + c\_n \epsilon\_n + c\_{n+1} \epsilon\_{n+1}} \\ & = & I\_{n+1} \end{eqnarray}
> 3 votes

---
Tags: algorithms, numerical-algorithms
---


# Question
Title: Fastest way to find the smallest interval of a number
Here is my problem : Given a range, let's say 0 to 10.000, and some numbers in that range (like 23, 1456, 280, 3586), I want to find, for any input x, the two closest numbers to x, the smaller one the greater one. For example for x=100, the two numbers are 23 and 280, for x=350 they are 280 and 1456.

Is there a faster way to do that than a binary search on the list of numbers ? I vaguely remember the existence of a data structure for this task, but in my case the numbers are dynamic and will change during the execution of my algorithm.

# Answer
> 1 votes
The relevant phrase is  "predecessor search" .

For that, you can dynamically choose whether-or-not equality is allowed by

for each number in the range, storing 2 times that number rather than that number directly
and
for each actual query q, submitting  (2\*q) ± 1  instead of q,
where the sign depends on whether you want to allow equality
and
dividing by 2 before returning

.

With that, the greater one can be found using predecessor search in the negatives of
the actual numbers.    For your case, you could simply reverse the range, like storing
10000-23,10000-1456,10000-280,10000-3586  rather than  23,1456,280,3586 .
Page 6 of this pdf gives upper bounds for dynamic predecessor searching
and references for data structures achieving those bounds.

This pdf gives another data structure which does what you want and much more.

---
Tags: algorithms
---


# Question
Title: How powerful are DFA with recursive calls?
A family of deterministic finite automata of degree $n$ over an alphabet $Σ$, with $\bigcap Σ = ∅$, consists of a set $\mathcal{A} =\\{(K\_i,Σ∪\\{1,\dots,n\\},δ\_i,s\_i,F\_i) : 1 ≤ i ≤ n\\}$ of deterministic finite automata. We fix implicitly a subscript function over $\mathcal{A}$, so that we can refer to the “$i$-th automaton $\mathcal{A}\_i = (K\_i, Σ ∪ \\{1, \dots, n\\}, δ\_i, s\_i, F\_i)$ of $\mathcal{A}$.”

Such a family performs the following processing:

* Given an input $w ∈ Σ^∗$, the automaton $\mathcal{A}\_1$ starts processing the input as usual, following the transitions in $δ\_1$, until it reaches a transition of the form $δ\_1(q, i) = p$, with $i ∈ \\{1, \dots, n\\}$. It then gives control to the automaton $\mathcal{A}\_i$. The automaton $\mathcal{A}\_i$ processes the not yet consumed input until it reaches a final state. When such a state is reached, $\mathcal{A}\_i$ terminates and gives control back to $\mathcal{A}\_1$, which resumes its operation from state $p$. $\mathcal{A}\_1$ accepts the input iff it is in a final state when the end of the input is reached.
* More generally, any automaton $\mathcal{A}\_i$ can “call” some other automaton $\mathcal{A}\_j$, which happens whenever $\mathcal{A}\_i$ performs a transition of the form $δ\_i(q, j) = p$. When such a transition happens, $\mathcal{A}\_i$ gives control to $\mathcal{A}\_j$. When the operation of $\mathcal{A}\_j$ reaches a final state, $\mathcal{A}\_i$ takes the control back and resume its operation starting from state $p$.

Call the whole system a *deterministic finite automaton with recursive calls*. It is in fact a usual finite automaton, with the added functionality that some edges represent a call to a different automaton instead of the acceptance of one input symbol.

1. How to show any language accepted by a deterministic finite automaton with recursive calls is context-free?
2. Are all the languages accepted by deterministic finite automata with recursive calls *deterministic* context-free?

# Answer
Recursion is implemented on a computer using a stack, and your case is no different. You can use a stack to emulate the "call-and-return" semantics of your DFA with recursive calls, and the results will be a DPDA.
> 1 votes

---
Tags: automata, finite-automata, computation-models
---


# Question
Title: Are Test and set primitives as powerful as semaphores?
I get confused because i don't know if it is possible to use **Test and Set** primitives in case where more then one process can be enter in critical section at the same time.

# Answer
Your hunch is correct, they aren't equivalent. Test-and-set has a consensus number of 2, which means, roughly speaking, that it is only able to efficiently synchronize between 2 processes. See Why is the consensus number for test-and-set, 2?. Semaphores allow synchronization between an arbitrary number of processes (assuming no bound on the number of processes waiting on a semaphore).

It isn't really a “fair” comparison, since test-and-set is a hardware primitive while semaphores are a software interface. But if does show that test-and-set isn't sufficient to implement (wait-free) semaphores.
> 5 votes

---
Tags: operating-systems, concurrency, synchronization
---


# Question
Title: Does two system's clock synchronises to communicate with each other?
If two computer system's has to do some kind communication like data transfer or receiving should its clock sync to do that?If not then how they transfer bytes without having syced clocks?

# Answer
> 2 votes
Your question is a bit vague, depending on what is communicating, so I will try to give a general answer. There are essentially two big ways of communicating:

* Sending data together with a clock signal (source synchronous): this is used in I2C, RAM, SPI
* Sending just data and let the other side recover the clock from it (clock recovery): this is used in USB, PCI Express, Ethernet (I think)

The bottom line is that synchronization is important, two systems will never have exactly the same clock because they drift and yet they have to agree on some clock when transferring data. Both approaches have advantages and drawbacks:

* source synchronous: can achieve higher speed but needs one more wire and increases complexity of the receiver because it has to deal with two clock domains (its own and the sender's)
* clock recovery: one less wire but requires the signal to toggle often enough, a process known as self-clocking which adds overhead to the signal (for example USB sends 10 bits for 8 bits of data, this is known as 8b/10b encoding)

---
Tags: computer-networks, clocks
---


# Question
Title: Why don't we encode church numerals like this?
I think the following encoding also works.

```
ZERO := λf. λx. x
ONE  := λf. f
TWO  := λf. f f
THREE:= λf. f (f f)

```

Note: the original encoding is

```
ZERO := λf. λx. x
ONE  := λf. λx. f x
TWO  := λf. λx. f (f x)
THREE:= λf. λx. f (f (f x))

```

Why is the original one better?

# Answer
> 3 votes
I think what you really are asking for are **criteria for judging correctness of coding**. Once you have got these, you can answer your question on your own.

Correctness of coding of some structure always originates from the structure itself. The structure of natural numbers $\mathbb{N}$ is:

1. A constant $0$,
2. A unary operation $S$,
3. For each set $A$, a recursion operator $\mathsf{rec}\_A : A \to (\mathbb{N} \to A \to A) \to \mathbb{N} \to A$, subject to equations: $$\mathsf{rec}\_A \\; x \\; f \\; 0 = x$$ and $$\mathsf{rec}\_A \\; x \\; f \\; (S n) = f \\; n \\; (\mathsf{rec}\_A \\; x \\; f \\; n).$$

So whatever your coding of natural numbers is, it has to have $0$, $S$ and $\mathsf{rec}$ (only one will do in the untyped $\lambda$-calculus as there are no types to worry about) such that the above equations are satisfied for all suitable $x$, $f$ and $n$.

You can ask yourself:

> *Does your coding allow you write down $0$, $S$ and $\mathsf{rec}$ which satisfy the desired equations*?

If it does, then it's a valid coding. There are many codings of natural numbers.

# Answer
> 1 votes
I am the guy who posted this question. I somehow figure this out.

In the original form, consider the `succ` operation is defined as below (+1).

```
succ = λn.λf.λx. f (n f x)

```

Thus,

```
succ ONE
= (λn.λf.λx. f (n f x)) (λf. λx. f x)
= λf.λx. f ((λf. λx. f x) f x)
= λf.λx. f ((λx. f x) x)
= λf.λx. f (f x)
= TWO

```

Same to `succ TWO`, `succ THREE` ...

In my form, let us define `succ` like following.

```
succ = λn.λf. f (n f)

```

Here,

```
succ ONE
= (λn.λf. f (n f)) (λf. f)
= λf. f ((λf. f) f)
= λf. f f
= TWO

```

This also works.

However, the pattern breaks when we try to do `succ ZERO`

In the original form,

```
succ ZERO
= (λn.λf.λx. f (n f x)) (λf. λx. x)
= λf.λx. f ((λf. λx. x) f x)
= λf.λx. f ((λx. x) x)
= λf.λx. f x
= ONE

```

But in my form,

```
succ ZERO
= (λn.λf. f (n f)) (λf. λx. x)
= λf. f ((λf. λx. x) f)
= λf. f (λx. x)

```

If we really want my new form holds, we have to define `ZERO = λf._` where `_` is something like NULL or empty, which is not supported by the syntax.

Alternatively, I think we can define:

```
ZERO  := λf. f
ONE   := λf. f f
TWO   := λf. f (f f)

```

So that the newly defined `succ` operation may still hold. However, other things/rules can break. For example, in the original form, the boolean FALSE (`λx.λy.y`) encoding is as same as ZERO. But in my form, this property will no longer hold. ... There may be better explanations. But finally, I've somehow convinced myself that Church's design is a piece of art!

# Answer
> 1 votes
> ```
> TWO  := λf. f f
> THREE:= λf. f (f f)
>
> ```

This looks like a type error to me. `TWO` and `THREE` should have the same type - regardless which one exactly. That would imply that `f` and `(f f)` had the same generic type as well, which is impossible however (without a recursive infinite type) or requires `f` to be the identity function (with type `∀a. a -> a`), which would be pretty useless and makes the numbers indistinguishable.

In the original version, the number type is `(a -> a) -> a -> a`.

# Answer
> 0 votes
You're breaking the η-reduction rule

```
M := λx. N x
->η
Μ := N

```

Note the parentheses in `TWO` – you *cannot* do η-reduction here

```
TWO := λf. λx. f (f x)

```

To demonstrate, as you propose

```
TWO := λf. f (f f)

```

Would result in a problem

```
TWO g x
= (λf. f (f f)) g x
= g (g g) x

```

But in Church's definition we get

```
TWO g x
= (λf. λx. f (f x)) g x
= (λx. g (g x)) x
= g (g x)

```

Your proposed `g (g g) x` is not equivalent to `g (g x)`

---

To remove `x`, use `B` — its not exactly what you’re asking for but shows that there’s room in the definition for change, while simultaneously keeping everything the same

```
B := λf. λg. λx. f (g x)

 ZERO := λf. λx. x
  ONE := λx. x
  TWO := λf. B (ONE f) (ONE f)
THREE := λf. B (TWO f) (ONE f)
 FOUR := λf. B (TWO f) (TWO f)
 FIVE := λf. B (TWO f) (THREE f)
...

```

Let's evaluate `THREE h z` to see it work

```
THREE h z
= (λf. B (TWO f) (ONE f)) h z
=      B (TWO h) (ONE h) z
= (λf. λg. λx. f (g x)) (TWO h) (ONE h) z
= (λg. λx. TWO h (g x)) (ONE h) z
= (λx. TWO h (ONE h x)) z
= TWO h (ONE h z)
= (λf. B (ONE f) (ONE f)) h (ONE h z)
= B (ONE h) (ONE h) (ONE h z)
= (λf. λg. λx. f (g x)) (ONE h) (ONE h) (ONE h z)
= (λg. λx. ONE h (g x)) (ONE h) (ONE h z)
= (λx. ONE h (ONE h x)) (ONE h z)
= ONE h (ONE h (ONE h z))
= (λx. x) h (ONE h (ONE h z))
= h (ONE h (ONE h z))
= h ((λx. x) h (ONE h z))
= h (h (ONE h z))
= h (h ((λx. x) h z))
= h (h (h z))
= THREE h z

```

Or the expression in this waterfall-style formatting - may help readability for some

```
THREE h z
=                                                      (λf. B (TWO f) (ONE f)) h z
=                                                           B (TWO h) (ONE h)    z
=                               (λf. λg. λx. f     (g     x)) (TWO h) (ONE h)    z
=                                   (λg. λx. TWO h (g     x))         (ONE h)    z
=                                       (λx. TWO h (ONE h x))                    z
=                                            TWO h (ONE h z)
=                        (λf. B (ONE f) (ONE f)) h (ONE h z)
=                             B (ONE h) (ONE h)    (ONE h z)
= (λf. λg. λx. f     (g     x)) (ONE h) (ONE h)    (ONE h z)
=     (λg. λx. ONE h (g     x))         (ONE h)    (ONE h z)
=         (λx. ONE h (ONE h x))                    (ONE h z)
=              ONE h (ONE h (ONE h z))
=          (λx. x) h (ONE h (ONE h z))
=                  h (ONE h (ONE h z))
=              h ((λx. x) h (ONE h z))
=              h (h         (ONE h z))
=              h (h     ((λx. x) h z))
=              h (h     (h         z))
= h (h (h z))
= THREE h z

```

---
Tags: lambda-calculus, church-numerals
---


# Question
Title: Is this language context free L=${a^mb^nc^pd^q: m+n=p+q}$?
L={ $a^mb^nc^pd^q: m+n=p+q$ }

I cannot find a grammar to prove that it is context free. However I can visualise a PDA which can accept this language. The PDA would push O's for every a and b which it can later match against c and d.

Please someone suggest a grammar for this language ?

# Answer
You can create a word of this language symmetrically from outside to inside. Here is a context free grammar for that. It produces for every $a$ or $b$ a $c$ or $d$. If it has started producing $b$s or $c$s, it cannot produce $a$s or $d$s anymore.

Here are the production rules where $S$ is the start symbol:

\begin{align\*} S & \rightarrow aSd \tag{1} \\ S & \rightarrow T \\ S & \rightarrow V \\ S & \rightarrow U \\ S & \rightarrow \epsilon \\ T & \rightarrow aTc \tag{2} \\ T & \rightarrow V \\ T & \rightarrow \epsilon \\ U & \rightarrow bUd \tag{3} \\ U & \rightarrow V \\ U & \rightarrow \epsilon \\ V & \rightarrow bVc \tag{4} \\ V & \rightarrow \epsilon \end{align\*} Edit: I've simplified the rules so that fewer terminal symbols appear in it, and adapted the proof.

Proof: All rules are symmetrical, and except for the $\epsilon$-rules they have one non terminal in the middle, which is preceeded and followed by a terminal. The preceding terminal is either an $a$ or $b$, and the following terminal is always a $c$ or $d$.

Obviously the rules produce for every $a$ or $b$ exactly one $c$ or $d$. Thus, the number of $a$s and $b$s must be equal to the number of $c$s and $d$s, and this is why $n + m = p + q$ is fulfilled. It also follows that in the left half of the word only $a$s and $b$s can be written, while in the right half only $c$s and $d$s are written.

In the rules $b$ is only followed by the non terminal $U$, which expand to $b\ldots{}$. Thus, an $b$ in the word can never be followed by an $a$. This shows that the left side of the word must have the form $a^nb^m$.

In the rules $c$ is only preceded by the non terminal $V$, which expand to $\ldots{}c$. Thus, an $c$ in the word can never be preceded by an $d$. This shows that the right side of the word must have the form $c^pd^q$.

A word $w = a^nb^mc^pd^q \in{} L$ can be constructed as follows:

1. Apply the rule (1) $\min(m, q) =: l$ times. You get $$\underbrace{a\ldots{}a}\_{l}S\underbrace{d\ldots{}d}\_l$$.
2. If $m \geq l$ apply rules $S \rightarrow T$ and then (2) $\min(p, m - l) =: k$ times, and you get $$\underbrace{a\ldots{}a}\_{l + k }T\underbrace{c\ldots{}c}\_k\underbrace{d\ldots{}d}\_{l = q}$$ If $k = p$ than $n$ must be zero. You can apply $T \rightarrow \epsilon{}$ and you're finished. Otherwise $k = m -l$ and $a$ appears $l + k = m$ times. Apply rule $T \rightarrow V$, rule (4) $p - k$ times, and rule $V \rightarrow \epsilon{}$. You will get $$\underbrace{a\ldots{}a}\_{m}\underbrace{b\ldots{}b}\_{p - k}\underbrace{c\ldots{}c}\_{k + p - k = p}\underbrace{d\ldots{}d}\_{q}$$ Since $m + n = p + q$ proved already above, $p - k = n$ follows and you are finished.
3. Otherwise $q \> l$, and you must apply rule $S \rightarrow U$, and rule (3) $\min(n, q - l) =: g$ times. You will get $$\underbrace{a\ldots{}a}\_m\underbrace{b\ldots{}b}\_gU\underbrace{d\ldots{}d}\_{g + l}$$ If $g = n$ than $p$ must be zero. You can apply $T \rightarrow \epsilon{}$ and you're finished. Otherwise $g = q - l$ and $d$ appears $l + g = q$ times. Apply rule $U \rightarrow V$, rule (4) $n - g$ times, and rule $V \rightarrow \epsilon{}$. You will get $$\underbrace{a\ldots{}a}\_{m}\underbrace{b\ldots{}b}\_{g + n - g}\underbrace{c\ldots{}c}\_{n - g = p}\underbrace{d\ldots{}d}\_{q}$$ Since $m + n = p + q$ proved already above, $n - g = p$ follows and you are finished.
> 6 votes

# Answer
Try to find a proper "nesting structure" to generate the words. Due to the tree form of CFG there is always such a structure inside the words of a context-free language. See examples in the reference question "How to prove that a language is context-free?"

We know $m+n=p+q$. Now assume $m\ge q$.

Then $m=q+t$ for some $t\ge 0$ and also $q+t+n = p+q$, so $t+n = p$. Hence a word $a^mb^nc^pd^q$ can be written as $a^q a^t b^n c^n c^t d^q$.

Using this structure you can write a CFG. Same for the symmetric case $m\le q$.
> 2 votes

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


title: When is the empty word part of $A^+$?

text:
# Question
Title: When is the empty word part of $A^+$?
My professor mentioned the below statement in class but without a proof. I am trying to prove it for myself as I don't understand 100% why this is always the case. Given is A, a subset of {0,1}$^\*$.

ε $\in\ A^+$ \<-\> ε $\in\ A$, where ε is the empty word. I thought of doing a proof by contradiction to show -\> by assuming the empty word is not part of A$^+$.

Any help is much appreciated!

# Answer
You can look at the length of words.

Any element of $A^+$ is a concatenation

$$ a\_1 a\_2 \ldots a\_n $$

where $a\_i \in A$ and $n \geq 1$. The *length* of such a word is

$$ L(a\_1 a\_2 \ldots a\_n) = L(a\_1) + L(a\_2) + \ldots + L(a\_n) $$

But the length is always nonnegative; for example,

$$ 0 \leq L(a\_1) \leq L(a\_1) + L(a\_2) + \ldots + L(a\_n)$$

If you're given that

$$ \epsilon = a\_1 a\_2 \ldots a\_n $$

then putting all of the above together gives

$$ 0 \leq L(a\_1) \leq L(\epsilon) = 0 $$

and thus $L(a\_1) = 0$, so $a\_1 = \epsilon$ and $\epsilon \in A$.

---

If you were to assume that $\epsilon \notin A$, you could modify the above argument by the fact that $L(a\_i)$ must be *positive*, and so

$$ 0 \< L(a\_1) \leq L(a\_1) + L(a\_2) + \ldots + L(a\_n) $$

and then the final deduction would be

$$ 0 \< L(\epsilon) $$

which is a contradiction.
> 2 votes

# Answer
For any languages $K,L$ the shortest string in $K(L\cup\varepsilon)$ is the shortest string in $K$.

Now $A^+ = A(A^+\cup\varepsilon)$. Hence the shortest string in $A^+$ is the shortest string in $A$.
> 1 votes

# Answer
This trivially follows from the definition of the Kleene plus operation. $A^+$ is known as the Kleene plus operation on the set $A$. This operation omits the $A^0=\\{\epsilon\\}$ in the the Kleene star operation on the set $A$. So, $\epsilon \in A^+ = A \cup A^2 \cup A^3\dots$ if and only if $\epsilon \in A$.

**Proof of $\epsilon \in A^+ \Rightarrow \epsilon \in A$**.
Let $ \epsilon \in A^+$. Then $ \epsilon \in A \cup A^2 \cup A^3\dots$. This means $\epsilon \in A^i$ for some $i\>0$. But $\epsilon \in A^i$ if $\epsilon \in A A\dots A$ ($i$ times) if $\epsilon \in A$.

**Proof of $ \epsilon \in A \Rightarrow \epsilon \in A^+$**.
Since $A^+ = A \cup A^2 \cup A^3\dots$ and $\epsilon \in A$, we have $\epsilon \in A^+$.

---

If $A$ and $B$ are sets of strings then $AB $ is defined as a set $$\\{uv \mid u \in A, v\in B\\}$$ and $$A^n = A A \dots A \ \ \ (n \text{ times })$$
> 0 votes

---
Tags: formal-languages, proof-techniques, kleene-star
---


# Question
Title: Difference between bit times and milli seconds
The propagation delay between two links is 200 bit time .....i want to know what is the difference between 200 bit time and 200 mill seconds

# Answer
The propagation delay is time it takes to transfer one bit from sender to receiver.
200 ms would be such time, for Bit Times it is the duration of given bits in the medium, the first bit of a header reaches the receiver before the last bit was transmitted by the source (here also given 200).
> 1 votes

---
Tags: computer-networks
---


# Question
Title: What do you call a lower/upper bound that is the best one?
I have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it were an optimization problem then I would call it the optimal value or the optimal bound. Is that right?

# Answer
> 1 votes
The phrase you're looking for is tight bound or in your case a *tight upper bound*.

---
Tags: optimization, combinatorics, performance
---


title: GCD of a pair of products

text:
# Question
Title: GCD of a pair of products
I have two numbers, which are each the product of a large number of smaller numbers that I know. I want to find the GCD (Greatest common divisor) of these two numbers. Is there any way I can make use of the partial factorization I have to speed up the process?

In particular, each larger number is the product of $2^{15}$ smaller numbers, each of which is on the order of $2^{4000}$. I don't know anything about the factorization of the smaller numbers.

Edit: While the input numbers are about 120,000,000 bits, the GCD is about 500,000 bits. The factors of the numbers are in particular in sequence. They are all integers in a consecutive range.

All of the GCD algorithms I've seen make use of the numbers directly, not in a partially factored form or anything. Are there any algorithms which could incorporate this information to speed things up?

# Answer
> 1 votes
You can compute the pairwise GCDs of the factors. You have to divide out the GCDs from the factors to avoid finding the same GCD factor twice:

```
a[1...m] = [given factors of A]
b[1...n] = [given factors of B]
g = 1
for i from 1 to m do
    c = a[i]
    for j from 1 to n do
        d = gcd(c, b[j])
        g = g * d
        c = a[i] / d
        b[j] = b[j] / d
return g

```

Unfortunately, I don't think that this is not notably faster than the computation of the GCD of the two numbers A and B.

# Answer
> 0 votes
There was a similar problem that has been solved reasonably efficiently: Assume you are using RSA which is all built on products of two large primes, where the products can't be factored in reasonably time. But if you have two products pq and p'q' and either p=p' or q=q' then you can calculated their gcd and get p=p' or q=q' and the other factor is trivial. Of course if p=p' and also q=q' then this is no help.

No imagine someone generates a billion such products and is a bit careless. A hacker finds that quite a few numbers are identical, so p=p' and q=q', so it's a good guess that quite a few pairs have a gcd ≠ 1. And that has happened in real life with routers whose encryption could be cracked as a result.

Sorry, I don't have any reference and the story is a bit old, but you should be able to find it. Was a few years ago, maybe six or so.

---
Tags: algorithms, number-theory, performance
---


# Question
Title: Does rice theorem applies to languages only or does it apply to machines as well?
Rice theorem says that any non trivial property of a language recognized by a Turing Machine is undecidable.

Now does this theorem applies to machines as well since we can define a language consisting of strings which are encoding of machines?

For example whether a machine will run more than 100 steps on some input? This is nontrivial but wikipedia says it is decidable.

# Answer
> 1 votes
The Rice's theorem can also be stated in terms of index sets of TMs.

Lets start with a basic definition of a property of a language. A *property of a language* is a set of languages. For example $$P\_{reg} = \\{L \mid L \text{ is regular } \\}$$ and $$P\_{fin} = \\{L \mid L \text{ is finite } \\}$$ are properties of languages.

We also define a language of indexes as $$L\_P = \\{\langle M \rangle\ \mid L(M) \in P\\}$$ In simple words, a set of TM indexes such that the language recognized by $M$ belongs to the property $P$. Now, the Rice's theorem states that if $P$ is nontrivial then the problem whether $n \in L\_P$ is undecidable, i.e., $L\_P$ is undecidable.

However, we cannot apply it to the following sets $$L\_1 = \\{\langle M \rangle\ \mid M \text { has } 5 \text{ states} \\}$$ and $$L\_2 = \\{\langle M \rangle\ \mid M \text { never writes to the tape} \\}$$ since they talk about properties of Turing machines and not languages (we cannot say a language $L$ has 5 states). They may be decidable or not which may be proved the other way (not using the Rice's theorem). For example, $L\_1$ is decidable since you simply count the number of states of a TM.

So, the answer to your question

> does this theorem applies to machines

depends on what set of TMs you are talking about. If this is a set of TMs whose recognizing languages belong to some nontrivial property of a language then the answer is "yes", otherwise the answer is "no".

# Answer
> 0 votes
Rice's theorem talks about the decision problem associated to a set of computable functions. There isn't a unique correspondence between computable functions and Turing machines, consider for example a machine that always returns $YES$ and a machine that does nothing for 100 steps and then returns $YES$.

You may apply Rice's theorem to a set of machines $S$ if $S$ is such that for all $x, y$:

$\qquad (M\_x \in S \wedge \phi\_x = \phi\_y) \rightarrow M\_y \in S$

where $M\_z$ is the $z$-th Turing machine in any Goedelization and $\phi\_z$ is the function computed by the $z$-th Turing machine.

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


title: Constructing a decider for a language

text:
# Question
Title: Constructing a decider for a language
I'm confused about the idea of constructing a decider for a language and i need some help with it.

For example, if i have an enumerator M1 for a language L and another enumerator M2 for the complement of L, how do i construct a decider for L that uses both enumerator M1 and M2?

I understand that i would first introduce a Turing Machine with an input string and simulate it but I'm lost in the next stage of constructing a decider. By the way, enumerators are Turing Machines that outputs a sequence of strings.

Could anyone please explain on how do i construct a decider for the language L that uses both enumerators M1 and M2?

# Answer
M1 and M2 together will eventually enumerate every possible string. So the trick is to alternate between them. Then you get an enumerator that enumerates all strings. Every time you compare the output string of the enumerator to your input string. At some point they will be equal. Then you just have to look whether you have used M1 or M2 in the last step.

You compute for input string w:

```
M1(0)=w?, M2(0)=w?, M1(1)=w?, M2(1)=w?, M1(2)=w?, M2(2)=w?,...

```
> 2 votes

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


# Question
Title: How to Formally define $\delta$ in a DFA?
I have made a **draw** of a DFA, and I have to formally define the automaton in the following format. Let $A$ be the necessary automaton : $$A=\<\Sigma,Q,q\_0,\delta,F\>$$

Where $\Sigma=\\{a,b,c\\}, Q=\\{q\_0,...,q\_4\\}, F=q\_3$ and $q\_0$ is the initial state.

The drawing is attached to this post:

Can I do something like $\delta\_{A}(q\_0,\sigma)=q\_1$ **for each state? should I unite a few states together?**

Thank you!

# Answer
> 2 votes
You're over-thinking this.

You need to define the value of $\delta(q,\sigma)$ for every $q\in Q$ and $\sigma\in\Sigma$ and, ideally, make it clear that you have done so. What format you use is a matter of your and your instructor's personal preferences.

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


# Question
Title: A two-tape deterministic Turing machine that recognizes an exponential string
How can I describe a Turing Machine recognizing the language $P=\\{a^{2^n} | n \geq 0 \\}$?

This Turing Machine is deterministic and uses **two tapes**, both bidirectional and R / W (read & write)

The computation should be done in linear time.

I've read Counters in Turing machines but it doesn't address my question. It can help but it doesn't answer my question. Turing Machines with $n$-tapes have the same computability that Turing Machines with one tape, but different behavior. Here I'm asking about the behavior of a two-tape TM.

**My approach:**

I think I may use the first tape as input tape and copy every character in the second tape. But I don't know how to keep track the exponential behavior.

# Answer
> 3 votes
To expand fade2black's answer; this is a simple proof by induction that the following TM

```
State    Symbol    Write  Move   Newstate
start    0         1      L      tolsb
start    1         0      R      carry

tolsb    _         _      R      start
tolsb    *         *      L      tolsb

carry    0         1      L      tolsb
carry    1         0      R      carry

```

performs a binary count from $0^n$ to $1^n$ in less than $2^{n} + n^3$ steps. Initially the head is placed on the LSB (which, we assume, is on the left part of the input string).

You can view a simulation of the Turing machine here.

We prove by induction that starting on the leftmost $0$, it counts up to $1^n$ and, at the end, the head is still placed on the LSB.

* case $n = 1$:

Immediate

```
 _ 0    start
   ^
 _ 1    step 1
 ^
 _ 1    step 2
   ^

```
* case $n$: suppose that it holds for $n-1$; i.e. it can count up from $0^{n-1}$ to $1^{n-1}$ in less than $2^{n-1} + (n-1)^3$ steps;

Then after less than $2^{n-1} + (n-1)^3$ steps the head is on LSB:

```
   1 2 3 ...   n
 _ 1 1 1 ... 1 0
   ^

```

It will convert all $1$s to $0$ and propagate the carry to the MSB and convert the MSB to $1$ in $n$ steps:

```
   1 2 3 ...   n
 _ 0 0 0 ... 0 1
             ^

```

Then it will go back to the LSB in $n$ steps

```
   1 2 3 ...   n
 _ 0 0 0 ... 0 1
   ^

```

Then it will count up to $1^n$ using less than $2^{n-1} + (n-1)^3$ steps.

```
   1 2 3 ...   n
 _ 1 1 1 ... 1 1
   ^

```

The total number of steps is less than:

$$2^{n-1} + 2^{n-1} + 2(n-1)^3 + 2n \leq 2^n + n^3$$

So if we have as input $w = a^{2^n}$; we can perform a binary count (on the second tape) in linear time $O( |w| )$.

# Answer
> 2 votes
A simple way is to scan the first (input) tape from left to right, and use the second tape to count the number of $a$s (you read) in binary format. Every time you read a single $a$ increase the counter (on the second tape) by $1$. When you reach the end of the input you check the second tape whether its content is of the form $100\dots000$. If it is then accept, otherwise reject.

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


# Question
Title: How does the Y combinator exemplify "Lambda calculus inconsistency"?
On the Wikipedia page for Fixed Point Combinators is written the rather mysterious text

> The Y combinator is an example of what makes the Lambda calculus inconsistent. So it should be regarded with suspicion. However it is safe to consider the Y combinator when defined in mathematic logic only.

Have I entered into some sort of spy novel? What in the world is meant by the statements that $\lambda$-calculus is *"inconsistent"* and that it should be *"regarded with suspicion"*?

# Answer
> 53 votes
It's inspired from real events, but the way it's stated is barely recognizable and “should be regarded with suspicion” is nonsense.

*Consistency* has a precise meaning in logic: a consistent theory is one where not all statements can be proved. In classical logic, this is equivalent to the absence of a contradiction, i.e. a theory is inconsistent if and only if there is a statement $A$ such that the theory proves both $A$ and its negation $\neg A$.

So what does this mean regarding the lambda calculus? Nothing. The lambda calculus is a rewriting system, not a logical theory.

It is possible to view the lambda calculus in relation to logic. Regard variables as representing a hypothesis in a proof, lambda abstractions as proofs under a certain hypothesis (represented by the variable), and application as putting together a conditional proof and proof of the hypothesis. Then the beta rule corresponds to simplifying a proof by applying modus ponens, a fundamental principle of logic.

This, however, only works if the conditional proof is combined with a proof of the right hypothesis. If you have a conditional proof that assumes $n=3$ and you also have a proof of $n=2$, you can't combine them together. If you want to make this interpretation of the lambda calculus work, you need to add a constraint that only proofs of the proper hypothesis get applied to conditional proofs. This is called a type system, and the constraint is the typing rule that says that when you pass an argument to a function, the type of the argument must match the parameter type of the function.

The Curry-Howard correspondence is a parallel between *typed* calculi and proof systems.

* types correspond to logical statements;
* terms correspond to proofs;
* inhabited types (i.e. types such that there is a term of that type) correspond to true statements (i.e. statements such that there is a proof of that statement);
* program evaluation (i.e. rules such as beta) correspond to transformations of proofs (which had better transform correct proofs into correct proofs).

A typed calculus that has a fixed point combinator such as $Y$ allows building a term of any type (try evaluating $Y (\lambda x.x)$), so if you take the logical interpretation through the Curry-Howard correspondence, you get an inconsistent theory. See Does the Y combinator contradict the Curry-Howard correspondence? for more details.

This is not meaningful for the pure lambda calculus, i.e. for the lambda calculus without types.

In many typed calculi, it's impossible to define a fixed point combinator. Those typed calculi are useful with respect to their logical interpretation, but not as a basis for a Turing-complete programming language. In some typed calculi, it's possible to define a fixed point combinator. Those typed calculi are useful as a basis for a Turing-complete programming language, but not with respect to their logical interpretation.

In conclusion:

* The lambda calculus is not “inconsistent”, that concept does not apply.
* A *typed* lambda calculus that assigns a type to every lambda term is inconsistent. Some typed lambda calculi are like that, others make some terms untypable and are consistent.
* Typed lambda calculi are not the sole *raison d'être* for the lambda calculus, and even inconsistent typed lambda calculi are very useful tools — just not to prove things.

# Answer
> 8 votes
I'd like to add one to what @Giles said.

The Curry-Howard correspondence makes a parallel between $\lambda$-terms (more specifically, the *types* of $\lambda$-terms) and proof systems.

For example, $\lambda x.\lambda y.x$ has type $a \to (b \to a)$ (where $a \to b$ means "function from $a$ to $b$"), which corresponds to the logical statement $a \implies (b \implies a)$. The function $\lambda x.\lambda y.xy$ has type $(a \to b) \to (a \to b)$, corresponding to $(a \implies b) \implies (a \implies b)$. We can convert any lambda-calculus type to a logical tautology by, in a sense, "pattern matching" on functions.

The problem arises when we consider the Y combinator, defined as $\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$. The issue arises because we expect the Y combinator, as a "fix-point" combinator, to have type $(a \to a) \to a$ (because it takes a function from a type to that same type, and finds a fixed-point for that function, which has that type). Converting this to a logical statement yields $(a \implies a) \implies a$. This is a contradiction:

$$(a \implies a) \implies a \\ \top \implies a \\ a \\\(\neg a \implies \neg a) \implies (\neg a) \\ \top \implies \neg a \\ \neg a$$

Accepting $(a \to a) \to a$ in a type system leads to the type system being inconsistent. This means we can either

* Disallow types like $(a \to a) \to a$ in a type system (this gives you the Simply typed $\lambda$-calculus), or
* Live with the type system being inconsistent as a system of logical deduction.

---
Tags: lambda-calculus, combinatory-logic
---


# Question
Title: What is the runtime of the 'Risch Algorithm'?
I have been trying to find the upper bound on the runtime of the 'Risch algorithm' used for finding the integral of mathematical functions, but have been unable to do so.

https://en.wikipedia.org/wiki/Risch\_algorithm

Does anyone know where I would be able to find the runtime of the 'Risch Algorithm'?

# Answer
> 3 votes
The Risch algorithm is undecidable by Richardson Theorem if absolute value is allowed or semi-undecidable with $\log\_2, \pi, e^x, \sin x$.
*Akitoshi Kawamura* in his dissertation Computational Complexity in Analysis and Geometry has proved that integration is $\\#P{-}complete$ operation.

There are multiple modifications of the Risch algorithm, but still nobody have implemented the full algorithm (source: Wolfram, survey over CAS systems) in algebraic case.

---
Tags: runtime-analysis, upper-bound
---


# Question
Title: Why is the array used for a restricted hashing scheme always sized to a 4k + 3 prime?
Why is the array used for a restricted hashing scheme always sized to a 4k + 3 prime? When they talk about a restricted hashing scheme are they talking about a non perfect hashing which includes having a collision algorithm which resolves that problem? Can someone please help me?

# Answer
> 1 votes
The mentioned scheme is the most probably Quadratic probing collision resolution in the Hash Table, so it is non-perfect.

The $4k + 3$ prime size of the table is to allow all cells to be probed, the size of different length will result in non accessible cells in the array, degrading performance and wasting space.

Please read about limitations of QP.

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


# Question
Title: Incorrect proof of closure under the star operation using NFA results in the NFA recognizing undesired strings?
I'm currently reading the book *Introduction to the Theory of Computation (2nd or 3rd Ed.)* by *Michael Sipser*, and have stumbled upon a question in *Chapter 1 - Regular Languages*, namely when the author is presenting the proof idea of *Theorem 1.49* \- **"The class of regular languages is closed under the star operation."** using NFA.

The approach suggested is that, if we have a regular language $A\_1$ and want to prove that $A\_1^\*$ also is regular, we can take an NFA $N\_1$ and modify it into an $N$ as in the image below, which is then a particular NFA recognizing $A\_1^\*$.

He noted:

> One (slightly bad) idea is simply to add the start state to the set of accept states. This approach certainly adds $ε$ to the recognized language, but it may also add other, undesired strings.

I have drawn the "bad" NFA as below and tried to figure out why this will result in undesired strings. However, I can't find an example of when the an undesired string is recognized. Why will this idea result in the NFA recognizing undesired strings?

Could someone point this out for me or give me a hint, or have I misunderstood the author? Thanks in advance!

# Answer
Consider a two state automaton for the language $a^\*b$, two transitions from the initial state, one looping with label $a$, the other with label $b$ to the final state.

Making the initial state final, would also accept $a^\*$.
> 13 votes

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


# Question
Title: Do system calls always means a context switch?
When a system call takes place some kernel code must be executed. If some kernel code is being executed it means it can alter register values. So before this code gets executed the old process state must be saved. This is called context switch. Now Wikipedia says that not all system calls need context switch. How is this possible?

# Answer
> 5 votes
Depends on how you define a context switch.

In the traditional sense it means saving all registers/cpu state changing the mmu state and then going elsewhere to answer the call and after it's finished restore everything.

It is not necessary to save all state for all operation. For example a mutex lock needs to check no other thread/process is using the mutex and then set it marked.

In a *single-core* cpu you can do that by ensuring that no interrupts happen during the mutex operation and then by virtue of being passed the point of interrupts being disabled you know you are the only one touching the mutex at that point. The only way another thread could be in the middle of the lock operation is if it re-enabled interrupts or it context switched out because the mutex was already taken. Both scenarios and where in the code they can happen are under full control of the kernel code.

Having said all that, saving the context isn't that expensive. The more expensive part is all the cache misses that will happen as the instruction flow goes to cold memory.

# Answer
> 17 votes
A system call does not necessarily require a context switch in general, but rather a privilege switch. This is because the kernel memory is mapped in each process memory. The user process cannot access the kernel's memory because the memory mapping indicates which part are for the user and which parts are for the system. Thus a system call is really just a change of privilege, not of process. On some systems, like micro-kernels, a system call may involve a context switch because drivers are in a different process. But on monolithic systems like Linux this is not necessary. Linux also supports what is called the vDSO to implement some system calls entirely in userspace.

EDIT: attached a picture

---
Tags: operating-systems
---


# Question
Title: Are these two regular expressions equivalent?
$u^\*v(w \cup xu^\*w)^\*$ and $u^\*v(w \cup x(u)^\*w)^\*$

Is that extra set of parentheses around the second $u$ needed?

# Answer
> 1 votes
First, an alternative notation (what I usually use, and it is my personal preference) to join two regular expressions is to use '+' instead of $\cup$ which is used to denote a union of two sets. So your regular expression can be written as $$ u^\*v(w + xu^\*w)^\* $$ or sometimes $$ u^\*v(w \mid xu^\*w)^\* $$ instead of $$ u^\*v(w \cup xu^\*w)^\* $$ That pair of parentheses around the second $u$ is redundant and so not needed since the Kleene star operator applies to only $u$ in $xu^\*w$, i.e., $xu^\*w$ and $x(u)^\*w$ denote the same set.

# Answer
> 0 votes
No, there is not requirement of an extra set of parentheses around the second u in this equation : u∗v(w∪x(u)∗w)∗

because () is useful for more than one operand or operation required in one parentheses.

---
Tags: regular-expressions
---


# Question
Title: Giving a regular expression for a situation of a question
I have the following question regarding a situation given and we are then required to derive a regular expression out of it.

What i have to do now i to give a regular expression for this language described by the knob movement from A,B and C. Because i have to go through B if i were to traverse to C, and vice versa, i know that B must be present as part of the expression.

Here's what i attempted:

ABC U ABA U BAB U BCB U CBA U CBC

Simplifying it:

AB(C U A) U B(AB U CB) U CB(A U C)

I'm not entirely sure if I'm doing it right as I find out that I'm brute forcing. I'm terrible at deriving regular expressions so I'll appreciate some corrections.

# Answer
Here's a rough sketch: let $S\_a, S\_b, S\_c$ be the set of valid strings of the language starting with $a, b, c$ respectively. Observe that:

$\qquad S\_b = ((a^\* + c^\*)b)^\*$

Furthermore:

$\qquad S\_a = aS\_a + bS\_b$

and symmetrically for $S\_c$. Therefore we may replace $S\_b$ in the latter, obtaining a "recursive" equation solvable by Arden's lemma.
> 1 votes

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


# Question
Title: Quick groupby - is this a well known algorithm?
I am interested in an algorithm that accepts an array that places identical elements contiguously but the array doesn't necessarily have to be sorted.

E.g. if input is

`array = ["a", "a", "c", "b", "c"]`

then output

`groupby(array) = ["a", "a", "c", "c", "b"]`

or

`groupby(array) = ["c", "c", "a", "a", "b"]`

etc. The point being the final order of the array isn't important; the only requirement is that identical elements have to be placed contiguously.

One algorithm that is inspired by quicksort is to pick an element, called it `pivot`, and divided the array into 3 segments with the first segment being all elements that equal `pivot`; and the other two begin those are "less than" and "greater than" `pivot`. Elements within each segment have to be placed contiguously.

The segmentation can be achieved in `n` time using a simple adaption of the pivoting in quicksort and then apply the algorithm recursively on the "less than" and "greater than" segment.

Is this algorithm well known and has a name? Or is it a novel algorithm?

# Answer
> 1 votes
Asymptotically and under usual assumptions, the problem you state is as hard as sorting, by reduction from duplication.

If you had a $o(n \log n)$ algorithm to solve your problem, you could combine it with a constant number of array scans to produce a $o(n \log n)$ time procedure to test whether the array contains a pair of identical elements, in contradiction with the well-known $\Omega(n \log n)$ lower bound on that problem.

I don't think there's much to be gained with custom-tailored algorithms in practice, either: a well-optimized implementation of a generic sorting algorithm should be -- without further assumptions -- as efficient as you can get.

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


# Question
Title: Context-free string that satisfies constraint?
I'm not sure on how to come up with a string that is in terms of $p$ for

$ a^ib^jc^k$ where $ i+j = k^2$

Where $p$ is the pumping length. I can't seem to find anything in terms of $p$ that satisifies the constraint. Any ideas or sugeestions are appreciated!

# Answer
> 1 votes
It is not necessary to define a string that has exactly length $p$. It only has to have length at least $p$. So $(i,j,k) = (2p^2,2p^2,2p)$ so that $2p^2+2p^2 = (2p)^2$ for a string of length $4p^2+2p$ would be OK.

---
Tags: context-free, pumping-lemma
---


# Question
Title: How to use stable matching algorithm in order to determine optimal schedule?
This is a problem 1.6 from the book Algorithm Design by Kleinberg/Tardos:

> There's a company that manages ships that do various tasks when in port. There're $n$ ships, $n$ ports, $m$ days in a month such that $m\>n$.
>
> At any given day there can't be two ships from the company in the same port. $(\*)$
>
> The company wants to perform maintenance on all the ships this month, via the following scheme: they want to truncate each ship’s schedule: for each ship $S\_i$, there will be some day when it arrives in its scheduled port and simply remains there for the rest of the month (for maintenance). This means that $S\_i$ will not visit the remaining ports on its schedule (if any) that month, but this is okay. So the truncation of $S\_i$’s schedule will simply consist of its original schedule up to a certain specified day on which it is in a port $P$; the remainder of the truncated schedule simply has it remain in port $P$.
>
> Now the company’s question to you is the following: Given the schedule for each ship, find a truncation of each so that condition $(\*)$ continues to hold: no two ships are ever in the same port on the same day. Show that such a set of truncations can always be found, and give an algorithm to find them.

As far as I understand from the example the ship must visit at least one port before it's on maintenance (although this condition is not mentioned in the book). I also assume that each ship is supposed to visit all ports. Then because there're more days than ports and ships we could simply create an array with the all the ports and then upon each encounter of a port we'd check if it's already been visited by another ship: if not then we leave the ship for maintenance at the port; if it's already been visited then we keep going forward until we encounter a previously unvisited port.

This is solution is too simple and it's not using Gale Shapley matching algorithm which I think is expected to be used in the book.

# Answer
> we could simply create an array with the all the ports and then upon each encounter of a port we'd check if it's already been visited by another ship: if not then we leave the ship for maintenance at the port; if it's already been visited then we keep going forward until we encounter a previously unvisited port.

The following is a counterexample to your algorithm:

> Ship 1: Port 1, at sea, Port 2, at sea, Port 3, at sea
>
> Ship 2: at sea, Port 1, at sea, Port 2, at sea, Port 3
>
> Ship 3: Port 2, at sea, Port 3, at sea, Port 1, at sea

This has the solution where Ship 1 stays at Port 3, Ship 2 stays at port 2, and Ship 3 stays at Port 1.

But your algorithm does the following:

* Day 1:

+ Ship 1 arrives at Port 1. Port 1 hasn't been visited so it stays for maintenance.
    + Ship 3 arrives at Port 2. Port 2 hasn't been visited so it stays for maintenance.
* Day 2:

+ Ship 2 arrives at Port 1 where Ship 1 is already staying, which isn't allowed (and you're not allowed to not have Ship 2 not arrive at Port 1 given the rules described in the end of the problem's 3rd paragraph).

If we add to your algorithm your unjustified assumption that ships can't stay for maintenance at the first port they visit, then your algorithm does the following:

* Day 1:

+ Ship 1 arrives at Port 1. It's not allowed to stay at the first port it visits.
    + Ship 3 arrives at Port 2. It's not allowed to stay at the first port it visits.
* Day 2:

+ Ship 2 arrives at Port 1. It's not allowed to stay at the first port it visits.
* Day 3:

+ Ship 1 arrives at Port 2. Port 2 hasn't been matched yet so it stays there.
    + Ship 3 arrives at Port 3. Port 3 hasn't been matched yet so it stays there.
* Day 4: Ship 2 arrives at Port 2 where Ship 1 is already staying.

As for the question of how to solve this using stable matchings, here's a hint: you're trying to find a matching between ships and ports (where they stay for maintenance), such that the following is impossible:

* Ship A is matched to Port A
* Ship B is matched to Port B
* Ship A arrives at Port B before it arrives at Port A (it's not yet on maintenance when it gets to Port B)
* Ship A arrives at Port B after Ship B does (so Ship B is already staying there for maintenance)

How can you translate that into preferences for ship-port pairs so you can apply Gale Shapley matching?
> 2 votes

---
Tags: algorithms, matching
---


# Question
Title: Is the problem of deciding whether a Context free grammar generates exactly K strings is decidable?
I am reading "Introduction to Theory of Computation" by Michael Sipser. One of the exercise problems asks to verify whether the problem of deciding whether a Context free grammar generates exactly K strings is decidable?

This problem has two parts

1. K can be infinite (I know how to solve this. If the grammar has any kind of loop then it will generate infinite number of strings
thus k=infinite.
2. K can be finite. I don't know how to solve this. Any Ideas?

# Answer
> 2 votes
As you said, if there is a cycle of variables (non-terminals), the language generated is infinite. If you can also show the converse, that is, if the language is infinite, then there exists a cycle of variables, then you can construct a machine to do the following given a finite $K$:

1. Given a context-free grammar $G$, check if it has any cycles of non-terminals.
2. If yes, then $L(G)$ is infinite, so output **no**; otherwise, $L(G)$ is necessarily finite (using the converse property above, which you need to prove).
3. Since the grammar generates a finite number of strings, it is safe to try all possible paths of productions starting from the starting variable. Each such path corresponds to a string in $L(G)$. Eventually, all possible paths will be exhausted (as otherwise $L(G)$ would be infinite), at which point you will have generated $L(G)$. If $|L(G)| = K$, output **yes**, otherwise output **no**.

---
Tags: formal-languages
---


# Question
Title: Find height of deepest FULL level in binary tree
Suppose I have a binary tree that is guaranteed to have at least one level that holds the maximum amount of nodes possible. I want to find the **height** of the **deepest** level that is full/holds the maximum amount of nodes possible. I have a function `highestFull()` that calls it's recursive version `highestFull(Node* t)` which is initially given the **root**. I cannot use any of the standard library functions.

How do I approach this problem? I am looking for the most intuitive solution, not the most clever. I found an answer here, but I cannot understand why it works. I really want to understand the thought process behind the solution.

# Answer
How would you determine the answer if you were looking at a graphical representation of the tree? You would scan all the levels from the root downwards until you found one that isn't full.

Formally, that is a breadth-first search of the tree that stops whenever a node with less than two children is found. Since you are working on a tree rather than a generic graph, you may rewrite it as follows:

* Let $Q$ be a new queue of nodes, initially containing only the root.
* While $v$, the first element of $Q$, has two children $v\_l$ and $v\_r$, remove $v$ and enqueue both $v\_l$ and $v\_r$.
> 1 votes

# Answer
My solution unlike the answer you indicate in your post assumes a general tree.

The idea is to recursively traverse all children. When we reach a leaf node we know it cannot be a node with the maximum nodes possible and return -1. If the current node is an internal node then we have two possibilities: either there is a full node in one of its subtrees, or the node itself is full. So we recursively check each subtree. Upon return from a recursive call, we check if its return value is -1 or a positive one equal to the height of the full node. -1 means we have not found any.

When we finish scanning of all subtrees of the current node we must check if we found any full node in one of its subtrees. If found we return its height. If not we check whether the current node is full. If it is full we return the current height, else we return -1, i.e., we failed to find. The following pseudocode implements this idea.

```
 Search(node, height)
   if node is leaf
    return -1

   #search in subtrees
   max_height = -1
   loop on node's children |child|
     hgt = Search(child, height+1)
     if max_height < hgt
       max_height = hgt
    end-loop

    if max_height == -1 #no full node found in any of subtrees
      if node's children count == MAX_NODES_POSSIBLE
        return height
      else
        return -1
    else
      return max_height
 end-Search

```

Initially we call `Search(root, 0)`.
> 0 votes

---
Tags: algorithms, data-structures, binary-trees, recursion
---


# Question
Title: Compute median in unsorted array in $\mathcal{O}(\log{}n)$ space and $\mathcal{O}(\log{}n)$ passes
I want to compute the median in an array of size $m$ which consists of **distinct** integers from $\\{0, 1, ..., n-1\\}$, I have $m\<n$. By median I mean the middle element (rounding up/down if the array size is even) in the sorted version of the array.

Ideally, the expected number of passes over the array should be $\mathcal{O}(\log{}n)$, the used memory should be $\mathcal{O}(\log{}n)$ bits and the solution should be exact. I'm flexible with the time complexity as long as it's feasible.

Since finding the median in an unsorted array is such a common problem I expected to quickly find some solution which suits my needs but after some research I'm wondering if this is even possible. Does anyone know a solution or where I could expect to find one?

# Answer
As @Yuval Filmus pointed out, you can use a histogram approach.

Since you know the number of integers and that they are all distinct you immediately know the rank. Now you create 2 histograms/buckets, one for all integers whose MSB is 0 the other one for 1's. By the number of elements in the buckets you can conclude in which one the median must be. You have effectively found the MSB of the median, simply repeat this procedure for the rest of the bits.

A Java implementation which does this can be found here.
> 0 votes

# Answer
The natural algorithm determines the $\log n$ bits of the median, MSB to LSB. Suppose that we have determined the $k$ MSBs of the median, $b\_{m-1},\ldots,b\_{m-k}$. Determine the number of integers in the array whose $k+1$ MSBs are $b\_{m-1},\ldots,b\_{m-k},1$, and use this to find the $(k+1)$th MSB of the median.

This algorithm uses $O(\log n)$ passes and $O(\log m + \log n) = O(\log n)$ space.
> 4 votes

---
Tags: algorithms, randomized-algorithms, selection-problem
---


# Question
Title: Finding multiple shortest path trees from an undirected, weight graph
In an undirected, weighted graph G the set of shortest paths from an arbitrary start vertex s form a spanning tree of G. We're calling this spanning tree a shortest path tree.

How do I find an example to show that, even if all edge weights are different (and non-negative), it is possible to have more than one shortest paths tree?

# Answer
> 0 votes
As mentioned by BlueRaja you can prove this with only three nodes.

Take 3 nodes (A,B,C) with the following edge weights:

A-\>B = 1

B-\>C = 2

A-\>C = 3

Now if you take A as source vertex and try to find the shortest paths you can get two different trees.

1- The edge AC and AB are present. Cost to C=3 and Cost to B=1.

2- The edge AB,BC are present. Cost to C=3 and Cost to B=1.

As you can see all edge weights are distinct yet we are getting two different shortest spanning trees.

The basic idea is that: Let C be the least cost of reaching a particular node in a spanning tree. Then it may be possible to find another path to C with the same cost if the sum of edge weights constituting the path is equal to C.

---
Tags: algorithms, graphs, shortest-path, weighted-graphs
---


# Question
Title: Are all finite strings over some infinite alphabet countable?
Over some infinite alphabet $\Sigma$, can we state that the set of all possible finite strings is countable?

# Answer
If the alphabet is uncountable then the set of all possible finite strings is uncountable. If you allow infinite length strings then by the diagonalization argument the set is also uncountable.

Assume the alphabet is countable and strings have finite length. Let's assign to each alphabet symbol a natural number, i.e., each symbol corresponds to a natural number and denote a string by a sequence of numbers. For example, if $a$ corresponds to $2$, $b$ to $5$, and $c$ to $11$ then $aabcb$ would be denoted by $2 \ 2 \ 5 \ 11 \ 5$ (I separate them by a single space to avoid confusion). We will prove that the set of all strings is countable.

We group every string of length $n$ whose individual symbols sum to $k$ into the set $C\_{n,k}$. For example $000 \in C\_{3,0}$, $1192 \in C\_{4,13}$, and $1\ 13 \ 3 \ 1 \in C\_{4,18}$. For each pair $\langle n,k \rangle$, $C\_{n,k}$ is clearly finite and hence is countable. Furthermore, any string $a\_1\dots a\_n$ does belong to $C\_{n,k}$, where $k=a\_1+\dots +a\_n$ which means every string is included in some set $C\_{n,k}$. Since the set of all possible pairs $\langle n,k \rangle$ is countable the union of all possible $C\_{n,k}$, i.e, $\bigcup\_{\langle n,k \rangle \in N\times N}{C\_{n,k}}$ is also countable.
> 4 votes

# Answer
Another way: If $\Sigma=\\{\mathbb{a\_0, a\_1,a\_2,...}\\}$ is countable, then to show that $\Sigma^\*$ is countable we need only produce an injection $f: \Sigma^\*\to\mathbb{N}$. But this is easy; e.g., just let $f(\[\mathbb{a\_{i\_1},a\_{i\_2},...,a\_{i\_n}}\])$ be the number whose *hexadecimal* (or any base $\>10$) representation is $\tt{Ai\_1Ai\_2...Ai\_n}$, where $\tt{i\_k}$ is the *decimal* representation of $i\_k$. E.g., $f(\[\mathbb{a\_0,a\_{12},a\_7}\]) = \tt{A0A12A7}\_{hex}=168432295\_{dec}$.
> 0 votes

---
Tags: strings, uncountability
---


# Question
Title: Solving SAT correctly on all but $poly(m)$ formulas
The question is to show that there is no deterministic polynomial time algorithm that solves SAT correctly on all but $poly(m)$ formulas of size $m$, for every $m \geq 0$ unless $P \ne NP$.

I know that if $P = NP$, a polynomial time algorithm exists that, given a Boolean formula φ, actually produces a satisfying assignment for φ if it is satisfiable. But I can't really understand how a poly time algorithm can solve SAT correctly on only $poly(m)$ formulas, if $P \neq NP$. Am I missing something in understanding the problem or there is a catch?

# Answer
I'll provide a sketch.

Given any formula $\varphi$ of size $m$, we can rewrite it in an equisatisfiable way as $\varphi \land p$ where $p$ is a fresh propositional variable. In this way, we can generate an infinite amount of equisatisfiable formulas.

Now, exploiting this, it is easy to find a way to generate, in PTIME, $2 poly(m')+1$ formulas $\varphi'$ equisatisfiable wrt $\varphi$, where each such $\varphi'$ is of size $m'$. We can then decide SAT on $\varphi$ by taking what is the result of the majority of $\varphi'$ instances ($poly(m')+1$ instances), and return that. Indeed, among the $2poly(m')+1$ test, at most $poly(m')$ can have a wrong result, so the result of the majority must be the correct one.

This runs a PTIME algorithm a polynomial number of times ($2 poly(m')+1$, where $m'$ is polynomial wrt $m$), so we indeed solve SAT in PTIME.

To generate all the needed $\varphi'$, we note that the "longest" variable name in $\varphi$ can't more than $m$ bit long for obvious size reasons. Hence if we take $p$ to be any variable whose name has size $m+1$ bits it is surely fresh, and this makes $\varphi'$ to have size $m' = m+(m+1)+O(1)$. Further, we have $2^{m+1}$ choices of such $p$, which is (asymptotically) a large enough space to choose $2 poly(m')+1$.
> 4 votes

---
Tags: np-complete, np-hard, satisfiability, decision-problem
---


# Question
Title: Does interrupt (for I/O and etc) requires support of Preemption? What is the relation between interrupts and Preemption in O.S?
So i just don't understand the relation between interrupts and Preemption in O.S?

For example in Multi-programming, do we need the support of Preemption or not? when a process needs I/O and sends an interrupt, do we use Preemption here to remove that process in order to get another process running, or no need for Preemption ?

# Answer
> 1 votes
For Multiprogramming you may or may not need Preemption. It depends upon the scheduling policy that is being used. For example First in First Out is non preemptive but shortest CPU burst is preemptive.

One more thing you are mixing blocking and preemption. When a process needs I/O it uses a system call. This system call results in a trap(software interrupt). Now this process is said to be blocked(waiting for I/O). Here the scheduler will definitely remove this process from running state and bring in a new process. Now please note that this whole thing does not invlove preemption.

Preemption means that the process is not blocked, yet the CPU is taken from it and given to some other process. Suppose a process is running and an interrupt comes which has no relation with this process. Now even though the process wants to run the interrupt must be served. Here we say that the process has been preempted.

Another example would be a list of processes being scheduled by shortest cpu burst algorithm. Suppose a process A having CPU burst 20 sec is running. Now suppose a new process arrives having a CPU burst of 10 seconds. Now A must be preempted to give chance to this second process.

Preemption is actually a good thing. It allows a CPU to serve more urgent things. Yet it may also cause some problems. A process may be preempted in the middle of updating a shared variable. This may lead to race condition.

Preemption can be simply avoided by disabling interrupts. But disabling interrupts is not a good thing at all. So nowadays all kernels used preemptive approach.

---
Tags: operating-systems, multi-tasking
---


# Question
Title: How does computer keep track of Empty and used memory space?
Where does computer store used and unused memory address to access it ?Are base address and length or ending address stored side by side?

# Answer
There are many possible data structures that can be used, but a very basic one is using a free list.

We divide memory in blocks. Each block starts with two words, one being a pointer, the other one being the block length. Then we organize such blocks in a linked list, called the "free list".

When memory is allocated (`malloc(s)`), we scan the free list until a large enough block is found. We remove it from the list, and return a pointer to the start to the block, plus two words.

When memory is freed (`free(p)`), we decrement `p` by two words, and prepend the block to the free list.

Further options: we can sometimes split / merge blocks. E.g. when `malloc(s)` finds a block which is much larger than `s`, it can split the block in two, and return the first part (say, of length `s`), only. This increases the number of the blocks. Similarly, `free` can check the free list to spot if there are adjacent blocks, and merge them into one. More advanced data structures can be used to make this operation efficient.

In the real world, the problem is more complex since the memory is handled by the OS, which grants it to processes, and then (usually) by the runtime support of the programming language, which implements something like `malloc,free` by further subdividing the OS-granted memory.
> 1 votes

---
Tags: memory-management
---