title: DPLL algorithm: OLR vs. PLR

text:
# Question
Title: DPLL algorithm: OLR vs. PLR
Can someone please show me examples of what is the difference between OLR (one literal rule) and PLR (pure literal rule) using the DPLL algorithm?

# Answer
The one literal rule, usually known as the unit clause rule, state that if you have a unit clause (a clause containing only one literal) then you should set that literal to the value which satisfies the clause.

The pure literal rule states that if some variable appears only positively or only negatively in all clauses, then you can set that variable accordingly (true if it appears positively, false if it appears negatively).

You can apply the unit clause rule but not the pure literal rule in the formula $p \land (q \lor \lnot p)$. The result would be setting $p$ to true and simplifying the formula to $q$. Another application of the unit clause rule will set $q$ to true and will satisfy the formula.

You can apply the pure literal rule but not the unit clause rule in the formula $(p \lor q) \land (p \lor r)$. The result would be setting $p$ to true, and satisfying the formula.
> 4 votes

---
Tags: discrete-mathematics
---


# Question
Title: 5-state DFA that recognizes only the string 00001111
I'm having trouble coming up with a 5-state DFA that, on all inputs of length 8, recognizes the string 00001111 and no other string (of length 8). The DFA must have an exiting transition for every symbol in the alphabet (namely {0, 1}). The behavior on input of other lengths does not matter. A 6-state solution is pretty simple, but reducing down to 5 states requires more sophistication.
Any help would be appreciated!

# Answer
\[If I understand the question correctly, this only relates to strings of length 8, i.e. for an automata $A$ we only look at $L(A) \cap \Sigma^8$\]

There is a slight variance in interpretation of what a DFA is that plays a role here.

You can construct a DFA with 5 states that accepts $00001111$, but it is not complete, meaning not every state has an exiting transition for every symbol of the alphabet. This quesiton addresses this point in more details.

What this difference in notation allows you to do is skip the sink-node:

If the input string is of length 8, this automaton accepts only $00001111$.
> 5 votes

