# Question
Title: Asymptotic analysis for machine learning algorithms
I wanted to know if it would practical and useful to analyse machine learning algorithms in terms of asymptotic computational complexity.

I have noticed this is very uncommon. However, I believe it would help us compare these algorithms and decide which one to use for a given scenario.

I am also aware that the running time of most machine learning algorithms is highly dependent on the data. For example, gradient descent algorithm can iterate significantly more times on certain data sets than others.

Considering this, what would be a nice complexity measure for comparing machine learning algorithms?

# Answer
Usually, when considering machine learning algorithms from a theoretical perspective, we are interested in PAC learnability, or some other learnability definition (most of those are very similar to PAC, since everything in the machine learning region is stochastic).

Under those definitions, there are a few possible "metrics" that measure something similar to complexity. However, there is no "standard metric", as to different algorithms for different problems can behave totally differently in structure.

An example of that would be the sample complexity when considering supervised learning tasks: How many input samples do we need in order to guarantee an error of up to $\epsilon$ with probability $1-\delta$ (as a function of $\epsilon$ and $\delta$)?

Or, in the reinforcement learning world, a "metric" could be considered the convergence rate of an algorithm to the wanted output: How much does the error "shrink" each iteration of the algorithm?

That being said, there is no standard way to compare the algorithms *theoretically*, but *practically* you can run each of them and see who is performing better and faster.
> 1 votes

# Answer
Well, first let's clarify the following. Asymptotic Complexity and real life situations are different. Please take a look at this Question.

Now, machine learning is a very hard topic to explore precisely the asymptotic complexity of your algorithms. If we think machine learning as linear algebra, then the asymptotic complexity is the complexity of multiplying matrices. In the area of machine learning, the most important thing is not so much the complexity, but the efficient use of GPUs and TPUs. Let's say you need to train a model for Natural Language Understanding and you use LSTM, GRU and CNN (CNN ?!). Each algorithm has its own complexity because each one does easier or harder calculations. Unfortunately there is no metric such as Model's Accuracy / # of computations. But we all can agree that two LSTM can vastly vary on their speed depending on how good use of GPUs and TPUs they make.
> 0 votes

---
Tags: asymptotics, machine-learning
---


