# Question
Title: Do proofs of $HALT$'s undecidability make it clear that it's practically relevant?
The proof of $HALT$'s undecidability usually goes like this: we assume the existence of a halting decider and incorporate it into a machine $D$ that takes a TM as input, runs it on its own encoding and does the "opposite" action. We then notice $D(D)$ has a contradicting behavior and conclude a halting decider cannot exist.

This is a rigorous, formal proof; there's no doubt about what it states: "given a Turing machine $M$ and a word $w$, we can't decide whether $M(w)$ halts".

But consider the following statement: "given a Turing machine $M$ with less than $2^{2^{100}}$ and a word $w$ with less than $2^{2^{100}}$ symbols, we can decide whether $M(w)$ halts".

This statement doesn't contradict the one above it, but it effectively makes $HALT$'s undecidability seem just a quirky theoretical fact, without any practical relevance.

My question is: how "obvious" is it that the second statement is false? It seems to me like neither Turing's 1936 paper, nor usual textbooks on computability address it explicitly. Am I missing something?

# Answer
The second statement (limited to size $\le 2^{2^{100}}$) is true. That problem is decidable: there exists an algorithm to decide it. There are only $2^{2^{101}}$ different problem instances, which is finite, so there exists an algorithm that has all answers for each problem instance hard-coded into it. I couldn't write down such an algorithm, but it doesn't matter. We know one exists, hence the problem is decidable. See also How can it be decidable whether $\pi$ has some sequence of digits?.

You ask about whether the Halting problem is "just" a quirky theoretical fact.

Well, from one perspective it is just a theoretical result. That theorem does not completely rule out of the possibility of an algorithm that is "good enough" at solving the problem, e.g., it solves most problem instances that we are likely to run into in a reasonable amount of time. It does not rule out the possibility of always-correct algorithms that output either "Yes, I'm sure, it halts", "No, I'm sure it doesn't halt", or "I'm not sure".

From another perspective, it is not just a theoretical result. It does help provide some understanding about why certain problems seem very hard to solve in a fully satisfactory way, and helps us avoid wasting our time trying to achieve the impossible.

For more, see Why, really, is the Halting Problem so important?, Practical importance of Turing machines?, What are some decidable problems which cannot be solved in real life(due to time and memory constraints)?, Undecidable problems with efficient heuristics, Gödels (first) incompleteness Theorem and the Halting Problem - How limiting is it?.
> 3 votes

---
Tags: computability, halting-problem
---


title: time complexity of loops

text:
# Question
Title: time complexity of loops
what is the time complexity of:

```
for (i = 1; i <= n; i = 2*i)
    for (j = 0; j < i; j++)
            sum++;

```

? I thought it is O(nlogn) since the otter loop run logn time and the inner loop run i time

# Answer
> 2 votes
Conside Geometric progression

$1+2+4+8+...+n=2n-1$.

So time complexity is $O(n)$.

---
Tags: algorithms, time-complexity, functional-programming, c++, code-generation
---


# Question
Title: A question about layered architecture in OS
In layered architecture, the operating system is broken into a number of layers (levels). The bottom layer (layer 0) is the hardware; the highest (layer N) is the user interface. Each layer is implemented only with operations provided by lower-level layers. The layers are selected so that each uses functions (operations) and services of only lower-level layer. The lowest set layer is always the hardware and the highest layer is the user interface. My question is does always a request should reach the lowest layer ( the hardware layer) so that it can be serviced? If no, then can you please give an example?

# Answer
There are many cases in which a higher-level request does not reach the lowest level. A simple example would be reading data from a file. If the file system already has the requested data cached, it will not call into the lower level disk driver to read the data.
> 1 votes

---
Tags: operating-systems
---


# Question
Title: Is this variant of multiset covering problem NP-hard?
Consider this variant of multiset covering problem.

Input: a collection of sets $S = \\{s\_1, s\_2, \ldots, s\_n\\}$ and a universal set $U$, in which $s\_k \subseteq U$ and $s\_k \neq \emptyset$ for all $k$.

The problem is, given an non-empty multiset $M$ containing elements from $U$, we are allowed to pick at most one element from each set in $S$ to form a new multiset $P$. We need $P$ to cover $M$ as many times as possible. For $P$ to cover $M$ $n$ times means for each element in $M$, there are at least $n$ copies in $P$.

For example, if $S = \\{\\{1, 2, 3\\}, \\{2, 3\\}, \\{2\\}, \\{2\\}, \\{1\\}, \\{1\\}, \\{1, 3\\}\\}$ and $M = \\{1, 1, 2\\}$, we should be able to form $P = \\{1, 2, 2, 1, 1, 1\\}$ by picking 1 element from the 1st, 2nd, 3rd, 5th, 6th and 7th sets respectively. This will cover $M$ 2 times. (To cover $M$ 3 times will require six $1$s and three $2$s, which is impossible from just 7 sets)

Is the above problem NP-Hard?

# Answer
This is a matching problem and can therefore be solved efficiently.

Make a bipartite graph where one side is $S$, and the other side is $B$, made up of $n$ copies of $M$. If you enumerate the elements of $M$, $m\_1,\ldots,m\_k$, then $b\_{i,j}\in B = m\_j$ for all $i\in \[n\]$. Then draw an edge from $s\_\ell$ to $b\_{i,j}$ iff $m\_j\in s\_\ell$ for all $i,j,\ell$. Now it's easy to see that you can cover $M$ $n$ times iff there is a matching in the graph with $|B|$ edges. Trying with different sizes of $n$, you can find the greatest one.

There is probably a more efficient way to find a matching that saturates one side $n$ times (such that you only need one copy of $M$), but this at least shows that the problem is not NP-hard (unless P=NP, of course).
> 1 votes

---
Tags: np-complete, np-hard, sets, subset-sum
---


# Question
Title: Chordal graphs - what are the use cases?
I'm taking a course in graph algorithms. I've just implemented recognition of chordal graphs for an assignment.

I'm wondering: what are the use cases for chordal graphs? In other words, what are the chordal graphs one can obtain from studying other computational problems? I'm interested in any problems, no matter how real-world or instead abstract they are, as long as chordal graphs are not just by design included in the problem definition.

I know that interval graphs are chordal and interval graphs seem more natural to me (i.e. to represent conflicts in some time schedules). Are there some use cases of chordality for interval graphs? Or is it maybe the case that the interval representation is mostly more useful?

Thanks!

# Answer
> 4 votes
The class of chordal graphs is a central graph class in both the area of graph classes, and also in algorithmic graph theory.

By *central*, I mean that it has important graph classes above and below (and on the side of it), and that it relates to very important topics in graph algorithms.

Chordal graphs is a superclass of important graph classes such as interval graphs (as you mention), split graphs, threshold graphs, trivially perfect graphs, and of course trees. As such, trivially perfect graphs (aka quasi-threshold graphs) is a generalization of trees, and chordal graphs are generalizations of those again.

There are many problems that are NP-hard on large graph classes that become polynomial time solvable on chordal graphs, for example treewidth, chromatic number, clique/independent set/vertex cover, feedback vertex set, etc., however some remain NP-hard, such as dominating set (already hard on split graphs) and Hamiltonian path.

There are interesting algorithmic concepts relating to chordal graphs: a vertex is simplicial if its neighborhood is a clique. A graph is chordal if and only if there exists a *perfect elimination ordering*, which is an ordering of the vertices such that vertex $i$ is simplicial in $G\_{\geq i}$, the induced graph on the vertices from $i$ up to $n$.

There is also an important relationship between chordal graphs and treewidth, arguably one of the most important structural properties of a graph, which is the following. A graph $G$ has treewidth $k$ if and only if there exists a *chordal completion* $G'$ of $G$ with maximum clique size $k$. A chordal completion is a spanning supergraph of $G$. Chordal completion is better known as *minimum fill-in*, which has application in Gaussian elimination of sparse matrices, which led the complexity of Minimum Fill-In to be posed as an important open problem in the 70s. Today we know a lot about this problem, including that it is NP-complete.

Interestingly, interval graphs are to pathwidth as chordal graphs are to treewidth, and the same relationship holds for trivially perfect graphs and treedepth, as well as threshold graphs and vertex cover(!).

In other words, chordal graphs have important applications in the real-world, they have interesting structural properties, and there are interesting algorithmic challenges relating to this class.

I could say much more, but I'll leave it at this. I hope it helps.

---
Tags: algorithms, graphs
---


# Question
Title: Simplest transformation from XOR to CNF SAT
What is the simplest way to transfrom $a\newcommand\*\xor{\oplus}b=c$ to a CNF SAT expression with minimum number of clauses. The default transformation requires upto 9 clauses. I think we can do much better.

# Answer
> 3 votes
Lets start with transforming $a\oplus b = True$. This is simple enough, since it happens if and only if either one of $a$ or $b$ is $True$ and the other is $False$. We can easily encode it as follows:

$$(a\lor b)\land (\lnot a \lor \lnot b)$$

Now, to transform $a\oplus b = c$ we need two cases: one for when $c=True$ and the other for when $c=False$. We covered already the case for $c=True$, so now lets go through $c=False$. In this case, both $a$ and $b$ must be the same value. Notice that $\lnot a \lor b$ is equivalent to $a\rightarrow b$, and hence $(\lnot a \lor b) \land (\lnot b \lor a)$ is equivalent to $(a\rightarrow b)\land (b \rightarrow a)$ which is also equivalent to $a\longleftrightarrow b$. Hence, when $c=False$ we need the encoding to be:

$$(\lnot a \lor b) \land (a \lor \lnot b)$$

Combining the two is rather easy:

$$(a\lor b\lor \lnot c)\land (\lnot a\lor \lnot b\lor \lnot c) \land (\lnot a \lor b\lor c) \land (a \lor\lnot b\lor c)$$

I will leave it to you to prove that this is indeed equivalent to $a\oplus b = c$

:)

# Answer
> 1 votes
I'd like to offer a more straightforward method for transforming XOR equations into SAT.

**step 1:**

Regardless of the number of variables on the right side of the equality, we can shift them to the left by iteratively XOR-ing the same variables one by one. For example:

$$a \oplus b = c \iff a \oplus b \oplus c = 0$$

**step 2:**

Now, **this equation implies that the count of 1s in $a , b , c$ must be even.** We can express all the clauses for cases where the count of 1s is odd, corresponding to an odd number of negations:

$$(a \lor b \lor \neg c) \land (\neg a \lor \neg b \lor \neg c) \land (\neg a \lor b \lor c) \land (a \lor \neg b \lor c)$$

For any XOR equation with a length of k, we require exactly $2^{k-1}$ clauses to encode it.

---
Tags: satisfiability
---


# Question
Title: How exactly does stale data appear in temporal buffer in Downfall attack?
I've read Downfall paper. In the university, I've had an introductory course on computer organization and operating systems. We also studied Spectre and Meltdown attacks there. I understood the interplay of speculative execution and side channels in the case of those attacks.