# Answer
\[Note: I'll add this as a separate answer to keep both answers for posterity. This answer satisfies the conditions added later in the question.\]

This is a 5-state DFA which, when provided only with inputs of length 8, only accepts the string 00001111:

(I should also note that I didn't come up with this solution myself. I wrote a quick tool to brute-force through 5-state DFAs to find this one)
> 4 votes

---
Tags: finite-automata
---


# Question
Title: Finding suitable NP-complete problem to reduce to my problem
I've been given a set $S$ of natural numbers (non-negative integers) $s\_1$, $s\_2$,...,$s\_n$ where $|S|=n$. My problem is to figure out if there is way to get a total sum of 0 when using all the numbers of $S$ **but** we get to "choose the sign" for each number: that is, for $s\_i$ we get to choose if we're going to add or subtract $s\_i$ from the total sum.

I've tried visualizing it using a directed cyclic graph with $n$ vertices where the only edges from $v\_1$ to $v\_2$ are $+/- s\_1$ and the task is to traverse the whole graph, ultimately getting back to our starting node $v\_1$ using a path with total weight 0.

What would be a suitable NP-complete problem to reduce into this one?

# Answer
This problem is essentially just a rephrasing of the classic NP-complete problem PARTITION. If you can partition a set $S$ of natural numbers into two partitions $S\_1$ and $S\_2$ with equal sum, then $\sum\_{s \in S\_1} s + \sum\_{s \in S\_2} -s = 0$ and vice versa.
> 2 votes

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


# Question
Title: For a turing machine which computes $y$ with argument $x$, how much does the descriptional length of a machine producing $y$ without input increases
Let $f$ be some function in some programming language (like C), and we need $n$ bits to store this function. Suppose we have some fixed value $v$ for the argument, then let

> g() { f(v) }

be the function with no argument which just calles $f$ with $v$ as an argument. Then we need $n + |v| + C$ bits to store it, where $C$ is some constant which takes account of the additional bits needed to declare $g$, and this is independent of $v$ and $f$.

So in any programming language so far, to go from programs accepting parameters, to the one for a fixed parameter the desriptional complexity raises up at most by a fixed constant plus the descriptional length of $v$.

Does the same hold for Turing-machines? If I have a Turing-Machine which for input $x$ produces $y$, then to have a machine without accepting parameter to produce $y$ I can built one that first writes $x$ and then runs $M$, and a general machine that writes $x$ for any $x$ would be one that saves the tokens of $x$ in its states and writes them one after another. If I look at how instructions are specified in Turing machines, then we see that for $x$ we need $|x|\cdot C$ bits (with $C \> 1$) then to store this additional machine, hence given $M$ with $M(x) = y$ we get a machine $M\_x = y$ without arguments with $$ |M| + C|x| + C' $$ needed bits, where $C \> 1$ and $C'$ account for some additional setup independent of $M$ and $x$.

But would it be possible to built a Turing machine $M\_x$ with $M\_x = y$ without input which has descriptional complexity at most $|M| + |x| + C'$ for some constant $C'$ independent of $M$ and $x$? Like above for ordinary programming languages?

# Answer
> 1 votes
First of all, there are two notions of Kolmogorov complexity, that Li and Vitanyi (in their classic monograph) call *algorithmic complexity* and *algorithmic prefix complexity*. Each of them is defined with respect to a universal computer which has a certain property.

Algorithmic complexity $C(x)$ has the property that for every computer $P$, if we denote by $C\_P(x)$ the complexity of $x$ with respect to $P$, then $|C(x) - C\_P(x)| \leq \gamma\_P$, where $\gamma\_P$ depends only on $P$. This property is known as *universality*.

Algorithmic prefix complexity $K(x)$ uses a computer in which the valid programs form a prefix code (a *prefix computer*), and we only require the universality property for prefix computers.

The actual definitions are slightly more complicated, since we also need to define, at the same time, the notion $C(x|y)$ or $K(x|y)$.

If you want to use some encoding of Turing machines as your definition of Kolmogorov complexity (of either kind), you need to use an encoding which is universal. But the point of Kolmogorov complexity is that which computer you use doesn't matter, since the resulting notions of Kolmogorov complexity only differ by an additive constant.

Finally, the Kolmogorov complexity analog of your "substitution" rule is $$ K(x) \leq K(x|y) + K(y) + O(1). $$ In fact, more is true: $$|K(x|y) + K(y) - K(x,y)| = O(1). $$ This holds for prefix complexity.

---
Tags: formal-languages, computability, turing-machines, kolmogorov-complexity, descriptive-complexity
---


# Question
Title: How to calculate page size of virtual memory
im new at OS and I want to know how to calculate the page size of this virtual memory system?

Information:

* Physical Memory - 32 KB
* Virtual Address - 16 bit
* Offset - 12 bits

Current content of the page table is this:

I just want a formula for this and not the answer. Thank you

# Answer
> 1 votes
@DavidRicherby is correct You don't need a formula. You need to understand how paging works and what it means to have a 16-bit logical address with a 12-bit offset.

Logical addresses are broken into two parts — the most significant bits make up the page number, and the least significant bits make up the offset. The page number tells you what logical page the address points to. The offset indicates where the data you want is, on that page.

So, if you have aN 8-bit offset, how many different bytes on a page can you reference? $2^{8}$

---
Tags: operating-systems, virtual-memory
---


# Question
Title: Set Basis Problem Variant reference for NP-Completeness?
**Given:** Collection $C$ of Subsets of a finite set $S$, positive integer $K \<=|C|$

**Problem Statement:** Is there a collection $B$ of subsets of $S$ with $|B| = K$ such that for each subset $c$ in $C$, there is a sub-collection in $B$ whose union is $c$ ?

This Set Basis Problem is NP-Complete.

If we enforce an additional constraint that $B$ is a subset of $C$, is the problem still NP Complete?

My assumption is yes, but I could not find any reference to this problem. Can anyone please point out to one?

# Answer
The problem is in fact solvable in polynomial time.

Let $$C\_0=\Bigl\\{c\in C:c\supsetneq\bigcup\_{\substack{c'\in C\\c'\subsetneq c}}c'\Bigr\\}.$$

On the one hand, if $B\subseteq C$ has the property in the question, then $C\_0\subseteq B$: since $c\in C\_0$ cannot be written as the union of its proper subsets from $C$, a fortiori it cannot be written as a union of its proper subsets in $B$, hence the only possibility is $c\in B$.

On the other hand, $B=C\_0$ *does* have the required property. We prove by induction on $|c|$ that any $c\in C$ is a union of a subcollection of $C\_0$: if $c\in C\_0$, this holds trivially; otherwise $c$ is the union of its proper subsets in $C$, which in turn can be written as unions of subcollections of $C\_0$ by the induction hypothesis.

Thus, the problem is equivalent to $|C\_0|\le K$, which can be checked in polynomial time.
> 4 votes

---
Tags: np-complete
---


# Question
Title: Time complexity of writing a number as power of 2's
I'm wondering about the time complexity of writing a number as power of 2's. For example writing $n=218$ as $2 + 2^3 + 2^4 + 2^6 + 2^7$. It seems to me that we do $\lceil \log\_2n \rceil $ divisions. Each division costs $O(n^2)$ so an upper bound is $O(n^2 \cdot \log\_2n)$. However, this seems like a very loose upper bound to me as the number we start with gets smaller with each division. So, what would be a better upper bound on the time complexity of writing an integer $n$ as power of 2's ?

# Answer
> 3 votes
Division by 2 is linear in the number of digits (lets call that $s$) $O(s)$ aka. $O(\log n)$.

```
output = [];
bool carry;
for(digit in digits){ // most significant digit first
    if(carry) digit+=10;

    carry = isOdd(digit);
    push_front(output, floor(digit/2));

}
if(output.front == 0) pop_front(output);
//carry is the new bit to push to the front of the result
// and output is the new digit array

```

Because the number of digits decreases with a constant rate (1 digit every 3 to 4 divisions). This algorithm results in a $O(s^2)$ time complexity aka. $O(\log^2 n)$.

---
Tags: time-complexity, asymptotics
---


title: Lambda Calculus in Rewriting systems

text:
# Question
Title: Lambda Calculus in Rewriting systems
How to do or implement Lambda Calculus in a Rewriting systems?

Rewriting systems are Turing complete.

But I can't figure out how to do lambda calculus or functions with them.

# Answer
> 9 votes
See also this question: "How is Lambda Calculus a specific type of Term Writing system?".

Term rewriting, as introduced in (1), and described in e.g. (2), is a first-order system that cannot handle binding. Consider the $map$ function.

$$ \begin{array}{lcl} map(f, \[\]) &\rightarrow& \[\] \\ map(f, cons(x, l)) &\rightarrow& cons( f\ x, map\ f\ l) \end{array} $$

The problem is that $f$ is used both as a variable and a function symbol, which is not permitted by first-order term-rewriting system.

This lead to *higher-order rewriting*, see e.g (3) for an overview. Another approach to unification of term-rewriting with the $\lambda$-calculus is the *rewriting calculus* (4). Yet another approach towards rewriting with binders -- arguably the most modern -- is *nominal rewriting* (5).

---

<sup> 1. D. E. Knuth, P. Bendix, Simple Word Problems in Universal Algebras.
2. F. Baader, T. Nipkow, Term Rewriting and All That.
3. T. Nipkow, C. Prehofer, Higher-Order Rewriting and Equational Reasoning.
4. H. Cirstea, C. Kirchner, Introduction to the rewriting calculus.
5. M. Fernandez, M. J. Gabbay, Nominal Rewriting.

</sup>

---
Tags: turing-machines, lambda-calculus, turing-completeness, term-rewriting
---


title: Binary Tree Question

text:
# Question
Title: Binary Tree Question
Using the diagram of a binary tree and algorithm answer the following:

If the following commands store(1,laurence), store(1, ron), store(1,graham), store(1,abe) and store(1,martin) are executed what will be stored at location (3)?

1. ron
2. abe
3. graham
4. empty

The answer is ron but I am struggling to work out why. How does the algorithm correspond to the tree? Thanks.

# Answer
We start in `store(1,laurence)` and since `1` is empty, we simply put `laurence` in `1`.

We then go in `store(1,ron)` and see that `1` is not empty so we compare `ron` to the value of `1`: `laurence`, and since `laurence`$\not\>$`ron`, we then go to `store(1.upper,ron)`. So since `1.upper`$=$`3`, we are now in `store(3,ron)`. Since `3` is empty, we simply put `ron` in `3`.

Now, since we always check that the spot is empty before settings its `data`, the `data` of `3` will never change. So at the end, it's still `ron`.

---

The tree is just here to tell you that `1.upper`$=$`3`.

But you can "run" the algorithm on this visual representation of the tree: Start at the leftmost node. If there's nothing written, write whatever you want to write, otherwise, depending on how what you want to write compares to what is written, either go up or down.

---

By the way, having "upper" pointing down and "lower" poiting up is really confusing...
> 0 votes

---
Tags: binary-trees
---


# Question
Title: Strategy to create a testbed and gold standard
I need to create a correct evaluation of the method I'm proposing. The problem is that in the field I'm working on there is no benchmark that I can use for this purpose. On the other hand, my method has to run, as much as possible, on top of "real documents", but these documents are mostly private and created by industry.

The documents are based on the AutomationML language, which is XML-based, and I do have some "real" ones. Until now, I have created the documents manually, and have also automatically generated them based on a given seed document and the AutomationML XML-Schema to ensure that the generated documents are syntactically correct. Also, they are generated following a uniform distribution.

I would like to extend the automatic generation but for this, I don't know how to automatically create the gold standard. I would appreciate any hints regarding this.

# Answer
> 1 votes
You can't. You can't squeeze blood out of a stone. If you want to evaluate how well your method will work on real documents, you need real documents. With synthetically/artificially generated documents, you'll never know if they have the same characteristics as real documents.

You don't necessarily need a standard benchmark that others have used -- but you do need to assemble a representative set of real documents to evaluate on. Basically, if there is no standard benchmark in your field, you'll have to assemble one yourself.

Yes, this is difficult to do. This is one of the less-well-known and less-glamorous aspects of working on machine learning: in practical projects, often we spend 80% of our time (or more!) just assembling data sets, and only 20% on the actual learning algorithms themselves.

---
Tags: machine-learning, semantics, benchmarking, evaluation-strategies
---


# Question
Title: Secretary Problem with 2 positions - Maximizing the difference
## Synopsis

Imagine the secretary problem, except the goal is to hire two secretaries with the greatest possible difference between the two.

## The Problem

I'm not particularly comfortable with this type of math so below are the modified constraints. The original constraints are from Wikipedia's page on the secretary problem.

* There are 2 positions to fill
* There are n applicants for the positions any applicant may fill any position, and the value of n is known.
* NOTE: It is fine to put one person in both positions, but wouldn't be the optimal solution unless n = 1.
* The applicants, if seen altogether, can be ranked from best to worst unambiguously.
* The applicants are interviewed sequentially in random order, with each order being equally likely.
* Immediately after an interview, the interviewed applicant is either accepted or rejected, and the decision is irrevocable.
* The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
* The objective of the general solution is to have the highest probability of selecting a pair with the greatest difference read (The best and the worst). This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant/worst applicant pair and zero otherwise.

## For Context

I realized that at work that many of the problems I'm working on at the moment are normally treated as a single optimization problem. However in reality they are pair values, and since the goal is often to maximize the distance between choosing two values over a given number of days it seems to be very close to the secretary problem. I'm not comfortable enough yet with the math to solve this myself. My intuition is that this problem is equal to having two instances of the stopping problem however I'm not sure if this is mathematically equal.

## Research

I've found papers on the Secretary Problem for TradeOffs, IE. The secretary's are evaluated on two rankings, and Random Walk, IE. dependent variables, while trying to answer this question. I have not managed to find anything directly related to this variant of the problem.

## Answers

Thank you for reading my problem. Any insight into solving this problem is appreciated!

# Answer
One trivial algorithm for the problem is exactly the same as the usual algorithm: observe $n/e$ of the applicants, then pick the first (if any) secretaries who are better than, or worse than, all applicants seen so far. This succeeds with probability roughly $1/e^2$. Answers to a question on math.se which includes your question claim that this algorithm (which is proposed in the answers) is obviously optimal.

To see that the success probability is roughly $1/e^2$, we follow the analysis in Wikipedia. We will analyze a more general algorithm, in which $n/e$ is replaced by $pn$, and then will show that the best choice for $p$ is roughly $1/e$. Let $q\_{ij}$ be the success probability given that the $i$th secretary is the best one and the $j$th secretary is the worst one. If $i,j \> pn$ then $q\_{ij}$ is the probability that:

* $i$ is the best secretary.
* $j$ is the worst secretary.
* Among the first $i-1$ secretaries, the best is one of the first $pn$.
* Among the first $j-1$ secretaries, the worst is one of the first $pn$.

Calculation shows that $$ q\_{ij} = \begin{cases} \frac{pn(pn-1)}{n(n-1)(i-1)(j-2)} & i \< j, \\ \frac{pn(pn-1)}{n(n-1)(i-2)(j-1)} & i \> j. \end{cases} $$ The overall success probability is thus at least $$ \sum\_{i=pn+1}^n \sum\_{\substack{j=pn+1\\j \neq i}}^n \frac{pn(pn-1)}{n(n-1)(i-1)(j-1)} \approx p^2 \left(\int\_{pn}^n \frac{dx}{x}\right)^2 = \left(p\log\frac{1}{p}\right)^2. $$ This is just the square of the usual formula, so it is maximized at $p = 1/e$, for which the success probability is roughly $1/e^2$.
> 2 votes

---
Tags: logic
---


# Question
Title: Decidability of the halting problem on real-life finite computers given unlimited input
It has been my understanding that, technically, our computers are Finite State Machines. And, since FSMs halt when they run out of input, the halting problem is technically solvable. At some point, we must reach an identical state without consuming input if there is an infinite loop.

I also understand that doing this in practice would take far, far, far too long to be useful. Thus, I have read over and over that, yes, technically the halting problem is solvable for real computers, but it doesn't matter, because we can't do it in practice.

*However*, in a real computer, while we have a finite (vast) set of states, isn't it the case that we don't have finite input? Input can easily be generated from non-cyclical random events, such as random radioactive decay, or the motion of water in a stream. Doesn't this mean that, in fact, our computers are *not* truly Finite State Machines, and that the Halting Problem is not merely practically unsolvable, but genuinely unsolvable?

# Answer
> 1 votes
The halting problem can be stated as follows:

> Given a program P and an input x, does P halt when run on x?

Here both P and x are *finite*. In some cases (for example, in program verification) we might also be interested in infinite input which is eventually periodic, or at the very least, has an effective finite description (i.e., it is given by some algorithm). Assuming that this algorithm is also executed on a real machine (otherwise it is "cheating"), the entire setup can be folded to a program running on a real machine, and so the property of having a finite number of states is recovered.

# Answer
> -2 votes
A Turing Machine is, strictly speaking, ALSO a Finite-State Machine; what gives it universal power is in how this FSM is allowed to interact in a largely unrestricted (but still finite) manner with one or more read/write tapes. Note that since the machine cannot visit more than N tape cells in N steps, these tapes do not need to be *actually infinite*; they merely need to be *enlargeable*, with no inherent bound on the eventual amount of enlargement. It is clearly possible to operate a *physically real* machine in this manner \[though at the moment humans would be required to supply and manage the ever-growing tapes\], therefore the theoretical analysis also applies to the physical machine.

---
Tags: finite-automata, halting-problem
---


# Question
Title: Synchronizing sequence and Synchronizable DFA, how come states repeat if synchronizing word length is $>|Q|^{2}$?
I am trying to prove problem 1.59 in Sipser's book: *Introduction to the theory of computation , 2nd Edition.*

> Let $M=(Q,\Sigma,\delta,q\_0,A)$ be a DFA and let $q'$ be a state of $M$ called its "home". A **Synchronizing sequence** for $M$ and $q'$ is a string $s\in \Sigma^\*$ where $\delta (q,s)=q'$ for every $q\in Q$. (We actually have extended $\delta$ to strings so that $\delta(q,s)$ equals the state where $M$ ends up when $M$ starts at state $q$ and reads input $s$).
>
> Say that $M$ is **Synchronizable** if it has a synchronizing sequence for some state $q'$.
>
> Prove that, if $M$ is a $k$-state synchronizable DFA, then it has a synchronizing sequence of length at most $k^3$.

This problem was already attempted here. I don't understand the answer though:

> The proof of this a standard shrinking argument: if such a word is longer than $k^{2}$, then during the runs from $q1$,$q2$ a pair of states repeats, and we can shrink $w$.

How come a pair of states repeats?

I don't see a problem with runs from $q1$ and $q2$ reaching separate states. I don't so how I could be sure that I could shrink to word without disturbing both routes.

# Answer
synchronously moving through the DFA beginning with two different states while an input of a word w can be described as choosing two states out of k on every step. So there exist $\binom{k}{2}$ possibilities to do that. As $k^2\>\binom{k}{2}$, there will be one step where we choose a pair of states which we already had before. So the word $w$ can be shortened: this is the contradiction to the claim that the word is longer then $k^2$.
> 3 votes

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


# Question
Title: How can a operating system run on more than one CPU architecture?
How can a operating system run on more than one CPU architecture?

Does the OS detect what type of architecture it is currently running on? If so, does it simply use a different set of code for that architecture?

How does the CPU detect the type of architecture?

# Answer
Operating systems don't detect the CPU architecture. Instead, you have to ensure that you install the correct version of the operating system given its CPU architecture. If you make the wrong decision, then the OS won't boot, as the CPU won't understand (either reject or misinterpret) the machine code that you've provided.

The reason's that an operating system is just a program written as a series of instructions for the CPU to execute. Since different types of CPU's have different instructions, a procedure (program) written (compiled) for one CPU could be gibberish for another.
> 3 votes

---
Tags: computer-architecture, operating-systems, cpu
---


# Question
Title: Efficient Algorithm to compute radius of tree
Given an acyclic undirected graph alike to this one :

*(Here the center is the node '2', and the radius is 5)*

What is the most efficient (ideally in `O(n)`) way to compute the radius of the tree ?

I've already used different methods like :

* Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
* Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
* Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter. I found almost nothing about this online

# Answer
Yes, it can be done in $O(n)$ time.

## Rooted trees

First let me describe how to do it for a rooted tree. We'll compute several quantities for each node $v$ in the tree:

* Let $p(v)$ denote $v$'s parent.
* Let $h(v)$ denote the height of $v$ (i.e., the distance from $v$ to its deepest descendant). You can compute $h(v)$ for all nodes $v$ in $O(n)$ time via a simple recursive traversal.
* Let $f(v)$ denote the length of the longest simple path that starts $v \to p(v) \to w \to \cdots$ such that $w$ is a sibling of $v$, i.e., $p(v)=p(w)$ and $v \ne w$. In other words, it's the length of the longest path that starts from $v$ by going up once and then immediately going down. Note that

$$f(v) = \max \\{2+h(w) : p(w)=p(v), w \ne v\\}.$$

Suppose we've computed $h(v)$ for all nodes $v$. Also, suppose that for each node we keep track of its two children with the two largest $h(\cdot)$ values. Then, we can compute $f(v)$ for each node $v$ easily.
* Let $g(v)$ denote the length of the longest simple path that starts $v \to p(v) \to \cdots$. In other words, it's the length of the longest path that starts by going up from $v$ (possibly several times). Note that $g(v) = \max \\{ f(p^i(v))+i : i \ge 0\\}$ and moreover

$$g(v) = \max(f(v), g(p(v))+1).$$

Therefore, if you've computed $f(v)$ for all nodes $v$, you can easily compute $g(v)$ for all nodes via a simple recursive traversal.
* Let $e(v)$ denote the eccentricity of node $v$, i.e., $e(v) = \max\\{d(v,w) : w \in V\\}$. The eccentricity of a node $v$ is given by $e(v) = \max(h(v),g(v))$.

This gives us a way to label all the nodes with their eccentricity, in $O(n)$ time. Then we simply find the node whose eccentricity is the smallest. The algorithm runs in $O(n)$ time in all.

## Unrooted trees

If we have an unrooted tree (as in the question), we can first turn it into a rooted tree (do a DFS; then the DFS tree will be a rooted version of the tree), then apply the previous algorithm.
> 3 votes

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


# Question
Title: What is the difference between a "meta model" and "design patterns"?
Where is the difference between a "meta model" and "design patterns"?

If you take, for example, Fowlers "Identity Field" from his book "Patterns Of Enterprise Application Architecture": Why is this a pattern and not a meta model?

Thanks!

# Answer
**Design Pattern**: It is a "good practice". It can be considered as a possible solution for a problem that may ofter occur. The solution usually comes from the experience. Examples are MVC and Identify Field.

**Metamodel**: It can be considered as a set of rules, constraints and constructs that allow to model a problem. As an example you can consider a map.

A map allows to model the reality, so a map can be considered the model. The metamodel of a map is the legend: the constructs that you need to use in order to represent borders, rivers, lakes,...

In your case *Identify Field* is just a good practice that you can decide to follow or not. It's not a constraint/rule.
> 1 votes

---
Tags: design-patterns
---


# Question
Title: What kind of language would you suggest for an University compiler project?
I'm not an instructor. I'm a student doing such course. And I'm just trying to figure out what to do, because we're not given an input language.

---

What kind of (input) language would you suggest for an University compiler project?

It's a project typical to the compiler course in CS programs.

However, I've been confused about, whether it would be easier to design a language for the project or use some existing programming language.

It should be able to handle the following requirements:

```
Readable (no binary noodles)
Comments
At least two different types of data (type errors must be captured at the latest during the run)
Integrity technology
Making choices (if tms)
Playback (loops, recursion etc)
Parameterizable subroutines (functions, methods, etc) that can use local variables

```

Additional features

```
Tables (multidimensional, 0.5 cr, one-dimensional 0.25 cr)
String input and output (0.25 cr)
String interpolation or printf-style formatting by yourself (0.25 cr)
    Complex printf formats (0.25 cr)
Records and variants (0.5 cr)
Generic (Static) Types (0.5 cr)
Classes and Late Binding (0.5 cr)
First-class functions (0.5 cr)
Garbage collection (entirely self-made) (1 cr)
Recursive pattern match (garden Haskell) (0.5 cr)
Lazy calculation (1-2 cr depending on the implementation technique)

```

Additionally the implementation would include:

```
Relatively effective interpreter without separate intermediate language 0 cr
Generation of intermediate language (eg own, JVM or LLVM) 1 cr
Generation of a machine language (eg AMD64 or ARM) from its own intermediate language
Naive register allocation 1 cr
Smart register allocation (eg graphing) 2 cr

```

Also, what existing programming languages would fit into all of these? Does it have to be a functional language or does even C implement all of these?

# Answer
I think you are trying to achieve too much in a single exercise. It would, in my opinion, be better to separate the compiler construction part of the exercise from the comparative language part.

Good code generation and optimisation are difficult for some of the additional features you have cited. In my view it is better that students learn to do some decent lexing, parsing, optimisation and code generation before having to handle some of the more complex features of languages.

If you create a portmanteau of a language you end up with lots of examples of rotten and partially functioning compilers which do not help them learn.

It also matters what the target language you are going to use. Are you asking them to generate CIL, Byte Code, **C** or some other output format? Each of these has different pedagogic reasons for their choice.

Choosing a language to build an example compiler for is like choosing a first programming language. There is no right choice.

To start building compilers I often recommend compiling something like Pascal or even simpler. (The choice of compiler implementation language depends on the tool set you choose to teach.)
> 3 votes

# Answer
I recommend looking at a well-written textbook on compilers, e.g. Modern Compiler Implementation in Java by Appel/Palsberg, and use the source language of the book. It has been battle tested in classroom many times, and builds up language complexity in an incremental fashion.

The surface syntax of the language isn't all that interesting, because it gets abstracted away by lexer/parser anyway.
> 2 votes

---
Tags: compilers
---


# Question
Title: Perform the following 8-bit two's complement arithmetic operation
How am I supposed to perform this subtraction?

For instance: $01110000\_2−11101011\_2$

$01110000\_2$ has a positive sign, so there is no need to perform two's complement. $11101011\_2$ has a negative sign, so I need to perform two's complement.

Two's complement for $11101011\_2$ is $00010101\_2$

Finally, I must perform the subtraction $01110000\_2 - 00010101\_2 = 1011011\_2$

# Answer
> 2 votes
Two's complement is a way of representing positive and negative numbers in binary. There is a very good explanation here: https://stackoverflow.com/questions/1049722/what-is-2s-complement

Basically, the really clever part about two's complement is that arithmetic works without making any special changes. Let's look at that in action with n addition operation: $10000001 + 00010000 = 10010001$. Notice that no special actions were taken in finding the sum. Nevertheless, what I've written there is that $-127 + 16 = -111$.

Two's complement is really just a clever way of encoding the numbers designed to make arithmetic straightforward.

By the way, an easy way of reading two's complement numbers is just to reverse the sign on the highest bit. To illustrate what I mean by this, regularly encoded (non-complement) 8-bit integers like $10010011$ and $01000010$ could be found by adding $1 + 2 + 16 + 128 = 147$, and $2 + 64 = 66$ respectively.

If we were to designate these same numbers as two's-complement, we would just reverse the sign on the 128s bit. Now our two numbers would be $1 + 2 + 16 -128 = -109$, and $2 + 64 = 66$. The second number didn't change because the highest bit was a $0$ already, so it doesn't matter if we are adding or subtracting it.

So, if you were to try to subtract $01110000−11101011$, let's get an answer first so that we can check ourselves. $64+32+16 = 112$, and $-128+64+32+8+2+1 = -21$. You are performing the subtraction $112 - -21$. This means that our final answer *should be* $133$.

So, just as you can subtract by negating before you add (ie. $112 + 21$ instead of $112 - -21$), we can perform a similar operation here. If we negate the second number, we flip the bits and add one: $00010100 + 1 = 00010101$. But now that we've negated the number, our subtraction has become an addition problem. So, our original $01110000−11101011$ has become $01110000 + 00010101$

```
  01110000
+ 00010101
  --------
  10000101

```

$10000101$ is $-128 + 4 + 1$, which equals...

$-123$.

*-123?? Wait, what happened?*

We've fallen into the classic two's complement trap! Because we only have 8 bits, we only have a limited range of possible numbers. 8 bits allows for 256 possible values. Two's complement divides these values nicely: half are positive and half are negative, giving us a range of $-128$ to $127$. Why one less in the positives? It's because Zero has to be somewhere, and since $00000000$ doesn't start with a leading $1$, it comes out of the positive space.

If you're just doing pure math, simply add an extra digit, and you'll be out of trouble. $010000101$ is $128 + 4 + 1$, which equals $133$. If you're on a computer, however, you have to pay more attention to this problem.

When you go outside of the range of your bits, you are said to have an *overflow error*. Modern processors and languages have evolved ways of dealing with this problem, typically through flagging operations that might have caused overflow.

---
Tags: computer-architecture
---


# Question
Title: Copy on write is an interesting idea used on server systems. Does it make any sense on a smartphone?
The data pages that are actually modified need to be copied. This approach, called copy on write, improves performance by reducing copying.

According to me it is unnecessary as every process has its own data. (not sure) A third process working with that data is really not possible.

Please tell me if it's possible, if possible then why? Also an example where this will be helpful would help. Thank you.

# Answer
Yes, copy-on-write makes sense on smartphones, too. Smartphones are just computers, packaged to be small. Smartphones run conventional operating systems, with multiple processes. For instance, each app typically runs in its own process. And yes, these processes do use shared memory, shared libraries, fork(), etc., so copy-on-write *is* useful (and *is* supported on typical smartphone operating systems).
> 2 votes

---
Tags: operating-systems
---


# Question
Title: Longest common subsequence of a set of sequences
There is as input a set of $m$ sequences of length $n$.

I thought it was pretty straightforward at first that the time complexity of *the algorithm provided below* is $O(m^2n^4)$ but then it occurred to me that the time taken depends on the length of a LCS such that the longer a LCS relative to the input length the shorter the computation. The question I have is can you confirm that while the (measured) time taken does depend on the length of a LCS (inversely), that fact does not have an effect on the result of the O-analysis?

```
// Let there be m sequences of lenght n.

// Length of lcs of two sequences. Theta(n^2)
lcs_length(x, y)
// Edit distance of two sequences. Theta(n^2)
d(x, y) = |x| + |y| - 2*lcs_length(x, y)
// Edit distance (total) of y to all of X. Theta(mn^2)
d(X. y) = sum of d(x, y) for x in X

// Longest common subsequence of a set of sequences S. O(m^2n^4)
lcs(S)
    X <- copy of S
    while true
        if exists x in X: |x| = 0
            return ""
        if exists x in X: for all s in S: x is a subsequence of s
            return x
        for x in X
            d_min <- +infinity
            i_min <- +infinity
            for i in 1..|x|
                // Make a copy of x with the ith symbol removed:
                x_i <- x[0..i-1] + x[i+1...]
                // Compute the sum of edit distances to all of the original sequences:
                d_i <- d(S, x_i)
                if d_i < d_min
                    d_min <- d
                    i_min <- i
        X <- X difference { x }
        X <- X union { x[0..i_min-1] + x[i_min + 1...] }

```

# Answer
> 1 votes
There may be multiple different ways to upper-bound the running time of an algorithm.

Saying that the running time of an algorithm is $O(m^2 n^4)$ is analogous to saying that the running time is at most $m^2 n^4$ (ok, $c \cdot m^2 n^4$, for some constant $c$). The keyword there is "at most". So, think of $O(\cdot)$ as more like $\le $ than like $=$.

I haven't tried to analyze the running time of your specific algorithm, but to make up some numbers, it is possible that the running time could simultaneously be $O(m^2 n^4)$ and it could also be true that the running time is (say) $O(m^2 \ell^4)$ where $\ell$ is the length of the longest subsequence. I'm totally making up those figures -- don't take them too seriously, as I don't claim they are actually valid running times for your algorithm -- I am just saying that both claims are consistent, i.e., they could both be true, without contradicting each other.

It's analogous to the fact that we could have both $x \le 3$ and $x \le 4$ be true. Or, we could have both $x \le c^2$ and $x \le d^3$ be true.

---

Side remark: I haven't looked at your algorithm closely, but it looks suspicious to me. I would be surprised if it is a correct solution for the longest common subsequence problem.

---
Tags: algorithms, time-complexity, subsequences
---


# Question
Title: Gray-like code with maximum value <= maximum value of original symbol
I want to iterate through the numbers $0,1,2,\dots,n-1$ in some order, where each number in the sequence differs by only one bit from the previous bit. I'm going to be using each number as an index into a matrix, and each index must be in the range $0..n-1$.

Gray codes look useful. The problem is that standard grey codes only work when $n$ is a power of two. Or, if we use a $k$-bit gray code (where $k = \lceil \lg n \rceil$), then some of the numbers in the gray code sequence will be larger than $n-1$, which will cause a segmentation fault when I try to access that index in the matrix.

So is there something like a gray code that works when $n$ is not a power of two? In other words, is there a way to construct a permutation of $0,1,\dots,n-1$ so that each number is at a Hamming distance of one from the previous number in the sequence?

# Answer
> 2 votes
Yes, such a Gray code sequence can be constructed for all $n$, even when $n$ is not a power of two. I'll describe how, below.

I will say that $a\_0,\dots,a\_{n-1}$ is a *Gray code sequence for $0,1,\dots,n-1$* if each $a\_i$ is in the range $0..n-1$, and if each $a\_i$ differs from $a\_{i-1}$ in a single bit position. Note that this generalizes the usual notion of a Gray code, to the situation where the numbers are not a power of two.

Let $n = 2^t + u$, where $u \le 2^t$. We'll use two steps:

* First, recursively construct a Gray code sequence for the numbers $0..u-1$. Suppose the sequence is $x\_0,x\_1,\dots,x\_{u-1}$. This means that each $x\_i$ is in the range $0 \le x\_i \le u-1$ (for each $i=0,1,\dots,u-1$), and each $x\_i$ differs from $x\_{i-1}$ in a single bit position (for $i=1,2,\dots,u-1$). This in turn gives us a Gray code sequence for the numbers $2^t,2^t+1,2^t+2,\dots,2^t+u-1$ by just adding $2^t$ to each element in the sequence: specifically, $2^t+x\_0,2^t+x\_1,\dots,2^t+x\_{u-1}$.
* Second, construct a Gray code sequence for the numbers $0..2^t-1$ that starts at the number $x\_{u-1}$. A cool fact about the standard Gray code construction (for a power of two) is that it is cyclic, i.e., you can start anywhere and get to all the numbers, from that starting point. Let $y\_0,y\_1,\dots,y\_{2^t-1}$ be this sequence. As mentioned, we have $y\_0 = x\_{u-1}$.

Now if we just concatenate these two sequences, we get an ordering of $0..n-1$ where each number in the sequence differs from its previous number by a single bit. In particular, the full sequence is

$$2^t+x\_0,2^t+x\_1,\dots,2^t+x\_{u-1},y\_0,y\_1,\dots,y\_{2^t-1},$$

with the $x$'s and $y$'s defined as above. This gives a simple and easy to implement construction for what you want.

---

Caution: Iterating through elements of the matrix in Gray code order will trash your cache. Caches are optimized for sequential access. You're doing random access (jumping around in the address space), so the caches will be useless and every memory access will be a miss in the cache. As a result, performance might suffer. Beware.

---
Tags: coding-theory, permutations, integers, hamming-code
---


title: Show that if A is regular so is $A^{R}$

text:
# Question
Title: Show that if A is regular so is $A^{R}$
I'm stuck on "For any language $A$, let $A^R = {w^R | w \in A}$ Show that if A is regular, so is $A^R$."

According to my research (see references), the steps required to prove this question, are:

1. Reverse all the links in the automaton
2. Add a new state (call it $q\_s$)
3. Draw a link labeled with ϵ from state $q\_s$ to every final state
4. Turn all the final states into normal states
5. Turn the initial state into a final state
6. Make $q\_s$ the initial state

Anyway, I decided to make a toy-example to check if those steps made sense to me.

So here it is :

---

Consider $\Sigma = \\{a,b\\}$

I want to read $w = {ab}$, However, I'm extrapolating that we can also read $w = \\{ab\\}^+$.

So I have built an DFA for it :

Then, I followed the instructions and built this NFA :

---

**Now the questions :**

1- Why do I have to make it as an NFA instead of making an DFA that recognizes $w = {ba}$ or $w = \\{ab\\}^+$ ?

2- Can i kill the state $q\_3$ of this NFA ? It's dead so why it should be there anyway?

3- Why the first state of the NFA transitions with $\epsilon$ ?

Whats really bothering me is the first question. I can make an DFA that recognizes the Reverse of w = "ab". So why everywhere I research says that I must do it as an NFA?

Here's the DFA that recognizes $w = {ba}$, Once Again, I'm extrapolating that we can also read $w = \\{ba\\}^+$. Not sure if i should assume that, anyway :

"You need at least 10 reputation to post more than 2 links."

So why isnt that DFA enough to prove that if A is regular, so is $A^r$ ?

References :

"You need at least 10 reputation to post more than 2 links." cs.stackexchange.com/questions/3251/how-to-show-that-a-reversed-regular-language-is-regular

# Answer
1. Why do I have to make it as an NFA instead of making an DFA...

You don't have to, but making an NFA allows you to use $\epsilon$ transitions, which are convenient for making your procedure.

2. Can i kill the state q3...

Sure, but it wouldn't be useful for your proof. Dead states don't hurt anything, and it would be harder to write this step into your procedure.

3. Why the first state of the NFA transitions with ϵ?

Because the FMS you are working from may have had multiple final states, so you need a way to encode multiple potential starting points. Using $\epsilon$ transitions gives you a choice of multiple states.

What you're trying to do is make a *procedural proof*. In essence, you're trying to show that for *every* FSM $A$, you can follow some formula to construct a FSM that also accepts $A^R$. If you can always construct a Finite State Machine for $A^R$, then $A^R$ must be Regular.

The machine that results from your process doesn't have to be the most efficient machine or contain the minimum possible number of states. This isn't a work of art, it's a proof of concept: if you can always make an appropriate reversal machine, then your reversal must always be regular. All it must do is *work every time* to accomplish your proof.
> 2 votes

# Answer
1.) You can make a DFA but the method you mentioned, or any other method for instance, doesn't provide an easy way to create a DFA.

> Plus now that we know that NFA = DFA in the computational power if he can design an NFA easily its the same thing.Once you have an NFA convert it to DFA.
>
> One More thing,
>
> Don't think that if there is only one accept state you can just construct a DFA directly( well you can but not by above technique).
>
> Because, as you can see in your toy NFA, there are states through which you don't have transition for some symbols.
>
> They will go to a reject state, but if you are creating a DFA you need to have them in your design

2.) You can kill it but its just optimization but right now we are focused on getting an NFA for reverse language, we can always optimize it later.

3.) In case you have multiple accept states you need to be able to start from any of that, which is why you create a new pseudo start state, and make e-transitions to actual start state.