# Question
Title: All words containing at least twice as many zeroes as ones
Consider the language $$ \\{ w \in \\{0,1\\}^\* : \\#\_0(w) \ge \\#\_1(w) \\} $$ consisting of all words over $\\{0,1\\}$ in which the number of zeroes is at least twice the number of ones.

Is this regular, context-free, Turing decidable?

**My Idea**

It's not regular, because we need to track the number of zeros and so it cannot be done with a finite number of states. I am not sure if this argument is a formal one.

**Turing Decidable - Yes**

Take a machine which reads 1 from the end, writes an X there and then traverses the tape and X's two 0's.

If after all ones are gone the tape is empty of there are still zeroes left then it's accepted. Otherwise, if there are ones left on tape after this operation, it's rejected.

***Context-Free***

I am unable to find any context free grammar for it. Neither can I prove that it's not context-free.

# Answer
> 1 votes
The language is context-free. As you read the string, you'll need a counter comparing two values: $\\#\_0 \cdot 2$ and $\\#\_1$. Such counter can be implemented using the stack of the PDA.

When a $0$ is read:

* if there is a $1$ on top of the stack, pop it. If the stack is now empty, add a $0$, otherwise pop again.
* else add $0$ to the stack twice

When a $1$ is read:

* if there's a $0$ on top of the stack, pop it.
* else add $1$ to the stack

It is easy to see\* that the stack contains now the difference between $\\#\_0 \cdot 2$ and $\\#\_1$, encoded as the number of symbols on stack and the symbol used. After the entire string has been scanned, the top symbol of the stack tells which of the numbers is greater: if the top symbol is $0$ or the empty stack symbol, accept. Otherwise reject.

\*If you need a more formal proof of this construction's correctness, it is fairly easy proven by induction: first establish that the symbols of the stack represent the correct counts after reading the first symbol, then perform an induction step with the assumption that the first $n$ symbols resulted a correct count on the stack and showing that the $n+1$th symbol read doesn't violate this correctness.

# Answer
> 0 votes
Let $L$ be your language

$L$ is context free since the following CFG generate all possible strings in $L$

```
S -> 1KK | KK1 | K1K | K | Ɛ
K -> S0S

```

$L$ is decidable since $L$ is context free and all context languages are also decidable

$L$ isn't regular since it doesn't respect the Pumping Lemma:

For a lenght $k$ we can chose the word $w = 0^{2k} 1^k \in L$

Then if we divide $w$ in $xyz$ where:

$|y| \> 0$

$|xy| \< k$

$y$ must be only made of zeroes, it we chose the exponent $i=0$ we get $xy^0z$ that isn't in $L$, thus $L$ isn't regular.

---
Tags: turing-machines, regular-languages, context-free
---


title: Prove undecidable and recognizable

text:
# Question
Title: Prove undecidable and recognizable
Is there a way that I can use If $L=\big\\{\langle M\_1,M\_2\rangle\mid M\_1, M\_2\text{ are TM and } L(M\_1)\cup L(M\_1)=\Sigma^\* \big\\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$? to prove that $L=\big\\{\langle M\_1,M\_2\rangle\mid M\_1, M\_2\text{ are TM and } L(M\_1)\cup L(M\_2)\neq\emptyset \big\\}$ is undecidable and recognizable?

# Answer
> 1 votes
To prove that the language is recognizable simply enumerate all words $w\_1, w\_2, \dots,$ and execute $L\_1$ and $L\_2$ on $w$ in dovetail fashion (perform one step of $M\_1$ and $M\_2$ on $w\_1$; perform one step of $M\_1$ and $M\_2$ on $w\_2$ and one additional step on $w\_1$; perform one step of $M\_1$ and $M\_2$ on $w\_3$, one more step on $w\_2$, and one more step on $w\_1$; etc). Halt and accept whenever $M\_1$ or $M\_2$ accepts.

To prove that the language is not decidable pick $M\_2$ as the Turing machine that always rejects and notice that $\langle M\_1, M\_2 \rangle \in L$ if and only if $L(M\_1) \neq \emptyset$. The problem of determining whether a Turing machine accepts at least one word is undecidable (as it can be seen from a simple reduction from the halting problem).

---
Tags: turing-machines, undecidability
---


# Question
Title: Asymptotics of recurrence $f(x) = 8f(x/2) + O(1)$
What is the asymptotic rate of growth of the following recurrence relation?

$$ f(x) = \begin{cases} 8f(x/2) + Θ(1) & \text{ if } x^2 \> M, \\ M & \text{ if } x^2 \leq M. \end{cases} $$ Here $M$ is a constant.

I'm not sure how to do it with the condition on $x^2$.

# Answer
> 3 votes
The case $x^2 \le M$ has no effect on the asymptotic growth rate of $f$ since it is essentially telling you that $f(x) = \Theta(1)$ whenever $x$ is (at most) a constant.

Then you can use standard methods (e.g., the Master theorem) to show that $f(x) = \Theta(x^3)$.

Perhaps the following transformation will make this more evident. Define $g(x) = \frac{f(\sqrt{M}x)}{M}$, then: $$ \begin{align\*} g(x) &= \frac{f(\sqrt{M}x)}{M} = \begin{cases} \frac{8}{M} f(\sqrt{M}x/2) + \Theta(1) & \mbox{if }Mx^2 \> M \\ 1 & \mbox{if } Mx^2 \le M \end{cases} \\ &= \begin{cases} 8g(x/2) + \Theta(1) & \mbox{if }x \> 1 \\ 1 & \mbox{if } x \le 1 \end{cases}. \end{align\*} $$

Since $g(x) = \Theta(x^3)$, you have $f(x) = Mg(\frac{x}{\sqrt{M}}) = \Theta(M \frac{x^3}{M^{3/2}} ) = \Theta(x^3)$.

# Answer
> 1 votes
First, simplify $f(x)$ conditions: $$f(x) = \begin{cases} 8f(x/2) + Θ(1) & \text{ if } x \> \sqrt{M}, \\ M & \text{ if } x\leq \sqrt{M}. \end{cases}$$ Now, if you draw recursion tree $\mathbb{T}$ of $f(x)$, each internal node has $8$ children, on other hand, the height of $\mathbb{T}$
$$\log\_2 x-\log\_2 \sqrt{M}=\log\_2 \left(\frac{x}{\sqrt{M}}\right)$$, because in each step input $x$ divide by $2$, until $$\frac{x}{2^k}\geq \sqrt{M} \rightarrow k\leq\log\_2\left(\frac{x}{\sqrt{M}}\right).$$

From full trees we know that, Since the number of leaves in a full tree is $\\#\text{(number of leaves)}^k$ then we get the following series ( note that leaves of $\mathbb{T}$ has value $M$) $$\sum\_{i=0}^{k-1}8^i+M 8^k=\mathcal{O}\left(8^k+M\times \left(\frac{x}{\sqrt{M}}\right)^3\right)=\mathcal{O}\left(M\times \left(\frac{x}{\sqrt{M}}\right)^3\right).$$

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


# Question
Title: How to prove Dense Subgraph problem is in NP
I have been studying NP-Complete problems and I saw the Dense Subgraph problem. Then I saw that they are trying to show that the problem is NP (see below quote), but I can't understand how it verifies that time is polynomial.

> Problem: Dense Subgraph
>
> Input: A graph $G$, and integers $k$ and $y$.
>
> Output: Does $G$ contain a subgraph with exactly $k$ vertices and at least $y$ edges?
>
> To prove Dense Subgraph is NP-complete, we show that Dense Subgraph is in NP and is NP-hard by reducing CLIQUE problem to Dense Subgraph.
>
> Dense Subgraph is NP: the polynomial time verifier will take $(G,k,y)$ and $H = (V', E')$ as certificate and check if $H$ is a subgraph of $G$, $|V'| = k$, $|E'| \geq y$.

# Answer
> 1 votes
You are right that that doesn't prove the algorithm is polynomial, as it just gives the certificate. But it is very easy to see that (for example with a program in a C-like language, given a reasonable representation of the graphs) the check is very easy to do (is polynomial).

The part of coming up with a polynomial verifier given a reasonable certificate (i.e., proof that the problem is in $\mathsf{NP}$) is usually easy, and left as an exercise for the gentle reader.

---
Tags: np-complete, np
---


# Question
Title: Is this solution for the Turing's "halting" problem correct?
I think that Alan Turing's solution for the "halting" problem might be wrong.

Turing's main premise is wrong, he assumed the only way to check whether a program halts is to run it. He didn't consider that it's possible to determine whether any given program will ever halt by parsing and analyzing its code without running it.

I wrote a simple program in Javascript to demonstrate that:

You can run it in the browser's console

```
/**
* @param {any} program // either a parsed evaluated tree or a simple statement
* @returns {boolean}
*/
function checkProgramHalts (program) {
  // If the input is a simple statement (e.g. number 5, string '5', boolean true),
  // rather than a parsed evaluated program tree, return true, since
  // simple statements always halt
  if (['number', 'string', 'boolean'].includes(typeof program)) {
    return true
  }

  // For simplicity, using a simple code analyzer,
  // that can only check simple single type programs:
  // - declare var condition in line 1
  // - run while loop in line 2
  // - change condition var value in line 3
  var programEnteredInfiniteLoop = false
  program.statements.forEach(statement => {
    if (statement.operator === 'while') {
      if (eval(statement.nestedCode.varChange.varValue) === true) {
        programEnteredInfiniteLoop = true
      }
    }
  })
  return programEnteredInfiniteLoop ? false : true
}

// Program with an infinite loop
var parsedEvaluatedProgramTree1 = {
  statements: [
    {
      operator: 'var',
      varName: 'condition',
      varValue: 'true'
    },
    {
      operator: 'while',
      condition: '(condition)',
      nestedCode: {
        varChange: {
          varName: 'condition',
          varValue: 'true'
        }
      }
    }
  ]
}

// Program without infinite loops
var parsedEvaluatedProgramTree2 = {
  statements: [
    {
      operator: 'var',
      varName: 'condition',
      varValue: 'true'
    },
    {
      operator: 'while',
      condition: '(condition)',
      nestedCode: {
        varChange: {
          varName: 'condition',
          varValue: 'false'
        }
      }
    }
  ]
}

// - test1: true: simple statement 'string' will halt
// - test2: false: program with infinite loop will never halt
// - test3: true: program without infinite loops will halt
// - test4: true: simple statement 'boolean' will halt
var test1 = checkProgramHalts('5')
var test2 = checkProgramHalts(parsedEvaluatedProgramTree1)
var test3 = checkProgramHalts(parsedEvaluatedProgramTree2)
var test4 = checkProgramHalts(checkProgramHalts(parsedEvaluatedProgramTree1))
console.log(test1)
console.log(test2)
console.log(test3)
console.log(test4)

```

In a real world program, we would use an advanced compiler that evaluates all used expressions and tracks all variable changes to guarantee that the state of all statements is known and all runtime errors are considered.

# Answer
> 3 votes
Please feed this program (pseudo-code) into yours.

```
for every integer n > 3:
  has_solution := false
  for every prime p < 2*n:
    if (2*n - p) is a prime:
      has_solution := true
      break from inner loop
  if not has_solution:
    halt

```

Congratulations! You have solved the Goldbach's conjecture!

A step-by-step analysis of your program when it is fed with my program should reveal the problem.

---

To make it clear, it seems that you solved a *subset* of the halting problem, and assumed that it can theoretically be extended to the general case. It cannot. In my program, the `has_solution` variable changes very unpredictably, and it is very hard for you to write a program that analyzes this change.

Indeed, Turing's proof constructed a program specifically aimed against a putative "solution" of the halting problem, in a similar spirit. So that any "solution" will have a weak point where it cannot accurately get the result.

# Answer
> 2 votes
The halting problem asks whether a particular Turing Machine will halt *if given a particular input*. If you don't consider the input, you can't claim to solve the halting problem; a given program might halt for some inputs and not for others.

You can substitute the input with a static initialisation without altering the sense of this objection. It's not sufficient to just detect the presence of an infinite loop. That says nothing, because for particular inputs, possibly even all inputs, the loop may never even happen.

Consider the following program (which assumes the existence of an arbitrary-precision integer arithmetic library) for deciding whether there is some $n\>7$ such that $n!+1$ is a perfect square (the so-called problem of Brocard). (Here, I've hard-coded the minimum value rather than taking it as an input.)

```
let n_factorial = 40320
let n = 8
while (!is_perfect_square(n_factorial + 1)) {
    n += 1
    n_factorial *= n
}

```

Can your program prove that it never halts? How?

---
Tags: algorithms, turing-machines, computability, decision-problem, halting-problem
---


# Question
Title: Is halting problem for /// solvable assuming programs that maches the regex "^/[ab]*/[ab]*/[ab]*$"?
/// is an esoteric language, and I thought of posting a code-golf problem related to it.

A /// program of the form `/p/q/r` where p, q, and r are strings that do not contain `/` or `\` does:

1. If the string p is a substring of r, go to step 2; otherwise step 5.
2. Replace the leftmost occurrence of p in r with q.
3. Let the result of step 2 be the new r.
4. Go to step 1.
5. Output r and halt.

In step 1, an empty string shall be a substring of any strings.

For simplicity I am thinking each of p, q, r consisting of zero or more `a`'s and `b`'s.

At first I thought the following algorithm would work:

1. Returns no if p is both a substring of q and r; otherwise yes.

But that was wrong; `/ab/bbaa/abb` can be one of the exceptions, as "ab" does not appear in "bbaa" but in "abb".

I am suspecting it's possibly impossible to make an algorithm to solve this problem. Is it solvable?

# Answer
According to this Math Overflow answer, the answer is not known as of 2014.

It seems your problem can be restated to asking if the termination of one-rule string-rewriting systems is decidable. A rule of a string-rewriting system is a substitution like the one you gave with $ab\to bbaa$.

Even though the Math Overflow answer doesn't distinguish between alphabet size, which in your case is only 2 consisting only of $\\{a,b\\}$, you can convert a SRS with a larger alphabet into one with only 2 letters, thus making their termination problems equivalent. Basically, give each letter a unique index $n$, then replace it with $ab^na$ in both the input string as well as the rules. So for example $cad→addc$ can be encoded as $abbbaabaabbbba→abaabbbbaabbbbaabbba$.
> 4 votes

---
Tags: halting-problem
---


# Question
Title: Convergence of graph neural networks (GNNs)
I'm new to the area, and we don't have a course on graph neural networks at our university. However, I will still like to know the main theoretical results when considering convergence of graph neural networks. Where can I learn more about the topic? Thanks.

# Answer
More generally, this area is known as *geometric deep learning*, i.e., it encompasses learning not only on graph but on other non-Euclidean domains. A good broad start is the survey of Bronstein et al. \[1\], after which I can recommend basically any material by Bronstein like his many excellent presentations (also available on Youtube - just do a search).

For graph neural nets, you might start with Kipf & Welling (the survey \[1\] will give references). Perhaps loosely building on their work, there is also GraphSAGE \[2\] and later developments like graph attention networks. I've not actively followed on the literature for the past 2-3 years, so I don't know what's hot currently or how badly outdated these methods might be, but these works definitely will give you the foundation.

---

\[1\] Bronstein, Michael M., Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. "Geometric deep learning: going beyond Euclidean data." IEEE Signal Processing Magazine 34, no. 4 (2017): 18-42.

\[2\] Hamilton, William L., Rex Ying, and Jure Leskovec. "Inductive representation learning on large graphs." In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035. 2017.
> 2 votes

---
Tags: graphs, reference-request, neural-networks
---


# Question
Title: Confused about definition of a non-deterministic decider
Fallowing are some definitions from book "introduction to theory of computation" by **sipser**.

> a nondeterministic turing machine is a **decider** if all its computation branches halt on all input.

> $NTIME(t(n)) = \\{L | L \text{ is a language decided by an $O(t(n))$ time nondeterministic turing machine } \\}$

What is the difference between **deciding** in deterministic and nondeterministic cases? why in deterministic case having a decider for language $A$ imply a decider for $\bar{A}$ but not in non-deterministic case?is it because there might be infinite number of branches ?

# Answer
> 2 votes
You basically have the right intuition. Let's expand the definitions one more step, to see it more clearly.

**detrminstic decider**: if $x\in L$, the decider will stop on YES (there is only a single branch for $x$)

**non-detrminstic decider**: if $x\in L$, there *exists* a branch on which the decider will stop on YES (there are multiple possible branches for $x$ chosen non-deterministically during the computation; some of which might be NO or non-halting).

You can state equivalent statements for any $x \not\in L$.

As you can see, there is a lot of difference between the two. It is also should be apparent why if first statement holds, the second holds as well, but not the other way.

# Answer
> 1 votes
Given a Turing machine, and an input $x$ written on tape:

*language decision* means that the Turing machine halts in one of its *accepting* states if $x \in L$, otherwise it halts in a *rejecting* state.

*language acceptance* means that the Turing machine halts in one of its *accepting* states if $x \in L$; it may loop forever otherwise.

For a deterministic Turing machine, given the current *configuration*, there is a *unique* next configuration. If $x \in L$, the deterministic Turing machine starts in one of its starting states, say $q\_{start}$ with the input $x = x\_1 x\_2 \cdots x\_n$ written on tape and follows a unique sequence of steps dictated by its deterministic transition function. This sequence of steps leads to one of the accepting states, say $q\_{accept}$. Simmetrically, if $x \notin L$, the unique sequence of steps leads to one of the rejecting states, say $q\_{reject}$.

In the case of a nondeterministic Turing machine, given the current configuration, there are *several* possible next configurations (owing to its nondeterministic transition relation: given a state and a symbol scanned, there are several choices of what to do next). This leads to an asymmetric accept/reject criterion (with regard to the deterministic case): the computation is not a chain of states (as in the deterministic case), rather it is a tree of possible computations with each path leading either to an accept or reject state. To accept a string $x$ ($x \in L$), the nondeterministic Turing machine needs to find *any* path along the tree leading to an accept state (one path is enough). However, in order to reject the string ($x \notin L$), it must reject an *all* of the paths. Regarding the computation, all paths terminate, the time used can be though of as the maximum length of paths starting from the root of the tree and the space used is the maximum number of work tape cells touched on any path starting from the root of the tree.

Note that a deterministic Turing machine is just a special case of a nondeterministic one.

Finally, in the deterministic case if one can decide a language $A$, then it can also decide its complement $\bar A$. This is exactly because of the symmetry available in the deterministic case and the asymmetry of the nondeterministic one. How to decide $\bar A$ ? Let TM be a deterministic Turing machine able to decide $A$. Then, the following deterministic Turing machine TM' decides $\bar A$: run TM on input $x$; if TM accepts, then TM' rejects and vice-versa.

---
Tags: turing-machines, nondeterminism
---


# Question
Title: Difference between function, method, routine, procedure, subprogram, subroutine, block, task
I don't know if I should have posted this on StackOverflow or here but what's the difference between these terms? Are the definitions of these dependent on the programming languages or they're things independent of them?

# Answer
Precise definitions are dependent on programming languages; if you are interested in a particular programming language, refer to the documentation of that language rather than to this answer.

## Function, pure function, and procedure

A function is usually expected to return an output; a procedure, on the other hand, is expected to perform an operation with side-effects. For instance, a `print` function which displays its argument to screen is a procedure; a `multiply_by_two` function which returns the double of its argument is a function.

Following this distinction, a function usually has only read access to its parameters, whereas a procedure might have write access to its parameters. For instance, a function `sort` might take a list, and return a new sorted list; whereas a procedure `sort` might take a list, and modify that list in-place without returning a new list.

Note that the distinction between function and procedure is not necessarily clear-cut; a function might return a result *and* have side-effects. A function which doesn't have any side-effects is usually called a **pure function**. Functional programming languages like OCaml and Haskell make a huge deal of the distinction between functions and pure functions.

Most programming languages today use the word "function" indifferently and don't use the word "procedure" at all.

## Function and method

In object-oriented programming, a method is a function defined inside a class; every object which is an instance of the class will have the method. Usually the method is called using the name of the object, followed by a dot `.`, followed by the name of the method. For instance, in python, the class List has a method `sort` so that if `lst` is an object of class List, you can write `lst.sort()` to sort `lst`.

The object is not passed as an explicit "argument" of the method, but the method implicitly has access to the object as if it were an argument. Languages often use a reserved keyword to designate this implicit argument in the code of the method; in C++ and Java, the keyword is `this`. In python, there is no reserved keyword, although `self` is almost always used. If you are programming in a non-object oriented language and want to simulate object-oriented behaviour, you can emulate methods by writing functions whose first argument is meant to be "the object".

### Class method and instance method

Sometimes people define methods that don't actually need access to an object. Those are not as common; if they don't need access to an object, why define them as method rather than function? but they do exist. Depending on the language, those methods might be referred to as "static methods" or "class methods". Instead of calling them as `<name of the object>.<name of the method>`, you can call them as `<name of the class>.<name of the method>`. For instance, in the python library "pandas", the class `DataFrame` has a class method `from_csv` which can be used to create a new dataframe by reading a csv file. This class method is called as `DataFrame.from_csv(filename)`, which you can contrast with the method `sort` from class `list` which is **not** called as `list.sort()`, but rather as `x.sort()` where `x` is a particular list.

## Routine and subroutine

Those words have mostly disappeared in modern languages. They were used in older programming languages. See also this related question:

## Subprogram

A subprogram is a part of a program that could be consider a program on its own. I don't think I've ever encountered a formal use of this word, so I won't attempt to give a formal definition.

## Block

In flow-oriented "graphical programming" tools, subprograms are often called blocks. The reason is that they are represented by a little box on the screen, with incoming arrows for the input, and outgoing arrows for the output. Representation of a program using block is very useful in fields where non-programmers need to assemble a pipeline using existing subprograms. For instance, biologists who need to do image analysis, and use subprograms such as "denoise the image", "distinguish between tissue and background", "count number of cells in image", "measure area of tissue in image", etc. Now all they need to do is choose the blocks they want and plug the blocks together, without writing any code at all.

## Task

The word "task" is mostly used in the context of scheduling, where it refers to an element with an identifier, a length of time, and some requirements such as a deadline or the use of a particular resource. In computing, scheduling happens all the time; for instance, the operating system of your computer must schedule a lot of tasks so that they complete smoothly. The precise meaning of "task" in the context of computing is not particularly precise, but is closer to words like "thread" or "process" than "function" or "procedure".
> 3 votes

---
Tags: functional-programming
---


title: How are lexical tokens produced

text:
# Question
Title: How are lexical tokens produced
I am studying Compiler Design. The instructor told us that when a program is given to lexical analyzer it find all tokens then a symbol table is created and it is updated at every phase accordingly, but I read this online notes and here is the statement

> *The lexical analyzer produces a single tokens each time it is called by the parser.*

I can't understand this statement. How does all this stuff happens? For a program with thousands line of code there may be thousands of tokens and for every token if the parser calls the lexical analyzer this may be very much time consuming? How does parser decide that all tokens are produced and it don't need to call lexical analyzer now?

I am asking this for general compiler not a language specific.

# Answer
Yes, normally a parser calls the lexical analyser every time it needs a token, and this results in many, many, many calls to the lexical analyser. It is well known by compiler writers that the lexical analysis can consume the larger proportion of the compilers execution time.

However, the lexical analysis process would normally use a Chomsky type 3 grammar, or a regular language, and thus can be implemented by a finite state automaton, which can be coded quite efficiently. The parser, by contrast, will normally be based on some form of Chomsky type 2 (context free) grammar and the algorithm would be less efficient as it may involve back-tracking or rule matching. Thus devolving some work from the less efficient parser to the more efficient lexical analyser makes the whole compiler more efficient.

It is possible also to implement the relationship between the lexical analyser and the parser in a different way. The lexical analyser could process the whole input source program from a file (of text) into a complete set of tokens, which could themselves be stored in a file. Then the parser could input that file of tokens. This would be slower because it involves the writing and reading of a file. The list of tokens could alternately be stored in memory, but now the compiler has a larger memory requirement. Historically, in early computers, with smaller memories and slower processors it was done in a similar way and perhaps the input (tape) of the source program resulted in an output (tape) of token which becomes the input (tape) of the parser program!

On a modern system this could be implemented in a pipe, for example:

```
lexer sourcefile.lng | parser | optimiser | codegen > program.exe

```

Internally, some compilers could implement it this way, but normally a parser (function) within the compiler calls a lexer (function) as described.
> 4 votes

---
Tags: compilers, parsers, lexical-analysis
---


title: Number of queries for $NP^{NP}$

text:
# Question
Title: Number of queries for $NP^{NP}$
So a few days ago my lecturer told us that for every nondeterministic polynomial time oracle machine $M$, there is a nondeterministic polynomial time oracle machine $N$ that gives us $L(N^{3-SAT}) = L(M^{3-SAT})$ and $N$ makes a single query to its oracle. He didn't give us a clear explanation for why this is true.

My explanation for that would be that if machine $M$ has $k$ queries for the $3-SAT$ oracle named $q1,q2...qk$ then for every query $qi$ out these queries we either ask if $qi \in 3-SAT$ or $qi \notin 3-SAT$. The single query for machine $N$ would be defined like this $Q' =$ ($Q1$ AND $Q2$ AND $...$ $Qk$) and we define:

$Qi = qi$ if we are asking $qi \in 3-SAT$ in machine M.

$Qi = NOT(qi)$ if we are asking $qi \notin 3-SAT$ in machine M.

We give the query $Q'$ to the $3-SAT$ oracle of machine $N$ and if it is true then we get $L(N^{3-SAT}) = L(M^{3-SAT})$.

Are there any problems in my explanation ? Is there a better explanation ?

# Answer
> 3 votes
Your idea is in a good direction. To complete this proof, you will need to note a few things, and explain why they are not problems (or how to fix them):

1. The new machine will only do one oracle call at the end. That means, that at any time that our original TM did an oracle call, it wont get an answer!
2. We need to "save up" and "remember" which oracle calls we want to do, until we finish the execution. Why won't this take us too much time or space?

And here is how to fix them:

1. Ask from the prover to give you a boolean number $b\_i\in\\{0,1\\}$ representing the "output" of the $i$'th query. In this sense, the prover replaces the oracle, and you ask it instead of the oracle. Then, at the end we will need to verify this against the original oracle (think how to do this!)
2. The machine will execute at most a polynomial number of steps. Lets denote that by $P\_1(x)$. Now, this means that the number of oracle calls (and the size of each oracle call) won't exceed $P\_1(x)$. But, to manage and store the oracle calls we might need $P\_2(y)$ time for $y$ being the number of oracle calls. Therefore, we will need at most $P\_2(P\_1(n))$ time overall to manage the oracles, when $n$ is the size of the input. This is only a polynomial factor, and since we are dealing with $NP$, then this is OK!

---

Additional explanation on how to verify that the $b\_i$'s are correct from the first part:

Define $B\_{true}=\\{i\mid b\_i=1\\}$ and similarly $B\_{false}=\\{j\mid b\_j=0\\}$. Now, define $Q'\_{true}=\bigwedge\limits\_{i\in B\_{true}}{Q\_i}$ while changing the variable names in the $Q\_i$'s to be disjoint (this is important!).

Now, we want to define $Q'\_{false}$ in a similar way that will capture all $B\_{false}$ indices. To do that, we need to take a small walk to the realm of the general SAT problem. For starters, we will assume without loss of generality that the indices of $B\_{false}$ are $1,\dots ,k$. Now, let us define auxiliary variables $a\_i$ for all $1\le i\le k$. We will use those auxiliary variables to "select" which $Q\_i$'s we want to show that has \ doesn't have a satisfying assignment. To do that, let us define $Q'\_i:=\lnot a\_i \lor Q\_i$, that will be built by adding $\lor \lnot a\_i$ to each clause in $Q\_i$. Notice that if some $a\_i$ is $true$, then we need a satisfying assignment of $Q\_i$ to satisfy $Q'\_i$. But if $a\_i$ is $false$, then $Q'\_i$ is immediately satisfied. We will need to make sure at least one of the $a\_i$'s is $true$, in order to ensure that at least one of the $Q\_i$'s will have to be satisfiable. To do that, consider the clause $(\lnot a\_1 \lor \lnot a\_2 \lor \dots \lor \lnot a\_k)$. Now, we are ready to finally define $Q'\_{false}$! We will define it as: $Q'\_{false}:=(\lnot a\_1 \lor \lnot a\_2 \lor \dots \lor \lnot a\_k)\land \left(\bigwedge\limits\_{i=1}^k Q'\_i\right)$.

Convert this $Q'\_{false}$ to $3-CNF$ form using the $SAT\le\_p 3-SAT$ reduction, and then ask this as the only single query you need to do. You are guaranteed to get back $0$ if all $Q\_j$'s for $j\in B\_{false}$ were not satisfiable, since if one of them *would* have been satisfiable, then we could satisfy $Q'\_{false}$ by choosing the auxiliary variable to "select" that satisfiable $Q\_j$, and satisfy $Q\_j$. Then, all other $Q\_{j'}$ were not "selected" and hence automatically we have that $Q'\_{j'}$ are satisfied, leaving us with that $Q'\_{false}$ is itself satisfied.

---
Tags: complexity-theory, np-complete, satisfiability, nondeterminism, oracle-machines
---


# Question
Title: Complementary language of $L\notin RE,coRE$
I mean if $L'$ defined as $L'=\overline{L}$, when $L\notin RE,coRE$.

From the logic point of view it should be $L'\in RE \cup coRE$, isn't?

But it's not make sense for me, where am I wrong?

# Answer
What you are complementing is the language, not $RE$ or $co-RE$.

$RE$ and $co-RE$ are ***families*** of languages. Complementing a language is *not the same* as complementing the *family* its in.

For instance, if we have a family of sets: $\mathcal{F}:=\\{\\{1,2\\},\\{3,4,5\\},\\{1,5\\}\\}$, when the "world" we live in only has $5$ elements: $W:=\\{1,2,3,4,5\\}$, then taking the complement of $\\{1,2\\}\in \mathcal{F}$ yields $\\{1,2\\}'=W\setminus\\{1,2\\}=\\{3,4,5\\}\in \mathcal{F}$. But also, taking the complement of $\\{1,5\\}\in \mathcal{F}$ will yield $\\{2,3,4\\}\notin \mathcal{F}$.

As you can see, complementing a language won't guarantee you anything when talking about the same family of languages. But in the particular case of $RE$ and $co-RE$, by the definition of $co-RE$, we have that if $L\in RE$ then $L'\in co-RE$ and if $L\in co-RE$ then $L'\in RE$. Notice, that $co-RE$ is **not** the complement of $RE$! It is the family of complements of languages, and as we said it is not correlated to the complement of $RE$ directly.
> 1 votes

---
Tags: turing-machines, computability, regular-languages
---


# Question
Title: Prove that the following algorithm is $\Theta(n^3)$ by induction
I have the following algorithm runtime: $T(1) = b $ for some positive constant. Otherwise, $T(n)=8T(\frac n 2) + 100n^2$ I am trying to prove that it is $\Theta(n^3)$ by induction. I proved that it is $\Omega(n^3)$ using constant $c=\frac b 2$ and $n\_0=1$.

I am trying to prove that it is $O(n^3)$ by induction (without the master theorem) and I get stuck at the induction step. I am using $c=b$ for the induction basis.

Any assistance will be welcomed.

# Answer
> 2 votes
Let's prove that $T(n)\leq (100+b)n^3-100n^2$

For $n=1$ we have $T(1)=b=(100+b)\cdot1^3-100\cdot 1^2$.

Assume that $T(k)\leq (100+b)k^3-100k^2$ for all $1\leq k\< n$. Then $$\begin{align} T(n)&=8T(n/2)+100n^2\\ &\leq8\left\[(100+b)(n/2)^3-100(n/2)^2\right\]+100n^2\\ &=(100+b)n^3-200n^2+100n^2\\ &=(100+b)n^3-100n^2 \end{align} $$

---
Tags: lower-bounds, induction, upper-bound
---


title: Minimal length cycle containing an edge

text:
# Question
Title: Minimal length cycle containing an edge
I need a polynomial algorithm that finds the minimal length cycle in a directed graph containing a specific edge (u,v), or prove that this is NP-hard. All edges weigh the same.

Thanks

# Answer
Use BFS to find a shortest path $v\rightsquigarrow u$, and then $u\rightarrow v \rightsquigarrow u$ is the cycle you want. Try to prove for yourself and see why this works!
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: How can I use induction for proving termination of a string rewriting system?
If we have a string rewriting system within the alphabet $\\{X,Y\\}^\*$ and the rule $XY\to YX$. How can we prove by induction that on every string input the system terminates?

# Answer
It's your exercise, so I'll let you answer it, but here is a hint. Consider the sequence of words visited by repeatedly applying the rewrite rule and its relationship to lexicographic order. Work through a few examples and see if you can form a conjecture.
> 1 votes

---
Tags: proof-techniques, induction, term-rewriting, termination
---


# Question
Title: Can a data abstraction use a class as a field, parameter, or return type?
I think that everyone will agree that the following class achieves *data abstraction* (hiding of its internal representation):

```
class A {
    private List x = new ArrayList();

    public List getX() {
        return this.x;
    }

    public void setX(List x) {
        this.x = x;
    }
}

```

But could we say the same about the following one, which uses a *class* (instead of an *interface* like in the previous class) as a field type, parameter type, and return type?

```
class B {
    private ArrayList x = new ArrayList();

    public ArrayList getX() {
        return this.x;
    }

    public void setX(ArrayList x) {
        this.x = x;
    }
}

```

# Answer
> 2 votes
Sounds subjective to me. Data abstraction is not a black-and-white binary property; it is a matter of shades of grey. Any abstraction hides some information and reveals others.

Another way to put it is that these two classes expose a different amount of functionality and make a different set of promises. So, what do you want the client to be aware of, and what do you want them to not have to know about? What future changes do you want to allow yourself to make to the class (without having to change clients), and what future changes are not important to be able to make? The answers to those questions will determine which of these two implementations you choose. Each could be a reasonable choice that is consistent with the principle of data abstraction in different circumstances.

Also, remember that abstraction is a means to an end, not a goal in and of itself.

See, e.g., https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-abstractions/.

---
Tags: terminology, object-oriented, abstract-data-types
---


# Question
Title: Test if $ \sum_{n=0}^\infty \frac{n^2}{2^n} $ = O(1)
I have to test if $ \sum\_{n=0}^\infty \frac{n^2}{2^n} = O(1)$.

To show: $ \sum\_{n=0}^\infty \frac{n^2}{2^n} \le c \cdot 1$

So my attempt was:

$ \sum\_{n=0}^\infty \frac{n^2}{2^n} = \sum\_{n=0}^\infty n^2\frac{1}{2^n} $ then split the sum to $ \sum\_{n=0}^\infty 2^n \cdot \sum\_{n=0}^\infty \frac{1}{2^n} $

With: $ \sum\_{n=0}^\infty \frac{1}{2^n} = \frac{1}{1-0.5} = 2 $

we have $ 2 \sum\_{n=0}^\infty 2^n \le c \cdot 1$

as $2^n $ grows to infinity means that there is no $c$ that the inequality is always true, so $ \sum\_{n=0}^\infty \frac{n^2}{2^n} \ne O(1)$.

I would be very grateful if someone could tell me if I am on the right way or if this is all wrong.

# Answer
> 6 votes
It is false that $$ \sum\_{n=0}^\infty \frac{n^2}{2^n} \ge \left( \sum\_{n=0}^\infty n^2 \right) \cdot \left( \sum\_{n=0}^\infty \frac{1}{2^n} \right), $$ assuming that's what you meant. You can see that the first series on the right side diverges while the second converges to a positive constant.

To show that $\sum\_{n=0}^\infty \frac{n^2}{2^n} = O(1)$ you can notice that, for $n \ge 16$, you have $n^2 \le 2^{n/2}$. Then, defining $c = \sum\_{n=0}^{15} \frac{n^2}{2^n}$: $$ \sum\_{n=0}^\infty \frac{n^2}{2^n} = c + \sum\_{n=16}^\infty \frac{n^2}{2^n} \le c + \sum\_{n=16}^\infty \frac{2^{n/2}}{2^n} \< c + \sum\_{n=0}^\infty \left(\frac{1}{\sqrt{2}}\right)^{n} = c+ \frac{1}{1-\frac{1}{\sqrt{2}}} = O(1). $$

# Answer
> 6 votes
The expression $$ \sum\_{n=0}^\infty \frac{n^2}{2^n} $$ is constant. Therefore there are two options:

1. The expression is not well-defined. This would happen, for example, if the series diverges.
2. The expression is well-defined, in which case it is $O(1)$ (since any constant is $O(1)$).

One fine point is that in computer science, we often only consider functions which are eventually positive. Therefore one reason for the expression to be not well-defined is if it the constant is non-positive.

In this particular case, it is easy to see that the series converges (in fact, it is equal to 6), and in particular, it is $O(1)$.

---
Tags: asymptotics
---


# Question
Title: Solving $T(n) = 2T(n/2) + \log n$ using the master theorem
Is there a substitution, so that the following recurrence relation can be solved using the given version of the master theorem?

$$ T(n) = 2T(n/2) + \log n $$

> Let $a,b \in \mathbb{N}$, where $b \> 1$, let $g\colon \mathbb{N} \to \mathbb{N}$ belong to $\Theta(n^c)$, and suppose that
>
> 1. $t(1) = g(1)$.
> 2. $t(n) = at(n/b) + g(b)$.
>
> Then the following hold:
>
> 1. If $a \< b^c$ then $t(n) \in \Theta(n^c)$.
> 2. If $a = b^c$ then $t(n) \in \Theta(n^c\log n)$.
> 3. If $a \> b^c$ then $t(n) \in \Theta(n^{(\log a)/(\log b)})$.

Considering $S(m) = S(m - 1) + m$ instead of the original recurrence relation turned out to be not very helpful.

# Answer
> 1 votes
Consider the recurrence relation $$ R(n) = 2R(n/2) + g\_R(n), \quad g\_R(n) = \max(\lceil n^{0.1} \rceil, \lceil \log n \rceil), $$ where $R(1) = T(1)$. Since $g\_R(n) = \Theta(n^{0.1})$, case 3 of your theorem implies that $R(n) = \Theta(n)$. Induction shows that $T(n) \leq R(n)$ for all $n$, and so $T(n) = O(n)$.

Similarly, consider the recurrence relation $$ S(n) = 2S(n/2) + g\_S(n), \text g\_S(n) = \min(1, \lfloor \log n \rfloor), $$ where $S(1) = T(1)$. Since $g\_S(n) = \Theta(1)$, case 3 of your theorem implies that $S(n) = \Theta(n)$. Induction shows that $T(n) \geq S(n)$ for all $n$, and so $T(n) = \Omega(n)$.

In total, $T(n) = \Theta(n)$.

---
Tags: recurrence-relation
---


title: Does this Qualify as Sub-Exponential?

text:
# Question
Title: Does this Qualify as Sub-Exponential?
I don't have a strong CS background so apologies if the question is trivially simple:

So I am working on an algorithm, say $A(n)$ , which runs over all integer partitions of $n$. Now the algorithm calls a sub-routine $S(\pi)$ for each of the partition $\pi$ (and does nothing else). The time-complexity of running the subroutine is $O(n^c)$ for some constant $c$.

Now the number of integer partitions is $\frac{1}{4n\sqrt 3}\exp\Big(\pi \sqrt \frac{2n}{3}\Big)$. And hence, the time complexity of my algorithm should be $O(e^{\pi\sqrt \frac{2n}{3}}n^{c'})$ or maybe just $O(e^{\pi\sqrt \frac{2n}{3}})$ or just $O(e^{\sqrt n})$ ?

Also, in my understanding I can call this SubEXP in the sense of $\textbf{III}$ category presented here.

I would basically like to understand how best to describe this complexity in an academically accurate manner. Thanks alot !

# Answer
Lets say there are $N(n)$ partitions. Then, for each partition you do $O(n^c)$ work (important note: make sure for all partitions this is the same $O(n^c)$. That is, for this particular $c$, for all partitions it takes $O(n^c)$!)

This means that the total work will be $O(n^c)$ times $O(N(n))$ (because you do $O(n^c)$ work for $N(n)$ iterations), hence a total of $O(N(n)\cdot n^c)$. Substitute here the number of partitions $N(n)$ and this will be the running time.

This running time is indeed considered sub-exponential in terms of category $\textbf{III}$ from the link you provided (and hence it is also $\textbf{IV},\textbf{V},\textbf{VI}$ in those terms), since the algorithm takes $$O\left(e^{c\cdot n^{\frac{1}{2}}}\right)=O\left(2^{\ln(2)\cdot c\cdot n^{\frac{1}{2}}}\right)=O\left(2^{n^\epsilon}\right)$$ for any $\epsilon\>\frac{1}{2}$ of your choice. Note, that this **isn't** category $\textbf{II}$ as this is true only if $\frac{1}{2}\<\epsilon$, rather than for all $0\<\epsilon$.
> 2 votes

---
Tags: complexity-theory, integer-partitions
---


title: PDA to recognize a language

text:
# Question
Title: PDA to recognize a language
The PDA has to recognize the language $L = \\{w\in \\{a,b,c\\}^\* \mid |w|\_a = |w|\_b$ or $ |w|\_a=|w|\_b\\}$.
Currently I have an automaton which recognises that language if $|w\_a|=|w|\_b$ xor $|w\_a|=|w|\_c$. It looks like this:

It is xor because it is going to empty the stack before it could check next letter's occurence.
My question is how can I divide this into two PDAs (one recognises $|w|\_a=|w|\_b$ and the other one recognises $|w|\_a=|w|\_c$) and take the union of those PDAs?
Or is there any better solution?

# Answer
actually you also had a mistake in the definition of the problem and I've considered its |Wa|=|Wb| or |Wa|=|Wc|. Any way using non-deterministic I've tried to separate two conditions:
> 1 votes

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


# Question
Title: Is this grammar well-defined? How do I prove the language generated by it is regular?
I have the following problem statement:

Is G well-defined here? I am unsure of this since there's no production rule for $X, Y, Z$, and this confuses me a bit.

And secondly, how do I prove $L$ is regular? I was thinking the grammar might be right-linear, but I'm not sure if this is the case. Do you have any ideas on how to build an automaton that recognizes this language?

According to the solutions manual, this should be regular, but no proof is given. Also, they don't seem to consider that $L = \\{ \lambda \\}$.

# Answer
From the supplied solution, it's clear that the question was written incorrectly. The fifth, sixth and seventh productions should produce $X$, $Y$ and $Z$, respectively, instead of $A$, $B$ and $C$. You might want to report this typo to whomever set the problem.

Once you make that change, the fact that it is equivalent to a right-linear grammar can be shown by substituting $A$, $B$ and $C$ with their respective right-hand sides ($a$, $b$ and $c$).
> 3 votes

# Answer
If you look at the formal definition of grammars, there is nothing requiring a nonterminal symbol to apppear in the left side of a production rule. So $G$ is a perfectly valid grammar.

If we drop all useless production we are left with $S \to \lambda$. Therefore $L(G) = \\{ \lambda\\}$, which is a finite language and hence it is also regular. If you really want to, it is easy to come up with a DFA that recognizes this language.
> 1 votes

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


# Question
Title: Given a list of comparisons, sort items with as few additional comparisons as possible
You have `n` items `x[0], ..., x[n-1]`. Beforehand, you're given a list of several comparisons `c[0], ..., c[k]` for those items (e.g. `c[0] = (x[0] < x[4])`, `c[1] = (x[3] > x[7])`, etc.).

The objective is to sort the items by requesting **as few additional comparisons** as possible.

For example, if `c` contains all the pairwise comparisons, then you don't need to request any additional ones to be able to sort the list. If `c` contained nothing, then you'd request `O(n*log(n))` additional comparisons to perhaps quicksort the items. But if `c` contained something in between, how could we smartly leverage those existing comparisons to guide the extra comparisons we request?

Computation time doesn't matter (so long as it's sub-exponential). All that matters is the algorithm requests roughly the fewest additional comparisons.

Vaguely, I have an idea about constructing a DAG from the comparisons in `c`, and then doing a topological sort for the DAG to get a partial ordering, but I'm not sure where to go from there.

# Answer
Your problem is solved in Kahn and Kim, Entropy and sorting.
> 2 votes

---
Tags: algorithms, graphs, time-complexity, sorting, dag
---


# Question
Title: Sorting from independently chosen comparisons
I want to sort a list of `n` items from pairwise comparisons. Each round, I receive `k` comparisons, one each from `k` different "arbiters".

The arbiters **cannot coordinate**, and must choose their comparisons independently from myself and each other. How should they choose their comparisons so that I can sort the list of items in as few rounds as possible?

A naive solution is that each arbiter independently runs quicksort, sending over the corresponding comparisons they make. Ultimately, I'd just be waiting for one arbiter to finish sorting, so this would take `O(n*log(n))` rounds for me to sort the list, and I literally receive no benefit from having `k` arbiter over just a single arbiter.

Another naive solution is each arbiter independently sends over random comparisons. This would result in a coupon collector problem, and would taken on average `O(n^2*log(n)/k)` rounds for me to get the right comparisons to sort the list. But unless k is in `ω(n)`, this run-time isn't better than `O(n*log(n))`.

Is there a better solution? Maybe one that uses `O(n*log(n)/k)` rounds? (i.e. double the arbiters = half the rounds needed)

To be more concrete about the independence of arbiters: ideally, the arbiters would use symmetric randomized strategies. If that's not possible, though, then I'll allow the arbiters to have a strategy meeting **one time only at the start**.

Also, arbiters **have to send exactly the comparisons they make**. E.g. an arbiter **cannot** just sort the entire list themselves, and then send only the comparisons `(arr[i] < arr[i+1]) for i=0 to n-2`. They have to send each comparison they make as they make it.

# Answer
> 2 votes
I think I have a solution. It's totally symmetric with no coordination.

Each arbiter runs the following algorithm to choose their comparisons.

First, they consider evenly dividing `n` into `k` "sections" (e.g. section 1 is from 1 to `n/k`, section 2 is from `n/k+1` to `2n/k`, etc.). Then, they randomly choose one of `k` sections to focus on. Next, they use quickselect to get all the elements that will end up in their section (which takes `O(n)` comparisons). Finally, they fully sort their section (which takes `O(n*log(n)/k)` comparisons). After that, they randomly choose another section and repeat.

To get all `k` sections sorted, it's a coupon collector problem, and takes `k*log(k)` tries, which, when distributed over `k` arbiters, will only take `log(k)` tries.

So the final number of rounds of this approach will be `O(n*log(k) + n*log(n)*log(k)/k) = O(n*log(n)*log(k)/k)`, which gives you an improvement factor of `log(k)/k`. This can be upgraded to `1/k` if the arbiters are allowed to choose at the start which sections they're in charge of.

# Answer
> 1 votes
This sounds quite a bit like a job for sorting networks (a fixed network of rounds that compare two elements and swap them if out of order).

---
Tags: algorithms, time-complexity, sorting, distributed-systems, parallel-computing
---


# Question
Title: Solve $\sum_{i=0}^{\log_3 n-1}i\times 3^i$
I want to find the answer for $$\sum\_{i=0}^{\log\_3 n-1}i\times 3^i$$

Can you please explain? I this a geometric series?

# Answer
> 0 votes
If you consider the infinite sum (instead of stopping the sum at $\log\_3 n- 1$) you obtain an arithmetico-geometric series.

These series have the general form $$ \sum\_{k=1}^{\infty} (a + (k-1)\delta)br^{k-1}. $$

In your particular case $a=0$, $\delta=1$, $b=1$ and $r=3$. Since a closed-form expression for the generic $m$-th partial sum is known (see the Wikipedia page), you can just substitute the above values in the relevant formula (in your case $m= \lfloor \log\_3 n \rfloor$).

# Answer
> 1 votes
A general way to handle similar sums is to start with:

$\begin{align\*} S\_n(z) &= \sum\_{0 \le k \le n} z^k \\ &= \frac{1 - z^{n + 1}}{1 - z} \\ z \frac{\mathrm{d}}{\mathrm{d} z} S\_n(z) &= \sum\_{0 \le k \le n} k z^k \end{align\*}$

Differentiate, substitute the desired value of $z$ and $n$, and you are set.

---
Tags: recursion
---


# Question
Title: How could a page be invalid in demand paging?
I was reflecting on what I learned about demand paging and I have a question:
In demand paging, we have entries in the page table only for frames that are present in physical memory. So I was wondering how could a page fault (not because of a bug , occur in such a state).
In my class we where shown an image :

My confusion comes from the definition of demand paging. If every entry in the page table exists in physical memory then how could an invalid (not present in memory) entry exist in page table and cause a trap?
But then again, I thought to myself: **Maybe when we need to replace a page and we exchange it with another one we do not replace the entry in the page table as well as we do with the frame but we change it's valid bit to invalid and we add a new entry for the page that we just brought from disk.** So basically, we these page replacements the page table of a process grows in time .
Is that right? Is that what happens? If so why we call it page replacement and not frame replacement?

# Answer
> 1 votes
I'm going to refer you to my previous answer on this topic. I went through a number of situations where even if a page table entry (PTE) correctly refers to a page frame in memory, marking the PTE as invalid still makes sense.

There are two views of a virtual address space: the CPU's view (which is implemented by the page table mechanism), and the operating system's view, which involves a bunch of additional data structures and concepts that the CPU's page translation hardware doesn't see.

These additional data structures are not included in your diagram, but they are extremely important. The vast majority of CPUs don't have a concept of "swap", or "memory-mapped file", or any of those other high-level ideas that we use virtual memory *for*. Those are entirely implemented by operating systems.

When a PTE is marked as invalid, it is invalid *from the CPU's point of view*. From the operating system's point of view, it may well be a perfectly valid mapping. Assuming the program isn't buggy, it probably is.

# Answer
> 0 votes
As to terminology, page frame and page is normally two terms which refer to the same thing (a physical page/frame).

Demand paging doesn't mean that the page tables are not present in memory. Demand paging means that the actual pages/frames are not present in memory.

More often than anything, the page tables of a process should be filled according to how much memory is available. For example, on a system with 4GB of memory, the page tables should span 4GB. This is for security reasons. If the page tables are not filled completely, then a certain process A could access the memory of another process. This is due to the fact that, when the page tables are not filled completely, an address can be translated to anything (because anything could happen to be in memory at the time of translation). It is one of the mechanism of paging which allows great hardware isolation of one process to other processes.

Each entry of every page tables have a present bit. When the MMU of the processor attempts to access a page which isn't present, it triggers a page fault. The kernel thus takes the page on the hard-disk and loads it to main memory (unless the page wasn't supposed to be accessed in which case it kills the process).

Every executable today supports virtual memory. The virtual memory in use by a process is specified in the executable directly. The kernel thus uses that to determine if a process should have access to a specific address. It determines the ranges of virtual addresses that a process has access to in the executable.

In demand paging, the kernel just leaves the executable on the hard-disk and builds a memory map of the process. Then, when the process is given a CPU to run (by the scheduler triggered by a timer interrupt), the kernel jumps to its entry point. When the process starts executing, it triggers a page fault immediately. The kernel thus looks in its memory map for that process and determines that the access was legal according to the ranges of virtual addresses that the process has access to. It will thus put the accessed page in main memory reading it from the executable and then put the process back on the run queue.

Your assumption that the page tables are not filled is wrong. The page tables are filled. The entries are just marked as not present. I don't know about Linux or Windows. What I would do, if I wrote something like that, is I would fill all page tables of a process with zeroes. On page fault, I would then check whether the address access was zero and kill the process if it is the case.

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


title: Simple problem of combinatorics

text:
# Question
Title: Simple problem of combinatorics
There are $3$ red socks, $4$ green socks and $3$ blue socks.You choose $2$ socks. The probability that they are of the same color is

Answer: $\dfrac{^{3}C\_{2}+^{4}C\_{2}+^{3}C\_{2}}{^{10}C\_{2}}=\dfrac{4}{15}$

But my approach was to $1-$all unfavorable cases

$i.e.$

$1-\dfrac{RED\*GREEN + GREEN\*BLUE + RED\*BLUE}{^{10}C\_{2}}$ = $1-\dfrac{3\*4 + 4\*3 + 3\*3}{^{10}C\_{2}}$ = $\dfrac{11}{30}$

I am not able to identify my mistake, it will be suffice if some one can provide a hint.

# Answer
> 1 votes
You just have an arithmetic error when computing $1 - \dfrac{3\cdot4+4\cdot3+3\cdot3}{10 \choose 2} = 4 / 15$.

---
Tags: combinatorics
---


# Question
Title: Issues in the proof of $E_{TM}$ is Turing reducible to $A_{TM}$
First definition:

> $A\_{TM}$ = $\\{ \<M,w\> | $M is a TM and M on w accepts$ \\}$

Second definition:

> $E\_{TM} = \\{ \<M\> |$ M is a TM and L(M) = $\phi \\}$

Let $T^{A\_{TM}}$ be an oracle Turing machine with an oracle $A\_{TM}$. We want to show that $E\_{TM}$ is Turing reducible to $A\_{TM}$.

$T^{A\_{TM}}$ = "On input $\<M\>$, where M is a TM:

1. Construct a TM N:

> 1. N = "On any input:
> 2. For i=0, 1, 2, 3. Run M on s\_i for i steps where $s\_i \in \Sigma^\*$ and $\Sigma^\*=\\{s\_0, s\_1, s\_2, .... \\}$.
> 3. If M accepts any of these strings, then accept."

2. Ask the oracle: Is $\<N, 0\> \in A\_{TM}$.
3. If the oracle answers NO, accept. If YES, reject."

Now, Sipser said in pp. 236-237, "If M's language isn't empty, N will accept every input and in particular, input 0. Hence the oracle will answer YES, and $T^{A\_{TM}}$ will reject. Conversely, if M's language is empty, $T^{A\_{TM}}$ will accept."

My question: Why N will accept every input and in particular, input 0? It is not clear how N will accept every string. For example, M will run on all input of $\Sigma^\*$ but only those strings that are in L(M) will be accepted and I don't understand how N will accept every input. Moreover, it is not clear why he choose string "0".

Note that I changed step 2 where Sipser wrote: "Run M in parallel on all strings in $\Sigma^\*$" since as I believe mean the same thing unless you have something to say.

# Answer
> 4 votes
First, note that Sipser says ""If **M's** language isn't empty, **N** will accept every input".

---

Let us first prove this statement: Assume $L(M) \neq \emptyset$.

Then there exists some $x \in L(M)$. Because $L(M) \subseteq \Sigma^\*$ we have $x \in \Sigma^\*$. Then because $s\_i \in \Sigma^\*$ and $\Sigma^\*=\\{s\_0, s\_1, s\_2, .... \\}$, there exists an $i^\*$ such that $s\_{i^\*} = x$.

The TM $N$ accepts "if M accepts any of these strings". Because $s\_{i^\*}$ is one of these strings, $N$ accepts.

---

Note that $N$ never considered *its own input*! It only decides whether to accept or not based on $M$ which is part of the TM $N$ itself, *not* $N$'s input.

The string 0 is totally arbitrary. You can pick any string because we know that $N$ will accept *any* string if and only if\* the language of $M$ is not empty. Because we want to reduce to $T^{A\_{TM}}$ this is indeed all we care for.

<sub>* The other direction remains to be shown for a complete proof.</sub>

---
Tags: computability, reductions, undecidability
---


# Question
Title: Can a Red Black tree be constructed of only black nodes using RB insert only?
I am trying to construct a red black tree out of only black nodes. I know it is possible getting it after some deletions but I am trying to construct one only via insertion orders. Is it possible? I couldn't find a way to do so , so far even after trying to use the simulator.

\*** exept of a root node being added to an empty tree.

# Answer
Properties of Red Black Tree:

0) Every node is black or red. Ok, no problem.

1) Root is black. Ok, no problem.