I understand the general similarity between Downfall and Spectre/Meltdown. I understand how once stale data is accessed from temporal buffer it can be transported using a cache-based side channel.

What I don't understand is what exactly makes the access to stale data possible? Does the CPU continue executing instructions with stale data passed even when it is concluded that a new fetch is needed? Is the execution restarted upon completing the new data fetch?

# Answer
> Does the CPU continue executing instructions with stale data passed even when it is concluded that a new fetch is needed?

Yes, that's right. This is the culprit in most of the attacks that are called *Spectre* or *MDS*, including this one. I think the best demonstration is the original Meltdown attack: you can just read some data you don't have permissions for. You can *just do that*, and the CPU doesn't stop you! The trick is to leak the data before the CPU does stop you, which is what the cache is used for.

The idea with MDS is very similar, but instead of directly reading data we shouldn't, we cause the CPU to load some data into some buffer and then use the buffer, but the load doesn't work and the next part of the instruction uses the old data from the buffer. Just like Meltdown, the CPU eventually stops you, but you can leak the data using the cache before that happens. Apparently, gather instructions can do this. Researchers keep finding more and more instructions that can trigger the same basic idea.

It seems to be a design decision of Intel CPUs that once an instruction faults, it will keep running instructions that have already been started, and then cancel their the effects so it looks like they didn't run. But the effects on the cache are not canceled, so the cache can be used to leak data.
> 1 votes

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


# Question
Title: Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s
Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of the set of palindromes with the same numbers of 0s and 1s is not context-free.

# Answer
Intuitively you cannot check palindromicity and (un)equality of numbers using a single pushdown, so also $P'$ must be non-context-free.

Formally proving unequal-repeating-numbers to be non-context-free is quite a challenge, see How to prove L := { a^n b^n c^m | n,m \>= 0 & n != m } is not context-free? for the language $\\{ a^nb^nc^m \mid n\neq m \\}$. For that language one needs a special $p!$ trick, as well as Ogden, a stronger form of the classical pumping lemma.

If one intersects your language $P'$ of strings that are palindromes and have unequal numbers of $0,1$ with $0^\*(11)^\*0^\*$ one obtains the language $\\{ 0^m 1^{2n} 0^m \mid m\neq n \\}$. It seems reasonable to attack that language with similar methods. Then it would follow that $P'$ itself is not context-free as context-free languages are closed under intersection with regular languages.
> 2 votes

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


title: How many bits do the pointers take?

text:
# Question
Title: How many bits do the pointers take?
So I am covering succinct trees, and in the lecture, it mentioned that "An n-node tree takes 2n pointers or 2n lg n bits (can be easily reduced to n lg n + O(n) bits). First, question is why 2nlgn bits, and how we can reduce it to nlgn?

# Answer
They say “pointer” but use that word in a very nonstandard way. What they actually mean is array indexes. Every item has an index from 0 to n-1. If n \< 2^k then you need only k bits to store such an index. The other way round, k = ceil(log n), that is the base-2 logarithm of the number of items, rounded up to an integer.

In practice, since items are likely to be many bits, and odd numbers of bits for indexes make your code complicated and slow, you would likely have an 8, 16 or 32 bit index for up to 255, 65,000 or 4 billion items. Or real pointers, usually 64 bit.
> 2 votes

---
Tags: memory-access, succinct-data-structures
---


# Question
Title: Efficient intersection of multiple paths in a tree
Consider a graph tree $T$, where we are given $k \> 1$ unique pairs of nodes $\\{u\_1,v\_1\\}\dots \\{u\_k,v\_k\\}$. Let $P\_{i}$ denote the unique path on $T$ between $u\_i$ and $v\_i$. Then, my problem is to efficiently find the intersection of all paths $\bigcap\_{i=1}^k P\_i$ (in terms of vertices). Note that the intersection is also a path.

A first algorithm which I could come up with works as follows; First, set a counter for each edge and vertex of $T$ to 0. Root $T$ arbitrarily to make it a rooted tree. For each $i=1\dots k$, we can find $P\_{i}$ in $|P\_{i}|$ time by processing the nodes with largest depth first (and simultaneously if they have the same depth). Then, simply increase the counter by one for all vertices and edges in $P\_{i}$. After doing this for all edges, we can check which edges and vertices have count $k$ to determine the intersection.

This algorithm runs in $O(|T| + \sum\_{i=1}^k |P\_{u\_i,v\_i}|$). Moreover, it still feels quite inefficient; an edge may be checked multiple times even though we already have determined that the edge is not in the intersection. I believe that there may be some algorithm which runs in (close to) $O(|T| + k)$ instead. Do you have any suggestions? Partial answers or ideas are also welcome.

# Answer
Here is a useful fact: in a tree, the intersection of two paths, $P\_1 \cap P\_2$, is another path (or is empty).

Also, you can compute that path explicitly in $O(1)$ time using a few least common ancestor queries and a case analysis. The resulting intersection will also be represented by a pair of vertices (the endpoints of that path).

Therefore, you can compute the intersection $P\_1 \cap \dots \cap P\_k$ of $k$ paths in $O(k)$ time.

(You *will* have to do a $O(|T|)$-time preprocessing step on the tree to build up the data structure needed to support $O(1)$-time LCA queries. I assume this is OK.)

See also Checking whether two paths are intersecting in a tree.
> 0 votes

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


# Question
Title: Regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$
> Design a regular expression for the language accepting the strings containing at most one pair of $1$'s over $\\{0,1\\}$

So basically we have the language $L=\\{11,011,110,0011,1100\ldots\\}$.
I find the expression to be $R=(0+1)^\*11(0+1)^\*$.
But I found here the answer to be $R=(0 + 10)^\*(11 + \epsilon)(0 + 10)^\*$.

I cannot differentiate these two answers and the logic behind the later answer.

**EDIT:** In my answer, the first $(0+1)^\*$ may provide $11$, so after this another $11$ is not permissible since at most one pair of $11$ is required. But what's the logic behind $(11+\epsilon)$?

# Answer
The logic behind $(11+\epsilon)$ is to either allow a $11$, or allow no such pairs. The question states "\[...\] containing **at most** one pair \[...\]", and therefore we need to allow either one or zero pairs, and this is achieved by $(11+\epsilon)$.
> 1 votes

# Answer
Although everyone seems to have given similar answers, I think $(0+10)^\*(11+1+ϵ)(0+01)^\*$ is the solution. On both sides, consecutive 1's should not appear, and in the middle, all cases that satisfy the condition of 'at most one pair' should be considered.
> 1 votes

# Answer
I think the answer itself is wrong (please correct me if not) because first choose 0 from (0+10)\* and 11 from (11+ε) so we get 011 and from the final (0+10)\* if we choose 10 the final string becomes 01110 where we get 2 consecutive 1 pairs.
This may work: (0+10)\* (11+ε) (0+01)\*
> 0 votes

# Answer
0∗+(1+ϵ)(0+01)∗1(0+01)\* might be the answer
> -2 votes

---
Tags: regular-expressions
---


# Question
Title: How does the sumcheck protocol help solving the #SAT (circuit satisfiability) problem?
I am going through Justin Thaler's book - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf \- "Proofs, Arguments, and Zero-Knowledge"

He presents the Sumcheck protocol & then claims on Page 41 that the interactive Sumcheck protocol helps solve the SAT problem in better than exponential time.

What Sumcheck does is

$H = \sum\_{b\_1 \in \lbrace 0,1 \rbrace} \space \sum\_{b\_2 \in \lbrace 0,1 \rbrace} \space ... \space \sum\_{b\_v \in \lbrace 0,1 \rbrace} g(b\_1, b\_2,...,b\_v)$

However, this is summing up all the total of all possible values the circuit can evaluate to. How does that give you the values which with satisfy the circuit?

# Answer
It doesn't solve SAT in faster than exponential time. It solves #SAT (not SAT), and the prover still needs exponential time.

It doesn't give you the values which satisfy the circuit. It doesn't need to. #SAT doesn't ask you to find the values that satisfy the circuit. It asks for a count of the number of satisfying assignments, i.e., assignments that satisfy the formula. $g$ is chosen so that $g(b\_1,\dots,b\_v)$ is 1 if the assignment $b\_1,\dots,b\_v$ satisfies the formula, or 0 otherwise. Summing those up counts the number of assignments where it is 1, i.e., the number of satisfying assignments.
> 2 votes

---
Tags: complexity-theory, satisfiability, zero-knowledge-proofs
---


# Question
Title: Data Structure for efficient nearest neighbor search using generalized distance?
I have a list of objects that have a defined measure of distance between them and I'm trying to store them in a data structure such that I can easily and quickly query which of the objects is closest to a key which is not necessarily in the list (like nearest-neighbor). The problem is that these objects aren't points and, as far as I'm aware, can't be converted to points, so something like a k-d tree won't work. All I have to compare them is this distance metric (which does obey the triangle inequality), though it is possible to compute the distance between any two of the objects. Is there any data structure that supports efficient nearest neighbor search but works only off of distance? One idea I had would be to try and convert each object to a point such that the distance between them maps to the euclidean distance of the points, but that seems computationally expensive and I think would require as many dimensions as points in the worst case.

# Answer
You can use a CoverTree. It indexes objects purely by distance. One implementation is available here.

I have my own implementation here (Java) which is based on a more recent publication "Faster Cover Trees" by Mike Izbicki and Christian R. Shelton.

You may have to modify my implementation because it expects points as input.
> 2 votes

# Answer
Have a good day!You can find the correlation coefficient between what you want and every node of a binary search tree , then choose the value with the highest correleation coefficient.
> 0 votes

---
Tags: data-structures
---


title: Is (a*b) or (a*b)* star-free?

text:
# Question
Title: Is (a*b) or (a*b)* star-free?
Here is the proof of a∗ being star-free:

$\Sigma\* = \bar{\emptyset} $

$ A∗= \overline{Σ∗(Σ∖A)Σ∗} $

Would this be a proof for $a * b$? : $ A∗B= \overline{Σ∗(Σ∖A)Σ∗(Σ∖B)} $

For $(A * B )\*$ it seems more complicated if not impossible, but is that proofable?

# Answer
> 1 votes
$a^\*b = (a^\*)\cdot b$

$(a^\*b)^\* = \\{\varepsilon\\} \cup \\{a,b\\}^\* b$

---
Tags: formal-languages, regular-languages, kleene-star
---


# Question
Title: Sorting a sorted array after increasing several elements
I know that most of the efficient sort algorithms can run with a complexity of $O(n\cdot log(n))$, but this is given an unsorted array.

However, given that the initial array is already sorted, is there an algorithm that can sort the array after multiplying several elements by 2 (or increasing them by some value) with complexity of $O(n)$?