4.) If you can give directly design a DFA for AR then of course there is nothing else you need to do to prove AR is regular,

> but you can do this only for a given A, to prove for general A you need to give a procedure to give a DFA for AR given A.
> 0 votes

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


# Question
Title: How unallocated memory space is represented?
I'm doing C programming stuff, and I'd like to know little bit about memory management - My problem is that I'm not understanding where the computer (or the OS or the programs) stores the information related to allocated space and how the unallocated space information is processed and how it is reported as a runtime error.

I did many searches but didn't find any information about this stuff yet. Can anyone try to explain, or recommend any book or online course?

# Answer
> 3 votes
Each page of RAM is typically a 4k block, with a set of privileges on it such as read, write, or execute. Broadly speaking, the memory manager for the operating system will allocate a bunch of pages for OS related storage, and when a program launches, it will allocate initial RAM, and as more items are allocated, the program will ask the operating system for more RAM.

From the program's point of view, the RAM is all contiguous. However, under the hood, the operating system is mapping the various blocks of system RAM, and each program's RAM.

Physically, the RAM is broken up into blocks, which are essentially unorganized, but the operating system itself has a table mapping what block belongs to each program.

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


# Question
Title: Finding f(n) so 2T(f(n)) + 1 ∈ Θ(log^4 n)
Given the recursive function: ($c$ is a constant)

