title: Building a Hyper Computer

text:
# Question
Title: Building a Hyper Computer
I had an idea for a theoretical super computer. Supposing, one was able to optimise(or significantly increase efficiency) all algorithms used in most computing tasks(An open source project on algorithm optimisation maybe? The system design is being optimised from the barest tools, the "axioms" of the RAM model(algorithms for file access and basic arithmetic operations will be optimised) all the way to the most complicated algorithms. Supposing one were to then develop a language that implemented these algorithms most effectively and had the best performance with the algorithms(A language was designed for the express purpose of getting the best performance possible out of the algorithms with no constraints based on the target machine). Suppose this was also a high level language like C++.

I hypothesised that one would be able to vastly increase the speed of the system, by designing entirely new architecture to effectively run programs built in this language. A sort of Hardware level compiler(By hardware level compiler, I was referring to architecture design, that can execute the program's source code through native hardware configurations. The hardware is designed ***for*** the language and ***NOT*** the other way round(which is what I thinks happens in with modern architectures).

An OS built on this language will be much faster on that hardware, but will lose portability. But gain a lot of speed. (I feel the tradeoff is worth it).

I have $3$ questions.

$(1.)$ Is my proposal feasible.

$(2.)$ Is my hypotheses correct.

$(3.)$ What magnitude of speed increases is **feasibly** possible.

# Answer
> 6 votes
You fundamentally misunderstand what a compiler is.

A compiler is just a translator: it transforms programs in one language (usally high level source code) into another language (machine code, assembly, LLVM, JavaScript, etc.)

A compiler can optimize code, and output code specialized for specific hardware, but what's important is, *that is completely independent of where the compiler is run*.

This means there is *literally no* difference in the quality of outputted code between a compiler that runs in software, and the same compiler running in hardware. A compiler is just a transformation, and whatever implements that transformation doesn't affect the quality of its output.

Answering your specific questions:

1. No, it's not feasible, and it's not even well specified. "Supposing, one was able to optimise(or significantly increase efficiency) all algorithms". What does that even mean? Why do you think such a thing exists?

Likewise, a language might be fast at implementing some algorithms, and slow at others. And a high-level language like C++ will always have some performance tradeoffs compared to expert-written assembly (although optimizers are crazy good at this).

Performance is not an absolute. There isn't necessarily a "most efficient" algorithm for all inputs, and there certainly isn't a "fastest language".
2. Your hypothesis is not correct, for the reasons I said above. Running a compiler on hardware doesn't improve the outputted code.

As for optimizing for specific hardware, this is already possible, and compilers already do this.
3. There's no way to determine this logically. You just have to experiment, especially since speed of code depends heavily on things like cache-misses, pipelining, branch-prediction, etc. These are all hard to reason about on paper.

# Answer
> 2 votes
TL;DR:
Your *approach* is valid (looking at the question benevolently: *What if* parts that can be identified to contribute to *experienced data processing performance* could be significantly improved) - that is what CS is about since at least Bletchley Park and Colossus, if not Babbage.
Your hypotheses have been put forward, and some have been dismissed (along with conclusions like *vastly increase the speed*). E.g., part of complexity analysis is establishing *lower* bounds for *any* algorithm for a given problem (using a specified machine model - RAM for starters, with useful *quantum computing hardware* feasible RSN). If an algorithm is known to have worst case performance coincide with the lower bound, *significance* of further improvement is debatable - but see the history of *sorting* \- mechanised radix sorting was popular decades before general purpose computers were created, the topic is hot a century after.
Another part is comparing models of computation (sometimes by types of (abstract) machines, e.g. Turing and RAM), leading to insights like the equivalence of many variants (accumulator, register, stack machines; "von Neumann" and Harvard,…)

There has been concern about a *semantic gap* between "high level" programming languages and computing hardware - attempts to close it led to the notion of *semantic clash*.
For ideas, look at *FORTH machines* (e.g. *Novix N4000*) and the history of the Intel iAPX 432 (same time frame - coincidence?).

(Another idea is: It takes intelligence and expert knowledge to improve data processing: let's create AI and Expert Systems, set them at improving data processing and lay back to dreams of machines taking over.)

# Answer
> 2 votes
To some extent such machines already exist – FPGA-based supercomputers. FPGAs are programmable hardware which can be tuned to the algorithm being executed.

In a similar vein, GPUs are specialized hardware originally designed for graphics, but now also used in other domains, being much more cost-effective than CPUs for some specific purposes.

In the past, Borroughs produced several CPUs which were optimized for specific languages such as ALGOL 60.

---
Tags: algorithms, formal-languages, optimization, asymptotics
---


# Question
Title: Parameterized vertex cover on $r$-regular graphs
I am trying to solve the following exercise from this book:

> Show that CLIQUE PROBLEM, parameterized by the solution size $k$, is Fixed-parameter tractable (FTP) on $r$-regular graphs for every fixed integer $r$.

Here, the CLIQUE PROBLEM is given a instance $(G, k)$, decide whether $G$ has a clique of size $k$ or not.

First of all, for an instance $(G, k)$, if $k \> r+1$, then the answer is NO, because each vertex is connected with exactly $r$ elements, the maximum size of a clique is $r + 1$ (vertex plus $r$ neighbours). So, we can assume that $k \le r+1$.

Let $N(v)$ be the set of neighbours of $v$.

I thought of that simple algorithm

.... for each vertex $v \in V(G)$

........ check if for any subset $X \subset N(v)$, such that $|X| = k - 1$, $X \cup \\{v\\}$ is a clique.

Since there is only $\binom r k$ such subsets $X$ for each vertex and we take time polynomial in $k$ to check if $X \cup \\{v\\}$ is a clique, then, this algorithm is already a FTP and is of the form $\left( k^{O(1)}\binom{r}{k} \right)n$.

If everything is right, them I have solved the exercise. However, the next thing I have to do in the exercise, is to show that this problem is also a FTP considering the parameter $k + r$ (so, $r$ is no longer seen as a constant), and the same algorithm works in this case. Since I was expecting to face a harder exercise in this case of $k + r$, I started to think my solution is not right.

So, what is wrong?

# Answer
> 3 votes
There's nothing wrong with your solution, the exercise is just easier than you expected.

Your analysis correct, apart from missing out the $-1$, so it should be $k^{\mathcal{O}(1)}\cdot\binom{r}{k-1}\cdot n$, which is, of course, of the required form $f(k+r)\cdot n^{\mathcal{O}(1)}$, and the $-1$ doesn't really change anything.

The biggest mistake is writing $\mathrm{FTP}$ instead of $\mathrm{FPT}$. The first is a protocol, the second is a complexity class.

Moving to pure speculation, I would guess the authors were, in the second part, simply looking for reinforcement of the difference between $\mathrm{FPT}$ and in class $\mathrm{X}$ for every fixed value of some parameter (in this case, something like $f(k)\cdot n^{r}$ would work for the first part of the exercise, but not the second. The Hitting Set problem, as an example, has such an algorithm, where the parameter $k$ is the size of the solution, and $r$ is the size of the input sets; it's in $\mathrm{FPT}$ for every fixed $r$, but not in $\mathrm{FPT}$ for parameter $k+r$).

# Answer
> 1 votes
Your answer is correct, since your algorithm indeed runs in time $\binom{r}{k}n$.

Let us go the extra mile and take a moment to think about the worst case input to your algorithm, and see if we can manage to write the running time as $f(r)n$ or $f(p)n$, to show that the algorithm is FPT. Of course, this is not necessary to determine that the problem is FPT, it is just a sanity check, say, to see if there are any surprises: if the algorithm is FPT then it must *also* be FPT on the hardest instances.

**The case when $r$ is fixed.** In this case, the worst case for $\binom rk$ is when $k=\frac 12r$, in which case $\binom rk=\binom r{\frac 12r}n\approx 2^{r}\frac 1{\sqrt r}n$. Indeed, we can write this as $f(r)n$ with $f(r)=2^r/\sqrt r$, so the algorithm is FPT.

**The case when $r+k=p$ is fixed.** Some math shows that the worst case is when $r$ takes the value $$r=\left(\frac 12+\frac 1{2\sqrt 5}\right)p\approx 0.724p, \quad \text{ so }k\approx 0.276p$$ The running time of your algorithm becomes $\binom{0.724p}{0.276p}n $. If we write $f(p)=\binom{0.724p}{0.276p}\approx 1.62^p$, then the running time of the algorithm is $f(p)n$, so the problem is FPT.

---
Tags: complexity-theory, graphs, clique
---


title: Expressive power of formal systems

text:
# Question
Title: Expressive power of formal systems
How do we classify formal systems' (propositional logic, first-order logic, second-order logic, higher-order logic, Hoare logic and type theory) expressivity?

In the same way that grammars (CSG, CFG, ...), languages (CSL, tree-adjoining language, ...) and abstract machines (Turing machine, ...) 'fit' into the Type 0-3 range of the Chomsky hierarchy, can we also classify the formal systems into it?

Or, is there another yardstick for describing the relative expressive power of formal systems?

# Answer
> 4 votes
Comparison of logics is a complicated subject.

Expressive power of logics can be 'measured' in various ways. The most well-known approach is that of **conservative extensions**. If $L$ is a logic with signature $\Sigma$, then a logic $L'$ over signature $\Sigma' \supseteq \Sigma$ is a conservative extension of $L$ provided every $\Sigma$-formula $\phi$ that is provable in $L'$ is already provable in $L$. In other words, conservativity means that by moving from $L$ to $L'$ we are not adding expressive power to the discourse about things that can be expressed in $\Sigma$.

Things become more complicated when you are looking at logics with signatures that are not comparable by $\subseteq$. When you want to compare e.g. set theories with type theories, then you won't get a nice match of signatures. In this case you need to look at encodings. This can be done in various ways. For example you can encode formulae, or formulae an proofs. You can study properties of those encodings (e.g. do they preserve formula/proof structure) etc?

An old example of encoding is Gödel's and Gentzen's double-negation translation that embeds classical logic into intuitionistic logic, and reduces the consistency of the former to that of the latter.

Comparison of programming languages is even more complicated and -- kind of, sort of -- contains the comparison of logics as a special case by the Curry–Howard correspondence.

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


# Question
Title: Reflexive transitive closure = (zero or more) Kleene star?
In Alloy Tutorial they denote some reflexive transitive closure with Kleene star saying that they admit zero or more elements at that position.

```
  // File system is connected
  fact {
    FSObject in Root.*contents
  }

```

> In Alloy, in can be read as "subset of" (among other things). The operator "\*" denotes reflexive transitive closure. Thus, this fact says that the set of all file system objects is a subset of everything reachable from the Root by following the contents relation zero or more times.

Reflexive Transitive Closure *

> In Alloy, "\*bar" denoted the reflexive transitive closure of bar. It is equavalent to (iden + ^bar) where ^ is the (non-reflexive) transitive closure operator.

Can you explain the closure and star operators such thut it becomes obvious that they are identical?

# Answer
(Note: I'm not 100% sure about the Alloy syntax since I never used it -- what follows is accurate on the general principles but the syntax could be slightly different)

Basically, `S.*bar` means starting from `S` and using `.bar` any number $n\geq 0$ of times.

Instead, `S.^bar` means starting from `S` and using `.bar` any positive number $n \> 0$ of times.

It is immediate to see that `S.^bar` is equivalent to `S.bar.*bar` since the latter denotes zero or more steps after a first step, hence one or more steps.

If the language allows `S.iden` to mean "zero steps from `S`", and `+` to denote union, then we can also write `S.^bar` as `S.(iden + ^bar)` which can be read as "zero steps or (one step or more)" which is the same thing as "zero or more steps".

---

In the underlying theory, one can define the reflexive and transitive closure of a relation $R \in \mathcal{P}(A\times A)$ as the smallest relation $R^\* \in \mathcal{P}(A\times A)$ satisfying

$$ R^\* = I\_A \cup R \circ R^\* $$

where $I\_A$ stands for the identity relation. The existence of the smallest $R^\*$ is guaranteed by the Tarski fixed point theorem (on the complete lattice of the relations). According to the Kleene fixed point theorem (and a few minor simplifications) one can also write it as $$ R^\* = \bigcup\_{n\geq 0} R^n $$ where $R^n$ denoted the self-composition of $R$ for $n$ times.
> 1 votes

---
Tags: terminology, closure-properties, kleene-star, transitivity
---


# Question
Title: Online algorithms and changing past decisions
We know that for some online problems, algorithms can decrease their competitive ratio greatly if they are allowed to change some of their past decisions (see http://epubs.siam.org/doi/pdf/10.1137/1.9781611973402.35).

I wonder if there are instances of online problems such that the competitive ratio does not decrease even if the algorithm is allowed to change its decisions ?

# Answer
Every problem where the online algorithm is optimal, i.e. has competitive ratio 1, is a (trivial) example. Such algorithms exist, for example for some scheduling problems.
> 1 votes

---
Tags: algorithms, optimization, reference-request, online-algorithms
---


# Question
Title: How is this expression a valid lambda expression?
Can you explain how this expression follows the grammar of the lambda calculus?

$$\lambda x.x((\lambda y.yy)x)x = λx.x(xx)x$$

I am not sure why we have the parentheses following the $.x$ (on both sides of the equation).

# Answer
When in doubt, write down a lot of parentheses: $$\lambda x . ((x ((\lambda y . ((y y) x)) x)) x)$$ and $$\lambda x . ((x (x x)) x)$$ In $\lambda$-calculus there is the convention that $A B C$ is understood to be $(A B) C$, that is, application associates to the left. So, if somebody wants to $A (B C)$ instead, they have to put in some parentheses.
> 5 votes

---
Tags: lambda-calculus
---


# Question
Title: It's necessary to replace all the population each generation in a genetic algorithm?
I'm creating a timetable generator using GA's, and I'm stuck in the crossover part.

Each generation, I just basically copy the best individuals (the 50% fittest individuals inside the population), and perform my crossover operator between them.

I'm using a 2 point crossover. I represent all my TT courses as a List. Each course has an assigned teacher, and an assigned position. The position is the index inside a 2D array. The first dimension represents times and the second represents classrooms.

When I perform the crossover, I choose a middle point inside the Course's list of each parent. Then I create 2 individuals mixing this Course's. If there are overlaps or other constraint violation, I repair the new individual.

My question is this, How can I ensure an optimal offspring?

Sometimes after the crossover and/or after the repair, the new offspring is not better than his parents. This makes the population gets stuck in high fitness values (I'm minimizing the errors, so, a low fitness score means a good individual), so, the GA never reach an optimal solution.

I've been reading an article about copy the fittest individuals in to the next generation, then perform the crossover, but I don't know if this is correct.

# Answer
GAs are heuristic algorithms. They don't guarantee optimality in any but the most trivial problems. Hence there are no strict rules how to implement them. What works and what doesn't depends your exact problem. Tuning the parameters of a GA is somewhat of a dark art and people turn to heuristics for tuning their heuristics.
> 1 votes

# Answer
Heuristics don't guarantee optimizality, so, there is no way to know if your implementation will find the optimal of your problem everytime, and the only way to know how good is your heuristic, is to compare it against an exact algorithm for a good number of problems.

With that said, there are a lot of variations of Genetic Algorithms, and your first concern is about what is called Elitism, that is carrying over the best individuals from the population into the next generation.

There are other techniques, and varying them may lead you to get better results, but as @adrianN said, it's an art by itself.

For more information, a quick look at Wikipedia Genetic Algorithms page will give you some insight.
> 0 votes

---
Tags: optimization, genetic-algorithms, constraint-satisfaction
---


title: What is a super universe?

text:
# Question
Title: What is a super universe?
I'm reading this well-known paper *On Universes in Type Theory*. At first I expected something similar to `Setω` in Agda, but it turns out that it's even something more general. It seems to generalize the universe construction from a plain inductive-recursive type to a binder (similar to $\Pi$ and $\Sigma$). The main question I want to ask is, what's the intention behind it?

Here's some Idris code defining usual Tarski-style universes:

```
mutual

  public export data U : (level : Nat) -> Type where
    GroundU : Ground -> U level
    BinderU : Binder -> (a : U level) -> (b : (x : T {level} a) -> U level) -> U level
    UnivU   : U (S level)
    LiftU   : U level -> U (S level)

  public export T : {level : Nat} -> (code : U level) -> Type

```

I'm trying to generalize it into something like

```
mutual

  public export data U : (a : Type) -> (b : (x : a) -> Type) -> Type where
    GroundU : Ground -> U a ???
    ...

```

What should `???` be? The author of the paper just said universes should be closed under set formers.

edit: I think `???` is simply `b` ...

# Answer
> 11 votes
One intention behind having a universe operator and a super-universe closed under it, is to give a type-theoretic version of large cardinal axioms known from set theory. An inaccessible cardinal is like a type-theoretic universe. The next interesting kind of cardinal is a Mahlo cardinal. Speaking intuitively, a Mahlo cardinal is one that has "a whole lot" of inaccessible cardinals below it. What would this be in type-theoretic terms? It ought to be some sort of a universe $U$ with lots and lots of universes in it. This is what Palmgren is addressing when he considers super-universes.

There is also a more practical side to having many universes. It is useful to have inductive-recursive types in type theory, for all sorts of purposes. But they let us define new universes, so the question is *how many*? To get a feel for what Palmgren is doing, instead of shooting for the super-universe right away, try the following sequence of constructions in Agda (using induction-recursion):

1. Define one universe $U\_0$, containing (a code of) $\mathbb{N}$ and closed under $\Pi$ and $\Sigma$. This kind of universe corresponds to an inaccessible cardinal.
2. Define an operator $U$ which takes any type $A$ and defines a universe which contains (a code of) $A$ and is closed under $\Pi$ and $\Sigma$. This sort of universe operator is akin to Grothendieck's axiom of universes. How many universes can we get by repeatedly applying $U$, starting from $\mathbb{N}$?
3. To get even more universes, we postulate a *super-universe* $V$ which contains lots of universes, as follows:

* $V$ contains $\mathbb{N}$, and is closed under $\Pi$ and $\Sigma$
    * Given (code of) a type $A : V$ and a family $B : A \to V$, there is a universe $U$, which is an element of $V$, it contains all types of the family $B$, and is closed under $\Pi$ and $\Sigma$.

How many universes does $V$ contain? Note that we can get a family $B : \mathbb{N} \to V$ such that $B(n)$ is the $n$-th universe, and so $V$ must contain a universe $U\_\omega$ which contains all of these. And this is only the beginning!

---
Tags: lambda-calculus, type-theory
---


# Question
Title: Pumping lemma for $\{110^n10^{n-m}1^m: 1\le m<n\}$
How can I prove that the language $L=\\{110^n 10^{n-m} 1^m \mid 1 \le m \< n \\}$ is not regular using pumping lemma?

I chose the word $w = 110^{2p} 10^{2p-q} 1^q$ to prove the non-regularity. Then I started partitioning the word to $xyz$ with $|y| \ge 1$, $|xy| \le p$ and for each $i\ge 0$, $xy^iz$:

\begin{align\*} x &= 110^r\\ y &= 0^s\\ z &= 10^{2p - q} 1^q\\,, \end{align\*} where $r + s = p$ and $s \> 0$.

The second partition: \begin{align\*} x &= 1\\ y &= 10^{2p}\\ z &= 10^{2p-q}1^q\\,. \end{align\*}

However, I got stuck at this point because I am not really sure how to find the other partitions and how the choose the correct $i$ for those which I already have. Any help with this will be appreciated.

# Answer
> 1 votes
You're basically there. Taking $w=110^{2p}10^{2p−q}1^q$, there are actually three cases (you missed the first one).

1. $x=\varepsilon$, $y=110^{p-2}$, $z=0^{p+2}10^{2p-q}1^q$.
2. $x=1$, $y=10^{p-1}$, $z=0^{p+1}10^{2p-q}1^q$.
3. $x=110^r$ for some $r\in\\{0, \dots, p-3\\}$, $y=0^{p-r-2}$, $z=0^{p+r+2}10^{2p-q}1^q$.

In all three cases, taking $i=0$ means that the string $xy^iz$ is not in $L$. I'd suggest trying $i=0$ and $i=2$ as your first two guesses in pumping lemma proofs – one of them usually works.

Notice that nothing above actually depends on the choice of $q$, so you can simplify things very slightly by just taking $q=1$ (or any other fixed, legal value).

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


title: Asymptotic bounds on geometric sums

text:
# Question
Title: Asymptotic bounds on geometric sums
So I'm doing exercises from Dasgupta's Algorithms. The exercise i'm having trouble with is:

> Show that, if $c$ is a positive real number, then $g(n) = 1 + c + c^2 +...+c^n$ is:
>
> 1. $\Theta(1)$ if $c\<1$
> 2. $\Theta(n)$ if $c=1$
> 3. $\Theta(c^n)$ if $c\>1$

(I dont know if this is a hint but it is included in the text: "The moral: in big-$\Theta$ terms, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly indreasing or the number of terms if the series in unchanging")

The only one that makes sense for me is 2) where $1+1^2+..+1^n$ is the same as $n+1$, and removing the 1 gives $O(n)$. I dont know if my reasoning makes sense, but thats all i've got. I have no idea where to start or how to think on the other two. Any suggestions?

# Answer
> 1 votes
Hints:

* In the first case, use the inequalities $$ 1 \leq \sum\_{i=0}^n c^i = \frac{1-c^{n+1}}{1-c} \leq \frac{1}{1-c}. $$
* In the second case, use the inequalities $$ c^n \leq \sum\_{i=0}^n c^i = \frac{c^{n+1}-1}{c-1} \leq \frac{c}{c-1} c^n. $$

# Answer
> 1 votes
For an intuition of the first case, start with a decreasing geometric sum with an infinite number of terms. Calculate $c \cdot g(\infty) = c + c^2 + \ldots$, and $g(\infty) - c \cdot g(\infty) = 1$, so $g(\infty) = 1/(1-c)$. Clearly $g(n) \leq g(\infty)$ for any positive $c$, and so the entire series (infinite or finite) asymptotically matches the first term.

For an intuition of the 3rd case, take the sum to be $1 + d + d^2 + \ldots + d^n$, where $d\>1$, and then let $c = 1/d$, so $c\<1$. Now, $1 + d + d^2 + \ldots + d^n = d^n(c^n + c^{n-1} + c^{n-2} + \ldots + 1)$. That parenthesized sum on the right is your finite decreasing geometric series from the first case (in reverse order), which grows asymptotically like $\Theta(1)$, so your entire term grows like $d^n$, the last term of the finite sum.

---
Tags: asymptotics, landau-notation
---


# Question
Title: Bridge theorems for group theory and formal languages
> Is there some natural or notable way to relate or link math groups and CS formal languages or some other core CS concept e.g. Turing machines?

I am looking for references/applications. However note that I am aware of the link between semigroups and CS languages (namely via finite automata). (Does this literature on semiautomata ever look at "group-automata"?)

I have seen one paper many years ago that might come close, that converts TM transition tables into a binary operation, possibly sometimes a group in some cases, conceivably based on some kind of symmetry in the TM state table. It didn't explore that in particular, but also didn't rule it out.

Also, in particular, regarding the large body of math research on classification of finite groups, does or could it have any meaning or interpretation in TCS? What is the "algorithmic lens" view of this massive edifice of mathematical research? What is it "saying" about a possible hidden structure in computation?

This question is partly inspired by some other notes e.g.:

# Answer
> 13 votes
Let me first answer your subquestion: *Does the literature on semiautomata ever look at "group-automata"?*. The answer is yes. In his book (Automata, languages, and machines. Vol. B, Academic Press), S. Eilenberg gave a characterization of the regular languages recognized by finite commutative groups and $p$-groups. Similar results are known for finite nilpotent groups, soluble groups and supersoluble groups.

Finite groups also play an important role in the problem of finding a complete set of identities for regular expressions. An infinite complete set was proposed by John Conway and this conjecture was ultimately proved by D. Krob. There is a finite number of "basic" identities, plus an identity for each *finite simple group*. See my answer to this question for references.

In the opposite direction, finite automata theory lead to an elementary proof of basic results on combinatorial group theory, like the Schreier formula. Based on Stallings's seminal paper Topology of Finite Graphs.

Also in the opposite direction, automatic groups are defined in terms of finite automata.

Profinite groups also play an important role in automata theory. An example is the characterization of the regular languages recognized by transition-reversible automata with possibly several initial and final states.

For a very nice connection between context-free languages, groups and logic, see the article by David E. Muller and Paul E. Schupp, Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems.

# Answer
> 11 votes
Barrington's famous theorem reduces computation in NC$^1$ to computing iterated products in the group $S\_5$ (or $A\_5$, or indeed any non-solvable group). There is also a connection to leakage-resistant computation, in Shielding Circuits with Groups by Miles and Viola (2012).

Regarding the classification of the finite simple groups, as far as I remember it is implicitly used in some algorithms for group isomorphism, a problem related to graph isomorphism.

# Answer
> 11 votes
A famous area of study in the theory of group presentations is the word problem for groups. A group presentation is given by a bunch of generators $g\_1, ..., g\_m$ and a bunch of equations $a\_1 = b\_1, ..., a\_n = b\_n$ that the generated group needs to satisfy. Now given two words $x, y \in \\{g\_1, ..., g\_m\\}^\*$, i.e. two strings over the alphabet $\\{g\_1, ..., g\_m\\}$, it makes sense to ask if $x = y$ holds in the generated group. This is the *word problem*. Can we decide the word problem mechanically? This was a long-standing open problem, solved negatively in 1955: there is a finitely generated (in fact, a finitely presented) group G such that the word problem for G is undecidable. However, for many classes of groups the word problem is decidable, e.g. finite groups and braid groups.

There are many deep results giving conditions for classes of groups having solvable word problems. It is also interesting to study the complexity of deciding word problems (for classes of groups that have a decidable word problem), see e.g. here.

# Answer
> -1 votes
With Google, I found the paper *Relatively free profinite monoids: an introduction and ex- amples, in Semigroups, Formal Languages and Groups* by Jorge Almeida (English translation in *Journal of Mathematical Sciences*, **144**(2):3881–3903, 2007) on this subject.

---
Tags: formal-languages, reference-request, automata, discrete-mathematics, group-theory
---


title: Justify the following running time

text:
# Question
Title: Justify the following running time
The book "Cracking the Coding Interview , 6th ed." describes the following method to sum the values of all nodes in a balanced binary search tree, and also claims that this method runs in O(n) time.

```
int sum(Node node) {
    if (node == null) {
        return 0;
    }
    return sum(node.left) + node.value + sum(node.right);
}

```

It seems to me that this method iterates through every node in the tree exactly once, **plus one null reference for each leaf in the tree**. I would say that n is the number of nodes in the tree, and we visit O(n+b) nodes (where b is the number of leaf nodes, is the number of null nodes traversed) and do constant work there.

How can n be an upper bound if we visit (or attempt to visit) more than n nodes? You might argue that b is constant and so we drop it, but b grows proportionally to n.

Please don't mark this as a duplicate just to get your internet points. Specific questions have specific answers.

# Answer
The book is correct, because $b\leq 2n$, so you visit no more than $3n$ nodes, which is $O(n)$, and $b\leq 2n$ because no node has more than two leaves. You correctly say that $b$ grows proportional to $n$, which is exactly the key.

Just for clarity, Big-Oh notation means "grows proportional to, ignoring constant factors" (roughly), which is why we say that $3n\in O(n)$, even though one is a multiple of the other, and $6n^2+3n+42\in O(n^2)$ and $42e^n\in O(e^n)$, for example.

(actually, $O(n)$ means, "is not more than $cn$". For "is proportional to $n$", use $\Theta(n)$ instead of $O(n)$).
> 3 votes

---
Tags: time-complexity
---


# Question
Title: Propositional logic and connectives(translating to english)
I want to know some stuff about translating compound statements to english:

For the propositions below:

p: You have the flu. q: You miss the final examination. r: You pass the course.

I want to know how to translate the following compound proposition to english:

```
1). p or q or r.

I tried something like this:

You have the flu or you miss the final examination or you pass the course.

```

I was just wondering about the usage of commas.

```
2). (p implies not r) or (q implies not r)

I tried something like this:

If you have the flu, then you do not pass the course, or if you miss the final examination, then you do not pass the course.

```

Again, I was wondering about the comma usage.

Can someone please help?

# Answer
The first thing to say is that in propositional logic every statement will have a truth value.

If (P or Q or R) evaluates to True (which it doesn't have to) then a natural English way to translate would be:

> Either you have the flu, you miss the final examination or you pass the course.

Note that this "or" is clearly inclusive - meaning that it is possible that *more than one* of those things happens but *at least one* must. To make that clear beyond doubt in natural English you might structure the sentence using "at least". This will be much more long winded but avoids the person you are communicating with thinking that you might mean exclusive "or" (e.g. the type of "or" used in "true or false" - it can be one or the other but not both). If you wanted to account for this you might say something like:

> At least one of the following is true: you have the flu, you miss the final examination or you pass the course.

For your second case what you said is not very natural. You would typically hear someone say:

> You won't pass the course if you have the flu or miss the final examination.

If you are supposed, for whatever reason, to structure the answer as you did, the commas should be removed after your "if" clauses. This would be better:

> If you have the flu then you do not pass the course, or if you miss the final examination then you do not pass the course.
> 2 votes

---
Tags: logic, propositional-logic
---


# Question
Title: Is the simulation of how a warehouse functions (eg Amazon) a discrete event simulation problem
If i wanted to write a piece of software that simulated a warehouse where typical warehouse procedures occur eg

* loading of trucks onto conveyors
* goods being transported around a warehouse by machines
* goods being packed by operatives
* goods being picked by operatives ... etc

should this be modelled / is this known as a discrete event simulation problem or a continuous event simulation problem.. or both?

# Answer
Like many real-world models, this type of situation can be modeled both continuously and discretely. For example, if you defined the problem as a series of equations defining the rates at which items arrived and departed it would be continuous, but if you modeled it at a more microscopic level, showing individual arrivals and departures of trucks, it would be discrete. Then, going further, if you were to model the actual acceleration of the trucks as they departed the loading bay, it would become continuous again.

In general, job shop-type simulations are usually modeled as a series of discrete events. You may want to refer to queuing theory.

Note that there is an open source project called Facsimile that does discrete event simulation and is intended to do the kind of simulation you are aiming at. There are also a lot of commercial systems that specifically do industrial logistics and job shop simulation; for example AnyLogic is one such package.

You can also use generic simulation languages like Modelica to create the simulation.

In general, it is good idea to use simulation software rather than write your own simulation in many cases because there are many subtleties to it that you would not expect. Using an existing simulation package you can create your simulation in a fraction of the time it would take to program it and the result is potentially much more reliable with less risk of bugs.
> 4 votes

---
Tags: simulation
---


# Question
Title: Can local variables be instance variables?
I know that variables can be categorized in two ways:-

**The first way is to classify them into global and local variables** based on their scope. When the variable is accessible by all the functions of an instance of a class then it is known as a global variable and when it is accessible only within a block of code in an instance of a class it is known as local variable.

**The the second way is to classify them into class/static variable and instance/non-static variable**. Class/static variables are those variables which belong to the class and only one copy of these variables exist for all instances of the class and it is shared by them. Instance local variables are those variables which belong to the instance of the class and for which a separate copy is created for each instance.

My instructor says that instance variables can only be declared outside functions. Why is this so? Can local variables not be instance variables?

# Answer
> 1 votes
Your instructor is right.

Instance variables refer to to variables that are defined in a class, where **every instantiated object has a separate copy of the variable.** For this to be true, it must be a variable within a class but outside any method- so that it is accessible by every method in the class.

A local variable cannot be an instance variable because of this reason. Local variables must exist in a method, constructor, or some other block.

---
Tags: data-structures, java
---


# Question
Title: Given a vertex, find a path between it and each other vertex that minimizes the maximum weight in the path
I'm revising for an upcoming exam and was wondering if someone could help me with a practice problem:

> We model a set of cities and highways as an undirected weighted graph $G = (V,E,l)$, where the vertices $V$ represent cities, edges $E$ represent highways connecting cities, and for every undirected edge $e = \\{v, w\\}\in E$ the number $\ell\[e\]$ denotes the number of litres of fuel that your motorcycle needs in order to ride the distance between cities $v$ and $w$. There are fuel stations in every city but none on the highways between the cities. Therefore, if the capacity of your motorcycle's fuel tank is $L$ litres, then you can only follow a path (a sequence of adjacent highways), if for every highway $e$ on this path, we have $L\geq \ell\[e\]$, because you can only refuel in the cities.
>
> Design an algorithm with a running of time of $O(m\log n)$ that, given an undirected weighted graph $G=(V,E,\ell)$ modelling a setting of cities and highways, and a city $s \in V$ as inputs, computes for every other city $v \in V$, the smallest fuel tank capacity $M\[v\]$ that your motorcycle needs in order to be able to reach city $v$ from city $s$.

I'm not sure how to solve this problem, but I do have a few ideas. I thought of possibly running Kruskal's algorithm since that would give me the MST of the graph. I'm not sure how I would then efficiently get the answer I need to produce.

Alternatively, I was thinking of using dynamic programming in some way since that's one of the things that we use a lot in the course, but I'm not really sure how to go about it.

# Answer
Let $T = \\{s\\}$, and let $Q$ be a new empty priority queue. Insert each edge incident on $s$ in $Q$. While there are still nodes with $d$ from $s$ yet to be computed, extract and remove the minimum from $Q$.

If such edge connects a node $u$ in $T$ with a node $v$ not in $T$, add each edge incident on $v$ that still isn't in $Q$ to $Q$, then set $M\[v\]$ to $\max\\{M\[u\], w(u, v)\\}$.

Otherwise, disregard the extracted edge and extract more edges until you find a suitable one.

The overall complexity is $O(|E| \log |E|) = O(|E| \log |V|^2) = O(|E| \log |V|)$.

To informally prove correctness, we can observe that whenever we set $M\[v\]$ to a certain value $x$, we can certainly reach $v$ from $s$ with a path in which each edge weighs at most $x$. On the other hand, no better path exists, because we already gave each edge lighter than $x$ a chance to connect to $s$.
> 0 votes

# Answer
It's modification of Dijkstra algorithm. In Dijkstra you take minimum of distance from beginning to visited plus distance to not visited adjacent, here you take minimum of max { visited, not visited adjacent }.
> 0 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Efficient Algorithm Linear Temporal Logic to Deterministic Rabin Automata
I am trying to construct an equivalent Deterministic Rabin Automata (DRA) given a Linear Temporal Logic (LTL) Formula. One (expensive) way to do this would be to construct an equivalent Non-deterministic Buchi Automata and then determinize it using Safra's construction.

I am interested to know whether there exist efficient algorithms which can 1. Directly construct DRA from LTL without intermediate NBA construction. 2. Are there any existing tools to do this.

\[This is my first question posted here. Kindly point in comment, if I missed any conventions of the forum. Thank you.\]

# Answer
There is a very recent tool to translate from LTL directly to deterministic Rabin automata. It can be obtained here:

https://www7.in.tum.de/~sickert/projects/ltl2dra/

The page not only contains a link to the downloadable implementation, but also has link to a technical report that describes the construction for the translation. Apparently, a peer-reviewed paper about the construction has not appeared yet. Note that the construction is rather involved - the paper has 50 pages, and there is a reason why for many years, the detour though Büchi automata was (and somewhat still is) state-of-the-art.

Note that the computational complexity of the direct translation is not better than the one that one can obtain by translating LTL to non-det. Büchi automata and then applying Safra's method.
> 3 votes

---
Tags: formal-languages, formal-methods, buchi-automata
---


# Question
Title: How can Turing machines loop forever given that the input is finite?
How Turing machine can loop forever when input length is always finite? I think this is a basic doubt but unable to understand how TM go into infinite loop? I think it can make transition forever on empty string. What are the other cases? Can it make without any empty alphabet ?

# Answer
> 3 votes
A simple example is a Turing Machine with one state $q$, alphabet $\Sigma = \\{a\\}$, tape alphabet $\Gamma = \Sigma \cup \\{\sqcup\\}$ and the two transitions $q\times a \to q \times a \times \mathcal{R}$ and $q \times \sqcup \to q \times \sqcup \times \mathcal{R}$. It doesn't even change the tape.

# Answer
> 5 votes
It might help to think of Turing machines as a programming language. It's easy to see how a program in your favourite language might loop (its input is finite, too!) so you can translate that to a Turing machine.

# Answer
> 4 votes
Assuming the tape contains a string over $\\{0,1\\}$, so it represents a binary number.

Repeat: go to right end, add $1$.

# Answer
> 3 votes
Is is a property of the transition function. Transition function might take the turing machine into an infinite loop on a particular input even when the input length is finite. Consider the transition function below with states Q0 and Q1 Q0 is the halt state If Q1 reads ‘L’, then stay in Q1 and go left one cell. If Q1 reads ‘R’, then stay in Q1 and go right one cell. If Q1 reads ‘H’, then change to Q0 and remain at this cell.

On the input RRRLLLL the machine goes into a loop but that doesn't mean language accepted by the machine is empty. It does halts on inputs such as RRRRH etc.

---
Tags: turing-machines
---


# Question
Title: Getting the idea behind pumping length correct
I am unsure whether I got the notion behind the pumping length correctly. I know its definition, and just want to make sure that I understood everything correctly.

Suppose we have an automata that accepts $0^{\*}1^{\*}$. The longest word accepted is $01$ without an iteration, whose length is $2$. So $n=2$, am I correct?

In case of $0......01^{\*}$ where there are $n$ zeroes, the constant would be simply equal to $n+1$.

Is my thinking correct?

# Answer
> 1 votes
One thing that's worth pointing out is that there can be many lengths that satisfy the pumping lemma. In your example, setting the pumping length to 2 does satisfy the pumping lemma. And so does length 3, 4, 5, etc. I think what you're asking about is the *minimum* pumping length. The pumping lemma is generally used to show proof that a language is not regular, in which case it doesn't really matter what the minimum pumping length actually is, just that there is some finite pumping length.

Anyway, I believe that the minimal pumping length for **0\*1\*** is actually one, not two. It's true that the **01** is the the longest word accepted without an iteration, but that's not precisely the definition of the pumping length. There are two possible words of length one: **0** and **1**. Both of these words can be pumped, and as you've shown, any words of length two or more can be pumped. Therefore, any word of length one or more can be pumped, so the minimal pumping length is one.

For your second example, I assume you mean the language L = {0n 1\* | n is a specified constant}. In that case I believe you're right that the minimum pumping length is n + 1. We can pump 0n1, but we can't pump 0n.

---
Tags: finite-automata, pumping-lemma
---


# Question
Title: What is the difference between strong normalization and weak normalization in the context of rewrite systems?
In the context of rewriting systems, how does strong normalization differ from weak normalization?

# Answer
> 14 votes
Weak normalization means that any term has a terminating rewriting sequence, i.e. admits a finite amount of rewritings which lead to a normal form (no more rewritings from that).

Strong normalization means that any term can never be rewritten infinitely many times. Any maximal rewriting sequence eventually reaches a normal form (hence it is finite).

For instance:

$$ S \rightarrow (SS) \qquad S \rightarrow A $$

is weakly normalizing (given any term, we can rewrite every $S$ into an $A$, after which normal form is reached) but not strongly normalizing ($S \rightarrow (SS) \rightarrow ((S S) S) \rightarrow \cdots$).

It is immediate to prove that strong normalization implies weak normalization.

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


# Question
Title: Why an ARM processor with 32 bits address bus can address 4 billion different bytes?
Why an ARM processor with 32 bits address bus can address 4 billion different bytes? I know that $2^{32}$ is equal to about 4 billions, but shouldn't it be 4 billion bits and not bytes?

Hence if I want to find how many different words it can address it should be $\frac{2^{32}}{8}$ so I will have the number of bytes, and if I want to find the number of words I divide it again by 4 (because a word in ARM is 32 bits = 4 bytes).

# Answer
> 5 votes
While there have been computers built that use bit addressing, notably the Burroughs 1700, 1800, and 1900 mainframes and the Intel iAPX-432, the vast majority of machines use byte addressing.

This means that each possible address corresponds to a potential byte in memory. Thus a 32 bit address would have a span of $2^{32}$ or $4,294,967,296$ bytes.

For completeness, the other category of machines use word addressing, where each address value corresponds to a word of memory. Examples here include the PDP-10 and CDC-6600 as well as many specialized DSP and embedded processors still in use.

# Answer
> 1 votes
Modern computers do not load and store individual bits from and to memory. Instead, an operation loads or stores a byte, or even a 32-bit quadword. These words or quadwords are addressed with 32 bits, giving the computer access to 128GB. Of course the computer can access individual bits, but it will first have to load the quadword into the CPU's registers, and afterwards, can manipulate that quadword however it likes.

# Answer
> 0 votes
2^32 = 4 billion addresses Each address points to 1 byte of memory. Most memory are byte addressable. So totally you can address 4gb of memory.

---
Tags: computer-architecture, computation-models, discrete-mathematics
---


# Question
Title: How does NULL behaves with distinct keyword?
Suppose I have a relation R

How many tuples are returned by SQL query

**SELECT distinct manager FROM R**

Is it $2$ or $4$ ?

# Answer
You will get 2 records, with value 2 and null

NULL is still a value when it comes to distinct, but it is not included if you do a count, so

```
select count(manager) from r;

```

would just return a count of 1
> 2 votes

---
Tags: databases
---


# Question
Title: Any significance to why a lot of big names in AI have math PhD?
I've been looking into AI research and I've noticed a nontrivial amount of individuals either received a PhD in math or had advisors who received a PhD in math. Some names include (Ben Goertzel, Marvin Minsky, Jürgen Schmidhuber).

I can see how a formal (arguably more difficult) training in math would help tackle issues in AI, but it'd make more sense to do a PhD in AI if one wants to make a career studying AI, no?

In contrast, all the high impact papers for top machine learning conferences (KDD, ICML, NIPS) were mostly from CS labs, but I cannot say that this is the norm in other AI subareas.

Is it actually better to do a PhD in math and do research in a topic that converge with AI?

# Answer
> 2 votes
All computer science is born out of Math. The are a lot of computer programmers, web designers and the like who may not have math background, but they do not count as as computer scientist.

AI and other machine learning is all based on Math and statistics, so even going for a PhD in AI would mean that would have to learn a significant amount of math anyway.

---
Tags: artificial-intelligence
---


# Question
Title: Given a string, is it possible to determine which hashing algorithm has produced it, if any?
Given a string, is it possible to determine which hashing algorithm has produced it, if any?

For example, the MD5 hash of "string" is b45cffe084dd3d20d928bee85e7b0f21.

Is it possible to determine whether the above hash is:

1) Indeed a genuine hash in some hashing algorithm, as opposed to a string of characters that is not a hash produced by one of some set of algorithms

2) a definite hash of a specific hashing algorithm?

Possible methods:

1) For hashes susceptible to rainbow-table attacks, it would be viable to search for the hash in such a rainbow table for various algorithms, to find a match; if a match is found, we know which algorithm produced it.

# Answer
You will first need to define what you mean by a *hashing algorithm*. For example, my favorite hashing algorithm is simple: check whether the input is "string", and if so, output "b45cffe084dd3d20d928bee85e7b0f21", otherwise output "error".

In the simplest case, you have one algorithm $A$, and string $w$ and you are wondering, *is there an input $x$ (and maybe a seed $s$) such that $A(x,s)=w$?* You can try brute force, but if you have the source code, is there something more clever that you can do? If not, then your algorithm is a *one-way function*. Whether one-way functions exist is an open question. We know that if one-way functions exist, then $P\ne NP$, and therefore if $P=NP$, one-way functions do not exist, but that still leaves three possibilities.
> 3 votes

# Answer
No it is not possible to determine that is produced by a hashing algo, or which one that produced it -- at least not from a single sample.

Good hashing algo will produce a uniform set of values across the entire range of possible values -- where modern algo produces values from 128 to 512 bit in width, but if we take it back to a simpler example that may be easier to understand and suppose that you hashing algo only produced values between 1 and 10, then for it to be a good algo it should produce any of the values 1 to 10 with equal likelihood.

If you were just given one value "7" you would not know if it was generated by the hashing algo, or by some other means -- there is simply not sufficient evidence.

Different hashing algo's may however have different weaknesses, so say our simple algo had a flaw that would make it more likely to produce the value 7 than the value 5, and supposed we had a million values that was generated by some hashing algo unknown to us but had the same distribution of fewer 5 and more 7's we could say that it would be likely to be generated by that hashing algo, but not certain.

---

As for your suggestion of Rainbow tables -- rainbow are easy to foil -- add salt or do multiple iterations of hashing -- something as simple as just sticking the letter 'a' in front of the input of 'string' gives a md5 of b9a15c6d632a44e7eb75d000e1dba40b which according to google does not appear in any public rainbow tables, so with a bit ingenuity of adding random salt and it would be hard to determine that the value is a md5 even with a rainbow table.
> 3 votes

# Answer
Any good hashing algorithm will be able to produce any possible output of the right format so, for example, to test if a string is a valid MD5 hash, it should be enough just to check that it's a string of 32 hex digits.
> -1 votes

---
Tags: algorithms, cryptography, hash, hashing, encryption
---


# Question
Title: How can I combine my interests for pure mathematics and computer science in college?
I’m a high school senior who's gone through quite the self-introspection the past few months while applying for college, and I have a bit of a dilemma. All my life, I've loved & excelled at mathematics, and wants to study & explore it very much in depth in college. I get very excited when I read up on fields such as number theory, analysis, topology, and algebraic geometry. On top of that, I've also realized that although I have no experience programming, there are wonderful merits to applying math to computer science and would love to apply my math skills to a fast-growing industry.

I feel, however, that studying comp sci will "limit" the scope and depth of the math I study, because joint programs of math and comp sci will only make you take math classes relevant to the study of computer science. Out of the Common App colleges I'm applying to, Emory, NYU, and BU have joint majors in math and computer science, while UMiami only has a BS in mathematics, and Georgia Tech has BSs in discrete and applied mathematics. For Emory, for instance, I'll be "missing out" on multivariable calculus, complex variables, real analysis, and abstract algebra.

If there is a way to combine these two interests without limiting the mathematics I learn, that'd be amazing, but if not, so be it. If you feel I have certain misconceptions, please feel free to point them out. Lastly, I know this is not the best place to ask this question, as it is directed towards students and researchers of computer science, but I would love your input and appreciate it ahead of time!

Thank you!

# Answer
Math is heavily used in both computer security, machine learning and AI.

* Computer Security, such as encryption and related fields is all about finding math that makes it impossible to retrieve information without being the intended recipient. With quantum computing possibility being a reality within the next 10 - 20 years there is a lot of work needed to come up with new ways of securing data. Number theory is very relevant here.
* Machine learning is heavily based on statistics. new algo's with better capability of prediction is always relevant, and a very hot topic.
* AI, while strictly an area of machine learning, are typically resolving to other areas of of learning than typical stats. Any advancements in this areas will be done by people with strong math background.
> -1 votes

---
Tags: education
---


# Question
Title: Why is the word "calculus" used to describe systems of logic and computation?
Why is the word "calculus" used in this context?

The reason I ask is because these usages of "calculus" seem unrelated to the far more popular use of "calculus" in "differential calculus" and "integral calculus" to which something like λ-calculus seems only very distantly related. This word choice seems very misleading yet very popular among many authors. Why?

# Answer
> 5 votes
The word *calculus* comes from the Latin word for limestone, because limestone pebbles were used for counting; you may have a *renal calculus*: a kidney stone$^1$.

In mathematics, the word is used to describe any system in which symbolic expressions are manipulated by fixed rules$^1$, so we may speak of tensor calculus, vector calculus, predicate calculus, $\lambda$-calculus and integral and differential calculus$^2$. The latter two are related to the former in the sense that both are sets of rules for manipulating expressions. Running a Google Books ngram search on these words, approximately 1890 was the first year in which both *"vector calculus"* and *"tensor calculus"* were mentioned, and they have been in frequent use ever since.$^3$

The reason that to you, these systems seem to be using the wrong meaning of calculus is probably that you grew up associating calculus with differentiating and integrating real-valued functions, but this is a bias.

**References**

\[1\] Wiktionary page for Calculus

\[2\] Wikipedia Disambiguation page for Calculus

\[3\] Google Books search for *integral, differential, vector, tensor calculus*

# Answer
> 5 votes
I posted the following in answer to the same question on CS Theory a couple of years ago:

> A calculus is just a system of reasoning. One particular calculus (well, actually two closely related calculi: the differential calculus and the integral calculus) has become so widespread that it is just known as "calculus", as if it were the only one. But, as you have observed, there are other calculi, such as the lambda calculus, mu calculus, pi calculus, propositional calculus, predicate calculus, sequent calculus and Professor Calculus.

---
Tags: terminology, lambda-calculus, history
---


# Question
Title: How can you construct 3-regular graphs with minimal diameter?
Given an even $N$, is it possible to procedurally construct a 3-regular graph $G$ with $N$ vertices such that the maximum distance between any pair of vertexes is the minimum possible for that $N$? I know that a cube, for example, is the solution for $N = 8$, but what about other N's?

# Answer
The interesting case is connected 3-regular graphs (otherwise the diameter is infinite). We can simply show that if $G$ is such a graph then $D(G)=\Omega\left(\log\_2|V|\right)$, where $D(G)$ denotes the diameter of the graph $G$.

Suppose $D(G)=d$. Start at an arbitrary vertex $v\in V$ and begin counting the vertices of the graph by scanning $G$ using BFS originating at $v$. In the first step you encounter 3 vertices ($v$'s neighbors). If at the $i'th$ step you encountered $k$ new vertices, then at the $i+1$ step you will encounter at most $2k$ new vertices (you have three edges to choose from, but at least one will take you back to a vertex you have already met). After at most $d$ steps you will encounter all of $G$'s vertices. This yields the following inequality:

$|V|\le 1+\sum\limits\_{i=1}^{d-1}3\cdot 2^{i-1}=1+3\cdot \left(2^{d-1}-1\right)$, hence $d=\Omega\left(\log\_2|V|\right)$.

You can see from the above that if $G$ is a connected d-regular graph then $D(G)=\Omega\left(\log\_{d-1}G\right)$.

To construct a graph which achieves this lower bound, think about binary trees, and find a way to fix the leaves (and root) in order to achieve 3-regularity.
> 1 votes

---
Tags: graphs
---


# Question
Title: How is non-ambuiguity different from determinism?
I am trying to understand what is meant by "deterministic" in expressions such as "deterministic context-free grammar". (There are more deterministic "things" in this field). I would appreciate an example more then the most elaborate explanation! If possible.

My primary source of confusion is from not being able to tell how this property of a grammar is different from (non-)ambiguity.

The closest I got to finding what it means is this quote from the paper by D. Knuth *On the Translation of Languages from Left to Right*:

> Ginsburg and Greibach (1965) have defined the notion of a deterministic language; we show in Section V that these are precisely the languages for which there exists an L R ( k ) grammar

which becomes circular as soon you get to the `Section V`, because there it says that what LR(k) parser can parse is the deterministic language...

---

Below is an example that I could find to help me understand what "ambigous" means, please take a look:

```
onewartwoearewe

```

Which can be parsed as `one war two ear ewe` or `o new art woe are we` \- if a grammar allows that (say it has all the words I just listed).

What would I need to do to make this example language (non-)deterministic? (I could, for example, remove the word `o` from the grammar, to make the grammar not ambiguous).

Is the above language deterministic?

*PS. The example is from the book Godel, Esher, Bach: Eternal Golden Braid.*

---

Let's say, we define the grammar for the example language like so:

```
S -> A 'we' | A 'ewe'
A -> B | BA
B -> 'o' | 'new' | 'art' | 'woe' | 'are' | 'one' | 'war' | 'two' | 'ear'

```

By the argument about having to parse the whole string, does this grammar make the language non-deterministic?

---

```
let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) [];;

let rec woe_parser s =
  match s with
  | 'w' :: 'e' :: [] -> true
  | 'e' :: 'w' :: 'e' :: [] -> true
  | 'o' :: x -> woe_parser x
  | 'n' :: 'e' :: 'w' :: x -> woe_parser x
  | 'a' :: 'r' :: 't' :: x -> woe_parser x
  | 'w' :: 'o' :: 'e' :: x -> woe_parser x
  | 'a' :: 'r' :: 'e' :: x -> woe_parser x
  (* this line will trigger an error, because it creates
     ambiguous grammar *)
  | 'o' :: 'n' :: 'e' :: x -> woe_parser x
  | 'w' :: 'a' :: 'r' :: x -> woe_parser x
  | 't' :: 'w' :: 'o' :: x -> woe_parser x
  | 'e' :: 'a' :: 'r' :: x -> woe_parser x
  | _ -> false;;

woe_parser (explode "onewartwoearewe");;
- : bool = true

```

---

```
| Label   | Pattern      |
|---------+--------------|
| rule-01 | S -> A 'we'  |
| rule-02 | S -> A 'ewe' |
| rule-03 | A -> B       |
| rule-04 | A -> BA      |
| rule-05 | B -> 'o'     |
| rule-06 | B -> 'new'   |
| rule-07 | B -> 'art'   |
| rule-08 | B -> 'woe'   |
| rule-09 | B -> 'are'   |
| rule-10 | B -> 'one'   |
| rule-11 | B -> 'war'   |
| rule-12 | B -> 'two'   |
| rule-13 | B -> 'ear'   |
#+TBLFM: @2$1..@>$1='(format "rule-%02d" (1- @#));L

Generating =onewartwoearewe=

First way to generate:

| Input             | Rule    | Product           |
|-------------------+---------+-------------------|
| ''                | rule-01 | A'we'             |
| A'we'             | rule-04 | BA'we'            |
| BA'we'            | rule-05 | 'o'A'we'          |
| 'o'A'we'          | rule-04 | 'o'BA'we'         |
| 'o'BA'we'         | rule-06 | 'onew'A'we'       |
| 'onew'A'we'       | rule-04 | 'onew'BA'we'      |
| 'onew'BA'we'      | rule-07 | 'onewart'A'we'    |
| 'onewart'A'we'    | rule-04 | 'onewart'BA'we'   |
| 'onewart'BA'we'   | rule-08 | 'onewartwoe'A'we' |
| 'onewartwoe'A'we' | rule-03 | 'onewartwoe'B'we' |
| 'onewartwoe'B'we' | rule-09 | 'onewartwoearewe' |
|-------------------+---------+-------------------|
|                   |         | 'onewartwoearewe' |

Second way to generate:

| Input             | Rule    | Product           |
|-------------------+---------+-------------------|
| ''                | rule-02 | A'ewe'            |
| A'ewe'            | rule-04 | BA'ewe'           |
| BA'ewe'           | rule-10 | 'one'A'ewe'       |
| 'one'A'ewe'       | rule-04 | 'one'BA'ewe'      |
| 'one'BA'ewe'      | rule-11 | 'onewar'A'ewe'    |
| 'onewar'A'ewe'    | rule-04 | 'onewar'BA'ewe'   |
| 'onewar'BA'ewe'   | rule-12 | 'onewartwo'A'ewe' |
| 'onewartwo'A'ewe' | rule-03 | 'onewartwo'B'ewe' |
| 'onewartwo'B'ewe' | rule-13 | 'onewartwoearewe' |
|-------------------+---------+-------------------|
|                   |         | 'onewartwoearewe' |

```

# Answer
A PDA is deterministic, hence a DPDA, iff for every reachable configuration of the automaton, there is at most one transition (i.e., at most one new configuration possible). If you have a PDA which can reach some configuration for which two or more unique transitions may be possible, you do not have a DPDA.

Example:

Consider the following family of PDAs with $Q = \\{q\_0, q\_1\\}$, $\Sigma = \Gamma = \\{a, b\\}$, $A = q\_0$ and $\delta$ given by the following table:

```
q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
...

```

These are nondeterministic PDAs because the initial configuration - `q_0, Z0` \- is reachable, and there are two valid transitions leading away from it if the input symbol is `a`. Anytime this PDA starts trying to process a string that begins with an `a`, there's a choice. Choice means nondeterministic.

Consider, instead, the following transition table:

```
q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
q1   a    a    q0   aa
q1   a    b    q0   ab
q1   a    b    q2   aa
q2   b    a    q0   ba
q2   b    b    q0   bb
q2   b    a    q1   bb

```

You might be tempted to say this PDA is nondeterministic; after all, there are two valid transitions away from the configuration `q1, b(a+b)*`, for instance. However, since this configuration is not reachable by any path through the automaton, it doesn't count. The only reachable configurations are a subset of `q_0, (a+b)*Z0`, `q1, a(a+b)*Z0`, and `q2, b(a+b)*Z0`, and for each of these configurations, at most one transition is defined.

A CFL is deterministic iff it is the language of some DPDA.

A CFG is unambiguous if every string has at most one valid derivation according to the CFG. Otherwise, the grammar is ambiguous. If you have a CFG and you can produce two different derivation trees for some string, you have an ambiguous grammar.

A CFL is inherently ambiguous iff it is not the language of any unambiguous CFG.

Note the following:

* A deterministic CFL must be the language of some DPDA.
* Every CFL is the language of infinitely many nondeterministic PDAs.
* An inherently ambiguous CFL is not the language of any unambiguous CFG.
* Every CFL is the language of infinitely many ambiguous CFGs.
* An inherently ambiguous CFL cannot be deterministic.
* A nondeterministic CFL may or may not be inherently ambiguous.
> 9 votes

# Answer
Here are examples (from Wikipedia):

The language of even-length palindromes over the alphabet of 0 and 1 is a non-deterministic, but unambiguous *language*. *A* grammar for this language is $S \rightarrow 0S0 | 1S1|\varepsilon$. The *language* is *non-deterministic* because you need to look at the whole string to figure out where the middle is. The *grammar* is *unambiguous* because there is one and only one parse tree for each string in the language.

A context free language is deterministic if and only if there exists at least one deterministic push-down automaton that accepts that language. (There may also be lots of non-deterministic push-down automata that accept the language, and it would still be a deterministic language.) Essentially a deterministic push-down automata is one where the machine transitions are deterministically based on the current state, the input symbol and the current topmost symbol of the stack. *Deterministic* here means that there is no more than one state transition for any state/input symbol/topmost stack symbol. If you have two or more next states for some state/input symbol/topmost stack symbol triple then the automaton is non deterministic. (You would need to "guess" which transition to take in order to decide whether the automaton accepts or not.)

What Knuth proved was that every LR(k) grammar has a deterministic pushdown automaton and that every deterministic pushdown automata has an LR(k) grammar. So LR(k) grammars and deterministic pushdown automata can handle the same set of languages. But the set of languages that have a deterministic pushdown automaton that accepts them is (by definition) the deterministic languages. The argument isn't circular.

So deterministic language implies that there exists an unambiguous grammar. And we've shown an unambiguous grammar that has no deterministic pushdown automaton (and thus it is an unambiguous grammar that accepts a non-deterministic language.)

Are there context free languages for which no unambiguous grammar exists? It turns out there are. An example (again from Wikipedia) is the union of $\\{a^nb^mc^md^n|n,m\>0\\}$ and $\\{a^nb^nc^md^m|n,m\>0\\}$. Each of the sets individually is obviously context free and the union of context free languages is context free. Strings of the form $\\{a^nb^nc^cd^n|n\>0\\}$ are obviously in this language (in fact that's the intersection of the two languages) and Hopcroft and Ullman proved that no matter what grammar you come up with for the union language, there will be some string in the intersection set that has two different parse trees.
> 8 votes

# Answer
Deterministic context-free languages are those which are accepted by some deterministic pushdown automaton (context-free languages are those accepted by some non-deterministic pushdown automaton). As such, it's a property of a *language* rather than of a *grammar*. In contrast, *ambiguity* is a property of a grammar, while *inherent ambiguity* is a property of a language (a context-free language is inherently ambiguous if every context-free grammar for the language is ambiguous).

There is a connection between the two definitions: deterministic context-free languages are never inherently ambiguous, as shown in the answer to this question.
> 5 votes

# Answer
**Definitions**

1. A **deterministic pushdown acceptor (DPDA)** is a pushdown automaton that never has a choice in its move.
2. DPDA and NPDA are not equivalent.
3. A **CFG** is **non deterministic** iff there are ***at least*** two productions with same terminal prefix on the right side of them.
4. A **CFG** is **ambiguous** iff there exists ***some*** w ∈ L(G) that has ***at least*** two distinct derivation trees. Thus, it has two or more leftmost or rightmost derivations corresponding to two different derivation trees.
5. A **CFG** is **unambiguous** iff ***every*** string has ***at most*** one valid derivation according to the CFG. Otherwise, the grammar is ambiguous.
6. A **CFL** is **inherently ambiguous** iff it is not the language of ***any*** unambiguous CFG. It cannot have any DPDA.
If ***every*** grammar that generates CFL is ambiguous, then the **CFL** is called **inherently ambiguous**. Thus it is not the language of ***any*** unambiguous CFGs.

**Facts**

1. Every CFL is the language of ***infinitely many*** nondeterministic PDAs.
2. Every CFL is the language of ***infinitely many*** ambiguous CFGs.
3. A CFL accepted by ***some*** DPDA is not inherently ambiguous. (There exist at least one unambiguous CFG for it.)
4. A CFL accepted by NDPDA may or may not be inherently ambiguous as there may exist ***some*** DPDA (or unambiguous CFG) for it.
5. A CFL generated by ambiguous CFG may or may not be inherently ambiguous as there may exist ***some*** unambiguous CFG (or DPDA) for it.
6. A CFL generated by **at least one** unambiguous CFG is not inherently ambiguous. (There exist some DPDA for it.)
7. A non deterministic grammar may or may not be ambiguous.

**Answer to your question (relation between determinism and ambiguousness)**

1. (Non) ambiguity applies mainly to the grammars (here CFGs). (Non) determinism applies to both grammars and automaton (here PDAs).

If you want logical differences, you can look at last four points in facts section as they try to relate both ambiguity and determinism. Here I am repeating them again:
2. A CFL accepted by some **deterministic** PDA is **not inherently ambiguous**. (There exist at least one unambiguous CFG for it.)
3. A CFL accepted by **non deterministic** PDA **may or may not be inherently ambiguous** as there may exist some DPDA (or **unambiguous** CFG) for it.
4. A CFL generated by **ambiguous** CFG may or may not be **inherently ambiguous** as there may exist some unambiguous CFG (or **deterministic** PDA) for it.
5. A CFL generated by at least one **unambiguous** CFG is not **inherently ambiguous**. (There exist some DPDA for it.)
6. A **non deterministic** grammar may or may not be **ambiguous**.

**PS:**

1. The accepted answer uses lines likes “CFL is deterministic”, “deterministic CFL”, “CFL cannot be deterministic”, “A non deterministic CFL”. I guess the adjectives “deterministic” and “ambiguous” does not apply to CFL, but to PDA and CFG.(Though the adjective “inherently ambiguous” applies to CFL) Though I dont want to criticize the original answer, as I myself learnt crucial points from it. (In fact I have literally copy pasted some lines from that answer.) But still I felt it should be made more correct. So I tried to put stuffs more clearly here in two parts definitions and facts (I might have made it unnecessarily verbose and long). I guess I should have edited the original answer, but then it will involve deleting many points that use above lines. And I dont know if this will make it any valid edit as it involve complete rewrite.
2. Notice that I have put a quantitative words in ***bold-italics*** to highlight comparative differences in different definitions and facts. The definition terms are **only boldfaced**.
3. Some couple of points I have made myself, so I will need confirmation from someone knowledgeable here about correctness of every point.
> 1 votes

# Answer
Perhaps an example would help here. Consider the language of palindromic strings on $\\{a,b\\}$, i.e.: $\\{ w \in (a+b)^\* \mid w = w^R \\}$. This is generated by the grammar $S\to aSa | bSb | a | b | \epsilon$. This is an unambiguous grammar for an unambiguous language. A PDA accepting this language would simply push $a$'s and $b$'s until it locates the middle of the string, possibly eating one $a$ or $b$ (for odd-length strings), then matching $a$'s and $b$'s by reading input and popping stack until both are empty. But there is no way to make a DETERMINISTIC PDA for this language, because there is no way for the PDA to locate the center of the string without guessing.
> 1 votes

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


# Question
Title: Why don't computers use the same architecture?
We just started on the Computer Architecture topic in our CS lectures and I have a few questions that are currently bothering me. So we have different computers, and there are always differences in the hardware and architecture.

Now, why don't all computers simply use the same architecture? Won't that make it easier to program? What makes this a bad idea?

# Answer
Why aren't all cars identical? Wouldn't that make easier to build and repair them?

There are big and small cars, cheap and expensive cars, fast gas guzzlers and slow energy savers… And similarly there are many different types of computers.

Here are a few criteria that influence the architecture of a computer. Optimizing for some of the criteria will have a cost against some other criteria.

* Speed to execute sequences of integer operations
* Speed to execute sequences of floating-point operations
* Speed to execute sequential computations that require a lot of memory
* Speed to make parallelizable integer computations
* Speed to make parallelizable floating-point computations
* Speed to make parallelizable memory-intensive computations
* Power consumption when idle
* Peak power consumption
* Ability to scale power consumption according to the amount of computation at a given time
* Special-purpose computations (graphics processing, cryptography, digital signal processing, …)
* Volume
* Design cost
* Per-unit manufacturing cost for large amounts
* Per-unit manufacturing cost for small amounts
* Possibility to connect many peripherals
* Ability to execute tasks in real time, i.e. fine control over the execution time of each operation (e.g. to control a physical object)
* Isolation between tasks (for robustness and security)

This is of course not an exhaustive list. In practice, you'll find architectures that find a few sweet spots, optimizing for some criteria at the expense of others.

Here are a few examples of different compromises.

* Intel x86 processors tend to be very good at raw speed for sequential execution of pure computation and memory accesses. ARM tend to be less fast, but consume less power, which is a large part of why x86 is so common on computers that are plugged into the mains while ARM is prevalent on computers that almost always run on battery such as mobile phones.
* GPU are very good at executing many tasks in parallel, which is well-suited to drawing images that consist of millions of pixels. But they're bad at accessing lots of memory in random ways, so they don't make good general-purpose processors.
* An MMU translates memory addresses used by programs into memory addresses used by the hardware. This allows the operating system to execute programs each in their own address space, so that they don't interfere with each other. This means that each memory access can take a variable amount of time, though, which is why most processors designed for real-time systems don't have an MMU.
* FPGA are extremely flexible processors — you can reconfigure them to optimize them for whatever computation you want to do today. But they aren't cheap.

Add to that historical factors. Designing a new processor architecture takes years of effort by teams of hundreds or thousands of highly-trained engineers, and changing architectures involves rewriting a lot of software, so it doesn't happen often. So just like you can have different car models from different manufacturers that have the same strengths and weaknesses, you can have different processor architectures from different manufacturers that vie for the same applications.
> 5 votes

# Answer
My first thought is that x86 is crappy, and that we only use it on computers for backward compatibility. But this is merely opinion-based. So, let just remember that most computers use x86 architecture, and that it would be expensive to switch to another architecture.

So, why don't Qualcomm use x86 on phones ? One part of the answer is that x86 is Intel property, and there is, to the best of my knowledge, only one firm that own a license for x86: AMD, who got it as IBM requested a second source for its CPU, as far as I remember.

And there is an other reason to maintain several architectures: to have architectures that fit the need. A modern x86 architecture requires much silicon, and much power. If you look at ARM architecture, you've got the high end ARMv8a, with much power and high power consumption (several watts), and, at the same time, ARM still develops ARMv6-M, with much less silicon (0.0066 mm2 instead of 9 mm2), reduced power consumption (200µW), but reduced performances (divided by 10000, roughly).

To sum up, we keep several architectures for backward compatibility, intellectual property, and purpose fit. You should probably study several architectures to get a better overview of this field of study.
> 2 votes

# Answer
There are several driving forces involved here:

a) Human Variation. Nature itself does not put any particular restriction on computer architecture, so people have to bring their own creativity to the task - and of course different people come up with different approaches. This was true when computers were just being invented, and has continued to be true with each new generation (of people and of machines).

b) Economics. A lot of old architectures (esp. IBM 360) persist in institutions - banks, insurance companies, etc - because migrating working software to a common shared architecture -different from theirs- is too costly, both in direct development cost and in risk due to the inevitable debugging shakedown. Here backward compatibility trumps performance almost all of the time.

c) The Bleeding Edge. There are always those who need to perform the largest feasible computations with the maximum speed. Meeting those demands is nearly always best achieved by using the latest techniques in new architectures rather than trying to beef up existing ones (esp. ones as mess y as x86).

d) Legality. If all the world agreed on a single common architecture, then the producers of that hardware would probably be at risk (in America at least) of massive Anti-Trust lawsuits. E.g IBM got hit with one after introducing the 360; Microsoft got hit with one after Windows got popular. Licensing to AMD is probably the only thing preventing one against Intel.
> 2 votes

# Answer
For at least two reasons:

One: Computers today are used for more than one thing, and a computer that is good for one task isn't necessarily the best for another. Like EvilJS said in his comment: Why do we have more than one kind of motor vehicle? Why do we have motorcycles, sedans, minivans, pick-up trucks, etc? Why not just have one type of car that everyone drives? Because that would be wildly impractical. A small two-seat coup is great for a single person commuting to work. Not so practical for a family of eight. Etc. The ideal CPU for a cell phone and the ideal CPU for a high-capacity server are not the same.

Two: People get new and better ideas. What if back in 1900 people had said, why do we need so many kinds of cars? Let's just agree on one kind and that's all anyone will make. Then today we would still all be driving 1900-style cars.
> 1 votes

---
Tags: computer-architecture
---


title: NFA that doesn't accept a language

text:
# Question
Title: NFA that doesn't accept a language
Suppose I want to draw a NFA that doesn't accept a language containing $aba$. Would this work:

# Answer
> 4 votes
Construct the obvious four-state NFA with minimum number of transitions, which DOES accept 'aba' (and no other string). Complete it as a DFA by adding a 'dead' state, then adding all missing transitions from the other states to the dead state, plus two transitions from the dead state - one on 'a' back to the second NFA state, one on 'b' back to the third NFA state. Now invert the finality - i.e change each final state to non-final and each non-final state to final. You now have an NFA (DFA, actually) which accepts all strings not containing 'aba'.

---
Tags: automata
---


# Question
Title: If $m \leq a \log m + b$, why does $m = O(\max\{a \log a, b\})$?
I'm found this claim in something I was reading and I'm having trouble working out the logic. Can someone help me out?

# Answer
$m \leq a \log m + b$ **has no asymptotic behavior**. This is because regardless of constants $a, b$, the left hand side grows faster than the right side, leaving only a finite range where $m$ is valid.

It is likely what was meant is $m \leq a \log a + b$. In this case we have that $m$ is bounded by something, so $m = O(a \log a + b)$. If you have that $O(x + y) = O(\max(x, y))$, then the question is solved.

But why is $O(x + y) = O(\max(x, y))$ true? With big-$O$ notation we are interested in the *asymptotically fastest growing part*. We ignore constant factors. Now check three cases (in the limit):

$$x \< y \rightarrow O(x + y) = O(y)$$ $$x \> y \rightarrow O(x + y) = O(x)$$ $$x = y \rightarrow O(x + y) = O(x + x) = O(2x) = O(x)$$

Since our choice for $x = y$ doesn't matter, we can see that choosing the minimum gives us the right asymptotic behavior.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Reduction from Maximum Independent Set to Independent Set Decision Problem
I was hoping someone would be able to help me with this question.

The Maximum Independent Set search problem is, given an undirected graph G, to output an independent set in G of maximum size.

Give a polynomial time algorithm for the Maximum Independent Set search problem which can use an oracle that solves instances of the Independent Set decision problem.

I can't see how you would do this without inputting every possible combination of the vertices into the Independent Set Problem, which obviously won't be polynomial time.

# Answer
It is certainly possible to do so, as every $\mathcal{NP}-$complete problem is self-reducible.

Let us first remember the definition of decisional maximum independent set: given an undirected graph $G=(V,E)$ and $k \in \mathbb{N}$, does there exist $S \subseteq V$ with $|S| = k$ such that $\forall x, y \in S \ . \ (x, y) \notin E$ ?

By a standard binary search argument, we can find the size of the maximum independent set with a polynomial number of queries to that oracle.

Let $s$ be the size of the maximum independent set of $G$. We pick some $v \in V$ and we use our construction to determine the size of the maximum independent set of $G \setminus v$. That can be either $s$ or $s-1$. If it's $s$, then there exists a maximum independent set in $G$ that does not include $v$, therefore we can exclude $v$ from our search.

Eventually, we'll reach a point where we can't exclude any other node. That means that the remaining nodes form a maximum independent set.
> 2 votes

---
Tags: reductions
---


# Question
Title: Finding k'th smallest element from a given sequence only with O(k) memory O(n) time
Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms of sequence and when get the $k+1$'th term, delete a term which we sure that it cannot be the $k$'th smallest element and then save $k+1$'th term. So we should have an indicator that shows this unusable term in each step and this indicator should be update in each step quickly. I began with *"max"*; but it cannot update quickly; Means that if we consider *max* then in first deletion we miss the max and we should search for max in $O(k)$ and its cause $(n-k)\times O(k)$ time that it's not linear. Maybe we should save first $k$ terms of sequence more intelligently.

How do I solve this problem?

# Answer
Create a buffer of size $2k$. Read in $2k$ elements from the array. Use a linear-time selection algorithm to partition the buffer so that the $k$ smallest elements are first; this takes $O(k)$ time. Now read in another $k$ items from your array into the buffer, replacing the $k$ largest items in the buffer, partition the buffer as before, and repeat.

This takes $O(k * n/k) = O(n)$ time and $O(k)$ space.
> 16 votes

# Answer
You can do it in $O(k)$ memory and $O(n \log k)$ time by forming a fixed size max-heap from the first $k$ elements in $O(k)$ time, then iterating over the rest of the array and pushing a new element and then popping for $O(\log k)$ for every element giving total time $O(k + n\log k)$ = $O(n \log k)$.

You can do it in $O(\log n)$ auxiliary memory and $O(n)$ time by using the median-of-medians selection algorithm, selecting at $k$, and returning the first $k$ elements. With no change to asymptotics you can use introselect to speed up the average case. **This is the canonical way to solve your problem.**

Now technically $O(\log n)$ and $O(k)$ are incomparable. However I argue that $O(\log n)$ is better in practice, as it's effectively constant considering no computer system has more than $2^{64}$ bytes of memory, $\log 2^{64}= 64$. Meanwhile $k$ can grow to be as large as $n$.
> 3 votes

---
Tags: data-structures, search-algorithms, quicksort
---


# Question
Title: About the first order logic (valid, Unsatisfiable, Syntactically wrong)
I am in trouble , I searched a lot about how to solve this kind of questions but I did not get any answers.

I understand how can I know when the sentences is valid and Unsatisfiable in propositional logic, but in FOL I can't.

Can someone help me how can I solve this kind of questions? Because it comes always in the past exams in AI.

Let us have the following:

```
1- ¬(Speed(Processor(MyPC))=Speed(Processor(MyPC)))
2- ¬ ∃ x ( Speed(x) = Speed(MyPC) )
3- Speed(MyPC)=MyPC
4- ∀ y ∃ x (Speed(x) ∧ Speed(y))= Speed(MyPC)

```

Note :

```
    MyPC:
    a constant symbols that represents my PC.

    Speed(x):
    a function symbol that refers to speed of x

```

The answer for 1 is Syntactically wrong
2 is Unsatisfiable
3 is Neither valid nor unsatisfiable
4 is Syntactically wrong

# Answer
> 2 votes
1 uses a function symbol `Processor` which is not in the logic signature. Hence, it's outside the syntax.

4 tries to equate a proposition with `Speed(MyPC)`. You can't equate propositions in FOL. Outside the syntax.

3 is not universally true for every function `Speed` and every argument `MyPC`. For instance interpret `MyPC` as the natural $0$, and `Speed` as the successor function to obtain $\mathsf{succ}(0)=0$ which is false. Hence the formula is not valid. However, it is satisfiable: now interpret `MyPC` as zero and `Speed` as the identity function to obtain $\mathsf{id}(0)=0$ which is true. The formula has a model and a countermodel: satisfiable and invalid.

2 `∃ x ( Speed(x) = Speed(MyPC) )` is always true, since we can take `x` to be `MyPC`. This holds no matter how we interpret `Speed` and `MyPC`. Hence is it valid. (Alternatively, we can even show it is a theorem of FOL using a proof system, and then rely on the correctness theorem to claim it is valid.) Since formula 2 is the negation of a valid formula, it is unsatisfiable.

---
Tags: logic, first-order-logic
---


# Question
Title: Efficiently computing the smallest integer with n divisors
In order to tackle this problem I first observed that

$$\phi(p\_1^{e\_1} \space p\_2^{e\_2} \cdots \space p\_k^{e\_k}) = (e\_1 + 1)(e\_2 + 1)\cdots(e\_k +1)$$

Where $\phi(m)$ is the number of (not necessarily prime) divisors of $m$. If $m$ is the smallest integer such that $\phi(m) = n$, then

$$\phi(m) = n$$ $$(e\_1 + 1)(e\_2 + 1)\cdots(e\_k +1) = n$$

Now we must choose $e\_i$ such that $\prod\_{i} p\_i^{e\_i}$ is minimal. The choices for $p$ are trivial - they are just the primes in ascending order.

However, my first thought for choosing $e\_i$ was incorrect. I thought you could simply factor $n$, sort the factors in descending order and subtract 1. Most of the time this works fine, e.g. the smallest integer with $n = 15$ divisors is:

$$15 = 5 \cdot 3$$ $$15 = (4 + 1)(2 + 1)$$ $$m = 2^4 3^2 = 144$$

But this is incorrect for $n = 16$:

$$16 = 2 \cdot 2\cdot 2 \cdot 2$$ $$16 = (1 + 1)(1 + 1)(1 + 1)(1 + 1)$$ $$m = 2^1 3^1 5^1 7^1 = 210$$

Whereas the correct answer is:

$$16 = (3 + 1)(1 + 1)(1 + 1)$$ $$m = 2^3 3^1 5^1 = 120$$

So it's clear sometimes we need to merge factors. In this case because $7^1 \> 2^2$. But I don't exactly see a clean and direct merging strategy. For example, one might think we must always merge into the $2$ power, but this is not true:

$$1552 = (96 + 1)(1 + 1)(1 + 1)(1 + 1)(1 + 1)$$ $$m = 2^{96} 3^1 5^1 7^1 11^1 \> 2^{96} 3^3 5^1 7^1$$

I can't immediately think of an example, but my instinct says that some greedy approaches can fail if they merge the wrong powers first.

### Is there a simple optimal strategy for merging these powers to get the correct answer?

---

**Addendum.** A greedy algorithm that checks every possible merge and performs the best one on a merge-by-merge basis, fails on $n = 3072$. The series of one-by-one merges is:

$$2^2 3^1 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1 31^1$$

$$2^3 3^2 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1$$

$$2^5 3^3 5^1 7^1 11^1 13^1 17^1 19^1 23^1$$

However the optimal solution is:

$$2^7 3^3 5^2 7^1 11^1 13^1 17^1 19^1$$

# Answer
Here's a solution, based on my comments above. I make no claims this is optimal.

The idea is to consider $T(n,m)$, which we defines as "the smallest positive integer with exactly $n$ divisors and $m$ distinct prime factors". We make the easy observations:

\begin{align} T(n, 1) &= 2^{n-1}\\ T(2^m, m) &= p\_1p\_2\cdots p\_m \end{align}

And we also have the recurrence:

\begin{equation} T(n,m) = \min\_{d|n} \[T\left(\frac{n}{d}, m-1\right)\cdot p\_m^{d-1}\] \end{equation}

Finally, the quantity you're looking for is \begin{equation} \min\_{1\le i\le\lceil\log(n)\rceil} T(n, i) \end{equation}

To that end, here is some Python code, which agrees with all the numbers you gave above. Note that it works with the logarithms to keep the numbers smaller: so the actual integer you seek is `round(2**smallest(n))`.

```
import functools
import itertools
import math

# All primes less than 100.
PRIMES = [
  2, 3, 5, 7, 11,
  13, 17, 19, 23, 29,
  31, 37, 41, 43, 47,
  53, 59, 61, 67, 71,
  73, 79, 83, 89, 97,
]

LOG_PRIMES = [math.log2(p) for p in PRIMES]

def smallest(n):
  max_factors = math.ceil(math.log2(n))
  min_so_far = float('Infinity')
  factors = factorize(n)
  memo = {}
  for i in range(1, max_factors+1):
    t = T(n,i, factors, memo)
    if 0.0 < t < min_so_far:
      min_so_far = t
  return min_so_far

def T(n, m, factors=None, memo=None):
  if memo is None:
    memo = {}
  if n < 2 or m < 1:
    return 0
  elif m == 1:
    # Everything on the smallest prime.
    return (n-1) * LOG_PRIMES[0]
  elif n < 2**m:
    return 0
  elif n == 2**m:
    # Product of first m primes, in log.
    return sum(LOG_PRIMES[:m])
  elif (n,m) in memo:
    return memo[(n,m)]

  if factors is None:
    factors = factorize(n)
  if len(factors) < m:
    return 0

  smallest = float('Infinity')
  for factor_list in powerset(factors):
    divisor = product(factor_list)
    first = T(divisor, m-1, factor_list, memo)
    # No such product.
    if first < 1.0:
      continue
    second = (n/divisor - 1) * LOG_PRIMES[m-1]
    total = first + second
    if total < smallest:
      smallest = total

  memo[(n,m)] = smallest
  return smallest

def product(nums):
  return functools.reduce(lambda x,y: x*y, nums, 1)

def factorize(n):
  prime_factors = []
  for p in PRIMES:
    while n%p == 0:
      n //= p
      prime_factors.append(p)
    if n == 1:
      break
  return prime_factors

def powerset(lst):
  # No empty set.
  return itertools.chain.from_iterable(itertools.combinations(lst, r)
                                       for r in range(1, len(lst)+1))

```
> 1 votes

# Answer
Possible candidates for "smallest integer with n divisors" are the integers of the form $2^a·3^b·5^c...$ where a ≥ b ≥ c ... and (a+1)(b+1)(c+1)... = n.

So you need to find all ways to express n as the product of integers ≥ 2 in non-ascending order, and calculate and check the corresponding candidates. For example, when n = 16, 16 = 8·2 = 4·4 = 4·2·2 = 2·2·2·2, so possibilities are $2^7·3$, $2^3·3^3$, $2^3·3·5$, $2·3·5·7$, and the smallest is $2^3·3·5 = 120$.

If n is the product of two primes p·q, p ≥ q, the only candidates are $2^{pq-1}$ and $2^{p-1}·3^{q-1}$, and the latter is always smaller.

You can figure out some condition when there could be a factor $2^{ab-1}$ for example, by checking whether $2^{ab-1} \> 2^{a-1}·x^{b-1}$ for some prime x that isn't a factor. In the example n = 16, there is a factor $2^3$ because $2^3 \< 2·7$.
> -1 votes

---
Tags: number-theory, primes
---


# Question
Title: Why is $\Omega(\log\log n)$ a lower bound for the depth of polynomial-width circuits computing parity?
I'm working on an exercise from The Nature of Computation concerning polynomial-width circuits computing parity. In particular the exercise asks to sketch a proof that the depth of such a circuit has the lower bound $\Omega(\log\log n)$ where $n$ is the number of input variables.

There is quite a large amount of literature on the subject flying around the web and I have seen claims for lower bounds of $\Omega(\log^\* n)$ as well as $Ω(\log n/\log\log n)$. However the proofs of these statements completely defeat me.

Does anybody see a simpler way to arrive at the desired result?

# Answer
After some more thought here is my own attempt at a solution:

Assume for contradiction that the depth $d$ isn't $\Omega(\log \log n)$. Then it must be that

$\forall C,N:\exists n \> N: d \< C \lg \lg n$.
(Base 2 is an arbitrary choice for the logarithm.)

In particular if $C = \frac 1 2$ then

$\forall N: \exists n \> N: 2^{2^{2d}} \< n$.

At this point the Switching Lemma is required. The Switching Lemma is stated in The Nature of Computation as follows:

> Consider a circuit with $n$ inputs $x\_1,...,x\_n$ consisting of a layer of OR gates which feed into a single AND gate, where both types of gates have arbitrary fan-in. Now suppose that we randomly restrict this circuit as follows. For each variable $x\_i$, with probability $1-n^{-\frac 1 2}$ we set $x\_i$ randomly to true or false, and with probability $n^{-\frac 1 2}$ we leave it unset. For any constant $a$, if there are $O(n^a)$ OR gates, then with probability $1-o(n^{-a})$ the resulting circuit can be expressed as a layer of a constant number of AND gates, which feed into a single OR gate.

The Switching Lemma is symmetric with respect to AND and OR. So every time the Switching Lemma is applied the top two layers are switched and the second and third layer can then be merged into a single layer leaving a circuit of depth $d-1$. Thus after applying the Switching Lemma $d-2$ times the circuit has depth $2$ remaining.
Applying the Switching Lemma one last time no longer reduces the depth of the circuit but does leave a circuit that only depends on a constant number of inputs. (This follows from details of the proof of the Switching Lemma.)
At the same time the number of remaining unset variables is

$\sim n^{\frac{1}{2^d}} \> (2^{2^{2d}})^{\frac{1}{2^d}} = 2^{\big(\frac{2}{\sqrt 2}\big)^{2d}} = 2^{2^d}$.

And since a previous result established that Parity isn't in $AC^0$, we know that $d$ and for that matter $2^{2^d}$ eventually exceeds any constant.
If we were then to set those variables on which the circuit still depends, we'd arrive at a constant circuit computing Parity with some variables still unset, which yields a contradiction.
Also note that the width remained polynomial since the Switching Lemma increases it by a constant factor $m$ each time it is applied. So the width is multiplied by

$m^{d-1} \< m^{\frac{1}{2} \lg \lg n} = (\lg n)^{\frac{1}{2} \lg m} = poly(n)$.

Hence $d = \Omega(\log \log n)$.

I want to point out however that this proof is fairly out of my personal comfort zone. So I don't want to make any guarantees.
> 1 votes

---
Tags: lower-bounds, circuits
---