# Answer
> 3 votes
You can update the array using the *merge* procedure of mergesort. Decompose your array into two smaller arrays: unchanged elements and updated elements. Since multiplying elements by $2$ preserves their relative order, you can do this decomposition in $O(n)$ while producing two *sorted* smaller arrays. You can then merge them in $O(n)$.

# Answer
> 0 votes
An alternative (to special handling of changed values, which, after all, might still be in the right place) might be smoothsort, designed to run $O(n)$ on sorted arrays and "degenerate" to $O(n \cdot log(n))$ with increasing disorder, well, smoothly.

# Answer
> 0 votes
Yuvals method works very well if you know which elements have been modified. If you don’t know which were modified, you make one pass through the array looking for elements followed by a smaller one. One of two must have been modified, so you move them both into a separate array. If there are k elements modified you move at most 2k elements. Apart from that you use Yuvals algorithm.

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


# Question
Title: Complexity of removing edges to eliminate a perfect matching
Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this problem?

I'm aware that perfect matching has a formulation as a max-flow. One approach is, therefore, to find a min-cut in a corresponding graph, and see how many edges need to be removed so that the max-flow cannot carry as much flow. The problem with this approach is that a different min-cut might require the deletion of fewer edges, so it seems like this involves looking at all the min cuts in a graph.

# Answer
This problem is known as the preclusion number of a graph, or minimum blocker perfect matching problem. It was shown to be $\mathcal{NP}$-hard in *Lacroix, Mathieu; Mahjoub, A. Ridha; Martin, Sébastien; Picouleau, Christophe*, **On the NP-completeness of the perfect matching free subgraph problem**, Theor. Comput. Sci. 423, 25-29 (2012). ZBL1237.68089.
> 0 votes

---
Tags: complexity-theory, time-complexity, network-flow, matching, bipartite-matching
---


# Question
Title: Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?
So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with *w2* or *w3*. The resulting string after pumping will also be in the language. I think the language *w1w2w3* is just similar to {0,1}\* . I can create a NFA for {0,1}\* , so that is why the language is regular. *w1w2w3* is just like a concatenation of *w1,w2,w3* but all of them are {0,1}\* so the NFA for the language {0,1}\* is also the NFA that accepts the language A2. Is my thinking so far correct? Will the NFA accept the language?

# Answer
> 2 votes
1. If you think the language is regular, there is no point using the pumping lemma. It is used to prove that some languages are NOT regular.
2. The sentence "$\\{0,1\\}^\*$ can represent the NFA for the language" makes absolutely no sense.
3. Your language is equal to $\\{0,1\\}^\*$ (you can choose any $w\_1$, and $w\_2 = w\_3 = \varepsilon$).

---
Tags: formal-languages, regular-languages, automata, regular-expressions, pumping-lemma
---


# Question
Title: What is the relation of branch instruction in single core CPU v.s. multicore CPU?
In the Computer organization and design book, there is an exercise in chapter 1 that stated:

> ```
> Assume that, as the program is parallelized to run over multiple cores, the number of arithmetic and load/store instructions per processor is divided by 0.7 × p (where p is the number of processors) but the number of branch instructions per processor remains the same.
>
> ```

My question is: While other instructions reduce as the number of processors are increased, why does the number of branch instructions per processor remain the same? Is it true in practice or this question is about an imaginary CPU?

# Answer
> 1 votes
This is very curious, and I would think someone is really misunderstanding something quite badly.

There is hyperthreading, where one core basically handles two instruction streams, without any execution units being added. The total performance for two threads will be closer to the theoretical maximum of instructions that this core could achieve. If you have incredibly good code that gets 80% of the theoretical performance it might go up to 90%. Bad code getting only 30% of the theoretical maximum might go to 60%. It is cheap to do and may or may not improve performance.

But beyond that, you will have n independent CPUs. They will usually be able to perform n times the instructions. Both branches, integer, floating point, and vector instructions.

The only problem you will have is that the hardware for accessing RAM will only exist once. You can bet that this hardware is as efficient as possible. On my personal computer, eight cores *cannot* use all available bandwidth. Another problem is that some caches will be shared. On my system, there is 24MB of L2 cache, with 12 MB each available to a group of 4 cores. So if two cores are used, one from each group of four, they have 12 MB each. If you use all eight cores, they have 3MB each on average. But that will not cause a slowdown like the one you were told about.

AMD is now building a monstrosity with 64 cores. According to your information that would only be able to perform about 40% more instructions than a single core. Somehow I think AMD ignored that information you were given and built their own reality.

A multi-core processor with p cores where the number of operations per core is divided by 0.7p would be impossible to sell.

---
Tags: computer-architecture, parallel-computing
---


# Question
Title: Why use Welford's Method over a more naive approach?
I came across this pair of blog posts explaining the problem with calculating variance on floating point data:

https://jvns.ca/blog/2023/01/13/examples-of-floating-point-problems/#example-3-a-variance-calculation-gone-wrong

https://jonisalonen.com/2013/deriving-welfords-method-for-computing-variance/

They show that a totally naive implementation of the variance calculation runs into the problem that the register in which you're accumulating the sum of squares will get so large that the floating point error becomes a fatal problem. In some cases this can even cause the variance to be negative at the end of the calculation.

To solve this, they propose using Welford's method, which (if I understand correctly) keeps a running estimate of the mean as you loop through the numbers, giving you an *approximation* of $x\_i - \mu$. The blog author gives the following pseudocode:

```
variance(samples):
  M := 0
  S := 0
  for k from 1 to N:
    x := samples[k]
    oldM := M
    M := M + (x-M)/k
    S := S + (x-M)*(x-oldM)
  return S/(N-1)

```

But then I thought "why can't we just calculate the mean first, and use that when calculating the variance?

```
variance(samples):
  M := 0
  S := 0
  for k from 1 to N:
    M := M + samples[k]
  M := M / N
  for k from 1 to N:
    S := S + (samples[k]-M)**2
  return S/(N)

```

It looks like this should be more accurate and run in about the same amount of time. To test it, I wrote it up in Python and compared numpy to my implementation of Welford, my fairly naive implementation ("good"), and the blogger's example of an overly naive implementation ("bad").

```
Numpy variance:     0.00029272912371828137
Good variance:      0.0002927291237197718
Bad variance:       -1.0752
Welford variance:   0.0002927584024568408

Numpy time: 2.579808235168457e-05
Good time:  0.0026930201053619383
Bad time:   0.0018948330879211427
Welford time:   0.004232816934585572

Good method suffered 42.12% peformance hit
Welford method suffered 123.39% performance hit

```

My expectations seem to have been borne out, assuming that the numpy implementation does it "right". So, is Welford actually the best choice for this for some other reason? Did I make a mistake somewhere in my implementation? Did the blog author just think it was cool so he decided to write a blog post? All of the code I wrote is given below:

import numpy, time

def calculate_bad_variance(nums):
    sum_of_squares = 0
    sum_of_nums = 0
    N = len(nums)
    for num in nums:
        sum_of_squares += num**2
        sum_of_nums += num
    mean = sum_of_nums / N
    variance = (sum_of_squares - N * mean**2) / N

    return variance

def calculate_good_variance(nums):
    sum_of_squares = 0
    sum_of_nums = 0
    N = len(nums)
    for num in nums:
        sum_of_nums += num
    mean = sum_of_nums / N
    for num in nums:
        sum_of_squares += (num - mean)**2
    variance = (sum_of_squares) / N

    return variance

def welford_variance(nums):
    M = 0
    S = 0
    N = len(nums)
    for k in range(N):
        x = nums[k]
        oldM = M
        M = M + (x-M)/(k+1)
        S = S + (x-M)*(x-oldM)
    return S/(N-1)

nums = np.random.uniform(10000000., 10000000.06, 10000)
N = 1000

true_var = np.var(nums)
bad_var = calculate_bad_variance(nums)
good_var = calculate_good_variance(nums)
welford_var = welford_variance(nums)

start = time.time()
for _ in range(N):
    np.var(nums)
np_t = (time.time() - start)/N

start = time.time()
for _ in range(N):
    calculate_bad_variance(nums)
bad_t = (time.time() - start)/N

start = time.time()
for _ in range(N):
    calculate_good_variance(nums)
good_t = (time.time() - start)/N

start = time.time()
for _ in range(N):
    welford_variance(nums)
welford_t = (time.time() - start)/N