$\qquad T(n) = \begin{cases}1 & n ≤ c\\2T(f(n)) + 1 & n \> c\end{cases}$

I need to find a $f(n)$ such $T(n) ∈ Θ(log^4 n) = Θ(\log \log \log \log n)$. I tried the iteration method, and it gave me $\qquad 2^i\*T($$f1$($f2$(...$fi$($n$)..$))) + i $ which revealing the pretty much expected formula for $i$. i know that $f(n) = \sqrt(x)$ would give $log(log(n))$, Is that the right direction? or which function will get closer?

Thanks.

# Answer
So $T(n)$ goes through the sequence 1, 3, 7, 15, 31, ... We want $T(n) = \Theta (\log \log \log \log n)$; I'll assume log n is the base 2 logarithm. We'll try to define f (n) so that T(n) = log log log log n, rounded up to the nearest element of the sequence 1, 3, 7, 15, 31...

1 \< log log log log n ≤ 3 if 2 \< log log log n ≤ 8 or 4 \< log log n ≤ 256 or 16 \< log n ≤ $2^{256}$ or 65,536 \< n ≤ $2^{2^{256}}$. So in that range we have T (n) = 3, and c = 65,536. BTW. The upper end of that range is so large that all the paper in the universe wouldn't be large enough to write it down as a decimal number.