2) All leaves (empty nodes) are black. Ok, no problem.

3) Every red node must have two black childs. Ok, no problem.

4) Every path from any node to leaf has equal number of black nodes. It seems problematic.

So now comes problems: When you insert element it's color is red. (In fact this not comes from properties but observation that adding red node does not violate $4$th rule, so it is easier to implement).

So for start you add one element, let me say 10. It is black root. Ok.

Now You add 13. It must be red, otherwise it violates rule 4.

Now you add 19. Depending on implementation you can leave all black, or recolor.

Now adding 12 gives recoloring and comes red.

And after several numbers

And now it starts nightmare, as you should propagate changes from one side of tree to another convincing somehow that you will change everything to black after insertion.

Basically I asked you about rules to obey, as it comes to mind that with $4$th can be fulfilled only in perfectly balanced trees.

So to answer your questions:

No you cannot with common implementations of RBT, but extending balance operation to recolor when it is possible - it does not violate rules, so it is possible. Also with extension that whenever there is $n = 2^k - 1$ nodes, restructure it to perfectly balanced tree and recolor everything to black, it would be also possible.

I did firstly answer "no" as purpose of balancing operation is to guarantee bound on worst case search / insert, and such extensions comes at price of time complexity. It does not violate rules, but is not implicitly implemented in standard RBT.