print(f"Numpy variance:\t\t{true_var}\nGood variance:\t\t{good_var}\nBad variance:\t\t{bad_var}\nWelford variance: \t{welford_var}\n")
print(f"Numpy time:\t{np_t}\nGood time:\t{good_t}\nBad time:\t{bad_t}\nWelford time:\t{welford_t}\n")
print(f"Good method suffered {((good_t/bad_t)-1):.2%} peformance hit")
print(f"Welford method suffered {((welford_t/bad_t)-1):.2%} performance hit")
```

# Answer
The fact that you first pass every value to calculate mean and then calculate variance means you need to store data and that's the problem ! For a lot of applications you want to be able to compute "on the fly"
> 1 votes

# Answer
It’s a good algorithm if you want a single pass through your data. If it is not precise enough you have two choices:

1. A more complicated algorithm. Calculate a rough estimate of the mean. Then get the precise mean: Add the differences between data points and the estimated mean, reducing your numbers. And add numbers \> mean and numbers \< mean separately: If the sum is \> 0 add the next number \< mean first, otherwise the next number \> mean. So the sum stays around zero with small rounding errors.

Then you calculate the average of (data point - mean) squared. You use exactly the same method. So all in all four passes.

2. Use higher precision. If your computer has well-implemented floating-point arithmetic then you can calculate the exact rounding error of a sum a+b: calculate the sum s. If |a| \>= |b| then the exact error is (a - s) + b, otherwise it is (b - s) + a. So you have one sum where you add up values, and one where you add up rounding errors, and finally you add both sums.
> 0 votes

---
Tags: efficiency, statistics
---


# Question
Title: Write a CFG for a language of the form L_1 ={a^ib^jc^kd^m|i,j,k>=0, i +j +k> m}
I'm currently having trouble coming with context free grammar to describe this language. My current intuition is to generate an arbitrary amount of a,b,c's on my string and then whenever the character d is added to my string, I add two instances of either a,b,c to my string. However, I'm struggling in defining the instance in which a d is added to my string.

# Answer
We have a "reference question" How to prove that a language is context-free? where one of the suggestions is to write the language according to its "nesting structure". Then the grammar follows that structure.

Let us start with the related language $\\{\\; a^ib^jc^kd^m \mid i +j +k \ge m \\;\\} = \\{\\; a^i a^{i'} b^j b^{j'} c^kc^{k'}\\, d^kd^jd^i \mid \\; \dots \\}$. That is, for every $a,b,c$ to the left we may write a $d$ to the right, but we can also skip that $d$. Then the number of $d$'s is at most the sum of the other letters, because every $d$ is matched with another symbol.

If we want to ensure that $i+j+k\>m$ (in the original formulation) or $i'+j'+k'\>0$ (in my second formulation), I can suggest two approaches. Either build three different grammars, one writing at least one extra $a,b,c$ respectively. Or build a finite state control in the variables of the grammar where the variable not only remembers which symbol it is generating ($a,b,c$) but also whether it has already written the extra symbol without matching $d$.
> 0 votes

---
Tags: formal-languages, automata, context-free
---


# Question
Title: Is the language given by the regex (ab)* star-free?
I was reading about star-free languages recently and a common example of a non-star free language is the one given by (aa)\*. I was wondering if (ab)\* would also work (for an alphabet of two symbols let's say).

# Answer
> 11 votes
No. $L=(ab)^\*$ is star-free. A word is in $L$ iff

1. It starts with $a$ (or is empty)
2. It ends with $b$ (or is empty)
3. It does not contain any consecutive $a$'s
4. It does not contain any consecutive $b$'s

Each of those conditions can be represented by a star-free language. Indeed, condition 3 is the first example given on Wikipedia of a star-free language. Here are star-free regular expressions for each of those:

1. $(b\emptyset^c)^c$
2. $(\emptyset^c a)^c$
3. $(\emptyset^c aa \emptyset^c)^c$
4. $(\emptyset^c bb \emptyset^c)^c$

where $S^c$ denotes the complement of $S$.

Consequently,

$$L = (b\emptyset^c)^c \cap (\emptyset^c a)^c \cap (\emptyset^c aa \emptyset^c)^c \cap (\emptyset^c bb \emptyset^c)^c,$$

which is a star-free representation for $L$. Another equivalent representation is

$$L = (b\emptyset^c | \emptyset^c a | \emptyset^c aa \emptyset^c | \emptyset^c bb \emptyset^c)^c.$$

# Answer
> 0 votes
Note that the four requirements in the excellent answer by D.W. are in fact first-order definable. That is, they can be formulated quantifying over positions in the string and the relative order of these positions. By a result of McNaughton and Papert these are star-free.

Every regular language, including the non-star-free example $(aa)^\*$, can be specified using a logic where one also is allowed to quantify over sets of positions. This is a result from Büchi, Elgot and Trakhtenbrot. (Intuitively sets of positions where a finite automaton reaches a specific state.)

---
Tags: formal-languages, regular-languages
---


# Question
Title: Construct a regular grammar that produces all possible strings of $\Sigma = \{a,b\}$ that do not contain substring 'abba'
I'm really stuck here and do not know what to do. So far, I've constructed a DFA and a regular expression that produces the aforementioned set of strings. Namely, the DFA looks like:

After a lot of efforts I managed to find a concise regular expression of it, namely: $$ b^\*\left( a + (b \\; | \\; bbb+)\right)^\*a^\*b^\*.$$

What I have tried so far as to construct the desired regular grammar is: \begin{align\*} q\_0 &\rightarrow b \ | \ a \ | \ aq\_1 | \ ε \ \\ q\_1 &\rightarrow aq\_1 \ | \ bq\_2 \ | \ ε \ \\ q\_2 &\rightarrow aq\_0 \ | \ bq\_3 \ | \ ε \ \\ q\_3 &\rightarrow bq\_0 \ | \ aq\_4 \ | \ ε \end{align\*}

Obviously $q\_4$ is non-yielding, therefore we can omit it, and we get

\begin{align\*} q\_0 &\rightarrow b \ | \ a \ | \ aq\_1 | \ ε \ \\ q\_1 &\rightarrow aq\_1 \ | \ bq\_2 \ | \ ε \ \\ q\_2 &\rightarrow aq\_0 \ | \ bq\_3 \ | \ ε \ \\ q\_3 &\rightarrow bq\_0 \ | \ ε \end{align\*}

Correct me if I'm wrong but the above rules as is, define a context free grammar since we have more than one non-Terminal symbol on the right side. How can I turn the above rules into a regular grammar? Any help would be greatly appreciated.

# Answer
That already is a regular grammar; in particular, it is right-regular.
> 1 votes

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


# Question
Title: Checking equality of self-referential lists
Define that an srlist ("self-referential list") over $X$ consists of a list of elements of $X \sqcup \mathrm{srlist}(X).$ So basically, the items can be primitive values, or further self-referential lists, or a mixture of both. Cycles are allowed.

For example, $S = \[S\]$ is a perfectly good definition of an srlist. Define two srlists to be equal if and only if the possibly infinite tree that the srlist represents are equal. For example, observe that $S$ looks a bit like this:

$$\* \rightarrow * \rightarrow * \rightarrow \\,...$$

So too does the srlist defined by $T = \[T\]$. Hence $T = S$. In a similar way, if we define $U = \[\[U\]\]$, the resulting infinite tree will look the same as above. So $U = S$.

**Question.** I'm trying to find an algorithm for checking equality of srlists, but unfortunately the naive approach of using recursion has issues with never halting for most srlists, due to the possibility of cycles. Ideas, anyone?

# Answer
> 2 votes
We define the signature of an srlist $S$ as the set of finite sequences $a\_i$ of integers such that $S\[a\_1\]\[a\_2\]\[a\_3\]...\[a\_n\]$ exists. It's not hard to see that two srlists are equal iff the have the same signature.

It's also not hard to see that the signature of an srlist is a regular language - the states are all values in $S$, recursively, but without following references, and the transitions are obvious.

So you can convert $S$ and $T$ to their finite automata and test for their equality.

If you want to support primitive types you can have $S\[a\_1\]\[a\_2\]...\[a\_{n-1}\] = a\_n$ as a signature instead, and allow $S\[a\_1\]\[a\_2\]...\[a\_{n-1}\] = \*$ if it's a list (to still test the list structure if it's infinite).

---
Tags: data-structures, recursion, equality
---


# Question
Title: Link utilization of sliding window protocol
Before I ask my doubt I would like to state that problem which led me to my doubt. It can also serve as a good example scenario.

> A $20\ Kbps$ satellite link has a propagation delay of $400\ ms$. The transmitter employs the "Sliding Window protocol" scheme with Window Size set to $10$. Assuming that each frame is $100$ bytes long. What is the link utilization of transmission medium.

From the question we can make out that Window Size $(WS)$ is $10$, transmission time $(T\_t)$ of a frame is $40\ ms$ , and propogation time $(T\_p)$ is $400\ ms$.

Now, the solution that book proposes simply states that Link Utilization $(LU)$ for sliding window protocol can be calculated as

$$LU = \frac{WS\*T\_t}{T\_t + 2\*T\_p}$$

That's where I'm facing the problem. From what I have learned about Link utilization

> It is the fraction of total time the host was busy in transmission of data. In other words, it is the ratio of **total transmission time** over **Total Time** involved in transmission.

Now if I try to fit the formula proposed in book with what I have learned, the total time involved in transmission is $T\_t+2\*T\_p$.

But that is only the total transmission time of one single packet over the medium. Why isn't it is $WS\*T\_t + 2\*T\_p$, since we are sending $WS$ packets without wating for acknowledgement.

---

The only thing I could figure out after thinking a lot about my doubt is that I am probably going wrong because of my incomplete understanding of what Link Utilization means.

I will appriciate any kind of help.

# Answer
> 2 votes
I had the same doubt and was getting nowhere close to grasp the concept. After banging my head for a few days I now think I have understood the basic concept. We define utilization as the total time used by the link to send good data divided by the total time link is engaged. In stop and wait, we send one frame and do nothing good unless we receive an acknowledgment this presents a low utilization.

Total time link is used is :

**ttransmission \+ 2\* tprop**

total time link is used for sending good data :

**ttransmission**

Consider the sliding window now we send one frame and instead of waiting for the acknowledgment we continue transferring frames until the acknowledgment arrives. The total time for the link remains the same however, we have increased the good time to:

**WindowSize * ttransmission.**

Why isn't the total time : **WSxttransmission \+ 2\* tprop** ?

> We have sent all the additional frames between the time frame of sending the first frame and receiving the first acknowledgment.

This time frame is equal to :

**ttransmission \+ 2\* tprop** and not **WSxttransmission \+ 2\* tprop**

We have just increased the fraction of this total time from :

**ttransmission.**
to

**WindowSize * ttransmission.**

Here is a Linkconsider the figure 7.11 in the same. It beautifully illustrates the concept. I wasn't sure of posting the picture due to copyright issues. Cheers!

# Answer
> 3 votes
Link utilitization is about the steady state, i.e., what happens when you send a *lot* of data... not what happens at startup (at the very beginning of the connection).

Imagine you have a humongous file to send. It takes far more than 10 frames to send the entire file. Calculate the total time to send the entire file. Calculate the total transmission time for that file. Now divide.

Try doing that calculation again. I think you'll see that you get a different answer. For instance, try calculating what happens if you send a file that is 1000 frames long... or 10,000 frames long. How long does it take to send the entire file? What fraction of that was spent in transmission time, as opposed to waiting for acknowledgements?

# Answer
> 0 votes
I too had the same doubt before but after solving many i got to a conclusion, see there is a Band width B for everything, so when you just use the stop and wait the bandwidth B is not entirely used for this the sliding window is used, It is like at one instant it can transmit many packets out, so you can say that many packets can be transmitted in the instant, but that will not be the case as link utilization will cross 100%, so for a fixed window size you can transmit the whole packets out and place it on the carriers.I gave a vague answer but i think you will get it.

# Answer
> 0 votes
If you define the unit time as WSTt + 2Tp, within this time frame, the sliding window can send the entire window twice (assuming a window size of 3, sending frames (0,1,2) and then (3,4,5)). Therefore, the result for utilization rate (LU) becomes LU = (2 * WS * Tt) / (WS * Tt + 2 * Tp).

If you ask whether you can ignore sending the second window (frames 3,4,5), the answer is no. The link's utilization rate is defined as the actual bits that pass through the link during a unit time divided by the maximum bits that can pass through the link during that same unit time. Since the link is shared, you cannot ignore the second window.

Furthermore, the unit time should be defined as a time that can repeat with the same pattern. When the first period is completed, it should return to the initial state (here, an empty state). However, if you define the period as (WS * Tt + 2 * Tp), it means you would be waiting for the ACK to return at the end of the first period, which is incorrect.

Therefore, the correct formula is LU = (WS * Tt) / (Tt + 2 * Tp).

---
Tags: computer-networks, communication-protocols
---


# Question
Title: For which values of $k$ is a $k$-state-bounded version of the halting problem decidable?
This is related to my previous question: Do proofs of $HALT$'s undecidability make it clear that it's practically relevant? I made a mistake of leaving something implicit when I asked it; namely that the machine that decides the bounded version of the halting problem should also be bounded.

Consider the following statement: "given a Turing machine $M$ with less than $k$ states and a word $w$ with less than $k$ symbols, we can decide whether $M(w)$ halts **using a machine with less than $k$ states**", for some $k$.

I am wondering for what $k$, if any, is this sentence true. Answers don't have to be precise (i.e. "for k = 27"), any approach of thinking about it is welcome.

# Answer
Consider the following:

Here is a formalization of a proof that halting is undecidable based on universal Turing machines. It uses the following components:

1. Adding a new state that loops forever to a machine. Each rule where the machine would halt with a $1$ focused on the tape is instead changed to a rule that transitions to the looping state.
2. A universal Turing machine $U$. This is a machine that when run on input $(M,w)$ behaves equivalently to $M(w)$
3. A fixed point construction, which modifies a machine $M$ into a machine $μM$ that first adds its own encoding to the tape before behaving like $M$. So, $μM(w)$ is equivalent to $M(w,μM)$. This is a pretty complicated thing to actually build for Turing machines, but there's a theorem that they exist.
4. A duplicating modification. This one changes $M$ to $ΔM$ so that $ΔM(w,x)$ is equivalent to $M(w,(x,w))$

If we indicate the first transformation as $¬$, then the machine we build is $\hat U = μ(Δ(¬U))$. Then for a machine $H$, we have the following equivalences:

$$\hat U(H) \simeq Δ(¬U)(H,\hat U) \simeq ¬U(H,(\hat U, H)) \simeq ¬H(\hat U, H)$$

and the last execution has the opposite halting behavior from what $H(\hat U, H)$ indicates. So, $H$ fails to decide the halting behavior of $\hat U(H)$.

Now, I don't know the actual size of $\hat U$, because I don't know how much blow-up $μ$ causes. For typical programming languages, that sort of 'Quine' like program would be around double the size of the input, plus some fixed cost. For instance, in Haskell, you can write something similar like:

```
f g x = let s = "f g x = let s = % in g x (sub s s)" in g x (sub s s)