Next we look for a range where 3 \< log log log log n ≤ 7. That happens when n \> $2^{2^{256}}$ and log log log log n ≤ 7 or log log log n ≤ 128 or log log n ≤ $2^{128}$ or log n ≤ $2^{2^{128}}$ or n ≤ $2^{2^{2^{128}}}$, and the numbers involved get quite big.

In the range $2^{2^{256}}$ \< n ≤ $2^{2^{2^{128}}}$ we want 65536 \< f (n) ≤ $2^{2^{256}}$. f (n) should map $2^{2^{2^{2^{2k+1}}}}$ to $2^{2^{2^{2^k}}}$.

To achieve this, let $g (n) = \log \log \log \log n$, $h (n) = (g (n) - 1)/2$, $f (n) = 2^{2^{2^{2^{h(n)}}}}$.
> 1 votes

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


# Question
Title: When did "regular" start referring to Type 3 languages/grammars?
In his 1959 paper, On Certain Formal Properties of Grammars, Chomsky defined a "regular" grammar as a specific form of a type 2 (context-free) grammar. (See Definition 8 of that paper.) He then goes on (in Section 6) to demonstrate that regular (type 2, context-free) grammars can generate more languages than type 3 (finite state) grammars.

However, in every other computer-science reference I've read, *type 3* languages (those recognizable by a finite state machine) are called "regular". (For example, see the Wikipedia entry for Chomsky Hierarchy.)

My question is, when did "regular" shift from referring to type 2 languages to type 3 languages? And why? (Was it intentional, or did someone mis-quote Chomsky at some point and that stuck?)

# Answer
I found an answer, at least a partial one, hinted at in Footnote 10 of Chomsky's paper where he refers to a 1956 paper by Kleene in which Kleene describes "regular events" -- a language recognized by finite state machines.

So it would seem the common usage of "regular language" today traces back to Kleene's "regular events" rather than to Chomsky's "regular grammar".

Furthermore, as renierpost pointed out in a comment, what Chomsky called a "regular" grammar in 1959 is now known as Chomsky normal form.

**Edit:** I asked Professor Chomsky via email whether he intended his "regular grammar" to have a connection to Kleene's "regular events". He replied: "Long time ago and I don't recall. I suppose just a coincidence."
> 5 votes

---
Tags: formal-languages, formal-grammars, history, chomsky-hierarchy
---


# Question
Title: Building automaton from regular expression
Let $L=a(a+b)^\*b$, a regular expression. I will try to build the automaton by the $a^{-1}L$, $b^{-1}L$ rule

1. $a^{-1}L = \\{a,b\\}^\* b=M$.
2. $b^{-1}L=\emptyset$.
3. $a^{-1}M=b\cup\\{a,b\\}^\*b=N$.
4. $b^{-1}M=\\{\varepsilon\\} \cup \\{b\\}\cup \\{a,b\\}^\*b = P$

But why are the result of 3 and 4 when doing $a^{-1}M$ and $b^{-1}M$ as given?

# Answer
You failed to notice that your $M$ and $N$ states are indistinguishable. Let's take a walk around the problem first.

---

We can express this all in regular equations, in the notation of John Conway's *Regular Algebra and Finite Machines*:

$\begin{align} L &= a M\\ M &= a M + b P\\ P &= 1 + a M + b P \end{align}$

We can see that $L$

* starts with an $a$;
* remains in $M$ for as many $a$s as you like;
* goes to $P$, the only terminal state, at the first sign of a $b$;
* stays in the terminal $P$ for as many $b$s as you like;
* returning to $M$ at the first sign of an $a$.

These equations translate immediately into a DFA. We can also solve them:

$M = a M + b P$

... has solution

$M = a^\*bP$

Substituting this into

$P = 1 + a M + b P$

... we get

$\begin{align} P &= 1 + a a^\*bP + b P\\ &= 1 + a^\*bP \end{align}$

... which has solution

$\begin{align} P &= (a^\*b)^\*\\ &= 1 + (a + b)^\*bP \end{align}$

Now we can solve for $M$:

$\begin{align} M &= a^\*bP\\ &= a^\*b(a^\*b)^\*\\ &= (a+b)^\*b \end{align}$

And for $L$:

$\begin{align} L &= a M\\ &= a(a+b)^\*b\\ \end{align}$

---

How do we solve the equations above? The solution to the equation

$X = \mathcal {x} + \mathcal y X$

... ,where $\mathcal {x}$ and $\mathcal {y}$ are regular expressions independent of $X$, is

$X = {\mathcal y}^\* \mathcal {x} $

---

OK. What did you miss?

$\begin{align} a^{-1}M &= b + (a + b)^\* b\\ &= (1 + (a + b)^\*) b\\ &= (a + b)^\* b\\ &= M \end{align}$

Even if you miss this, you should find out by further beheading that $M$ and $N$ are indistinguishable.
> 1 votes

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


# Question
Title: Complexity of inserting an integer to an empty hashtable
What's the complexity of inserting an integer $n$ to an empty hash table? My guess is that it's $O(\log n)$ as we require to scan every bit of $n$ to compute its hash. However, I often see it as $O(1)$. Am I mixing up things here ?

# Answer
The answer depends on your model of computation. In other words, it depends on how you count the number of basic operations, or on what you consider to be a "basic operation".

In the transdichotomous model or Word RAM model, you can do computation on an entire word in $O(1)$ time, and the word size is guaranteed to be large enough to hold the integer (and, in particular, at least $\log n)$. An operation on a single word counts as a single operation, even though you're operating on a bunch of bits. Consequently, there exist hash functions that can hash the number $n$ in $O(1)$ time, in these models of computation.

In the bit complexity model, it takes at least $\log n$ time to read an integer with $\log n$ bits, so you're right that hashing $n$ will take $\Omega(\log n)$ time.

You might find it useful to read https://en.wikipedia.org/wiki/Transdichotomous\_model and https://cstheory.stackexchange.com/q/2656/5038.

Ultimately, the time to compute a hash will depend on the hash function (some hashes might be even slower than the above), but this might be enough to clear up your particular question.
> 1 votes

---
Tags: time-complexity, asymptotics, hash-tables
---


# Question
Title: What does a solution to the Rectangle-Fit problem look like?
I've been learning about NP-Complete problems, and came across the rectangle fit problem. Basically, the rectangle-fit problem is the problem of whether or not a set of 2d rectangles can fit in a larger 2d rectangle. What I have not been able to find, or solve myself, is what a possible solution looks like.

Say there is a set of rectangles $R$ and a large rectangle $T$, how do I indicate a possible placement of all rectangles in $R$ into $T$? I was thinking coordinates, but there is no assumption $T$ is defined as a graph. At a high level, how would I denote where/how each rectangle should be placed?

I am not asking for how to solve this NP-Complete problem. I am asking how do I define the placement of rectangles in $R$ for a candidate solution. I saw an academic paper saying that it is obvious there is a polynomial time verifier for the problem, but there was no explanation of what the certificate the verifier is using looks like.

Particularly, I was looking at: http://ranger.uta.edu/~weems/NOTES5311/hw3ansold.pdf for the verifier.