Given only root, you have it. Given three nodes inserted in order with implementation changing all to black (rather rare case and counterproductive), you can. But this is last one that is without deletions possible.

When you are about to insert element and want all tree to be black that would mean there is violated rule $4$ (so not possible) or you have to rebalance tree, which would recolor nodes, so it is not pure black anymore.

With deletions on the other hand ;)
> 3 votes

# Answer
insert 1,2,3,4 then delete 4,thank you.
> -2 votes

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


title: Variable name starting with integers

text:
# Question
Title: Variable name starting with integers
When I started doing programming I wondered that why the variable names can't start with integer. Back then I accepted that , may be this is how the compiler designers have decided to go with. But now I am studying Compiler Design and they say that lexical analyzer produces token and it is easy / fast if we use identifiers as regular languages. So the regular expression like this : $(number)^\*(underscore + alphabet)^+(number)^\*$

Why they don't use this? As per compiler I don't see any ambiguity or problem in this as we have symbol table entries for each token. I know that many similar question are asked but I want to know as per lexical analysis and compiler design perspective.

# Answer
In many languages, `1e3` is a literal that represents 1000, `0x10` is a literal that represents 16. If we used your proposed regexp for variable names, it would be ambiguous whether those expressions should be represented as a literal or as a variable name.
> 1 votes