```

where `sub s t` is a function that replaces occurrences of `%` in `s` with `t` surrounded by quotes.1 This is considerably longer than the two occurrences of `g`, but if the code for `g` were inlined, it could be longer than the fixed overhead for `f`. In any case, I'd expect the factor to be worse for Turing machines.

As mentioned in the comment above, there are 2 state UTMs, although other combinations might be more economical. $Δ$ is a fixed, relatively small cost and $¬$ is even smaller. The bottom line, though, is that $\hat U$ has some particular (honestly probably not very large) size, and it is a sort of universal diagonal machine. So there is a state size $k$ for which *no* machine $H$ can predict what all machines of size $k$ will do when run with an encoding of $H$ as input.

I suspect that the loophole in this argument is that the encoding of $H$ as a word has significantly more symbols than $H$ has states. So, by stating that both the number of states in $M$ *and* the symbols in $w$ are less than $k$, you are excluding the diagonal case that this argument presents.

However, that also means that in the case of a universal machine like $\hat U$, you are only considering what it does with inputs that correspond to machines with a fraction of the states in $H$. In other words, the idea that a program's halting behavior can only be reliably decided by a significantly *longer* program is built into your question. And this can't be fixed, or else diagonalization will work.

\[1\] If you want to inline `g`, then `sub` might have to become more elaborate about quoting the substituted string. This is also necessary if you want to include the code for `sub` and the quotation directly in `f`. But it's ultimately possible.
> 2 votes

---
Tags: computability, halting-problem
---


# Question
Title: What is the Minimum length of a string that is accepted by a DFA that shows that the language accepted by that DFA is infinite?
What is the minimum length of a string that is accepted by a DFA, shows that the language accepted by that DFA is infinite?

I checked this post How to determine if an automata (DFA) accepts an infinite or finite language? and in the answer provided by Rick Decker, he states, "The language accepted by a DFA M with n states is infinite if and only if M accepts a string of length k, where n≤k\<2n." But, if I have a string of minimum length 'n-1' that gets accepted by a DFA having 'n' states, it proves that the language accepted by the DFA is infinite. So, is the minimum lower bound 'n' or 'n-1'?

# Answer
Possibly the off-by-one is due to the fact that sometimes we (slightly) abuse the definition of DFAs by using a transition function that is not total. Of course, such a DFA is equivalent to a DFA with a total transition function and one more state, so the distinction usually does not matter. However, since you are after an exact bound on the length of a string as a function of the numbers states, we have to be careful.

To avoid confusion let's consider total transition functions only.

**Claim:** Let $D$ be a DFA with $n$ states. $L(D)$ is infinite if and only if $D$ accepts some string $x$ with $|x| \ge n-1$.

**Proof:** Let $\Sigma$ and $\delta$ be the alphabet and the transition function of $D$, respectively.

One direction is trivial: if $L(D)$ is infinite, then $L' = L(D) \setminus \left( \cup\_{i=0}^{n-2} \Sigma^i \right)$ is also infinite (since $\cup\_{i=0}^{n-2} \Sigma^i $ is finite) and we can pick any $x \in L'$.

Suppose then that $D$ accepts some $x$ with $|x| \ge n-1$. There must be some (not necessarily simple) path $\pi\_x$ from the initial state $q\_0$ of to an accepting state $q\_A$ of $D$. Our goal is to show that there are infinitely many such paths. In particular, it suffices to show that there is a path $\pi^\*$ from $q\_0$ to $q\_A$ that is not simple (i.e., it has some repeated vertex), since then $\pi^\*$ must contain a cycle.

If there is some $s \in \Sigma$ such that $\delta(q\_A,s)$ can reach $q\_A$ (possibly $\delta(q\_A,s)=q\_A)$ via some path $\pi'$, we can choose $\pi^\* = \pi\_x \circ \pi'$, where $\circ$ denotes concatenation. Otherwise, there is at least one state $q$ that cannot reach $q\_A$, which means that $\pi\_x$ does not traverse $q$. Since the length of $\pi\_x$ is at least $n-1$, and at most $n-1$ vertices can be traversed, the pigeonhole principle ensures that $\pi\_x$ cannot be simple (i.e., we can choose $\pi^\* = \pi\_x$). $\square$

The above bound is tight in the sense that, for every $n \ge 1$, you can build a DFA $D$ with $n$ states such that all strings of length at most $n-2$ are accepted but $L(D)$ is finite (the graph of the DFA is a directed path with vertices $q\_0, \dots, q\_{n-1}$ where $q\_0, \dots, q\_{n-2}$ are accepting, and $q\_{n-1}$ is a catch-all rejecting trap).

Moreover, the following holds:

**Claim:** if $L(D)$ is infinite then there must be some string $x$ with $n-1 \le |x| \le 2n-2$ that is accepted by $D$.

**Proof:** Let $\pi$ be the shortest accepting (non-simple) path of length at least $2n-1$. Since $\pi$ traverses $2n \> n$ states (counting repetitions), $\pi$ must include a cycle. Deleting the cycle from $C$ yields an accepting path of length at most $2n-2$ and at least $2n-1-n=n-1$. $\square$

This is tight in the sense that there are DFAs $D$ such that $L(D)$ is infinite but all strings $x$ with $n-1 \le |x| \le 2n-3$ are rejected (the graph of the DFA is a directed cycle with states $q\_0, \dots, q\_{n-1}$, only state $q\_{n-2}$ is accepting).

---

**To summarize**

If $D$ be a DFA with $n$ states then $L(D)$ is infinite if and only if $D$ accepts some string $x$ with $n-1 \le |x| \le 2n-2$.
> 3 votes

---
Tags: finite-automata
---


# Question
Title: Is there any example of a Turing-recognizable language mapping reducible to a NOT Turing-recognizable language?
Theorem: "If A is mapping reducible to B and B is recognizable, then A is recognizable."

I know that the following statement is FALSE.

"If A is mapping reducible to B and A is recognizable, then B is recognizable."

But I can't come up with an example to prove that.

# Answer
> 1 votes
Assume we have alphabet $\\{0,1\\}$. Map string $w$ to $0{\cdot} w$. Then a copy of $A$ is found in $B$ as all strings starting with $0$. The strings in $B$ that start with $1$ can have any property you like.

---
Tags: complexity-theory, turing-recognizable
---


# Question
Title: What are common heuristic algorithms of self-organizing list?
So in my "Advanced algorithms" course, we were taught about the "self-organizing list" data structure. The professor showed the following three heuristic algorithms: Frequency Count, Move to Front and Transpose.

Looking online, I could not find any other "popular", "common" or "used" heuristic algorithms. Are there any other heuristic algorithms that the self-organizing list can implement (without knowing the distribution of the input)? What are their benefits?

# Answer
> 0 votes
You can check these two surveys for discussions of other heuristics like TIMESTAMP and MRI, beyond the 3 common heuristics:

# Answer
> 0 votes
There are two situations. One, you want a list organised so that the most requested items are at the front of the list and found quickest. In that situation you will more likely use a hash which gives you fast access to all items (and finds equally fast that an item is not present, which a linked list cannot do).

The other situation is that you want items in a rough order of importance. In that case you might use a priority queue instead.

From a programming point of view, the implementation will often be hidden from you. You use an abstract data structure, you know what features it offers, but you wouldn’t even know if it is a linked list, a hash map, or for very small numbers of items even an array.

(I had a situation where I needed many many thousands of lists. But many lists were empty, 90% contained just one item, and the others had few. So I created a class with a pointer that could be null, point to the single item, or to a small array of items - providing the full interface for a linked list. )

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


# Question
Title: Do function problems have an interpretation in terms of formal languages?
> In computational complexity theory, decision problems are typically defined as formal languages, and complexity classes are defined as the sets of the formal languages that can be parsed by machines with limited computational power.

https://en.wikipedia.org/wiki/Formal\_language

Can function problems also be seen as problems of formal languages? (Without converting them to a decision problem that is).

# Answer
The lemma at wikipedia is very much restricted to languages as sets of (finite length) strings. I believe that formal language theory is nowadays considered more broadly. Its "languages" may consist of infinite length strings, trees, partial orders, two-dimensional grids and graphs.

One studies ways to define (grammatical, logical, algebraical) or recognize (with automata) such languages, and given one of those language families their (combinatorial) properties.

As in the remark by Steven, one may code one type of object into another. A string function consists of string-pairs, which can be coded into single strings. Another example is the coding of a tree into a string (sometimes using brackets).

A function translating objects is sometimes called a transducer. One has for instance finite state transducers, like finite state automata but with output. In complexity theory transducers play a role in problem reductions where the transducer might be a two-tape Turing machine translating one problem into another.
> 0 votes

---
Tags: formal-languages, decision-problem
---


# Question
Title: Showing that all gomory hu trees of $K_{3,3}$ are stars with 5 edges
My lecture notes for gomory-hu trees says that it's easy to see that every GHT of the utility graph $K\_{3,3}$ is a star with 5 edges. Is there any easy way to see this without manually computing every gomory-hu tree of the graph? Could I make use of the symmetry of the graph?

# Answer
**Outline:**
For generality, we will be looking at $K\_{n,n}$ with $n\ge3$ and all edge weights equal to 1. One can prove that any (s,t)-mincut in $K\_{n,n}$ cuts off exactly one vertex. From that, it follows that the longest path in the GHT has length \<=2. The only connected graph with this property is an (2n-1)-star.

---

**Lemma 1:** Any (s,t)-mincut in $K\_{n,n}$ with $n\ge3$ cuts off exactly one vertex.

**Proof:**

* The vertices of $K\_{n,n}$ can, by definition be partitioned into two subsets such that no edge has both endpoints in the same subset. Call these subsets $L$ and $R$.
* Consider any cut and call the smallest connected component after cutting $C$. $C$ contains $i$ vertices from $L$ and $j$ vertices from $R$, with $1\le i+j\le n$. Now $$w(C)=i(n-j)+j(n-i)=n(i+j)-2ij$$
* A cut that cuts off one vertex has weight $n$.
* A cut that cuts off 2 or more vertices has (by AM-GM) weight \begin{align} w(C) &\ge n(i+j)-\frac{1}{2}(i+j)^2 \\ &= (i+j)(n-\frac{i+j}{2}) \\ &\ge 2\cdot \frac{n}{2}=n \end{align} Where equality holds iff 2=i+j=n, which is impossible for $n\ge3$
* Thus the (s,t)-mincuts in $K\_{n,n}$ are the cuts that cut off only $s$ or only $t$.

**Lemma 2:** Every path in the GHT has length $\< 3$

**Proof:** If there was a path $(v\_1,v\_2,...,v\_k)$ with $k\ge4$, then $GHT \setminus (v\_2v\_3)$ would have two connected components of size $\ge2$ each. Because of the properties of GHTs, a $(v\_2v\_3)$-mincut in $K\_{n,n}$ would have the same connected components, which contradicts Lemma 1.

**Lemma 3:** Any GHT of $K\_{n,n}$ is a (2n-1)-star.

**Proof:** The only connected graph with the preceding property is a star.
> 0 votes

---
Tags: graphs, trees
---


title: Page fault, virtual memory

text:
# Question
Title: Page fault, virtual memory
I am reading the book: Digital Design and Computer Architecture: ARM Edition

I am on the chapter about virtual memory. I am wondering, when a page fault occurs, is it the processor or the OS that "fixes it". In the text below they first say that the processor fixes it, then they say it is the OS that fixes it.

Do you understand why it is written this way?

# Answer
> 1 votes
Both. The OS is software that executes on the processor.

# Answer
> 0 votes
Let’s say you want to access data at a certain logical address. Your program might use a “load” instruction. That instruction is implemented in the CPU; it will determine if the data is in a cache and return it quickly, or if it is in RAM and at what physical address and return it slowly, or the hardware determines that the data is not in RAM at all. In that case the hardware interrupts your code and switches to code in the OS that handles the situation.

At that point code in the OS takes over. So it’s the OS running instructions using the processor. The OS is just given the logical address. It will then decide whether your program had the right to access that logical address - if not the OS might even kill your program. Or you have the right, then the OS will arrange things so that your logical address is in RAM and then tell the processor to run the instruction again; this time it should work.

# Answer
> 0 votes
It's done by the software, usually OS. Paging out is the process of writing data to the external memory, a CPU can't do that on its own.

So, the user program is interrupted, OS reads this page from the disk, maybe writes another page to the disk, updates virtual memory tables and returns control back to the user program.

The first citation is incorrect, although from a user program perspective, it doesn't make much difference - the page magically appears in the memory and execution continues.

---
Tags: virtual-memory, page-replacement
---


title: An elementary question about grammar

text:
# Question
Title: An elementary question about grammar
Recently, I am studying grammar in automata. And, I have few information about this subject.

I have a grammar with rules $\\{S\to ASA, A\to aA, A\to \epsilon\\}$.

Is it true if I say that $S\to aASA$ by rules $S\to ASA, A\to aA$?

# Answer
> 2 votes
You are close, but not precise.

Usually one distinguishes between the arrow notation for the rules $A \to aA$ and the notation for derivation in the grammar, that is the application of the rules in strings $ASA\Rightarrow aASA$.

In your example two consecutive rules are applied, and we write $S\Rightarrow ASA \Rightarrow aASA$, or combining steps $S\Rightarrow^\* aASA$.

Observe that your grammar will generate the empty language. There are no productions that remove the initial variable $S$.

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


# Question
Title: Are there any programming languages which support user defined control structures?
For instance, the user would define a for each loop in their code as having a structure something like: `foreach([variable1] : [variable2]){
 [statements]
}` (when \[ \] are placeholders) and then the pieces would be used like this: `for(i = 0; i < variable2.length; i++){
 variable1 = variable2[i];
 statements
}` and then in the rest of the program, the user could use a for each loop with that format: `total = 0;
foreach(num : numbers){
 total += num;
}`

I hope that example makes sense. To be clear, I am saying that in this hypothetical language a for each loop does not exist, but the user can define one which will, for then on, work exactly the same as any other structure. Are there any languages which allow this?

# Answer
There are two aspects to your question:

1. Can we arrange a convenient syntax to express one control structure in terms of another?
2. Can we actually define new control flow mechanisms.

For example, suppose we have a language which only has the `if` statements without `else`:

```
if A then B