# Answer
> 1 votes
You can simply list the coordinates of the upper-left corner of each rectangle (and its orientation, if you're allowed to rotate rectangles). That completely determines its position, and thus listing that for all rectangles completely identifies the configuration of all rectangles.

---
Tags: turing-machines, np-complete, np, packing
---


title: Find the odd shortest path is NL

text:
# Question
Title: Find the odd shortest path is NL
OddPath be a set of all G, s, t, such that G is a directed graph with a path from node s to node t, and the shortest such path has odd number of edges.

How can I show OddPath is NL? I think about it for a long time, the main problem is that I don't know how to get length of the shortest path in non-deterministic log place.

I tried to use coNL = NL to attack this problem. The problem become "find G with the shortest path with even number of edges". Again, I can't deal with "shortest path".

# Answer
The graph is log-space reducible to the same question restricted to a leveled directed graph. We know the problem whether there is a path between s, t can be solved in NL, so the idea is to repeat the question for different distances. Let G be the leveled directed graph where v(i) denotes vertex v in level i.

```
i=1
while i<=N where N is the size of the original graph before leveling.
    check if path exists between s(1) and t(i+1) using an NL machine.
    if yes:
        then return Accept if i is odd, else reject
    else: i++

```

If you have a copy of Sipser checkout page 333 for more about leveled graphs since that is where I got the idea.
> 0 votes

---
Tags: turing-machines, turing-completeness
---


title: How do I interpret this question?

text:
# Question
Title: How do I interpret this question?
For any language $L \subset \Sigma^\*$, define $S(L)$ to be $$\\{x\in L \mid \neg \exists y \in L: \exists z \in \Sigma^\*: (z \ne \epsilon) \land (x=yz) \\}$$

Show that $S(L) = S(S(L))$

I'm confused about the question here. The way we define $S(L)$ takes elements from $L$ $(x \mid x \in L)$, but $x=yz$ and $y \notin L$. How is it possible for x to concatenate an element from $\bar{L}$ (complement of $L$ since $y \notin L$) and still be an element of $L$?

# Answer
The formula means "it is not true that there exists $y \in L$ and $z \in \Sigma^\*$ such that $z \ne \epsilon$ and $x=yz$." That is, there is no way of writing $x=yz$ such that $y\in L$ and $z\neq\epsilon$.
> 1 votes

# Answer
$S(L)$ = $$\\{ x\in L: \forall y \in L. \forall z \in \Sigma\*. (z \ne \epsilon) \land (x \ne yz) \\}$$

$S(L)$ is all strings $x \in L$ which don't have non-trivial prefixes $y \in L$
> -1 votes

---
Tags: regular-languages
---


# Question
Title: Show that a Language can be Generated by a regular grammar
I'm looking for hints on the following exercise from *Introduction to Automata Theory, Languages and Computation* by Hopcroft and Ullman.

> Let $G$ be a grammar where all the productions are of the form $A\to xB$ and $A\to x$, where $A$ and $B$ are single variables and $x$ is a string of terminals. Show that $L(G)$ can be generated by a regular grammar.

This is from the second chapter of the book, so the solution should just require grammars (automata don't appear until chapter 3).

I assume that "Show that $L(G)$ can be generated by a regular grammar" means that I have to show the language generated, since this can be shown as regular grammar just by pointing out the productions.

This is where I get a bit confused...

**Edit:** Wrong usage of production so this is wrong, therefore what i did below is the wrong way to tackle this exercise

If i start doing the productions: \begin{align\*} A&\to xB\\ \text{(with second)} A&\to AB\\ \text{(with first)} A&\to xBB \end{align\*} And so on... so in the (n)th step $A^\* → x^{n-1}B^n$ Since There would always be one $B$ more than $x$.

I was thinking that maybe I could change $xB$ for $A$ then for $x$ again to have just the string of terminals $x$ resulting in what the language generates, and this is where I think I am probably not understanding something right. I assume I am wrong because there cant be a non terminal when generating a Language...Right? Or am I just doing it all wrong?

Thank you for your time. I'm learning in Japan and my professor's English isn't very good so I can't ask him.

# Answer
> 2 votes
The only thing that prevents your grammar from being a regular grammar is that $x$ is a string rather than a single terminal. That means that you have to deal with two kinds of problems:

1. $x$ is a string containing more than one terminal.
2. $x$ is the empty string.

To deal with the first problem, replace each problematic rule by a chain of equivalent rules of the proper form. For example, $A \to \alpha \beta$ is the same as $A \to \alpha X$ and $X \to \beta$.

To deal with the second problem, you have to get rid of rules of the form $A\to B$ and of rules of the form $A \to \epsilon$. Hopefully this is something you already know how to do. If not, notice that $A \to B$ means that whenever you have $A$, you can replace it with $B$, and $A \to \epsilon$ means that whenever you have $A$, you can remove it. Doing so recursively will allow you to get rid of these rules.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Number of triangles in an undirected graph
How do we count the numbers of traingles (i.e., different triads of vertex $u,v,w$ such that edges $u-v,v-w,w-u \in E$ ) in a given graph $G$?

It is obvious that it can be done in $O(N^2)$: is there anything better?

# Answer
> 2 votes
I'm assuming that the graph is given as an adjacency matrix. The trivial algorithm for counting triangles goes over all triples of vertices $u,v,w$ and checks whether $\\{u,v,w\\}$ is a triangle, for a total running time of $\Theta(N^3)$. This can be improved using matrix multiplication: if $A$ is the adjacency matrix, then the number of triangles can be extracted from $\operatorname{Tr} A^3$, taking into account the number of vertices and edges in the graph (details left to you). This takes time $O(n^\omega)$, where $\omega$ is the exponent of matrix multiplication.

---
Tags: graphs
---


# Question
Title: What does one mean by addressing capability of a microprocessor?
I read in a book that the Intel 80286 microprocessor has an addressing capability of 16 MB. Does this mean it can process 16 MB of data at a time? Please explain what is actually meant by addressing capability.

# Answer
It means that the CPU can access 16MB of memory directly, since each memory address is 24 bits long. This is although the registers are only 16 bits long (the trick is the segment registers).
> 1 votes

---
Tags: memory-hardware, cpu
---


title: Can BNF consist of zero rules?

text:
# Question
Title: Can BNF consist of zero rules?
I am trying to use BNF to describe its own grammar to get used to it. What I can not find any information about is whether BNF must consist of ***zero or more rules*** or ***one or more rules***. The difference would be:

```
<grammar> ::= <grammar> <rule> | <rule>

```

vs.

```
<grammar> ::= <grammar> <rule> | ""

```

The only difference I can see is that an empty language can be described by an emtpy BNF in the second case, but must use `<grammar> ::= ""` in the first case.

# Answer
Concretely speaking, the Backus-Naur form is a notation for context-free grammars, applied to the (formal) description of languages at the syntactical level.

While there are extended versions of BNF that have been standardized, the BNF itself hasn't, so there is no way of determining if the empty grammar is "legal" BNF.

As a mathematical object, the possibility of an empty grammar will depend on the definition (of grammar) used. A grammar that has no productions is usually said to define the empty language, but any grammar whose set of possible terminal derivations is empty is also a candidate definition of the empty language.
> 1 votes

# Answer
There is nothing logically wrong with allowing a grammar to have zero rules. But such a grammar would be entirely useless, as it would not define any language (not even the empty-string by itself).
> -1 votes

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


# Question
Title: Why is it most efficient to resize a dynamic array to 2 * array.length()?
By dynamic array, I mean an array that when it becomes full we replace it with a new array having greater capacity than the previous array.

I read in a textbook that doubling the size of the array is the most efficient resizing. I want to know if this is in fact demonstrably true and not just a matter of personal preference.

We will want to minimize the amount of resizing events, because each such event requires O(n) time where n is the number of elements in the list.

We also should be careful not to make the list too big because it might be a waste of memory.

Why does the author of my textbook say that 2 * array.length() is the magic number?

# Answer
Consider a model in which elements are only added, one at a time, and once an array is full, it is increased in size by a factor of $C$. Suppose also that resizing an array of size $x$ costs $Cx$. Adding $N = C^n$ elements (the worst case in terms of resizing cost per element) has cost $C(1+C+C^2+\cdots+C^n) \approx \frac{C^2}{C-1} N$. The amortized cost of adding an element is thus $f(C) = \frac{C^2}{C-1}$. The derivative of this function is $$ f'(C) = \frac{2C(C-1)-C^2}{(C-1)^2} = \frac{C(2-C)}{(C-1)^2}, $$ which vanishes at $C=2$. It is not hard to check that this is a minimum of $f(C)$.
> 4 votes

# Answer
Let $C$ be the growth factor. In practice, we don't use small $C$ because reallocation would be too frequent; we don't use large $C$ because we would waste $(C−1)/C$ of space in the worse case or $(C−1)/(2C)$ in average. I don't think there is an accurate model to compute $C$ because it is hard to precisely weight speed vs space waste. $C=2$ is something we feel comfortable most of time. It is also fast to compute (a bit shift) and may align well with typical page size which is almost always power-of-2.
> 3 votes

---
Tags: arrays, efficiency
---


# Question
Title: A multi-user, multi-processing operating system cannot be implemented on hardware that does not support
A multi-user, multi-processing operating system cannot be implemented on hardware that does not support

1. Address translation
2. DMA for disk transfer
3. At least two modes of CPU execution (privileged and non-privileged)
4. Demand paging

---

My attempt:

Somewhere it explain as : Address translation is needed to provide memory protection so that a given process does not interfere with another.

We also need at least 2 modes of execution to ensure user processes share resources properly and OS maintains control. This is not required for a single user OS like early version of MS-DOS.

Demand paging and DMA enhances the performances- not a strict necessity.

> > Can you explain it in a formal way, please?

# Answer
None of the above.

As you noted, DMA and demand paging can be useful features but are not necessary to support multiple users and multiprocessing.

Address translation is not necessary even for memory protection. Memory protection can be separated from address translation via a protection lookaside buffer or memory protection unit.

Providing a distinct privileged operating mode in the processor is not necessary for a multiuser system. In theory, provable trust of software can provide protection against misuse by users. Another alternative is capability systems; one can use non-forgeable fat pointers to provide resource protection.
> 21 votes

# Answer
I remember a counter-example from the 1980s:

OS-9/68000 was quite popular then: a multi-user, multi-processing real-time operating system for the Motorola 68K processor family, loosely patterned after UNIX. It didn't require any of the features from your list.

The 68000 didn't have address translation. OS-9 compilers produced position-independent code that could run from any address, using only relative branches (N bytes forward or backward) instead of absolute jumps (to a given address X). Static memory was always addressed relative to the OS-provided data start address. Dynamically-allocated memory always comes at "random" addresses, so applications always address dynamically-allocated data relative to an OS-provided address.

DMA disk transfer was typically used in OS-9 device drivers, but that was not necessary for the multi-user feature, only to avoid the blocking time of programmed I/O that would otherwise negatively affect the real-time capabilities.

If I remember correctly (wrong! Thanks, @davidbak), the 68000 itself didn't have a privileged mode, so the protection against evil code was limited. There was an optional memory management unit chip available that OS-9 could use for protection purposes.

OS-9 typically ran without demand paging. When physical memory was exhausted, new memory allocation attempts simply failed (demand paging doesn't fit nicely to a real-time OS). I even know a few Windows servers today where the admins completely switched off the pagefile feature.

But don't misunderstand me: The features you listed perfectly make sense for multi-user, multi-processing operating systems, I just wanted to point out that none of them is strictly necessary.
> 9 votes

# Answer
You could change the question to "I would not want to implement a multi-user, multi-processing operating system on hardware that does not support ... " and my answer to all four points would be "Yes", except for point two (DMA for disk transfer). But the question was "cannot be implemented..." and the answer is clearly no to everything.

You would probably have the problem that there would be no separation whatsoever between processes, so this would be very unsafe, and one rogue application could easily take down any other application and/or the operating system itself.

From personal experience, I remember one place that had high end workstations (16 GB of RAM each, which was *a lot* at that time), and they turned off demand paging. That way the machines ran 5% faster, and they knew that for their use, if 16 GB was not enough, demand paging would totally kill performance, and the only reasonable solution was buying a machine with more RAM.
> 3 votes

# Answer
*Cannot be implemented* is not the same as *it's very hard to implement*.

If a hardware supports turing-complete programming, then anything can be implemented on it, given enough time and memory. This means you could theoretically implement a multi-user, multi-processing operating system on a Turing machine. Written in Brainfuck.
> -1 votes

---
Tags: computer-architecture, operating-systems, cpu
---


# Question
Title: "not provable", what does this to do with unification?
I found one interesting point in nominal unification. Just after proposition 2.16 of Nominal Unification by Urban, Pitts, and Gabbay, it said the following, which I found confusing:

> For non-ground terms, the relation $=\_{\alpha}$ and $\approx$ differ! For example, $a.\\!X=\_{\alpha} b.\\!X$ always holds, whereas $\emptyset\vdash a.\\!X \approx b.\\!X$ is not provable unless $a = b$.

The $=\_{\alpha}$ is the standard $\alpha$-equivalence and $\approx$ is defined in the paper.

It seems to me that $\vdash a.\\!X \approx b.\\!X$ has a unifier which is ${a \\# x},\[X:=(a \\, b)X\]$ no matter what $a$ and $b$ are according to the unification algorithm in the same paper.

So, I am trying to understand why the paper said the above lines? what is the relationship between something is "not provable " but has a unifier? or I am misunderstanding something?

Hoping someone could clarify this point for me, thanks in advance!

# Answer
> 5 votes
They mean you can't use the rules in Figure 2 defining $\approx$ (and $\\#$) to derive $\emptyset\vdash a.\\!X\approx b.\\!X$. If you attempt to do it you'll use *$\approx$-abstraction-2* followed by *$\approx$-suspension* at which point you'll not be able to satisfy the premise as $\nabla$ is empty but the disagreement set is $\\{a,b\\}$. There are no other applicable rules, so there is no derivation.

Conceptually, though conceptual understanding is not needed to answer this question, what's happening is with an empty freshness environment we're free to replace $X$ with $a$ (or $b$) but $a.\\!a \neq\_\alpha b.\\!a$. This is what it means in the sentences following that quote by $\alpha$-equivalence not being preserved by substitution. The freshness constraints in $\nabla$ are what disallow such substitutions. So in an empty freshness environment $a.\\!X$ and $b.\\!X$ can't be unified as their instances need not be $\alpha$-equivalent.

I recommend getting more familiar with inductively defined judgements and derivations, as e.g. discussed in Chapter 2 of Robert Harper's Practical Foundations for Programming Languages. You should do the exercises there, and write out the complete derivations for the examples in the Nominal Unification paper. Ultimately, checking derivability like this should be as straightforward and mechanical as checking $(x+3)(x-1) = x^2+2x-3$.

---
Tags: lambda-calculus, unification
---


# Question
Title: How to interpret plot of cost function in gradient descend algorithm?
I have a data set to which I want to apply logistic regression. I set my cost function to be

$J(\theta) = -\frac{1}{m} \[\sum\limits\_{i=1}^{m} y^{(i)} log{(h\_\theta \cdot x^{(i)})} + (1-y^{(i)}) log(1-h\_\theta(x^{(i)}))$

and I am running gradient descend algorithm.

When I plot the cost function as a function of the number of iterations, I am getting a plot like this

Which I think is a good sign.

However, when I zoom in on the initial portion of the curve, I get this plot

I don't know what to make out of the rising and falling in the cost in the beginning. Is that something that we can expect? If so, why? Shouldn't the gradient descend algorithm decrease the cost after every step? How is it that after some iterations there is an increase in the cost? I know that it is possible for gradient decent not to converge if the learning rate is big enough but the algorithm does seem to converge eventually. So why is it that there are some instances where gradient descend tends to increase the cost?

# Answer
> I don't know what to make out of the rising and falling in the cost in the beginning. Is that something that we can expect? If so, why? Shouldn't the gradient descend algorithm decrease the cost after every step?

Gradient descent only minimizes the cost if the learning rate is low enough. Also, in practice most of the time you don't use gradient descent on the whole dataset, but on a mini-batch. This means you don't get an guarantee that the global cost is falling for a single step.

An analogy which is often used is that of a landscape with hills. The landscape is your cost. Each point in the landscape is a specific configuration of weights. The gradient shows in the direction of steepest descent. That might be a rabbit hole on a hill, but it might also be downwards to the valley. Now, imagine it shows to the rabbit hole. Instead of going down the rabbit hole, you make a bigger step and so you go up the hill. But then you are on a different position. For your next step, you come away from the rabbit hole and get towards a better (local) minimum.

As always when it comes to training, I would like to point out the awesome gifs by Alec Redford: Gifs 1, and Gifs 2
> 4 votes

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: How did the Logic Theorist prove the Pons Asinorum?
I was reading about the Logic Theorist proving many of the Whitehead and Russell's *Principia*'s theorems. However, I cannot find any technical explanation on *how* the program proved those theorems and specifically what method did it use to solve the Pons Asinorum. I'm interested in understanding how "independent" it was in providing those proofs, mostly since it is celebrated as an "AI" program.

# Answer
> 5 votes
If you google "logic theorist source code" you find this which is clearly not the original source code, but presumably is a modernization of the ideas in the code. You can also find this 1963 RAND memorandum which is a more contemporary description of the system. It seems to include a complete code listing as well as descriptions in terms of flowcharts.

As far as I can tell, it proved basic statements in essentially classical propositional logic. The main idea is backward chaining.

Page 52 of Perspectives on the History of Mathematical Logic shows the (erroneous) proof of Theorem 2.85 in Principia Mathematica and the proof Logic Theorist produced. Theorem 2.85 (using more common notation) is $$((P\lor Q)\Rightarrow(P\lor R))\Rightarrow(P\lor(Q\Rightarrow R))$$ which (ironically) is actually easier to read in Logic Theorist's notation, `(((PVQ)I(PVR))I(PV(QIR)))`, than it is in the aforementioned page. As you should be able to tell, this has no particular connection to any geometrical theorem, let alone the isosceles triangle theorem. I have no idea why it's linked that way on Wikipedia. You could, however, take e.g. Tarski's axioms for planar geometry and apply the same proof search techniques to questions in Euclidean geometry as done in Automated Development of Tarski's Geometry by Art Quaife. I can't find a good reference, but I'm fairly certain novel and elegant proofs have been found when automated theorem proving (in this style) has been applied to planar geometry. This isn't surprising as these systems tend to search the proof space starting from the shortest proof candidates.

---
Tags: artificial-intelligence, mathematical-programming
---


title: Exact amount of loop iterations here?

text:
# Question
Title: Exact amount of loop iterations here?
What is the exact number of loop iterations here and how do you find out?

```
def func(n):
  i = 4

  while i < n:
    print(i)

  i = i + 1

```

The solution says max(n-4,0) which is theta(n), but I am confused about how they reached this. I see it starts from 4 and can guess that this relates to the n-4, but would like to be sure.

# Answer
It will iterate $n-4$ steps if $n\>4$ . If $n\leq4$ there will be no iteration since the condition is not satisfied. The important thing is that the linear search runtime grows like the sequence size in the worst case. The notation we use for works like $c\_1.n+c\_2$ is Θ (n).
> 1 votes

# Answer
Seeing that $i$ starts with 4 $i = 4$, if it was $i = 0$ the number of times the loop would execute was be $n$ times.

Let $A$ and $B$ be the iterations of $i$.

$A = { 0,1,2,3, ... , n-1 }$

$B = { 4,5,6,7, ... , n-1 }$

The size of the $A$ set is $n$, the $B$ set has the same components of $A$ minus 4 numbers ${( 0,1,2,3 })$ , therefore the size of $B$ is $n-4$.

For $n-4$ be $\theta(n)$ $\exists$ $c\_1,c\_2$ and $n\_0$ such that, $c\_1 . n \leq n-1 \leq c\_2 . n$.
> -1 votes

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


# Question
Title: How can I prove that there is a decidable language which is not in P?
Generally, I want to use the diagonal argument to prove it. I tried to define a language $A$ which is constructed by a Turing machine $D$:

It will only take a input which has a form of a Turing machine $\langle M\rangle$ (the description of $M$) and simulate $M$ on $\langle M\rangle$. If it halts in polytime and accept, reject. If it halts in polytime and reject, accept.

If $A$ is in **P**, there must exist a Turing machine $M'$ that decides it in polytime. However, if I run $D$ on the input $\langle M'\rangle$, the result will be converse to the simulation. Contradiction! So $A$ should not be in **P**.

The problem is that I don't know whether a turing machine will halt in polytime or not. Polytime can be $n^2$, $n^3$, $n^4$, ...

# Answer
> 2 votes
Unfortunately, this doesn't work at all. What you're proposing to do is to simulate a Turing machine on some input, and ask whether it accepts/rejects that input in polynomial time, and that question is not well-formed.

"Polynomial time" is the class **P** of Turing machines $M$ that have the following property: there is are constants $c$ and $k$ such that, for every input of length $n$, $M$ halts in at most $cn^k$ steps. Notice that this property talks about *all* inputs, so you can't test it just by looking at one input.

Indeed, it doesn't make sense to ask if a particular input is "accepted in polynomial time." Let the input have length $n$ and suppose that the Turing machine takes $t$ steps to accept it. We can always find constants such that $t\leq cn^k$. For example, we could take $c=t$ and $k=0$.

You need to look at the time hierarchy theorem which says, loosely, that Turing machines with longer running time can decide more languages than Turing machines with shorter running times. Its proof does indeed use diagonalization, so you started with the right idea.

# Answer
> 0 votes
One problem is that for **time** hierarchy you have to increase the class by a logarithmic factor to obtain new languages since the simulation introduces a logarithmic time overhead (unless you come up with something more efficient). Instead, we prove P is properly contained in EXP with a diagonal argument. Define language A that is decidable in $O(2^n)$ but not in $o((2^n)/n)$. We define A as the language decided by D where D is defined as follows:

```
D= "on input w:
    Store ceiling(2^n/n) in a binary counter.
    #We can do this in O(2^n) because of time constructability
    Now, on each following step, decrement the counter and if it reaches 0 reject.
    If w doesn't have form <M>01* for some M that is TM, reject.
    Simulate M on w and reject if it accept, accept if it rejects."

```

So the counter's length is approximately $log(2^n/n)\in O(n)$ and the simulation adds a cost in $O(2^n/n)$ so we can give bound D's runtime above in $O(2^n)$. So A is in EXPTIME.

For contradiction, assume $A\in P$. Then $A \in Time(o(2^n/n))$. Let M be a TM such that M decides A in $o(2^n/n)$ , then D can simulate M in time $t(n)=d\cdot o(2^n/n)$ for some constant d. Then, $\exists n\_0,\forall n\>n\_0, t(n)\<2^n/n$ by definition of $o$. Then, the simulation in D will get to the last line without timing out for M on w if $||w||\>n\_0$. Now, run D on $w=\<M\>01^{n\_0}$ so the input is large enough. Now, D will do the opposite of M so M cannot decide A, since A is defined as the language decided by D, which is the contradiction we wanted. Therefore, we conclude $A\notin P$.

---
Tags: turing-machines, polynomial-time, semi-decidability
---


# Question
Title: ML to approximate a dampened harmonic oscillator from a related curve
I want to approximate the output of a Monte Carlo simulation that takes a probability density function sampled at x-axis points $0,1,2,3,\ldots,n$ and outputs what tends to look like a dampened harmonic oscillator.

Four examples appear below. The blue dots are the sampled pdf (or pmf), and the heights of the black lines give the curves I want to approximate.

My inclination is that I would be able to use Machine Learning to either (a) provide second-order differential equations that approximate the output of the Monte Carlo simulation, or (b) bypass the dampened harmonic idea and approximate the output of the MC simulation directly.

Needless to say, I can generate tons of learning data using the MC simulation. I should also mention that once the ML has done its training, it needs to perform much faster than the MC simulation!

I'm hoping this will be a good introduction to ML algorithms for me, but I'm not sure where I would start. Hints about learning resources and software frameworks to do my research in are welcome.

Can this be solved with ML? If so, would I bother with the oscillator stuff?

# Answer
I would suggest that you try to learn the function $f$ that maps the parameters of the pmf to the parameters of the dampened harmonic.

For each example, you can presumably derive the parameters of the Weibull distribution for the pmf. You can also presumably derive the parameters of the dampened harmonic (by curve-fitting, or other means). So, each example gives you one input-output pair for $f$.

Now, try to learn $f$ from these input-output pairs. You should start by visualizing the function $f$, to try to understand how each output of $f$ depends on the inputs of $f$, and then you can probably select an appropriate (nonlinear) regression model. k-nearest neighbors regression might be worth a try in this context.
> 2 votes

---
Tags: machine-learning, numerical-algorithms
---


# Question
Title: Mapping between kernel-level thread and user-level thread
This is my understanding:

*There are two types of processes: user and kernel(OS). Each process can have single or multiple threads. The threads of a user process are called a user-level thread and the threads of a kernel process are called kernel-level threads. Scheduler, dispatcher etc. contains kernel-level threads. Both user-level threads and kernel-level threads can able to run on CPU.*

*There may be several user-processes in ready queue for execution, scheduler(kernel) decides which user process/ thread to run on CPU, dispatcher(kernel) gives control to the corresponding user-thread on CPU, the corresponding user-thread executes and terminates.*

Consider the following statement (From Galvin os textbook):

**To run on a CPU, user-level threads must ultimately mapped to an associated kernel-level thread.**

My doubt is as follows:

**What is the need of such mapping? Where am I going wrong?**

# Answer
I don't know the book, so what follows is only my speculation. Take it as such.

"User vs kernel level threads" might mean two different things. Carefully check your book terminology.

One interpretation is that user level threads are those who execute users' programs, while kernel level threads execute OS code. This is the interpretation you described in your question.

Another possible interpretation is the following. The OS provides processes and threads as usual. Within a OS-provided thread CPU time, user code might choose to run several subroutines concurrently. I.e., within the same OS thread, user code can execute a subroutine for 100ms, and then jump to another one for 100ms, and so on. Essentially, the user code is implementing a scheduler among several sub-threads. These "simulated" threads can be named "user level threads". In practice, some programming language implementations provide these, often called "green threads" or something similar. Note that the OS is completely unaware of those user level threads.

If at that point your book is referring to such threads, then the sentence you quoted simply means that each user thread, to be executed, must be run inside a OS provided thread. A simple implementation is to map N user level threads to a single OS thread, but running N user threads exploiting M OS threads is also possible.
> 3 votes

---
Tags: operating-systems
---


# Question
Title: LOGSPACE in different Turing Machine variants
Let's consider two-head (and two tapes) Turing machine. Let some problem $P$ be decidable in $LOGSPACE$ on that machine. What about complexity of that problem on the normal Turing machine ( one head, one tape?)

I asked that question because I am thinking of some problem- I have to be able to get value of $i$-th cell but my input is read-only.

# Answer
> 1 votes
Let T(n) be the time complexity of problem on two tapes Turing machine then time complexity on single tape Turing machine is going to $O(T(n)^2)$ (more precisely $10 \times T(n)^2$). You have mentioned that your problem is in $LOGSPACE$, So $T(n)$ will be going to be some polynomial in $n$. To simulate two tapes Turing machine by single tape encode locations 1,3,5,7... to encode the first tape and locations 2,4,6... to encode second tape and also use symbol for the encoding of head positions. Now to simulate the one movement of two tape Turing machine you need to first find the head position (swap left to right) so you need $O(T(n))$ steps. Now to simulate the $O(T(n)$ many steps you need $O(T(n)^2)$ time.

---
Tags: complexity-theory
---


# Question
Title: Does solving subproblems in logspace in different models implies solving original problem in logspace?
Let's consider the following situation:

We have a problem $\mathsf{L\text{}}$ . We would like to solve it in $LOGSPACE$. Let assume that our problem $\mathsf{L\text{}}$ can be divided to two parts: $A$ and $B$.

We can solve $A$ using computatation model $M\_1$ in $LOGSPACE$.

We can solve $B$ using computation model $M\_2$ in $LOGSPACE$, $M\_1 \neq M\_2$

Does it mean that we can solve $P$ in $LOGSPACE$ ? Why?

# Answer
> 0 votes
The composition of two logspace functions is again in logspace. This is a classical result that you can try to prove on your own.

---
Tags: complexity-theory
---


title: Decidability of Context free languages

text:
# Question
Title: Decidability of Context free languages
Is is decidable whether 2 given PDAs accept the same language?

Also, is it decidable whether the language accepted by a given grammar is context free (the given grammar could be unrestricted but there may exist an equivalent CFG for it)

# Answer
These problems are undecidable. For more other problems, visit this page https://www.cs.wcupa.edu/rkline/fcs/grammar-undecidable.html
> -1 votes

---
Tags: computability, automata, pushdown-automata
---


# Question
Title: Is binary tree just a two-dimension-doubly-linked-list?
We all know the structure of a binary tree:

```
struct binary_tree {
  binary_tree *parent;
  int          data;
  binary_tree *left;
  binary_tree *right;
};

```

So a doubly linked list has the following structure:

```
struct linked_list {
  linked_list *prev;
  int          data;
  linked_list *next;
};

```

But a binary tree can also be manipulated like this:

```
struct my_linked_list {
  my_linked_list *prev;
  int             data;
  my_linked_list *next0;

  my_linked_list *next1;
} binary_tree;

```

By that, I have "proven" that binary tree shares a similarity to doubly linked list. (with the addition of another next element)

So my question is here: Is binary tree really a vertically-descending graph, or just an extension to the linked list, that can be drawn horizontally?

I know this is a kind of stupid and meaningless question but it was confusing me for years and years. I am just an apprentice to the computer science...

# Answer
> 3 votes
"\[A\] binary tree shares a similarity to doubly linked list"

Why, yes, it does, but the doubly linked list format you have made is really just a way to represent a connected graph, with the one limitation that a node can be connected to at most 3 other nodes. A lot of structures could fit into that format, for instance a binary tree or many cyclic structures in addition to lists.

You have made one limitation to a general graph, of which binary trees are a subset. The reason we care about more restricted versions of graphs is that it allows for many useful optimizations. Your two dimensional doubly linked list has many redundant properties regarding use as a binary tree, for instance it allows for cyclic structures, which a binary tree can not be, and it includes information about the parent node, which is also unnecessary as such trees are used for descending searches.

# Answer
> 0 votes
Well, No. I think you have observed similarity in the use of pointers in both of these data structures. But there are some differences. I think you should think these data structures a bit more abstract manner $-$ think them as the set of objects and relationships between those objects.

For doubly linked list, there is a set of nodes containing data and there are two relations defined on these nodes $-$ Predecessor and Successor.

For binary tree, you observe that you can also define two relations $-$ LeftChild and RightChild which are analogous to Predecessor and Successor. But there is additional relationship between noded called Parent. The corresponding couterpart is not there for doubly linked list.

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


title: What's the advantage of typed assembly?

text:
# Question
Title: What's the advantage of typed assembly?
I've seen scattered references to typed assembly in high assurance literature, but I don't really understand the advantage.

If the compiler/runtime are capable of passing the types down to the CPU, then aren't they are capable of emitting equivalent checks in assembly? Bloating an instruction set with high-level primitives increases the complexity of the assembler and slows down execution time because the assembler is busy doing the compiler's job.

It sounds like this would make a compiler writer's job easier but expands the TCB without any real gains in speed or safety.

# Answer
> 6 votes
> If the compiler/runtime are capable of passing the types down to the CPU, then aren't they are capable of emitting equivalent checks in assembly?

It could be done, but then

* we move those checks from compile time to run time, impacting performance
* we detect type errors at runtime instead of compile time, losing all the benefits of a type system

> Bloating an instruction set with high-level primitives increases the complexity of the assembler

True, but this instruction set may still be different from the CPU one, so it's just another (intermediate) language, not something the CPU needs to follow.

> and slows down execution time because the assembler is busy doing the compiler's job.

No, the assembler does not run at run time. At compile time, the assembler emits machine code. Compile time may get longer, but the runtime performance should not be affected.

> It sounds like this would make a compiler writer's job easier but expands the TCB without any real gains in speed or safety.

Expanding the TCB is not always detrimental to safety. Assume a nuclear power plant with some software to check that the temperature is kept in the safe range. Removing that software would make the TCB smaller, but the plant would hardly be more safe.

Adding a type system to a TCB puts more safety checks in the system. As long as the type system is not allowed to modify the program code, but only to report "well-typed / ill-typed", it can not harm safety. If it passes ill-behaved programs, say because of some bugs in the type checker, those would be executed anyway without the type system. If it fails some well-behaved programs, that's unfortunate, but preventing the deployment of a new program is always a safe choice -- this impacts productivity but not safety.

# Answer
> 6 votes
One of the benefits of typed assembly language is that it can *reduce* the TCB, not expand it.

The type checker in the assembler for type-checking the typed assembly language can be fairly simple, and thus potentially fairly trustworthy. In contrast, a compiler is a much more complex beast, and putting a type-checker in a compiler typically involves trusting a large fraction of the compiler (the entire code generation stage, and typically the optimization stages, too). Moreover, if you put the type-checker in the compiler, the assembler must be trusted too.

So if you compare "trust the assembler + a simple type-checker in the assembler" vs "trust the assembler + many stages of a complex compiler + the type-checker in the compiler", hopefully you can see how the former can lead to a smaller TCB, with good system design.

---
Tags: programming-languages, compilers, type-checking
---