# Answer
It's worth noting that there are some programming languages, even common ones, that support what you want. For example:
> 2 votes

# Answer
Many languages support unicode. For example, ①②③⑳ would be a valid Swift identifier. But being able to have the same character sequence being both an identifier and a number is at best confusing and useless.
> 0 votes

---
Tags: compilers, lexical-analysis
---


# Question
Title: Turing machine with "move to origin" instead of "move left"
> You have a Turing machine which has its memory tape unbounded on the right side which means that there is a left most cell and the head cannot move left beyond it since the tape is finished. Unfortunately, you also find that on execution of a head move left instruction, rather than moving to the adjacent left cell, the head moves all the way back to the initial left most cell of the tape. Now figure out whether you can still use this TM effectively. The Turing machine with left initialize is similar to an ordinary Turing machine, but the transition function has the form
>
> $$\delta \colon Q × Γ → Q × Γ × \\{R, \mathit{INIT}\\}.$$
>
> If $\delta(q, a) = (r, b, \mathit{INIT})$, when the machine is in state $q$ reading an $a$, the machines head jumps to the left-hand end of the tape after it writes $b$ on the tape and enters state $r$. Show that you can program this TM such that it simulates a standard TM.

I can't figure out how to simulate this as standard TM. One thought I have is to copy the content of the tape which is afterwards the left move to the starting point of the tape before making a left move. Any further help would be appreciated.