```

Can we express `if A then B else C` somehow? Yes, like this:

```
a = A ;
if a then B ;
if not a then C

```

It would be even better if we could package up the above piece of code into convenient syntax so that we could write just `if A then B else C`.

Sometimes we can define new control structures using existing ones. For instance, a `while` loop

```
while A do B

```

can be replaced with a call to a recursive function (under some technical assumptions):

```
function whileLoop():
   if A then (B ; whileLoop ())

whileLoop();

```

This sort of transformation is a bit more involved because it requires that for each `while` loop we define a new recursive function. If we were to automate the process, we would have to worry about many details (how to invent unique names of generated functions, do the functions have access to the local variables, etc.) than when we're performing just a straightforward syntactic translation of one variant of loop to another.

On the other hand, there are control mechanism which simply are not expressible in a language, unless already supported. One such example would be continuations. You can't get these in C, for example, but they exist in Scheme.

Your question is about syntax: can we make a syntactic transformation that replaces one piece of syntax with another piece of syntax. Languages usually deal with this sort of thing through a macro mechanism or syntax extensions. Here are some examples:

* C has macros which will get you some of the way
* Scheme has a more elaborate macro system which gets you a lot further
* Racket, a descendant of Scheme, has an elaborate multi-stage computation system which allows essentially arbitrary syntax extensions
* OCaml has the camplp5 syntax extension tool which allows pretty much arbitrary syntax extensions
* Template Haskell is an extension of Haskell which allows meta-level transformations of syntax.

I am sure there are many other languages with similar facilities that I am not familiar with.
> 2 votes

# Answer
Swift has a syntax that allows you to write something that *looks* like user defined control structures.

Swift has "closures". Closures are roughly bits of code that can be assigned to a variable or used as a function parameter. That means you can write a function that takes a closure as a parameter, and calls it when it wants.

And there is a syntactic rule: If a closure is the last parameter in a function call, then instead of passing it as the last parameter, you can remove it from the parameter list and add it *after* the call in { parentheses }. For example, I have a function that executes code on a background thread. I call it like

```
run_in_background () { write the code here to run in the background }

```

or a function that does something with all array elements

```
for_each_array_element (somearray) { code to apply to each array element }

```

In reality, this is equivalent to a simple function call, but it looks like a control structure.

BTW. || and && are operator functions that don't evaluate their second argument until the code in the operator function asks for it. So you can write

```
if p != nil && p.x == 0 { }