# Answer
When you want to move one position to the left, execute the following algorithm:

* Mark the current position as special.
* Move to the origin.
* Translate the tape one cell to the right, while keeping the special marker in place.
* Move to the origin.
* Scan until reaching the special marker.
* If you move to the right, don't forget to erase the special marker.

(This simulates a Turing machine with a single *two-sided* tape.)
> 3 votes

# Answer
Interesting faulty TM!

First, given any standard TM, there exists a TM with one-sided tape that simulates it. Basically, we can split a one-sided tape into odd-numbered cells and even numbered cells. Use odd-numbered cells to represent one side of an ordinary tape and use even-numbered cells to represent the other side of an ordinary tape. The current state of the TM always track whether it is on an odd-numbered or even numbered cell.

Now the question is shifted to how to simulate any given TM whose tape is one-sided. Let $S$ be such a machine. The cells of $S$ are $S\_0, S\_1, S\_2$, $\cdots$.

Let us design a faulty TM $F$ to simulate $S$. The cells of $F$ are $F\_0, F\_1, F\_2$, $\cdots$, where $F\_0$ is the origin. Even-numbered cell $F\_{2i}$ corresponds to $S\_i$. Odd-numbered cells will be selected to function as landmarks. Every odd-numbered cell is initially marked blank, $\mathbb{\color{blue}⯁}$.

* If $S$ moves from $S\_i$ to $S\_{i+1}$, then $F$ should move from $F\_{2i}$ to $F\_{2i+2}$. This is easy to implement.
* If $S$ moves from $S\_i$ to $S\_{i-1}$, then $F$ should move from $F\_{2i}$ to $F\_{2i-2}$. The idea to implement that is to construct an identifiable array of contiguous cells of some fixed length closer and closer to the intended cell.

1. First $F$ moves to the right and write $\mathbb{\color{blue}{V}}$ on $F\_{2i+1}$. Note that $F\_{2i-2}$ is three cells to the left of $\mathbb{\color{blue}{V}}$.
    2. Let $F$ move left, i.e, it goes back to the origin, $F\_0$.
    3. $\ \ $

    1. Let $F$ read the first seven cells, keeping track of whether $\mathbb{\color{blue}{V}}$ has been read and on which cell.

        If $i\le 3$, then $F$ must have read $\mathbb{\color{blue}{V}}$ on $F\_{2i+1}$. Let $F$ go back to $F\_0$ and, then, move to the right $2i-2$ times to reach $F\_{2i-2}$. Mission is accomplished.

        Otherwise, Let $F$ go back to $F\_0$ and move right to write $\mathbb{\color{blue}{U}}$ on $F\_1$. Go back to $F\_0$.
        2. Now $F$ is on $F\_0$. $\mathbb{\color{blue}{U * ⯁ * ⯁ * ⯁}}$ sits somewhere before $\mathbb{\color{blue}{V}}$, where each $\mathbb{\color{blue}{\*}}$ stands for a possibly different tape symbol that is neither $\mathbb{\color{blue}U}$ nor $\mathbb{\color{blue}V}$. Except that $\mathbb{\color{blue}{U}}$ and $\mathbb{\color{blue}V}$, all odd-numbered cells are blanks.

        Keep $F$ moving to the right. When it reaches $\mathbb{\color{blue}{U}}$, change it to a blank. Moving two more cells to the right, mark $\mathbb{\color{blue}{U}}$ on the cell. Now we have $\mathbb{\color{blue}{⯁ * U * ⯁ * ⯁}}$ in place of the original stripe.

        Let $F$ move to the cell to the immediate right of the last $\mathbb{\color{blue}⯁}$ above.
        3. If $F$ reads $\mathbb{\color{blue}{V}}$, then we know that $F$ should, for simulation, go to the cell right after $\mathbb{\color{blue}{U}}$. Let $F$ move left, then move right until it reaches $\mathbb{\color{blue}{U}}$. Move right one more time. Mission is accomplished. Note $F$ should also restore $\mathbb{\color{blue}{V}}$ and $\mathbb{\color{blue}{U}}$ to $\mathbb{\color{blue}⯁}$ along the way.
        4. Otherwise, $F$ does not read $\mathbb{\color{blue}{V}}$. That means we have $\mathbb{\color{blue}{U * ⯁ * ⯁ * ⯁}}$ somewhere before $\mathbb{\color{blue}{V}}$ again, but two cells closer. Let $F$ move left. Go back to step 3.2.

The above design concentrates on the ability of $F$ to move like $S$. To simulate $S$, $F$ should also keep track of the current state of $S$, which is easy to implement.
> 1 votes

# Answer
1. you can simulate Standard-TM -\> "TM without left option" S.T. a) put a new alphabet at the first place (leftmost) of the tape b) shift all other written into one place right for each init move we go left until we reach out new alphabet

---

2. you can simulate "TM without left option" -\> Standard-TM S.T. for every time you needed a left move: a) mark where you are b) using init go back to the beginning and mark there c) we go right until we reach a marked d) we move right one place again if it is already marked that means we reach what we wanted and the previous place was where we need -- \> SO : unmark here - \> go initial -\> move right until reach mark -\> here is previous and we are done! e) if it was unmarked -\> mark here -\> go all the way back to the beginning then move right until the first marked place, unmark there and go to the beginning of the tape.

---

so both have equal power
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Why did finite-state controller with datapath win?
I just finished watching the 1986 *SICP* lectures, and the concepts are rolling around in my head.

> **My question**: why is "finite-state controller with datapath" the implementation of computer programs we use?

I can think of a few of *types* of answers, which have different emphases:

1. **We** don't use it: there are various implementations of computation in use; this is just one of the more important ones.
2. We don't **use** it: it is a pedagogical abstraction which isn't a total lie, but when you get into microarchitecture, the trade-offs at multiple levels of design yield implementations which defy simple categorization.
3. This model has arisen over time through a selection process, with selection pressures from economics and managability of design.

Types 1 and 3 are enticing to me, because these would endeavor to explain the comparative advantages of FSCwD compared to other models/implementations of computing. (And explain what those other models *are* along the way.)

Note I'm not asking about *models of computation* as such, as those are about how to model computation conceptually, not how to model the implementation of computation on hardware.

Lastly let me say I am aware that a thorough answer to this question would constitute a whole book or more; therefore I am looking for "leads" in my search (search terms, particular books or articles). I've been searching things like

* Models of computation
* FSM with datapath
* Processor design

etc, but none of them have so far have compared various models of implementation.

# Answer
> 6 votes
This is a very good question, which I don't think I can completely answer. What I can try to do is

1. give some history of how the idea emerged (although I haven't been able to discover as much of the story as I'd like).
2. provide *an* explanation of why FSM+datapath is a valuable abstraction technique. (Note: *an* explanation, not *the* explanation)

I don't think I'll be able to satisfactorily answer what other alternative design abstractions might have been possible, or why FSM+datapath might be preferable (or not) to those other design abstractions.

Historically, I've found at least 3 inter-related lines of thought that seem to have come together in

> Christoper R Clare; *Designing Logic Systems Using State Machines*, McGraw-Hill, 1973.

This book is considered the origin of the idea of Algorithmic State Machines (ASMs) that are now taught in most intro digital design books, and was based on ideas that Tom Osborne developed while desigining and implementing his prototype of what became the HP 9100A.

I think there were several ideas "floating around" in the 1950's and 60's that influenced Osborne's ASMs.

1. The idea of using microprogramming as in M.V. Wilkes and J.B. Stringer; Microprogramming and the design of the control circuits in an electronic digital computer, *Proc. Cambridge Phil. Soc.*, pt.2, vol. 49, pp. 230-238, April, 1953. (You can find an online copy as Chapter 28 of Bell and Newell).
2. The idea of *Register Transfers*. These were introduced (as far as I know) by Irving S Reed in a series of technical reports at the beginning of the 1960s, and then popularized in the book T. C. Bartee, I. L. Lebow, I. S. Reed, *Theory and Design of Digital Systems*, McGraw-Hill, 1962. An early paper on synthesizing circuits from Register Transfer specifications was H. Schorr, "Computer-Aided Digital System Design and Analysis Using a Register Transfer Language," in *IEEE Transactions on Electronic Computers*, EC-13(6):730-737, Dec. 1964, doi: 10.1109/PGEC.1964.263907. An overview paper that covers a lot of the variants is M. R. Barbacci, "A Comparison of Register Transfer Languages for Describing Computers and Digital Systems," in *IEEE Transactions on Computers*, C-24(2):137-150, Feb. 1975, doi: 10.1109/T-C.1975.224181.
3. The idea of Control Flow Graphs from the compiler community. This subfield really started blossoming in about 1970 with the publication of Frances E. Allen's "Control flow analysis", in *Proceedings of a symposium on Compiler optimization*, July 1970, Pages 1-19.

Microprogramming may have been an important influence because it showed both that (a) you could decompose relatively complicated operations into multiple steps, and (b) that the resulting state machine transition functions could be relatively easily implemented (using something like a ROM instead of ad-hoc combinational logic networks).

Register Transfers are important for describing datapaths. Note that when you decompose a problem into a finite-state controller + datapath, most of the state is actually in the datapath. The Register Transfer description of the datapath operation abstracts the specification in two key ways. First it groups the datapath state bits into chunks that are operated on together (for example an 8-bit register), and discusses the state transitions on those chunks in abstract terms. Consider the register transfer:

```
R_a <- R_b + R_c

```

If registers `R_a`, `R_b`, and `R_c` each have 8 bits then you are describing a set of state transitions on a state machine with 24 bits, so 2^24 possible start states, and the transitions for each of those start states to its next state.

Second, Register Transfers break the state up into a bunch of independent chunks. That is, the transitions on `R_a` are independent from the transitions on `R_b` are independent from the transitions on `R_c`. For the parallel transfer `R_a <- R_b+R_c; R_d <- R_e-R_f`, we know that only the bits of `R_a` and `R_d` are changing. `R_b`, `R_c`, `R_e`, and `R_f` are not changing. These two advantages (that each register is multiple bits and that the registers are independent of one another) gives us leverage to describe state machines with enormous state spaces with just a few lines of "code".

Finally, the control flow graph (or the similar Algorithmic State Machine) allows you to talk about the sequence of states, and conditional state transitions of an algorithm independently of the complicated state transitions that are happening in the data path. That is: we can reason abstractly about sequences of operations without worrying about the concrete values stored in the datapath.

# Answer
> 2 votes
FSM+Datapath, in this context, is a *design technique* of logic design. *Any real-world sequential circuit* can be modeled as an FSM, but in practice only sequential control logic is modeled as an FSM. For example, a D Flip-Flop can be modeled as an FSM, i.e. **in terms of explicit states and their transitions**, or it can be modeled in terms of logic gates, or a behavioural description with implicit states. **Whichever method you use for modeling a D Flip-Flop, the D Flip-flop remains an FSM, but *only when the design is expressed in terms of explicit states and their transitions, do we say the flip-flop has been designed using the FSM design technique*.** Similarly, **only when a logic design is modeled using the explicit flow of data, do we term it as datapath design technique.**

To answer the question of why FSM+Datapth became the dominant technique, we should look into some of the alternatives to FSM+Datapath that exist, and why these alternatives failed.

**Synchronous logic vs. Asynchronous logic**