```

and the operator&& function gets called - but p.x == 0 isn't evaluated yet at that point.
> 1 votes

# Answer
In FORTH control structures are defined in code. I think Smalltalk had some related features.
> 0 votes

# Answer
On one level, all computer hardware has primitives capable of expressing various control structures.

The process of "user-defining" a particular control structure is then the process of writing a compiled high-level language.

That process of devising a language and compiler is usually quite difficult, because it involves a careful study, long experience, and a delicate settlement of human factors. Human factors is ultimately the only reason for high-level languages - otherwise, everything can be done with assembly language and integers.

When an already high-level language attempts to furnish a limited set of primitives by which all other concepts are supposed to be implemented, the usual casualty is human factors.

The goto statement (in languages which have it) is the all-purpose solution to control structures which don't easily fit within the standard set of control structures. Often, there is only a very small amount of extra syntactic fuss to using goto instead of the standard control structures.

But the reason languages do not retain only the goto statement, is because it is convenient to have and to use a set of standard and widely understood control structures, which are sufficient on their own to express all possible computation.

And the reason goto is highly discouraged, is precisely because "user-defined" structures outside those standard ones already furnished, are usually misconceived. But it's there for some legitimate residual cases.

Finally, interpreting your question as strictly as possible as being about the definition of custom blocks, with an identifying keyword, and further elements which control details of how the block behaves, there are languages like C with macro preprocessors, in which it is often possible to cobble together what appear visually as custom block structures, and which when compiled are replaced with a more elaborate set of primitive statements.
> 0 votes

# Answer
My programming language, MICGBF, solves your problem.

Any time you make a program, it turns that program into a single command, using a self-changing interpreter.

For example, if you give it the commands `������` and run it, then my programming language would make a new command called `<insert tab here>` which would execute `������`. This could be helpful for making long programs short.

The proof for this is in the Python 3 code
> -1 votes

---
Tags: programming-languages, language-design
---


# Question
Title: Finding the Point with Maximum Distance from the Boundary of a Closed Polygon in 2D Euclidean Space
Given a closed polygon defined in the 2D Euclidean plane. My objective is to determine the point within this polygon that is furthest away from its boundary. In other words, I want to find the point where the distance to the polygon's boundary is maximized.

More formally, given a polygon $P \in \mathbb{R}^2$, for any point $x\in P$ we define $D\_P(x) = \min\_{y\in \partial P}dist(x,y)$. We wish to find a point $x\in P$ which maximizes $D\_P(x)$.

Here are my specific questions:

1. Is there an analytical or closed-form equation for finding the point with the maximum distance from the boundary of a closed polygon in 2D Euclidean space, expressed as a function of the polygon's vertices?
2. How can I algorithmically find such point?
3. More generally, can the above be solved for a connected convex set in a d--dimensional Euclidean space instead of a polygon, how would the approach change? Are there general methods for solving this problem in higher dimensions?

I'd appreciate any insights, algorithms, or references that can help me achieve this goal.

# Answer
> 2 votes
The medial axis is the set of points in the interior of the shape that has two closest points on the boundary.

Intuitively, the largest "incircle" in a polygon must touch the boundary at at least three points. It follows that you can just consider the set of points that are the "junctions" on the medial axis: points where three line segments of the medial axis meet.

To compute the medial axis for a simple polygon, linear algorithms are known, although it may be worth using a simpler $O(n \log n)$ algorithm. See:

The cells formed by the boundary and the medial axis is known as a generalised Voronoi diagram; it's generalised because some of the "points" are the boundary lines. There are plenty of software packages out there that compute generalised Voronoi diagrams.

---
Tags: algorithms, computational-geometry, polygons, euclidean-distance
---


title: Longest Fibonacci word

text:
# Question
Title: Longest Fibonacci word
We define Fibonacci words as: $F\_0 = a, F\_1 = b, F\_{n+2} = F\_n F\_{n+1}$, $a, b$ can be any symbols.

How can we find the longest Fibonacci sub-word in a given string in linear time?

This question is similar to: Complexity of a naive algorithm for finding the longest Fibonacci substring But I'm in particular interested if there is an $O(n)$ solution.

# Answer
> 1 votes
This might be a sledgehammer to crack a nut, but here is my solution.

First let me consider the Fibonacci strings I am used to: $f\_{n+2} = f\_{n+1} f\_n$. Observe that each $f\_{n+2}$ is a prefix of the previous $f\_{n+1}$. This makes it simple to construct the next Fibonacci string from the previous one. For instance keep a reference to the last prefix and copy that prefix after the current Fibonacci string.

Representing all substrings of a string can be done by constructing the suffix-tree or suffix-array of that string. Magically this suffix-tree $T$ can be constructed in linear time. Start reading Fibonacci string $f\_k$ in $T$, and once we have found this string extend the search into $f\_{k+1}$, etcetera. This is possible because of the prefix property of Fibonacci strings.

For your definition of Fibonacci strings you can read the search string backwards.

(I had to google the "sledgehammer" idiom; in my native language we "use a canon to shoot at musquitos".)

---
Tags: algorithms, strings, substrings, subsequences
---


# Question
Title: How big is a formula equivalent to a wff over $n$ variables with $2^n$ subformulas?
**Definitions**: Let $n \in \mathbb{N}$. If $\alpha$ and $\beta$ are propositional formulas, then we'll call $\alpha$ and $\beta$ *independent* if neither implies the other, or more formally, if $\lnot (\alpha \rightarrow \beta)$ and $\lnot(\beta \rightarrow \alpha)$ are each satisfiable, perhaps under different variable assignments. The notation $|\phi|$ refers to the length of $\phi$ in characters.

We saw in the answer to a previous question that if a formula $\phi$ has $2^n$ independently varying propositional variables, then any formula logically equivalent to $\phi$ must be of length at least $2^n$. I'll call this answer $A$.

We now attempt to generalize that result from independent variables to independent formulas. We are constrained to consider only those wffs $\phi$ that contain $2^n$ pairwise independent formulas over $n$ variables. Syntactically, these formulas $\alpha\_i$ are constrained to occur at the leaf level of $\phi$, so that if a variable were substituted for the formula, it would occur at the syntactic leaf level of $\phi$. No other formula may occur at the leaf level of $\phi$. Neither $\phi$ nor any of the $\alpha\_i$ is allowed to be identically true or false.

**Question**: Can we then conclude that any formula $\varphi$ logically equivalent to $\phi$ must be of exponential length, that is, if $\varphi \leftrightarrow \phi$, then $|\varphi| = \Omega(2^n)$?

**Argument**: We create $2^n$ new propositional variables

$$p\_1,\ldots, p\_{2^n}$$

and then define $2^n$ equivalences $p\_i \leftrightarrow \alpha\_i$ for each of the independent $n$-place formulas $\alpha\_i$. At this point, we can just substitute the variable for the corresponding formula and reduce the problem to the one solved in answer $A$.

# Answer
> 0 votes
No. Consider the formula

$$\phi = \alpha\_1 \lor \alpha\_2 \lor \dots \lor \alpha\_{2^n} \lor \text{True},$$

where the $\alpha\_i$ are pairwise independent according to your definition.

$\phi$ meets the requirements of your question ($\phi$ contains $2^n$ pairwise independent formulas $\alpha\_i$, all $\alpha\_i$'s occur at the leaf level of $\phi$).

However $\phi$ is equivalent to $\psi = \text{True}$, which does not have exponential length.

---
Tags: complexity-theory, logic, propositional-logic
---


# Question
Title: Prove $T(n)=10T(\frac{n}{3})+n\sqrt{n}=\Theta(n^{\lg_3{10}})$ using induction
We have this recurrence: $$T(n)=10T(\frac{n}{3})+n\sqrt{n}.$$

We can solve it using Master Theorem and say it is $\Theta(n^{\log\_3{10}})$. I want to prove it using induction but I don't know the correct and perfect procedure for proving these kinds of problems using induction.

I know that

* $f(n) = \mathcal{O}(g(n))$ if there exist positive constants $c$ and $n\_0$ such that $f(n)\le cg(n)$ for all $n\ge n\_0$.
* $f(n) = \Omega(g(n))$ if there exist positive constants $c$ and $n\_0$ such that $f(n) \geq cg(n)$ for all $n \ge n\_0$

And I know if $f(n)=\mathcal{O}(g(n))$ and $f(n)=\Omega(g(n))$, then $f(n)=\Theta(g(n))$. So I first tried to show $T(n)=\mathcal{O}(n^{\log\_3{10}})$. I assumed we know $T(n)\le cn^{\log\_3{10}}$ for some positive constant $c$.

Then we have:

$\begin{align} T(n) = & 10T(\frac{n}{3})+n\sqrt{n}\\ \leq & 10(c(\frac{n}{3})^{\log\_3{10}})+n\sqrt{n}\\ = & 10c(10)^{\log\_3{\frac{n}{3}}}+n\sqrt{n}\\ = & 10c(10)^{(\log\_3{n})-1}+n\sqrt{n}\\ = & c(10)^{\log\_3{n}}+n\sqrt{n}\\ = & cn^{\log\_3{10}}+n\sqrt{n} \end{align}$

At this point I don't know how can I prove that this expression is lower than or equal to $c\_1n^{\log\_3{10}}$. I don't even know that $c\_1$ is equal to the $c$ above necessarily or no? How can I complete this?

And we know this is the "step" part of the induction (if its correct), how can we prove the base cases and find $n\_0$ and $c$.

# Answer
> 1 votes
I'll solve a simpler recurrence, $$T(n) = 4T(n/2) + n,$$ but the point is the same, namely that your *induction hypothesis is too weak*.

We show something stronger: $T(n) \leq c \cdot n^2 - dn$ for some $d$. (!!)

So, by induction, we want to show that $T(n) \leq cn^2 - dn$, and we'll set $d$ at the end.

**Induction hypothesis**. For all $m \< n$, $T(m) \leq cm^2 - dm$.

**Induction step**. $T(n) = 4T(n/2) + n \leq 4(c \frac{n}{2}^2 - d\frac{n}{2}) + n = 4(c\frac{n^2}{4} - d\frac{n}{2}) + n $.

Simplify to get $cn^2 - 2dn + n = cn^2 -dn -dn +n = cn^2 -dn + (1-d)n$.

Now we've got it: $cn^2 -dn + (1-d)n \leq cn^2 -dn$ as long as $d \geq 1$.

Let $d = 1$, and we have that $T(n) \leq cn^2 -dn$, which is what we set out to prove. It follows that $T(n) = O(n^2)$.

---

For your problem, first try to solve the above, then solve $T(n) = 4T(n/2) + n \sqrt n$. For the latter, you will probably need to show that $T(n) \leq cn^2 - dn \sqrt n$, and it should probably work if you just set $d = \sqrt 2 + 1$.

# Answer
> 0 votes
Let $n = 3^m$ and Q(m) = T($3^m$), and rewrite the recursion in terms of m and it’s easy.

---
Tags: time-complexity, algorithm-analysis, recurrence-relation, master-theorem, induction
---


# Question
Title: Why superscalar processors use dynamic branch prediction
I'm studying for an exam on Advanced Computer Architecture and in an exam question the question above is asked.

I know that branch prediction is crucial in superscalar processors in order to exploit ILP as much as possible, but I was wondering what could be the precise reason why superscalar processors use dynamic branch prediction instead of static one.

Update:

Hi again, as the two comments below suggested, I tried to think about it and thought that in case of a misprediction a processor using branch predictor has to flush the pipeline from the incorrect instructions issued because of the prediction.

So, for a superscalar processor issuing multiple instructions at the same time, the penalty would be much higher, but I'm still not sure this is the real point...

Any other help?

# Answer
What you want from a branch predictor: Low implementation cost, prediction speed (you don't want to wait for branch prediction), and high accuracy (high percentage of correctly predicted branches).

So compare static and dynamic branch prediction: Dynamic branch prediction is more expensive, after all it needs to store the history of branches. Dynamic branch history is as fast as static prediction, but its accuracy is enormously higher.

The logical consequence is that when you build a chip that is going to be expensive and high performance anyway, you are not going to scrimp on the cost of branch prediction and use the more accurate method.

And look at Pseudonym's comment: Look at what a static branch predictor does, and see why it will be often less good than dynamic prediction. (Not always. Any dynamic branch prediction can be tricked into *always* predicting wrong).
> 2 votes

# Answer
About the cost of mispredictions: I have a newish superscalar processor, and timing can be “interesting”. It can issue three floating-point instructions per cycle, but they usually have four cycles latency. So you might have a loop with 20 instructions that take 80 cycles to finish using only one 12th of the available capacity. Now you do 1000 iterations and the calculations from 12 iterations can overlap if they are independent. So suddenly you have 240 operations in flight simultaneously, using all the available hardware.

And then you get a branch misprediction. That misprediction might be detected at the very end of an iteration after 80 cycles. With 200 instructions incorrectly executed. That really costs.

And dynamic prediction tends to mispredict rarely, while static misprediction may mispredict most of the time.
> 0 votes

# Answer
Something else happens in compilers that try to do static prediction. On many processors branches taken take longer than branches not taken. Now take a statement “if (x == 0) ++z;”. Typically you will have a conditional branch around the ++z. Now assume the compiler thinks that x is almost never zero. So the branch is always taken. The compiler can put the code for the ++z somewhere else, have a conditional branch that almost never branches to the ++z but 99.9% falls through to the next statement-which is faster. So you can use static prediction in the compiler to rearrange your code to have fewer branches taken.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Find time complexity of $T(n)=3T(n-2)+O(n)$
I try to find the time complexity of following recurrence relation: $$T(n) = 3T(n-2) + O(n)$$ After subtitution,I get: $$T(n)=3^{\frac{n}{2}}T(0)+\sum\_{i=0}^{\frac{n}{2}-1}3^iO(n-2i)$$

I wonder if the ans is $O(3^{\frac{n}{2}})$ or $O(3^{\frac{n}{2}} n)$, can someone give a help to determine the ans and give a proof about it.

# Answer
Recurrence relations do not have time complexities, algorithms do.

That said, assuming $T(1)=O(1)$ and $T(2)=O(1)$, both $T(n)=O(3^{n/2})$ and $T(n)=O(3^{n/2} n)$ are true. Indeed: $$ T(n) = 3T(n-2)+O(n) =3^i T(n-2i) + \sum\_{j=0}^{i-1} 3^j O(n-2j) \quad \text{for }i\<n/2, $$ choosing $i=\lfloor n/2 \rfloor - 1 $: $$ \begin{align} T(n) &= 3^{\lfloor n/2 \rfloor - 1} \cdot O(1) + \sum\_{j=0}^{\lfloor n/2 \rfloor - 2} 3^j O(n-2j) = O\left( \sum\_{j=0}^{\lfloor n/2 \rfloor - 2} 3^j (n-2j) \right) \\ &= O\left(3^{n/2} \sum\_{j=0}^{\infty} \frac{1}{2^i} \right) = O(3^{n/2}). \end{align} $$

Where we used the fact that each term of the summation increases by at least a factor of $2$ compared to the previous one. Indeed: $$ \frac{3^{j+1} (n-2j-2)}{3^j (n-2j)} = 3\left(1-\frac{2}{n-2j}\right) \ge 3\left(1-\frac{2}{n- 2(\lfloor n/2 \rfloor - 3)}\right) \ge 2. $$

The above shows that $T(n) = O(3^{n/2})$, which also implies $T(n)=O(3^{n/2} n)$.
> 0 votes

---
Tags: time-complexity, asymptotics, recurrence-relation
---


# Question
Title: Time complexity and content free evaluation
I am having trouble answering the question below:

"Explain why the statement, “The running time of algorithm A is at least O(n^2)”, is content-free."

The statement apparently does not give any information on the running time of A but if A = T(n), then T(n) \>= O(n^2). Doesn't this at the very least tell us that A runs bigger than n^2?

# Answer
> 1 votes
As suggested by Steven, I turned my comment into a full answer.

I think the question aims to point out that for a constant running time $c$ you have $c \in \mathcal{O}(1) \subseteq \mathcal{O}(n^2)$.

So you might interpret the statement in your exercise as *"There is a running time in $\mathcal{O}(n^2)$ that is a lower bound for $\mathcal{A}$'s running time."*

However, as a constant running time is suitable to select from $\mathcal{O}(n^2)$ this is a completely trivial statement that does not provide any insights about $\mathcal{A}$'s actual running time.

---
Tags: time-complexity
---


# Question
Title: Why is 2's complement used for representing negative numbers?
So I was reading the use complement operation in the digital logic and found, it is used to give additive inverse of the number and subtracting a number (like we do) is difficult for computer. So it adds the negative representation of the number, which is $a - b = a + (-b)$.

Now both complement's used to represent the negative of the number, but why 2's complement is preferred? This is my main question

```
#include <iostream>
#include <bitset>