FSM + Datapath is a term often used for *synchronous* logic design of sequential logic. While asynchronous FSMs do exist, the most common ones are synchronous. Asynchronous logic does not use a clock for synchronization, while synchronous logic uses a global clock for synchronization of operations. In synchronous logic, the FSM changes its state on the active edge of the clock. So the operation is predictable and it is regular. The change of state happens at regular intervals of time, since the clock frequency is constant (varying clock frequency dynamically is also possible, but let's keep things simple for our discussion). In asynchronous FSM, change of state is not synchronized with a clock. Synchronous logic is *much easier to design*. The logic is less complex, so it is easy to get a correct design using synchronous logic. This is the reason all the processors we use in daily life are synchronous.

**Top-down methodology vs. bottom-up methodology**

The bottom-up methodology focuses on designing the circuit from the bottom-up, i.e. from transistors to gates to the final circuit. The top-down methodology focuses on designing the circuit from higher-level abstractions, such as **behavioral descriptions** and **flow-diagrams**. While the bottom-up methodology works well for smaller design blocks, it does not scale up for large designs such as processors. This is the reason a top-down methodology is used for processor design. In practice, smaller functional blocks are designed bottom-up, and the entire system is designed top-down, and the 2 meet in the middle, i.e. the system is broken down into smaller blocks, which are designed from the bottom up.

A top-down methodology has 3 advantages over a bottom-up methodology:

1. Promotes regularity: This refers to designing a complex unit using simpler units repeatedly. For example: Designing a 4 bit adder using 4 1-bit adders.
2. Promotes design reuse: The top-level design can contain many units, which can be broken down into even more units. Different design units can have a common design for the lower-level design units. For example, both a 4-bit adder and a 4-bit multiplier can have a common design of a 1-bit adder. Multipliers can be built from shifters and adders.
3. Ease of design: The designer does not get **lost in a sea of gates** when designing a complex unit. The processor architect (system-level processor designer) can **split the design work among multiple teams, so design work can be done in parallel.**

All these factors result in far lesser design time for a top-down methodology than a bottom-up methodology. As time-to-market is crucial in the semiconductor industry, this resulted in top-down methodology becoming the methodology of choice.

**Motivation for Finite State Machines**

For controlling sequences of operation, it is natural to think of it in terms of *how the machine should behave*, rather than how the machine should be implemented using logic elements such as Flip-Flops and combinational logic. This led to the evolution of FSM design technique. In this technique, the FSM is implemented using gates and flip-flops, from the behavioral description of the FSM, **in a top-down design methodology**. The behavioural description of the FSM contains explicit states and state transitions in the FSM Design technique.

**Motivation for Datapath**

For operations in which I need to move my data around, for example from register to memory or register to register, it is natural to think about *how the data should flow*. By thinking this over, I can then draw an abstract diagram of the *datapath*. This led to the evolution of the datapath design technique. In the datapath design technique, the datapath is implemented using combinational logic and registers, from the datapath diagram, **in a top-down design methodology**. The behavioural description of the datapath contains explicit flow of data in the Datapath Design technique.

**Putting it all together: Motivation of FSM+Datapath for processor design**

So while the FSM design technique excelled at designing control logic of sequences, the datapath design technique excelled at designing logic to support the flow of data. Coming to the processor, it is natural to split the design of a processor into 2 parts:

1. **The sequence of operations:** Fetch data from memory, decode the instruction and then execute it, finally write it back. We use **control signals** to signal the completion of one operation and flow control (such as branching). This control of sequences can be designed naturally using the FSM design technique.
2. **The flow of data:** How data should flow from register to memory or register to ALU and so on. This can be designed naturally using the datapath design technique.

**Availability of EDA tools:**

The availability of Electronic Design Automation (EDA) tools played a crucial role in enabling a top-down design methodology and the synchronous design philosophy, since EDA tools had great support for logic synthesis (automatically generating logic gates from a behavioral description) for synchronous designs, and also had great support for logic synthesis from an abstract, behavioural textual description written in a special computer language called a Hardware Description Language.

**Summary and conclusion:**

Synchronous logic became the dominant design technique simply because it was easier to design working machines. FSM design technique by itself is limited in usefulness, since it would be difficult to create an FSM for the entire processor, because this would result in a very large and complex FSM that is difficult to debug or read. Sequential control of the processor can be designed naturally using the FSM Design technique, so only the sequential control of the processor is designed using the FSM design technique. The rest of the processor is designed using the datapath design technique, since the dataflow aspect of the processor is easy to model as a datapath. The availability of EDA tools further motivated the design of processors using abstract, behavioural descriptions such as FSMs and datapaths.

Related Question: Mathematical models of computation that capture more advanced OS and CPU design features

---
Tags: computer-architecture, reference-request, computation-models
---


title: updating n elements in $O(\lg{n})$ time

text:
# Question
Title: updating n elements in $O(\lg{n})$ time
I need to devise a data structure $S$ with the following functions:

* BUILD($S$) - build the data structure from a series of $n$ elements in time $O(n \lg{n})$
* INSERT($S$, $k$) - insert a new element with the key $k$ to $S$ in time $O(\lg{n})$
* DELETE($S$, $p$) - delete the element $p$ from $S$ in time $O(\lg{n})$
* D-SUCCESSOR($S$, $p$, $d$) - return the $d$-successor of $p$ in time $O(\lg{n})$ where $d$-successor of $p$ is the $d$-th element after $p$ if the elements where ordered by their key
* DECREASE-UPTO($S$, $k$, $val$) - decrease by $val$ all keys in $S$ where the key is not larger than $k$, in $O(\lg{n})$ time

---

I've managed to do the first 4 points using order static tree, as an extension of red black tree, but I'm having trouble with the last one, assuming $k$ is bigger than all elements in $S$ the function will need to update the values of all $n$ elements in $S$ how can this be done in $O(\lg{n})$ time?

# Answer
The idea is to maintain a balanced BST where each node is suitably augmented with satellite information, as you have already done for the first 4 points.

To handle the last point you just need to add a new field $\delta(v)$ to each node $v$. The meaning of this field is as follows:

If $u$ is a vertex of the tree, the key **stored** in $u$ is $k(u)$, and $\langle r = u\_1, u\_2, \dots, u\_\ell = u \rangle$ is the path from the root $r$ of the tree to $u$ then the key $k^\*(u)$ that is **logically represented** by $u$ is: $$ k^\*(u) = k(u) + \sum\_{i=1}^\ell \delta(u\_i). $$

This fields can be maintained while the other operations are performed, while preserving the BST order of the represented keys in the tree. I.e., if $v$ is the left (reps. right) child of $u$ then $k^\*(v) \< k^\*(u)$ (resp. $k^\*(v) \> k^\*(u)$).
> 1 votes

---
Tags: data-structures, red-black-trees
---


# Question
Title: What is so special about a majority and why is it the key for Paxos to work? (Paxos made simple)
Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and I was wondering, what is so special about a majority of nodes having a value? Why is that the key fact for consensus to work on Paxos?

It says on the paper that "any two majorities have at least one acceptor in common, this works if an acceptor can accept at most one value" (page 2). Its true that if we have two majorities then at least one node between the two must be the same one, but I was not entirely sure if I fully appreciated why that was special for consensus. How does this guarantee that a single value gets accepted? Or how does it aid in that goal?

---

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

# Answer
Let's assume there were more than 1 Majority. Then at least 1 acceptor would contribute to all majorities. This mandates, however, that this acceptor accepts at least 2 different values, a behaviour ruled out by assumption.
> 2 votes

# Answer
The majority requirement ensures that the electorate cannot "go in two directions" simultaneously. E.g. if you had an electorate of 6 priests, and only 3 were required to make a decision, then on one day, 3 priests might be present in the chamber, and pass value 1 for decree *D*, and on the next day, another three, having no knowledge of the prior day, pass a different value 2 for the same decree *D*, leading to inconsistency.

Because with any majority, on the second day, one of the priests was present in the prior decision (and recorded it in his ledger), he can respond to any new proposal with an accept, but include his previously accepted value, which will compel (by the protocol) the proposer to choose it, and not some arbitrary value.
> 1 votes

# Answer
Consensus of a certain value by Praxos is defined to be the value accepted by a majority of the acceptors.

One can view the convenience of using a majority (which has the nice intersection property you mentione din the question) as a motivating factor for defining the consensus as such.

Another reason is that it simply is the go-to option for electing a common value (once we see that using only one acceptor is out of the question).
> 0 votes

---
Tags: algorithms, algorithm-analysis, distributed-systems
---


# Question
Title: What does n with an index 0 mean in defenition of Theta/Big Omega/ Big-oh notation?
We define theta notation as follows: $\Theta(g(n))$ = {f(n): there are exist $c\_1, c\_2$ \> 0 and $n\_0$ such that 0 $\leq$ $c\_1$g(n) $\leq$ f(n) $\leq$ $c\_2$g(n) for all n \> $n\_0$}.

I found an illustration of this statement on Wikipedia, but I cannot figure out what exactly point $n\_0$ means. How should we choose $n\_0$ in practice? If I found, how should I use it?

# Answer
It just means that the condition $0 \le c\_1 g(n) \le f(n) \le c\_2 g(n)$ only needs to hold for large enough integers.

This allows you to ignore all integers that are smaller than $n\_0$ so you can just pick $n\_0$ as large as needed for the inequalities to hold.

Notice that you do not need to pick $n\_0$ as the smallest integer with that property, so you might as well pick one that makes proving the inequalities as easy as possible.
> 2 votes

---
Tags: big-o-notation, notation
---


# Question
Title: Having trouble calculating the asymptotic running time of MAX-HEAPIFY
I don't understand the $T(2n / 3)$ part in the recurrence relation for MAX-HEAPIFY in the book CLRS. There is another post that explains it but I can't realize it.

# Answer
> 1 votes
Suppose that you are running MAX-HEAPIFY on some vertex $v$ of a heap $H$. Then the subtree $H\_v$ rooted at $v$ is also a heap. Let $n$ be the number of vertices of $H\_v$.

Clearly if $v$ has no children or only one (left) children then $T(n) = O(1)$ so let's focus on the case in which $v$ has two children $u$ and $w$, where $u$ is the left child and $w$ is the right child. Let $n\_u$ be the number of vertices in $H\_u$ and $n\_w$ be the number of vertices in $H\_w$.

Clearly the worst case happens when we choose to recurse on the subtree with most nodes between $H\_u$ and $H\_w$. By the properties of the heap we know that $n\_u \ge n\_w$ so we can restrict ourselves to the case in which we recurse on $H\_u$.

The question now becomes: **how large can $n\_u$ be compared to $n$?**

To answer this question let $h\_v$ be the height of $H\_v$. We know that the height $h\_u$ of $H\_u$ must be $h\_v - 1$. Moreover, the height of $H\_w$ can be either $h\_v-1$ or $h\_v-2$ (otherwise $H$ was not a complete binary tree).

The maximum number of nodes in a binary tree of a generic height $h$ is at most $2^{h+1}-1$ (which corresponds to a perfect binary tree binary tree). This tells us that $n\_u \le 2^{h\_u + 1} - 1 = 2^{h\_v} - 1$.

Moreover, the number of nodes in a complete binary tree of height $h$ is at least $2^h$ (where $2^h - 1$ nodes are from a perfect binary tree of height $h-1$ and there must be at least one node on the $h$-th level). This tells us that $n\_w \ge 2^{h\_w} \ge 2^{h\_v-2}$.

We are now ready to find the maximum possible ratio between $n\_u$ and $n = n\_u + n\_w + 1$.

$$ \begin{align\*} \frac{n\_u}{n} &= \frac{n\_u}{n\_u + n\_w + 1} \le \frac{n\_u}{n\_u + 2^{h\_v-2} + 1} = 1 - \frac{2^{h\_v-2} + 1}{n\_u + 2^{h\_v-2} + 1} \\ &\le 1 - \frac{2^{h\_v-2} + 1}{2^{h\_v-1} + 2^{h\_v-2} + 1} = 1 - \frac{2^{h\_v-2} + 1}{3 \cdot 2^{h\_v-2} + 1} \\ & \< 1 - \frac{2^{h\_v-2} + 1}{3 \cdot ( 2^{h\_v-2} + 1)} = 1 - \frac{1}{3} = \frac{2}{3}. \end{align\*} $$

# Answer
> 1 votes
Consider a tree $\mathcal{T}$ at root $\mathcal{r }$, and contain $\mathcal{n}$ nodes and $\mathcal{h}$ be height of $\mathcal{T}$ such that leaves are half full, so, without loss generality, suppose the left sub-tree $\ell$ of $\mathcal{T}$ is a full binary tree (i.e. leaves are half full).

> ***(i)*** Now it's sufficient to show that ratio of $\ell$ to $n$ (i.e. $\frac{|\ell|}{n})$ is $\frac{2}{3}$.

Consequently the worst case of MAX-HEAPIFY happen when we recurse on $\ell$.

For showing (i), first of all, let the number of nodes in $\ell$ is: $$|\ell|=\sum\_{i=0}^{\mathcal{h}-1}2^i=2^h-1$$ The number of nodes in $\mathcal{R}:$ $$|\mathcal{R}|=\sum\_{i=0}^{\mathcal{h}-2}2^i=2^{h-1}-1$$ As a result $$n=|\ell|+|\mathcal{R}|+\mathcal{r }=|\ell|+|\mathcal{R}|+1=3\times 2^{h-1}-1$$ So $$\frac{|\ell|}{n}= \frac{2^{h-1}-1}{3\times 2^{h-1}-1}\leq \frac{2\times2^{h-1}}{3\times 2^{h-1}}=\frac{2}{3}.$$

---
Tags: asymptotics, heaps
---


title: Hashing using Horner’s Rule

text:
# Question
Title: Hashing using Horner’s Rule
When hashing a (key, value) pair where the key is a string, I have seen the following hash function in use:

E.g. $c\_n + 256c\_{n-1}+ 256^2c\_{n-2}+...256^{n-1}c\_1$, where this represents the string $c\_1c\_2..c\_n$. I understand the equation above can be written as: $c\_n + 256(c\_{n-1} + 256(c\_{n-2}+...256c\_1))$, could someone explain how the following is valid, when I have to compute mod over the entire sum, how can we take it term by term?

```
r= 0;
for i = 1 to n do
r := (c[i] + 256*r) mod TableSize

```

# Answer
Let's prove by induction that after $i$ iterations, $$ r = \sum\_{j=1}^i 256^{i-j} c\[j\] \bmod m, $$ where $m$ is the size of the table.

The base case is $i = 0$, where $r = 0 = 0 \bmod m$. Now suppose that the formula holds after $i-1$ iterations. After $i$ iterations, we have \begin{align\*} r &= \left\[ c\[i\] + 256 \left(\sum\_{j=1}^{i-1} 256^{i-1-j} c\[j\] \bmod m\right) \right\] \bmod m \\ \\ &= \left\[ c\[i\] + \sum\_{j=1}^{i-1} 256^{i-j} c\[j\] \right\] \bmod m \\ &= \sum\_{j=1}^i 256^{i-j} c\[j\] \bmod m, \end{align\*} using several times the formulas $$ (a + b) \bmod m = \left\[(a \bmod m) + (b \bmod m)\right\] \bmod m, \\ (ab) \bmod m = \left\[(a \bmod m)(b \bmod m)\right\] \bmod m. $$

For the proofs of these two formulas check: this and this.
> 9 votes

---
Tags: hash
---


# Question
Title: Obtaining a set of $O(\log n)$ classifiers using multiplicative weights algorithms
I'm trying to find an algorithm that uses the multiplicative weights algorithm to obtain a set of $O(\log n)$ classifiers that classify a set $X=\\{x\_1, x\_2, ...,x\_n\\}$ where the set of labels is $l \in\\{0,1\\}.$

The original question goes as follows:

> Suppose we have a set $X=\\{x\_1,...,x\_n\\}$, each with a label $l\_i\in \\{0,1\\}$, an hypothesis class $H$ and a learning algorithm $A$ that for every distribution $D$ on $X$ outputs a classifier $h\in H$, such that $P\_{i\sim D}\[h(x\_i)=l\_i\]\geq 0.51$. Show an algorithm that produces a set of $T= O(\log n)$ classifiers $h^{(1)},h^{(2)},...,h^{(T)}$, such that the majority vote among these $T$ classifiers yields the correct label for all $1 ≤ i ≤ n$.

My idea was to use multiplicative weights where each example $x\_1,...,x\_n$ is an expert and the initial weight for each one is $w\_i^{(1)}=1$, and $p\_i^{(1)}=\frac{1}{\Phi^{(1)}}=\frac{1}{n}$, where $\Phi^{(t)} = \sum\_{i=1}^n w\_{i}^{(t)}$. In each iteration of the algorithm we run the learning algorithm $A$ and use the output $h$ to determine $\sum\_{i=1}^n {p\_i^{(t)}h(x\_i)}$ and act accordingly just like in the classic multiplicative weights algorithm. We update the distribution of our experts $p\_{i}^{(t+1)}=\frac{w\_i^{(t+1)}}{\Phi^{(t+1)}}$ and their weight: $w\_i^{(t+1)} = w\_i^{(t)}e^{\epsilon l\_i\cdot h(x\_i)}$ which means giving more weight to examples the classifier made an error on, and leaving the weights of correctly classified examples unchanged, thus increasing the probability of falsely classified examples to the point where their accumulated mass is at least $0.51\Phi$ and then we feed that new distribution $\bar{p}$ to the algorithm $A$ in the next iteration and the classifier we get will certainly be right on some of them. What I'm still struggling with is how do I know that at some point there's a majority among the classifiers produced so far that classify each example correctly?

# Answer
At each step, you are dividing the weights of correctly labelled elements by $e^{-\epsilon}$, and multiplying the weights of wrongly labelled elements by $e^{\epsilon}$. If a $p \geq 1/2 + \delta$ fraction of elements were labelled correctly and the current total weight is $\Phi$ then the new total weight is $$ (e^{-\epsilon} p + e^\epsilon (1-p)) \Phi \leq (e^{-\epsilon}(1/2+\delta) + e^{\epsilon} (1/2-\delta))\Phi = (1-2\delta \epsilon + O(\epsilon^2)) \Phi. $$ For small enough $\epsilon$, this is at most $\rho \Phi$, for some constant $\rho \< 1$.

Initially, $\Phi = n$. After $t = C\log n$ iterations, $\Phi$ drops to $\rho^t \Phi \< 1$ (for an appropriate choice of $C$). This means that all weights are less than $1$. If $a$ of the classifiers are correct on an element and $b$ are incorrect, then its total weight is $e^{(b-a)\epsilon}$. Since all weights are less than $1$, we see that $b \< a$, and so a majority of the classifiers are correct on the element.
> 1 votes

---
Tags: algorithms, learning-theory
---