int main() {
    std::cout << std::bitset<8>(7) << std::endl;     // 00000111
    std::cout << std::bitset<8>(-7) << std::endl;    // 11111001
    return 0;
}

```

Fyi, I know that in 1's complement there can be two zeros $+0$ or $-0$.

# Answer
> 2 votes
As you said, one's complement wastes one configuration of bits. Moreover, it requires additional logic to handle the two representations of zero. It also requires a more complex (hardware) implementation of addition when the operands have different signs (in two's complement the addition implementation is exactly the same as the one for "unsigned" numbers).

# Answer
> 2 votes
The main reason is that there needs to be no special handling to perform arithmetic with negative numbers. The hardware does not need to check the sign bit and inverse the operation (add becomes subtract and subtract becomes add) if the sign bit is set as would be necessary with Sign & Magnitude.

So **why** does Two's Complement have this property? Let us use base 10 as an example. Suppose we have a base 10 number that only has a fixed number of digits. For example 4 digits. We could represent any number between 0 and 9999. But note that if we add any multiple of 10000, there is no effect since the only digits that change are overflowed and therefore ignored. As such, adding 10000-*n* is equivalent to just subtracting *n*. 9999 would effectively be -1. Because for example if we add 1234+9999 we get 11233 but then we forget about the leading 1 because we only have 4 digits so we end up with just 1233 which is in fact 1234-1. Similarly, adding 9998 would be like subtracting 2, and so on.

If we apply the same logic to binary instead of base 10 we can see why the Two's Complement representation works. If we have a 4-bit number and add 0b1111 that is the same as subtracting 1 because this is equivalent to adding 0b10000 then subtracting 1 then discarding the extra leading bit. And by the way 0b1111 is Two's Complement for -1 for 4 bits.

This same logic can be extended to any number of bits or any number that is *'negative'* in Two's Complement.

---
Tags: binary, digital-circuits, bit-manipulation
---


# Question
Title: find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$
> We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and assume $T(1)$ is a constant. Find asymptotically tight bounds $\Theta(f(n))$ for $T(n)$.

There's something that confuses me. We know $\\{n\log{n}, n, \sqrt{n}\\}\subset \mathcal{O}(n\log{n})$. So with Master Theorem applied:

* if $T(n)=2T(\dfrac{n}{2})+n\log{n}$, then $T(n)=\Theta(n\log^2{n})$
* if $T(n)=2T(\dfrac{n}{2})+n$, then $T(n)=\Theta(n\log{n})$
* if $T(n)=2T(\dfrac{n}{2})+\sqrt{n}$, then $T(n)=\Theta(\sqrt{n})$

If its asymptotically tight bounds varies, then how can we provide a asymptotically tight bounds for $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$? If we can, how? Can we prove it using induction?

# Answer
You are right, you can't find a tight bound with those hypotheses.

I think you should interpret the question as:

> find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(f(n))$

In this case, your first relation gives the right answer ($f(n) = n(\log n)^2$).

Also, as noted in the comment, your third relation is wrong, it should be $\Theta(n)$, not $\Theta(\sqrt{n})$.
> 0 votes

---
Tags: time-complexity, algorithm-analysis, asymptotics, recurrence-relation, master-theorem
---


# Question
Title: What is the reason or motivation for having 128-bit pointers?
I read here that the reason that `intptr_t` and `uintptr_t` are optional in C is because there might be a platform where pointers are much bigger than any built-in integer type. They specifically cite some platforms with 128-bit pointers.

However a 128-bit pointer seems a pointless (no pun intended) waste as a 64-bit pointer already has enough possible values to accommodate 18 quintillion bytes (18 exabytes) of RAM. No computer will realistically have even close to that.

So my question is what is the motivation for having any pointers larger than 64-bits? What can 128-bit pointers do that 64-bit pointers cannot do on any realistic computer?

# Answer
Pointers don't have to be just memory addresses. Pointers with extra information are known as "fat pointers" and have various uses.

A bounds-checked C implementation may use pointers that contain the start and end addresses of the array into which they point. Judging by this comment, the 128-bit pointers on the Elbrus architecture are of that type: they use a 64-bit array start address and a 32-bit size and current position (which limits arrays to 4 GiB).

According to this comment, AS/400 uses fat pointers for capability-based security. The capability attached to a pointer is similar to a segment in x86 protected mode (a feature that was dropped in x64).
> 4 votes

---
Tags: virtual-memory
---


# Question
Title: How does the program counter "know" when the fetch cycle is complete?
So my understanding of updating the PC is as follows:

1. Put memory address indicated by PC into memory address register
2. Load the contents of the address pointed to by memory address register into memory data register
3. Place this instruction in the current instruction register.
4. Update PC
5. Decode instruction by passing it to the control unit and letting it handle it. Execute after that

That makes sense

What I don't get is, how does the PC know when the fetch phase is done? How does it know WHEN it needs to update?

Is there an update flag attached to the current instruction register? If there is, how does it work?

What mechanism tells the program counter when to update?

# Answer
> 1 votes
A very simple and straightforward mechanism is to have the PC update automatically in a combinatory fashion, as soon as the cycle of the instructrion start: we design the system to pass the content of the PC to the memory address register and simultaneously to an adder, the output of wich is forward in input to the PC register. When the next cycle start, the PC contains the right address. Obviusly this mechanism does not allow for more flexible operations on the instruction flow, like jumps or branches.

(In the image the PC is increased by 4 bytes, assuming 32 bit instructions)

It has to be noticed that this kind of setup could work for single-cycle style processor, but needs to be adjusted for multy-cycle designs, and obviously does not take into account many variables that require real CPUs to perform potentially much more articulated update logics.

---
Tags: cpu
---


title: Process Control Block

text:
# Question
Title: Process Control Block
As we know, the operating system maintains a data structure for every process called process control block. My question is where this data structure is stored inside the OS ?

# Answer
> 1 votes
You can not store something inside the OS. The OS is a program, or better a set of programs designed to manage a machine.
Same as any other program, the data used during execution are stored inside the RAM, at least during their use. The OS interacts in a special way with a computer memory, having at his disposale a protected area inside wich sensible (from the OS point of view) data can be stored. The PCBs are stored inside this special area.

---
Tags: operating-systems
---


# Question
Title: Maximum Weighted coverage approximation algorithm?
I am looking for an algorithm similar to the unweighted maximum coverage. However, I have been unable to find a similar algorithm for the weighted version.

How should I modify the algorithm above to take into account the weighted version whereby each element is weighted and would the approximation ratio of $(1 - 1/e)$ still hold for the weighted version ?

# Answer
> 1 votes
If you check more closely, the Wikipedia link points to the paper: An analysis of approximations for maximizing submodular set functions.

The paper proves that $(1-1/e)$ approximation holds in general for any objective function $f$ that is monotone and submodular. You can also find a formal statement in Exercise 2.10 of the Book "The Design of Approximation Algorithms".

It is easy to see that the objective function of the weighted maximum coverage problem is monotone and submodular. Let $E$ be the given set of element. Each element $e\_i \in E$ has weight $w\_i$. Let $S = \\{S\_1,\dotsc,S\_m\\}$ be the collection of subsets of $E$, i.e., $S\_j \subseteq E$ for each $j \in \\{1,\dotsc,m\\}$.

Let $A \subseteq S$ be any subcollection of subsets of $E$. Let $f(A)$ denote the value of subcollection $A$: the sum of the weights of all the elements covered by sets in $A$. That is, $f(A) = \sum\_{e\_i \in \bigcup \\{S\_j \in A\\} } w\_i$.

1. $f$ is monotone since for any subcollections $A \subseteq B \subseteq S$, $f(A) \leq f(B)$.
2. $f$ is submodular since for any subcollections $A,B \subseteq S$, $f(A) + f(B) \geq f(A \cup B) + f(A \cap B)$.

The proof of both the above statements is easy; leaving those steps to you. Thus, the standard greedy algorithm gives $(1-1/e)$-approximation for the weighted maximum coverage problem. You may find reading Section 2.5 of the Book "The Design of Approximation Algorithms" helpful.

---
Tags: complexity-theory, np-complete, combinatorics, set-cover
---