# Question
Title: Terminology for Digitally Interpretting Environment
I am looking into coding a program that can Analyse an image and identify objects in that environment (incl their depth and contours/shape).

What is the term for this? Is there a term or area of expertise for this? 'Computer Visualisation' is too broad a term I believe. Maybe Computer Vision and Pattern Recognition (CVPR)? Object Detection? Environment Analysis?

A real world example of what I am looking to develop; autonomous cars with software that can identify and classify objects in its path (pedestrians, curb, centre line, cars, etc.). I am most likely going to use OpenCV, code in C++ and the video stream will come from a cheap drone camera. The drone wont have an infrared/ultra violet hardware component so detecting depth will need to be performed using alternate methods - maybe there are image processing algorithms that can provide a crude idea of the depth of objects.

# Answer
> 1 votes
This falls within the broad field of computer vision. It's related to object recognition, which is about the following problem: given a picture of an object, figure out what kind of object it is. More generally, there's "scene analysis" (I think that's the right phrase): given an image, identify the objects in the scene and work out some understanding of their relative position and relationship.

---
Tags: terminology, computer-vision, software-engineering
---


title: Computer science asymptotic terminology

text:
# Question
Title: Computer science asymptotic terminology
I have been hearing the phrases quasipolynomial, superpolynomial and subexponential.

I think know what quasipolynomial and subexponential is. I believe these are functions respectively of form $n^{\log^c n}$ and $n^{n^{1/c}}$ for some $c\>1$.

What does superpolynomial mean?

# Answer
Superpolynomial means $n^{\omega(1)}$, that is, growing faster than any polynomial. More clearly, $n^{f(n)}$ for some function $f$ satisfying $\lim\_{n\to\infty} f(n) = \infty$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Pumping lemma: if you can keep pumping, what does this tell you?
Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation, do you have to "throw out" the lemma so to speak? I am under the impression that the answer is yes, but I'm just not sure.

# Answer
> 6 votes
If you are not sure, it is probably because you want to know why. This question is frequent among students in computer science that are learning the pumping lemma for the first time and it is the cause of a lot of errors.

## Logic

The reason is very simple. It is because of logic. I will explain it considering the pumping lemma for the regular languages but it is analog for the context-free version of the lemma. The statement that has been proved is the following:

$$1)\ L\text{ is a regular language}\implies L\text{ complies with the pumping lemma}$$

This is all we know. Notice that this implication is in one direction. In other words we can't conclude:

$$2)\ L\text{ complies with the pumping lemma}\implies L\text{ is a regular language}$$

It is a common mistake to invert the propositions in the first implication and expect to obtain a logically equivalent statement (you can't use the second statement!).

When we use the pumping lemma we are actually using the contrapositive of the first implication:

$$3)\ L\text{ doesn't complies with the pumping lemma} \implies L\text{ is not regular}$$

The first and the third statements are logically equivalent. This is why we search for a contradiction when trying to force $L$ to fulfill the pumping lemma. If $L$ doesn't comply with the lemma then we are sure that $L$ is not regular. If you were paying attention you could have noticed that we can't prove that $L$ is regular using the pumping lemma. If you want to prove that $L$ is a regular language you should find a regular expression, NFA or a DFA (or even a regular grammar) that denotes $L$.

## Inside the pumping lemma

Another big source of error is the incorrect interpretation of the lemma. Every word in the lemma is very important:

**Pumping lemma**: **If** $L$ is regular **then** there **exists** a constant $N\in \mathbb{N}$ such that **for all** $\sigma$ in $L$ with $|\sigma|\geq N$ there **exists** a decomposition $\sigma=\alpha\beta\gamma$ such that:

a) $|\alpha\beta|\leq N$

b) $\beta \neq \epsilon$

c) $\alpha\beta^i\gamma \in L\ \forall i \in \mathbb{N}\_0$

**Common mistakes**

1) *My word $\sigma$ complies with the pumping lemma so $L$ must be regular*:
This is wrong for so many reasons. First, we can't conclude that $L$ is regular using the pumping lemma (see the Logic section). Second, a lot of words can comply the three conditions but the lemma clearly state that **all** $\sigma\in L$ with $|\sigma|\geq N$ should comply. So good luck trying with another word!

2) *If I choose this particular $\alpha$, $\beta$ and $\gamma$ I find a contradiction!*:
This is wrong too. The lemma states that there **exists** a decomposition(at least one) that fulfill the lemma. So if you choose one and it doesn't meet the three conditions it doesn't say too much... Now you have to try with all the remaining possible decompositions! You will find a contradiction when you prove that is impossible to find such a decomposition.

3) *If I choose the word $\sigma=\epsilon$ I find a contradiction!*:
This is wrong for two reasons. First, $N\>0$. Second, the lemma states that there **exists** a constant $N$. If you choose $N=0$ (wrong by definition) or $N=1$, $N=2$, etc and you find a contradiction it is okay. Now you have to try all the remaining integer $N$! This is the reason why you should never try to choose a specific constant $N$ and why you should use a generic constant instead.

4) *I tried a lot of words and all of them comply with the pumping lemma... what do I do?*:
At this point you have two options. You can suspect that $L$ is regular and try to find a regular expression(or NFA, DFA, regular grammar...) that denotes $L$. If you suspect that $L$ is not regular then maybe it is time to use closure properties to simplify the problem or you can continue your epic quest of proving that $L$ is not regular by trying others words.

These are all the tips I have for now. If I can remember some more in the future I will add them here.

# Answer
> 4 votes
This question refers to "the pumping lemma" but there are actually several pumping lemmas available. Thus a short answer to the question "Do you have to "throw out" the lemma?" might be "Try a stronger version first".

**1. Regular languages**.

Let us first state the standard pumping lemma.

**Pumping lemma**. *If $L$ is regular, then there exists $k \> 0$ such that each word $y$ of length $\geqslant k$, there exist $u, v, w$, with $v$ nonempty and $y = uvw$ such that, for all $n \geqslant 0$,* $$ uv^nw \in L \iff uvw \in L $$ If the pumping lemma fails, you can try its contextual version. According to Wikipedia, the language $\\{ a^mb^nc^n \mid m \> 0 \text{ and } n \> 0\\}$ satisfies the pumping lemma, but can be proven to be non-regular by using its contextual version.

**Pumping lemma (contextual version)**. *If $L$ is regular, then there exists $k \> 0$ such that, for all words $x$, $y$, $z$ with $|y| \geqslant k$, there exist $u, v, w$, with $v$ nonempty and $y = uvw$ such that, for all $n \geqslant 0$,* $$ xuv^nwz \in L \iff xuvwz \in L $$ The pumping lemma, even in its contextual version, only gives a necessary condition for a language to be regular, but there are more powerful versions giving necessary and sufficient conditions. The first one is due to Jaffe \[2\]

**Jaffe's pumping lemma**. A language *$L$ is regular if and only if there exists $k \> 0$ such that each word $y$ of length $\geqslant k$, there exist $u, v, w$, with $v$ nonempty and $y = uvw$ such that, for all $z$ and for all $n \geqslant 0$* $$ uv^nwz \in L \iff uvwz \in L $$ Note the subtle difference with the contextual version of the pumping lemma: the pump is now uniform for all $z$...

Other sufficient conditions using "block pumping properties" were proposed in \[1\] and \[3\]. A language $L$ satisfies the *block pumping property* if there exists $m \> 0$ such that, for any $x$, $u\_1, u\_2, \ldots ,u\_m, y$, there exist $i,j$ such that $1 \leqslant i \< j \leqslant m + 1$ such that, for all $n \geqslant 0$, $$ xu\_1u\_2 \cdots u\_{i-1} (u\_i \cdots u\_{j−1})^n u\_j \cdots u\_my \in L \iff xu\_1u\_2 \cdots u\_my \in L \quad (\*) $$ A language $L$ satisfies the *positive block pumping property* if $(\*)$ holds for all $n \> 0$. Ehrenfeucht, Parikh and Rozenberg \[1\] proved the following result.

**EPR's block pumping lemma**. *A language is regular if and only if it satisfies the block pumping property.*

This result was improved by Varricchio \[4\] as follows:

**Varricchio's block pumping lemma**. *A language is regular if and only if it satisfies the positive block pumping property.*

See also \[3\] for other conditions.

\[1\] A. Ehrenfeucht, R. Parikh, and G. Rozenberg, Pumping lemmas for regular sets, *SIAM J. Comput.* **10** (1981), 536-541.
\[2\] J. Jaffe, A necessary and sufficient pumping lemma for regular languages, *Sigact News - SIGACT* **10** (1978) 48-49.
\[3\] A. de Luca and S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages (Monographs in Theoretical Computer Science. An EATCS Series), Springer 1999. ISBN: 978-3-540-63771-4 (Print) 978-3-642-59849-4 (Online) \[4\] S. Varricchio, A pumping condition for regular sets, *SIAM J. Comput.* **26** (1997) 764-771.

**2. Context-free languages**.

This case is thoroughly discussed in the question How to prove that a language is not context-free?. Pumping lemmas for context-free languages include the standard version of the pumping lemma and Ogden's lemma.

Raphael's nice answer also mentions the Interchange Lemma and gives further references.

**Updated references**.

C. Bader, A. Moura, A Generalization of Ogden’s Lemma. *JACM* **29**, no. 2, (1982), 404-407.

R. Boonyavatana, G. Slutzki, The interchange or pump (DI)lemmas for context-free languages, TCS **56** (1988) 321-338

P. Dömösi and M. Kudlek, Strong Iteration Lemmata for Regular, Linear, Context-Free, and Linear Indexed Languages, G. Ciobanu and G. Paun (Eds.): FCT'99, LNCS 1684, pp. 226–233, (1999).

W. Ogden, R. J. Ross and K. Winklmann, An "interchange lemma" for context-free languages, *SIAM J. Comput.* **14** (1985) 410-415.

D.S. Wise, A strong pumping lemma for context-free languages, *J. Comput. System Sci.* **3** (1976) 359-370.

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


title: What's non-algorithm-specific

text:
# Question
Title: What's non-algorithm-specific
I am reading the paper "Understanding Random SAT beyond the Clauses-to-Variables Ratio" and at beginning of the page 2 say

> the hardest region corresponds exactly to a phase transition in a non-algorithm-specific theoretical property of the instance

I am a Spanish speaker. Can you help to understand what means "non-algorithm-specific theoretical property of the instance".

# Answer
The phrase is explained by the rest of the passage. I'll give a larger excerpt of the paper for context.

> A seminal paper by Selman, Mitchell and Levesque considered the empirical performance of DPLL-type solvers running on uniform-random SAT instances. It found a strong correlation between the instance's hardness and the ratio of the number of clauses to the number of variables in the instance. Furthermore, it demonstrated that the hardest region (e.g., for random 3-SAT, a clauses-to-variables ratio of roughly 4.26) corresponds exactly to a phase transition in a non-algorithm-specific theoretical property of the instance: the probability that a randomly-generated formula having a given ratio will be satisfiable.

The non-algorithm-specific property is the probability that a randomly-generated formula having a given clauses-to-variables ratio will be satisfiable. While the perceived hardness of a particular instance will vary depending on the algorithm used to solve it, the probability that a randomly generated SAT instance is satisfiable does not change if you use different SAT solvers. Yet these two properties are somehow linked.

An example of an algorithm-specific property would be the apparent hardness of pigeon-hole problems encoded as SAT instances. It's been proven that deciding the unsatisfiability of such instances requires exponentially long proofs in the resolution proof system, and thus exponentially long runtimes of solvers implementing that system. However, a solver that implements a simple procedure to break the symmetry of such instances (such as forcing a specific ordering of the pigeons in the holes) allows unsatisfiability to be decided in polynomial time.
> 3 votes

---
Tags: satisfiability
---


# Question
Title: What are examples of inconsistency and incompleteness in Unix/C?
In Richard Gabriel's famous essay The Rise of Worse is Better, he contrasts caricatured versions of the MIT/Stanford (Lisp) and New Jersey (C/Unix) design philosophies along the axes of simplicity, correctness, consistency, and completeness. He gives the example of the "PC loser-ing problem" (discussed elsewhere by Josh Haberman) to argue that Unix prioritizes simplicity of implementation over simplicity of interface.

One other example I've come up with is the different approaches to numbers. Lisp can represent arbitrarily large numbers (up to the size of memory), while C limits numbers to a fixed number of bits (typically 32-64). I think this illustrates the correctness axis.

What are some examples for consistency and completeness? Here are all of Gabriel's descriptions (which he admits are caricatures):

**The MIT/Stanford approach**

* Simplicity -- the design must be simple, both in implementation and interface. It is more important for the interface to be simple than the implementation.
* Correctness -- the design must be correct in all observable aspects. Incorrectness is simply not allowed.
* Consistency -- the design must not be inconsistent. A design is allowed to be slightly less simple and less complete to avoid inconsistency. Consistency is as important as correctness.
* Completeness -- the design must cover as many important situations as is practical. All reasonably expected cases must be covered. Simplicity is not allowed to overly reduce completeness.

**The New Jersey Approach**

* Simplicity -- the design must be simple, both in implementation and interface. It is more important for the implementation to be simple than the interface. Simplicity is the most important consideration in a design.
* Correctness -- the design must be correct in all observable aspects. It is slightly better to be simple than correct.
* Consistency -- the design must not be overly inconsistent. Consistency can be sacrificed for simplicity in some cases, but it is better to drop those parts of the design that deal with less common circumstances than to introduce either implementational complexity or inconsistency.
* Completeness -- the design must cover as many important situations as is practical. All reasonably expected cases should be covered. Completeness can be sacrificed in favor of any other quality. In fact, completeness must be sacrificed whenever implementation simplicity is jeopardized. Consistency can be sacrificed to achieve completeness if simplicity is retained; especially worthless is consistency of interface.

Please note I am not asking whether Gabriel is right (which is a question not appropriate for StackExchange) but for examples of what he might have been referring to.

# Answer
> 16 votes
The question's title suggests that some basic user interface inconsistencies may interest you:

Unix commands don't follow any particular syntax for specifying options and flags. For example, most commands use single letters preceded by '-' as flag: `cat -n some_file`, but exceptions like `tar tf some_file.tar` and `dd in=some_file out=some_other_file count=2` exist in commonly used commands.

Unix and its descendants and relatives have multiple slightly different regular expression syntaxes. Shells use "\*" where other programs (grep, egrep, vi) use '.\*'. egrep has '+' and '|' as operators, grep does not.

The basic "everything is a file" system call interface could be viewed as incomplete: read/write/seek/close doesn't fit every I/O device. Badly needed exceptions get lumped into "ioctl" calls, but devices like sound cards don't even fit that very well.

# Answer
> 8 votes
*Consistency*

Lisp has a very consistent syntax, all language extensions can be embedded naturally via macros and such. C, on the other hand, has a rather code syntax, which allows one to take some "shortcuts", so in some cases C code actually look simplier.

*Completeness*

In Lisp, if you do not have a specific language feature you need, you can implement it yourself with macros. C too has preprocessor, but it is rather perplexing.

# Answer
> 8 votes
C's strings cannot contain character 0 and its library functions are unsuitable for dealing with binary data.

Filenames on Unix systems cannot contain character 0 or character 47 (the slash).

In the original implementation of Unix, filenames were limited to 14 characters. Later versions only relaxed this limitation; they did not eliminate it.

**Added**: The `E2BIG` system error condition, when one tried to `exec` with an argument list that had too many arguments, or occupied too much memory, or an environment that was too big.

Unix is notorious for this sort of arbitrary limitation. Until the advent of Perl in 1987, handling large data sets, or data sets with long records, or binary data, was extremely unreliable.

# Answer
> 4 votes
IIRC my teacher said the inability to use `char *` variables in `switch` statements in C is a matter of inconsistency, but for me that was generality (completeness) issue. I think it's better to use "consistency" just in *your* algorithms or software design not in programming language itself (at least not in languages like C. maybe a buggy language has consistency issue), because programming languages have solid standards that define domain of rules and work by applying input to rules. So if something is not allowed in language, it *planned* to not being allowed and is not inconsistency in language, IMHO.

---

1. I've used generality as completeness. i think they are same thing. maybe I'm wrong.
2. This is Not an answer. maybe suggestion or my opinion.

# Answer
> 3 votes
The best example I have is the poor user who had a file named `.. -r` and typed in `rm *`.

Whether this story is true or not, it's become a Unix hater's classic.

See The Unix-Haters Handbook, which has an introduction by Dennis Ritchie himself, for lots of these examples.

I'll add furthermore that avoiding these types of problems was a major force in the design of Microsoft's Power Shell.

# Answer
> 3 votes
* Certainly the myriad meanings of the same (short) flags to commands is an inconsistency.
* Each program that uses regular expressions has it's own syntax for them
* Configuration files for services are all different syntax (that can be forgiven in part, your mailer daemon has little in common with your webserver or system startup, but still)
* There are different editors! Users use different shells!! Why are there so many desktop environments?!?

OTOH, the fact that the shell expands globs, and not the progam, eliminates a lot of irritating inconsistencies present in other systems. Ditto the fact that you can use the same command to copy a file from one place to the other in the filessytem, to a diskette or from a Zip disk to tape.

So, yes, Unix is inconsistent. So are the other systems, just differently ;-)

# Answer
> 3 votes
LISP supporting infinite precision numbers versus C supporting only machine integers is not an example of language 'correctness'. It is a simple matter arising from the fact that the languages had very different design goals.

The point of C was to be a language close to the machine that could be used to implement operating systems. Machines (mostly) don't support infinite-precision decimal numbers. Machines (mostly) do have integers of fixed bit-lengths.

---
Tags: programming-languages, operating-systems
---


title: Find permutation minimizing distance

text:
# Question
Title: Find permutation minimizing distance
You have a square matrix of weights $W$ and a square matrix of distances $D$. You want to find a permutation $\sigma$ minimizing $$\sum\_{i,j} W\_{i,j} D\_{\sigma(i), \sigma(j)}$$

Is there a known algorithm for that? Is the problem NP-complete? Is the optimal solution easily approximable?

# Answer
> 2 votes
Your problem appears to be very close to the *minimum quadratic assignment problem*, see for example a paper by Hassin, Levin and Sviridenko; your problem is close to the metric variant (since $D$ is a metric). When $D\_{i,j} = |i-j|$ we get the NP-hard problem *minimum linear assignment*, whose best known approximation ratio is $\tilde{O}(\sqrt{\log n})$.

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


# Question
Title: How to make an undecidable Turing Machine decidable?
I came across the following question in my revision. I would like to know how to solve this and in general what are the techniques I can use to make an undecidable TM decidable by changing inputs?

> Suppose that there is a Turing Machine T when, starting with an empty tape, will generate an infinite sequence of programs C1, C2 .... Let L denote this set of programs.
>
> Note that L can be recognizable by a Turing Machine M, which, given any program C, runs T until it has an output Ci equal to C. If C is in L, M will halt and accept C; otherwise M will not halt.
>
> Show how to modify each program Ci in L to another program Ci' such that Ci and Ci' have the same functions and the set L' of all the modified programs C1', C2', ... is decidable. Justify your answer. \[Hint. Make C1', C2', ... strictly increasing in size\]

# Answer
> 5 votes
First of all, as David mentioned, undecidability is a property of a language, not a Turing machine.

As for your question, the hint kind of gives it up. Note that we only need to recognize the programs $C\_i$, not programs who are equivalent (which would be undecidable), so were only dealing with syntax, not semantics.

Let $C\_i'$ be the Turing machine which on input $x$ operates the same way as $C\_i$, but with enough additional states (which were not going to use, i.e. they will be unreachable from the initial state), such that the length of the encoding $|C\_i|$ will satisfy $\forall j\<i : |C\_j|\<|C\_i|$. In that case, to decide $L'$, given an encoding of a Turing machine $\langle M \rangle$, run the machine $T'$ which generates $C\_i'$. If you meet the program $\langle M \rangle$ accept, if you pass the length of the encoding of $M$ (i.e. you reached $i$ such that $|C\_i|\>|\langle M \rangle|$) halt and reject. The difference here is that if we reject, we can be sure we will never meet the encoding of $M$, since $C\_i$ is a series of programs with strictly increasing encoding length.

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


# Question
Title: Does having one large L1 cache instead of L1 and L2 cache makes computation faster?
Does having one larger L1 cache instead of L1 and L2 cache makes computation faster? Also will this make the CPU more expensive to make?

# Answer
Whether a shallower memory hierarchy provides better performance depends on the workload, the microarchitecture, and the implementation technology.

A workload that has a high miss rate for a "conventionally-sized" L1, when run on such a processor, would have more overhead in transferring cache blocks from L2 to L1 and (if writeback) dirty blocks from L1 to L2. In addition, if access to L2 was only started when a miss in L1 is determined, then latency for L2 would be larger (even if L1 in the shallow hierarchy processor used the same memory array implementation as L2).

A microarchitecture suited to modest-sized L1 caches would be biased (relative to one suited to huge L1 caches) toward speed-demon rather than brainiac design, exploiting the lower latency of a cache hit. (Workload, implementation technology, and other factors influence other tradeoffs with respect to speed-demon vs. brainiac.)

If the targeted workload can benefit from extensive hardware threading, providing a larger (and more associative) L1 can be advantageous as the thread-level parallelism can hide greater L1 access latency.

If the implementation technology reduces the latency penalty of a larger cache, the variety of workloads where the tradeoffs (in miss handling overheads and other factors) weigh in favor of a shallower memory hierarchy will increase. For example, in the future it is conceivable that 3D integration might be used for L1 cache and the memory used for this might have relatively high cell access latency (for low power to avoid thermal issues associated with 3D integration), so reduced distance (from 3D integration) and slower memory cells could increase the incentive for a larger L1 cache.

These types of questions become even more complex when one considers that the definition of L1 cache can get somewhat less clear. For example, if what would conventionally be called L2 cache is accessed in parallel with L1 but with higher latency, is it an L2 cache or part of a non-uniform cache architecture L1, especially if some cache blocks are never allocated to the smaller portion of the cache (cache bypassing has been proposed as a mechanism to better utilize capacity and bandwidth). (Even the NUCA L2 cache proposals allowed for transfers between slow and fast portions of L2.) Way prediction can also introduce variable latency for L1; if the prediction mechanism included consideration of expected criticality (and such was used for allocation to near or distant memory arrays within a NUCA design), one might reasonably consider the far memory arrays part of the L1 cache even though their inherent access latency is greater.

(Itanium 2 did not even probe the small L1 data cache for floating-point register loads, so for floating-point data one could almost consider the L2 cache as an L1 cache.)
> 5 votes

# Answer
Note: I first intended to make this a comment under Paul's answer, but it grew too big.

> Does having one larger L1 cache instead of L1 and L2 cache... Also will this make the CPU more expensive to make?

The major issue is that just modifying the size of the L1 cache and removing the L2 one is no more a realistic design, it isn't just the costs of design and fabrication which will change but other design choices will be impacted. You probably can't make only that change, whatever the money you are able to spend out (increasing the size of the L1 cache without slowing it down or switching away from being fully associative is probably not an option, if it was possible it would probably have been done), you have thus now an unbalanced design, and it is not fair to compare a balanced design to an unbalanced one. As an example to show the effect on the design: how do we take the slower cache into account?

* slow down the clock? The pipeline can now and probably should be split differently.
* let the cache access take more pipeline cycles? Again, this means that a redesign of the pipeline is probably in order.

> ...makes computation faster?

Again lots of things missing here. Which computation? And when the computation (or workload which is a set of computations which may have different characteristics) is fixed, what other changes do you accept? A fixed program or do you accept changes (even algorithmic changes) to take into account the new size of caches? In the past I've preferred $O(N \log N)$ algorithms to $O(N)$ one because the $O(N)$ one had a working set too big for the cache, your change could speed it the computation if I change the algorithm, but not if I don't.
> 3 votes

---
Tags: computer-architecture, efficiency, cpu-cache, cpu
---


# Question
Title: Combinations of elements with mutual relationships
I need to create the combination of 3 elements from a array of given *n* elements, however every of those 3 el. has to be in "relationship" with each other. Here is an example I can describe my issue better on:

We've got elements 1, 2, 3, 4, 5 & 6. We know following relationships:

* 1 \<--\> 2
* 1 \<--\> 3
* 1 \<--\> 4
* 1 \<--\> 6
* 2 \<--\> 3
* 2 \<--\> 5
* 3 \<--\> 5
* 3 \<--\> 6
* 4 \<--\> 5
* 4 \<--\> 6

A group {1,2,3} is viable, because 1 is in relationship with either 2 & 3 and 2 is in relationship with 3.

In a group {1,2,4} is 1 in relationship with 2 & 4, however 2 isn't with 4, thus this combination can't exist.

I programmed a functional solution(which involved the above mentioned creating of combinations, redirecting to the list of relations of every element) for small amount of elements and relationship, but I need to have one for approx. 500 000. I'm a high school student and I haven't met a branch of mathematics which would help me to understand or to solve this problem.

I've been searching the net and I think that a relational algebra (binary relations) might be the solution, yet I'm not quiet sure where to start.

Can you think of any hint, advice, web source or view that could help me?

Thank you

# Answer
> 3 votes
The relevant branch of mathematics is graph theory.

Your elements are the vertices of the graph and the relationships between them are the edges. The triples you're looking for are known as triangles: sets of three vertices with all possible edges between them.

I'm not quite sure what you're looking for in your question. If you just want a list of all the triangles in the graph, that can be done naively just by trying all the triples. If you have $n$ vertices in your graph, that takes about $n^3$ tests. More advanced algorithms turn out to be closely related to matrix multiplication, which can be done a little faster – roughly $n^{2.5}$ steps. That might still be rather slow for half a million vertices. If you want to go faster, you'll have to either use approximations (if you're happy with finding most but not necessarily all of the triangles). Alternatively, the particular graph you're interested in might have properties that make it easier to find triangles, for example by ruling out a lot of the possibilities.

Your Google search term is "enumerating triangles in graphs".

---
Tags: combinatorics, relational-algebra
---


# Question
Title: Complete finite automaton to never fail a match but either match original or up until the orginal
Suppose I have a finite automaton to match a simple string "abc" and I built some software around it to not only match the start of a string or a full incoming string, but rather to search through a string and find the first match. As an example consider the string to be "12abcxxx".

The naive approach is to start with reading the '1' and trying a transition in the automaton. It fails. So we advance the input and try again, with \`2'. Fail again. Now read 'a', 'b', 'c' nicely transition though the automaton, reach the stop state, store it, read 'x', fail and declare a match for the latest stop state we ran through.

If we assume that every 'fail' in this algorithm is inefficient, while transitions through the automaton are fast, an improvement would be to extend the automaton such that it matches either 'abc' or '\[^a\]+' and mark the different stop states as 'found abc' and 'not found abc'. Then '123' would be a match, supposedly much faster then three fails to skip over.

But adding '\[^a\]+' is not the only optimization. We could even add something like '(\[^a\]|a\[^b\]|ab\[^c\])+' (which is not completely correct) to the automaton to skip over the non-matching sequences quickly.

**Question**: Working with a finite automaton that allows to mark stop states with different markers, and given an automaton for a regular expression `re`, is it possible to "complete" the automaton such that it implements the quick skip over non-matching substrings as described informally above.

If it is possible, what would be the operation to perform either on the regular expression or an NFA or DFA representation? I would expect the result to talk about something like the complement set of the prefix set recognized by the original automaton.

**Question rephrased**: Reading the first answer I realized that the question is equivalent to the following: Given a regular language $L$, is there a regular language $L\_p$ that satisfies the following: For all strings $s\in\Sigma^\*$, $L\_p$ shall contain the prefix of $s$ that ends just before an $s\_x\in L$ or the complete $s$ if no such substring exists.

# Answer
> 3 votes
Here is what I came up with finally. I need the following operations on finite automata, for automata a and b.

1. allPrefixes(a) creates an automaton that matches all non-empty prefixes of the language L(a). The implementation is quite simple on a DFA. Make sure there are no useless states (those with no path to a stop state). Then make all states except the start state into stop states.
2. invert(a) creates an automaton that matches the complement of L(a).
3. asSubstring(a) creates an automaton that matches every string in $\Sigma^\*$L(a)$\Sigma^\*$.
4. not(a) is a shortcut for invert(asSubstring(a)).
5. or(a,b) is the automaton that recognizes L(a)$\cup$L(b).

Given an automaton a, the automaton which comes very close to what I was after is then easy to describe as c=or(a, not(allPrefixes(a)).

Remember that I want filtering, i.e. find a match, remove the matching input, find a match again and so on until end of input. The automaton c either matches my original a or all kinds of stuff that does not end in any prefix recognized by a. Except for a suffix of the input matching only a prefix of a, there will always be a prefix of the input being matched by c.

# Answer
> 2 votes
Let's use your $abc$ example. Of course, the standard regexp-NFA construction yields a 3-state DFA for the language $\\{abc\\}$. What you want is a DFA which accepts every string represented by the regexp $\Sigma^\*abc\Sigma^\*$. The regexp-NFA construction yields a 4-state NFA with transition table $$\begin{array}{r|ccc} \delta & a & b & c & other\\ \hline q\_0 & \\{q\_0,q\_1\\} & \\{q\_0\\} & \\{q\_0\\} & \\{q\_0\\} \\ q\_1 & \varnothing & \\{q\_2\\} & \varnothing & \varnothing \\ q\_2 & \varnothing & \varnothing & \\{q\_3\\} & \varnothing \\ q\_3 & \\{q\_3\\} & \\{q\_3\\} & \\{q\_3\\} & \\{q\_3\\} \\ \end{array}$$ where $other$ represents any symbol other than $a, b$, or $c$, $q\_0$ is the start state, and $q\_3$ is the final state. Using the standard NFA-to-DFA construction (and merging the 3 final states that result into one) we obtain a 4-state DFA with table $$\begin{array}{r|ccc} \delta & a & b & c & other\\ \hline p\_0 & p\_1 & p\_0 & p\_0 & p\_0 \\ p\_1 & p\_1 & p\_2 & p\_0 & p\_0 \\ p\_2 & p\_1 & p\_0 & p\_3 & p\_0 \\ p\_3 & p\_3 & p\_3 & p\_3 & p\_3 \\ \end{array}$$ where $p\_0$ is the start state and $p\_3$ is the final state. This DFA will take any input string and halt in a final state if the input string contains $abc$ as a substring. If we run out of input and are not in the final state, we know $abc$ does not appear in the input.

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


title: Two red children in a red-black tree

text:
# Question
Title: Two red children in a red-black tree
My data structures exam contains the following question:

> Which of the statements below about red-black trees is true? (select one or more)
>
> 1. Every path from the root to a leaf has the same amount of red links.
> 2. A node never has two red links to his childs.
> 3. Using a red-black tree, you can always draw the associated 2-3 tree.
> 4. All leafs of a red-black tree are at the same height.

The correct answer is: 2 and 3.

I don't understand why a node can never have two red links to his child. On the image below (from Wikipedia), I can see two red childs at node 25.

Could someone explain this to me?

# Answer
> 1 votes
If 2 and 3 are both true, then the red-black trees you are sudying are not the standard ones, i.e., the ones from wikipedia.

The red nodes are usually assumed to be "satellites" of the black node above. If there is at most one red node attached to a black one that means either one or to keays belong together (with altogether either two or three pointers to their children). That nicely corresponds to a 2-3 tree.

The "usual" red-black trees can have two red children (but no red child to a red node) and correspond to 2-4 trees.

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


title: Language of Palindrome-Prefixed Words

text:
# Question
Title: Language of Palindrome-Prefixed Words
> Classify the language $L = \\{xx^Rw\ \big|\ (|x| \geq 0\ \wedge |w|\gt 0)\ where\ x,w\in\Sigma^\*\\}$ as one of:
>
> 1. Regular but not Context-Free
> 2. Context-Free but not Regular
> 3. Decidable but not Context-Free
>
> Most generally, $\Sigma^\*$ can be any regular language (say $(a+b)^\*$).

My first thought is that it can't be regular because palindromes themselves are not regular but I'm unsure if it is context-free or not. My hunch is to attempt the pumping lemma for CFL's to show that it is not context-free and, if that works, try to show that $L$ is decidable.

However, this approach feels prone to confirmation bias so I'm seeking some intuition by observing one's thought process in approaching such problems.

# Answer
Somewhat surprisingly, the language is regular. The key idea here is that you aren't given a $x$ and a $w$, but rather you want all words that *can be expressed* as $xx^Rw$ for *some* $x, w$. The only constraints are that $|\\,x\\,|\ge 0$ and $|\\,w\\,|\>0$.

**Hint** Since you have free choice of $x$, why not choose $x=\epsilon$, the empty string. Then what will $xx^rw$ have to be?
> 2 votes

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


# Question
Title: Need help understanding textbook solution
I am studying for my final exam in coding-theory class, and as textbook provides poorly written solution to the exercise question, I decided to ask the question here, hoping for more clarification.

**Question:**

> If $C\_1$, $C\_2 \subseteq V$ are linear codes, with generator matrices $G\_1$, $G\_2$ and parity-check matrices $H\_1$, $H\_2$, explain how to find a generator matrix for $C\_1 + C\_2$ and a parity-check matrix for $C\_1 \cap C\_2$.

**Textbook solution:**

> Form a generator matrix $G$ for $C\_1 + C\_2$ by adjoining the rows of $G\_2$ to $G\_1$ and then using elementary row operations to eliminate linearly dependent rows. A similar process with the rows of $H\_1$ and $H\_2$ gives a parity-check matrix $H$ for $C\_1 \cap C\_2$.

**Clarification:** My question is by word "adjoining", solution is referring to addition of two matrices or adjudicating them. Also, what is definition of "linearly dependent row"? If you could provide an example, it would be great.

**Note:** I really don't like asking this type of question but combination of unhelpful professor and awful textbook made me to do this.

# Answer
Try to think of it that way. A code $C$, is just a subspace. A generator matrix is simply one basis of that subspace (i.e., each row is a basis element).

So in order to create the subspace $C\_1+C\_2$, you can take a basis of $C\_1$ (for instance, the rows of its generator matrix), and add to it a basis of $C\_2$. The new set is not a basis anymore, but if you eliminate dependencies it will be, and this new basis can be seen as the generator matrix of the new subspace (why?).

Same goes with $C\_1 \cap C\_2$. This subspace contains only elements which are **both** in $C\_1$ and in $C\_2$. Stated via parity matrix, it contains only vectors that are in the kernel of $H\_1$ and in the kernel of $H\_2$. What happens if you build a matrix $H$ that contains both the rows of $H\_1$ and of $H\_2$? Which vectors will be in the kernel now?
> 3 votes

---
Tags: coding-theory
---


# Question
Title: Why is bipartite perfect matching a special case of clique problem?
In Lovász writes \[1\] :

> bipartite graph has a perfect matching, which is a special case of the clique problem

Why is bipartite perfect matching a special case of clique problem?

---

1. The Work of A.A. Razborov by L. Lovász (1990)

# Answer
> 6 votes
Let $G=(V,E)$ be the bipartite graph. Construct a new graph $G'=(V',E')$ whose vertices are the edges of $G$, and where we add $(e,e')$ to $E'$ if $e,e'$ are two edges from $G$ that don't touch each other (don't have an endpoint in common). Now there's a matching of size $s$ in $G$ if and only if there's a clique of size $s$ in $G'$. In particular, there's a perfect bipartite matching for $G$ if and only if there is a clique of size $|V|/2$ in $G'$.

---
Tags: graphs, bipartite-matching, clique
---


# Question
Title: Algorithm A vs Algorithm A*: What's the difference?
I can find quite a bit of literature on A\* but very little on A.

What is the difference between the two search algorithms?

# Answer
> 5 votes
Both A and A\* algorithm use a best-first search to find the least cost path from a start state to a goal state.

Best-first search applies a heuristic evaluation on the states to find the 'best' state. Consider the evaluation function f,

f(n) = g(n) + h(n)

where g(n) measures the cost of reaching any state n from the start state and h(n) is a heuristic **estimate** of the cost of going from state n to a goal. f(n) **estimates** the total cost of the path from the start state throngh n to the goal state

If this evaluation function is used with best-first search, then the result is Algorithm A. Here h(n) is just an estimate of the cost of going from n to a goal. The actual cost is not known.

Now consider the evaluation function f\*,

f\*(n) = g\*(n) + h\*(n)

where g\*(n) is the cost of the **shortest** path from start state to state n and h\*(n) is the **actual** cost of the shortest path from state n to goal.

Although f\* does not exist for most real problems, we would like f to be a close estimate of f\*. In algorithm A, g(n) is a reasonable estimate of g\*(n).

g(n) \>= g\*(n)

They are equal when the graph search has discovered an optimal path to n.

Although we may not compute h\*, it is often possible to determine whether or not the heuristic estimate h(n) is always less than or equal to the actual cost of minimum oath, h\*(n).

If the Algorithm A uses a function f in which

h(n) \<= h\*(n) ,

it is called algorithm A\*.

---
Tags: algorithms, graphs, search-algorithms, shortest-path, heuristics
---


# Question
Title: Proving that two sets of strings are equal
I am stucked at this problem:

---

Let $A=(\Sigma, Q, q\_1, F, \delta)$ be a finite **deterministic** automaton (I.e. $\delta:Q\times\Sigma\to Q$) such that $Q=\\{q\_1,...,q\_m\\}$.

Let's define foreach $i,j\in\\{1,...,m\\}$, $k\in\\{0,1,...,m\\}$

(Note: the $\delta$ below is the extension of $\delta$ to $\Sigma^\*$)

$L\_{i,j}^k=\\{w\in\Sigma^\*|\delta(q\_i,w)=q\_j \land \forall u\in PREFIX(w)-\\{\epsilon,w\\}, \delta(q\_i,u)=q\_x\to x\leq k\\}$

Now let's define the following sets recursively:

For all $i,j\in\\{1,...,m\\}$:
$M\_{i,j}^0=\\{\sigma\in\Sigma|\delta(q\_i,\sigma)=q\_j\\}\cup\begin{cases} \emptyset, \text{if $i\neq j$} \\ \\{\epsilon\\}, \text{if $i=j$} \end{cases}$

For all $i,j,k\in\\{1,...,m\\}$:
$M\_{i,j}^k=M\_{i,k}^{k-1}\cdot (M\_{k,k}^{k-1})^\* \cdot M\_{k,j}^{k-1}\cup M\_{i,j}^{k-1}$

Prove that for all $i,j\in\\{1,...,m\\}$ and $k\in\\{0,1,...,m\\}$ we get $L\_{i,j}^k=M\_{i,j}^k$.

---

I've tried to prove it by induction on $k$ but failed.

(Note: I've encountered these sets in the proof of the Theorem that says that every regular language has a regular expression)

Thanks a lot.

# Answer
It is not totally clear what are your main obstacles to get the proof done.

Note that $L\_{i,j}^k$ is the set of all strings $w$ on a path $\pi$ from $q\_i$ to $q\_j$ such that for each intermediate state $q\_x$ we have $x\le k$; i.e., all intermediate states have index at most $k$.

Consider state $q\_k$. Now either the path $\pi$ does not enter $q\_k$ at all: then all indices are at most $k-1$ meaning that $w$ belongs to $L\_{i,j}^{k-1}$. Or it may enter $q\_k$ one or more times. Thus the path is of the form $\pi: q\_i \leadsto q\_k \leadsto \dots \leadsto q\_k \leadsto q\_j$, where the subpaths may start and end in $q\_k$, but do not pass that state. So the string $w$ can be partitioned into strings that belong to $L\_{i,k}^{k-1}$, $L\_{k,k}^{k-1}$, ..., $L\_{k,k}^{k-1}$, $L\_{k,j}^{k-1}$.

That should prove that $L\_{i,j}^{k} = L\_{i,k}^{k-1} ( L\_{k,k}^{k-1} )^\*L\_{k,j}^{k-1} \cup L\_{i,j}^{k-1}$ (or at least the inclusion from left to right, the other inclusion follows similar argumentation).

With this knowledge the induction is on the subscript $k$, and the induction step is

* If $L\_{i,j}^{k-1} = M\_{i,j}^{k-1}$ for *all* $i,j$ then $L\_{i,j}^{k} = M\_{i,j}^{k}$ for *all* $i,j$.

This should be obvious, just plug in the equations we have.
> 4 votes

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


# Question
Title: Relation between number of edges and vertices in a DAG
I conjecture that, in a Directed Acyclic Graph, $O(|V|) = O(|E|)$. Is this statement correct, can it be refined? This is probably standard material; is there a simple reference about this?

# Answer
> 4 votes
The maximum number of edges in a DAG with n vertices is $\Theta(n^2)$.

Refer https://stackoverflow.com/questions/11699095/how-many-edges-can-there-be-in-a-dag

# Answer
> 4 votes
Take the complete bipartite graph $K\_{n,n}$ and direct all edges from left to right. This is a DAG with $2n$ vertices and $n^2$ edges.

---
Tags: graphs
---


# Question
Title: Meaning of: "'If factoring large integers is hard, then breaking RSA is hard,' is unproven"
I was reading CLRS and is said:

> If factoring large integers is easy, then breaking the RSA cryptosystem is easy.

Which makes sense to me because with the knowledge of $p$ and $q$, it is easy to create the secret key which the knowledge of the public key. Though, it explains the converse statement, which I don't quite understand:

> The converse statement, that if factoring large integers is hard, then breaking RSA is hard, is unproven.

What does the statement above formally mean? If we assume factoring is hard (in some formal way), why does that not imply that breaking the RSA crypto system is hard?

Now consider that if we assumed that factoring is hard...and that we discovered that it meant that the RSA cryptosystem is hard to break. What would that formally mean?

# Answer
> 51 votes
The easiest way to think about it is to think of the contrapositive.

The statement:

> if factoring large integers is hard, then breaking RSA is hard

is equivalent to the following:

> if breaking RSA is easy, then factoring large integers is easy

This statement has not been proven.

What they're saying is, assume we have an algorithm that solves factoring in polynomial time. Then we can use it to construct an algorithm that solves RSA in polynomial time.

But, there could be some other way to crack RSA that doesn't involve factoring integers. It's possible that we will find we can crack RSA in a way that doesn't let us factor integers in polynomial time.

In short, we know that RSA is *at least as easy* as factoring. There are two possible outcomes: RSA and factoring are of equivalent difficulty, or RSA is a strictly easier problem than factoring. We don't know which is the case.

# Answer
> 32 votes
The existence of a hard way does not imply there is no easy way.

There may be a number of ways to break RSA and we only need to find one of them.

---

One of these ways is factoring a large integer, so if that is easy we can do it this way and RSA is broken. This is also the only way we know yet. If it is unfeasible to do that, we can still find another, computationally less demanding way to perform our task without the need to explicitly calculate ***p*** and ***q*** from ***n***.

---

To prove RSA is broken, we need to prove that **one** way to do it is easy.

To prove RSA is safe, we need to prove that **all** ways to do it are hard.

---

Finally, your statement is unproven because it is unproven that no other, easier method exists that extracts information from a cyphertext.

# Answer
> 10 votes
One additional way to look at it, is that breaking RSA requires only a special case of factoring, which may or may not be easy regardless of the general question of factoring.

As a simple example, consider the case that factoring is indeed difficult, but only for numbers with $3$ different factors. Factoring composite numbers with only *two* different factors (as used in RSA) may still be easy.

# Answer
> 7 votes
It means that **the RSA problem seems (at this time) to be more specific than factoring.**

So the RSA problem is this: knowing a semiprime $pq$ and some exponent $e,$ and a value $v,$ find the $m$ such that $v \equiv m^e \mod pq$. (I actually got this wrong in my original answer, so that my phrasing of the RSA problem was equivalent to factoring up to some PP algorithm. Whoops! So you're not alone in being confused at the details here.)

The factoring problem is this: knowing a semiprime $pq,$ find both $p$ and $q$.

If you can efficiently solve the factoring problem, then you can efficiently solve the RSA problem: take the semiprime, factor it, use some theorems about prime moduluses to calculate an inverse exponent $d$ which reveals all ciphertexts as $m \equiv v^d$. (In fact these theorems are how the setup for RSA works: we know the two primes during the setup phase.)

However, it is **not** known that solving this above problem for arbitrary messages $m$ will tell you anything about the factors of the modulus or the exponents involved. It might or it might not; we don't know. Many smart people have presumably looked at the problem but nothing obvious has jumped out at any of them. So it's not known that the factoring problem is solved by solutions to the RSA problem (plus polynomial effort), only that the RSA problem is solved by solutions to the factoring problem (plus polynomial effort).

In fact in 1998 Boneh and Venkatesan published a proof that a certain simple class of algorithms (plus, times, exponents, no XOR/NAND type stuff) cannot be used to turn an RSA-problem solution into a factoring algorithm. The argument had a simple ingenuity to it: by manipulating those arithmetic operations mathematically, we can find out that the "reduction algorithm" (for precision: this is the algorithm which uses an RSA "oracle" for a semiprime to factor that semiprime) turns out to be a factoring algorithm in its own right, so that we can modify it to a variant which makes no calls to its oracle. So we have a trichotomy: either (a) there is no such reduction algorithm, or (b) the reduction algorithm does not have a nice arithmetic interpretation or (c) factoring is polynomial-time just like the reduction algorithm was.

# Answer
> 4 votes
RSA depends on *two* abstract mathematical tasks that are believed to be hard: integer factoring, as you know, but also the discrete logarithm problem. You can break RSA if you can quickly factor a number that's the product of two large unknown primes; but you can *also* break RSA if you can quickly find $\log\_e C$ in the finite group $\mathbb{Z}\_{m}$, where $e$ and $m$ are the public RSA exponent and modulus, and $C$ is the ciphertext.

These two mathematical tasks are related, but (if I remember correctly) it's believed that a solution to one would *not* imply a solution to the other. I don't know if they are the only two ways to break RSA mathematically.

---
Tags: cryptography
---


title: Turing Machine to write number

text:
# Question
Title: Turing Machine to write number
How to construct a single-tape Turing Machine which writes the number 7 in UNARY number system, leaving the tape with a delimiter symbol followed by 7 1s?

So outout would be a tape contains #111111 and blank symbols afterward.

# Answer
The language you describe is regular (because it's finite), so this can be really straight forward.

You could simple write a `1` and advance to the next state. Create 7 states, one state for each `1`.

Consider `input\output/direction` the syntax for "if `input` is on the tape write `output` and move in `direction`"

---
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Is computing a square root of a number and having more than 2 roots a reliable way to decide primality?
I was reading CLRS and it mentions that if $p$ is a prime of the form $4k+3$ and $a$ is a quadratic residue, then $a^{k+1}$ is a square root of $a$. One can also easily show that $a^{-k}$ is a square root of $a$ as well.

Can we use this to get a primality test, for numbers $N$ of the form $N=4k+3$?

After reviewing Miller-Rabin (and after asking the related question Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function? ) and thinking about it a little more I thought of an algorithm that seems promising. The intuition is that if $N=pq$ (or some other composite) there will be more than 2 square roots. Therefore, if we can find more than 2 square roots, we have evidence that $N$ is a composite. With that idea, here is the algorithm:

PrimalityTest$(N)$: (where $N = 4k + 3$)

1. Choose $x \in \mathbb{Z}\_N$ and compute $a = x^2 \pmod N$.
2. Compute $y = a^{(N+1)/4} \pmod N$. (Notice that if $N$ is prime, this is just computing a square root of $a$.)
3. If $y^2 \equiv a \pmod N$ but $y \not \equiv \pm x \pmod N$ then there are more than 2 distinct square roots of $a$. Therefore, return "composite".
4. If $y^2 \not \equiv a \pmod N$ then return "composite". (If $N$ were prime, then step 2 would have computed a valid square root of $a$, so by the contrapositive, if $y$ is not a valid square root, then $N$ is not prime.)
5. If $y^2 \equiv a \pmod N$ and $y \equiv \pm x \pmod N$ we have no idea what $N$ is. Therefore, go back to step 1 and choose a different $x$. If this step happens too often, simply return "prime".

I believe this will succeed with probability 1/2, since it has half chance of choosing a "bad" square root that gives us no information. The only step I am not sure how to analyze probabilistically is step 4, but it seems that step 2 might do nonsense when $N$ is composite, it seems the probability that 4 catches is is quite high. I'd guess around $\frac{N-2}{N}$.

# Answer
There are composite numbers where this primality test fails with probability 1: it always outputs "prime", even though the number is actually composite. These numbers are basically the Carmichael numbers, with a slight twist. Therefore, this is unfortunately not a correct primality testing algorithm.

Recall that $N$ is a Carmichael number if $x^{N-1}\equiv 1 \pmod N$ holds for all $x \in \mathbb{Z}\_N^\*$. All Carmichael numbers are odd. I'll define a super-Carmichael number to be a number $N$ such that $x^{(N-1)/2}\equiv 1 \pmod N$ holds for all $x \in \mathbb{Z}\_N^\*$.

Now consider what happens in your algorithm if $N$ is a super-Carmichael number. We pick $x$ randomly, then compute

$$y=a^{(N+1)/4}=(x^2)^{(N+1)/4}=x^{(N+1)/2} = x^{(N-1)/2} \cdot x = x \pmod N,$$

since $x^{(N-1)/2} = 1 \pmod N$. It follows that we also have $y^2 = x^2 \pmod N$. Thus, no matter what value of $x$ you choose, you'll always find that $y^2 \equiv a \pmod N$ is true and that $y \equiv \pm x \pmod N$ (when $N$ is a super-Carmichael number). So, your algorithm will always give an incorrect answer, when you run it on a super-Carmichael number.

For instance, $1729 = 7 \times 13 \times 19$ is a super-Carmichael number: we have $x^{36} \equiv 1 \pmod{1729}$ for all $x \in \mathbb{Z}\_{1729}^\*$, and $36$ divides $(1729-1)/2 = 864$. Therefore, your algorithm gives an incorrect answer on 1729. I suspect there are infinitely many super-Carmichael numbers. I also suspect that your algorithm might actually give an incorrect answer on all Carmichael numbers (not just the super-Carmichael ones), but I haven't tried to check the details to see if that's actually true.
> 3 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Backpropagation on a matrix of functions
As nicely described in this article, backpropagation for multi-layer perceptrons defines the error term for a neuron in terms of the partial derivative of the weights.

It's traditional to represent the weights between neutrons in matrix form: $w\_{ij}$ representing the weight between neuroma $i$ and $j$. Since a weight can be considered as being as constant multiplier of any input, so a possible generalisation is instead to replace the $w\_{ij}$ with some univariate function $f\_{ij}$.

Since. a 3 layer MLP is already a universal approximator for continuous functions, this generalisation won't be more expressive, but the hypothesis is that it might converge faster for some problems.

My question then concerns the nature of the learning algorithm for this extended formulation:

How might it be possible to define backpropagation if the weight matrix is replaced by a matrix of functions? The functions can be assumed to be differentiable as required.

# Answer
The problem isn't well-defined as you've stated it. Backpropagation involves updating the *weights*, i.e., finding weights that cause the neural network to behave well. If you have no weights, then there's nothing to update.

For these reasons, the standard approach to building neural networks involves both weights *and* univariate functions. In the standard perceptron architecture, there are weights $w\_{ij}$ along each edge (from neuron $i$ to neuron $j$), *and* a univariate function $f\_j$ applied to the output of each neuron (neuron $j$). So standard artificial neural networks *already* incorporate the univariate function. The univariate function $f\_j$ is called an "activation function".

Standard backpropagation does work with arbitrary activation functions. You don't need to modify or generalize it: it already deals with them. In particular, backprop can be used with an arbitrary activation function, as long as you know its derivative. So, I suggest you take another look at how standard backprop works.

Backprop is basically just (a) computation of the partial derivatives (the partial derivative of some objective function, with respect to the weights), computed using the chain rule, plus (b) gradient descent. Introducing arbitrary univariate functions affects only part (a), and the chain rule from calculus tells you how to calculate the partial derivatives.
> 1 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: Show Language is not context free without pumping lemma
Can we show that following language is not context free using Push down automata approach?

```
L = {a^i b^i a^i : i>=1}

```

For every a we will Push 'A' onto stack, for every b we will pop 'A' out of stack so at the end we will have a's onto stack and the input word would be empty as string would be something like aabbaa

Does it seem correct?

# Answer
Your approach doesn't work. We don't know how a putative push-down automaton for the language works. What you show is that a particular PDA doesn't work, but perhaps another one does.
> 2 votes

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


# Question
Title: Update labels of a tree depending on ancestors of nodes in linear time
> You are given a tree $T=(V,E)$ along with a designated root node $r \in V$.The parent of any node $v \ne r$, denoted $p(v)$, is defined to be the node adjacent to $v$ in the path from $r$ to $v$. By convention, $p(r) = r$.
>
> For $k \> 1$, define $p^k(v) = p^{k−1}(p(v))$ and $p^1(v) = p(v)$ (so $p^k(v)$ is the $k$-th ancestor of $v$).
>
> Each vertex $v$ of the tree has an associated non-negative integer label $l(v)$. Give a linear-time algorithm to update the labels of all the vertices in T according to the following rule: $$l\_{new}(v) = l(p^{l(v)}(v)).$$

This is problem 3.20 in Dasgupta's Algorithm.

My thoughts so far:

1. The problem comes down to how you find the $l(v)$-th parent of a node $v$, for all $v \in V$, in linear time.
2. Since chapter 3 is about depth first search, I'm trying to use it. The only way to get the parent once we have the child is to do something in the post-visit routine

```
explore(v):
  v.visited = true
  previsit(v)
  for all u adjacent to v:
    if u.visited == false:
      explore(u)
  postvisit(v)

```
3. If $l(v) = 3$ then somehow we need to send this information up 3 levels in the recursion. But depth first search only moves one level at a time. I don't know how we can preserve the information across multiple calls.

# Answer
> 0 votes
> how we can preserve the information across multiple calls.

Excactly; we use a standard trick of functional programming and add additional parameters to the recursion.

**Idea:** Store (a copy of the) call stack in an array. Then, all ancestors of the current node are accessible in $O(1)$ time. You can do BFS or DFS.

**Details:** The main procedure starts at the root and creates an empty array of sufficient size:

```
relabel(T : Tree) {
  relabelH(T, 0, new Tree[T.size])
}

```

The second parameter stands for the current index in the array (i.e. recursion depth) which we use to determine the index of the $k$th ancestor. The actual work is done here:

```
relabelH(T : Tree, level : Int, ancestors : Tree[]) {
  ancestors[level] = T
  T.label = ancestors[max(0, level - T.label)].label

  for c in T.children {
    relabelH(c, level + 1, ancestors)
  }
}

```

*Correctness*: You can show by induction that `ancestors[0..level-1]` always contains the current node's ancestors in order from root to parent. Hence, the label update is correct. All nodes are reached (we do DFS) so the procedure is correct.

*Running time:* Every line in `relabelH` is executed once per visited node. Every individual line runs in constant time, assuming a reasonable implementation of `Tree`. The main call `relabel(T)` takes linear time (array initialization) plus the cost of the call to `relabelH`. In total, we get a running time in $\Theta(n)$ with $n$ the number of nodes (`T.size`).

---
Tags: algorithms, trees, graph-traversal
---


# Question
Title: Substituting two different identifiers with the same identifier in Coq - why does this work?
I'm playing around with Coq and Software Foundations and is somehow very confused by something I took for granted since forever.

To prove

```
Theorem app_length_cons : forall (X:Type) (l1:list X) (x:X),
                              length (l1 ++ x :: l1) = S (length (l1 ++ l1)).

```

we can first prove

```
Theorem app_length_cons' : forall (X:Type) (l1 l2:list X) (x:X),
                             length (l1 ++ x :: l2) = S (length (l1 ++ l2)).

```

which is a straightforward induction,

```
Proof.
  intros.
  induction l1 as [| h l1'].
  reflexivity.
  simpl.
  rewrite -> IHl1'.
  reflexivity.
Qed.

```

Then simply

```
Proof.
  intros.
  apply app_length_cons' with (l1:=l1) (l2:=l1).
Qed.

```

However, there is something strange going on here - in the induction proof, we are doing induction on l1 and not l2 - and from the proof, it looks like we are assuming l2 doesn't change in the induction case. But when we later apply it with `l2:=l1`, we are breaking this assumption.

Indeed, if we try to prove

```
Theorem app_length_cons'' : forall (X:Type) (l1:list X) (x:X),
                              length (l1 ++ x :: l1) = S (length (l1 ++ l1)).

```

use the same method

```
Proof.
  intros.
  induction l1 as [| h l1'].
  reflexivity.
  simpl.
  -- Can't rewrite use IHl1' : length (l1' ++ x :: l1') = S (length (l1' ++ l1')),
  -- since the goal is S (length (l1' ++ x :: h :: l1')) = S (S (length (l1' ++ h :: l1')))

```

it looks like the assumption that l2 doesn't change is broken thus the proof won't work.

I'm pretty sure I'm missing something here. Why can we substitute different identifiers with the same identifier?

# Answer
> 7 votes
> it looks like we are assuming `l2` doesn't change in the induction case. But when we later apply it with `l2:=l1`, we are breaking this assumption.

No. If we regard `l1` to be a value which is repeatedly decreased in the induction proof, note that we let `l2` to be equal to the *initial* value of `l1` -- such value will not change in the induction steps. In other words: the value of `l1` will decrease, but `l2` will always be the *initial* value of `l1`.

We can even compare it with recursion in programming:

```
# pseudocode
def f(x, y):
   if x==0: return baseValue
   use f(x-1, y)
   return something

```

Just because `f(x, y)` is defined by induction on `x`, it does not mean that later on we can't call `f(a, a)` where both arguments have the same value `a`.

# Answer
> 6 votes
(1) We are just using this general theorem to prove a special case, we don't change anything here. When we use this coq construction

```
apply app_length_cons' with (l1:=l1) (l2:=l1).

```

we just in some sense instantiate this **universally quantified** formula

$$ \forall l\_1, l\_2. \mid l\_1 \cdot (x :: l\_2) \mid~=~succ \mid l\_1 \cdot l\_2 \mid $$

with $l\_2 = l\_1$:

$$ \forall l\_1. \mid l\_1 \cdot (x :: l\_1) \mid~=~succ \mid l\_1 \cdot l\_1 \mid. $$

(2) As for your last proof, it's often harder to prove a special case than a more general one. When you do induction on $l\_1$ you get the head $h$ of the list $l\_1$ twice. You can easily get rid of the first occurrence of $h$, but the second one is buried deeply inside concatenation.

By the way, you can still do one rewrite if you generalize the induction hypothesis in the variable $x$, but this seems to lead nowhere:

```
Theorem app_length_cons'' : forall (X:Type) (x:X) (l1:list X),
                              length (l1 ++ x :: l1) = S (length (l1 ++ l1)).
Proof.
  intros.
  generalize dependent x.
  induction l1 as [| h l1']; intro.
  reflexivity.
  simpl.
  rewrite IHl1' with (x := h).

```

---
Tags: logic, induction, coq
---


# Question
Title: Lower Bound for Comparison-based sorting algorithms
We know that the lower bound for comparison-based sorting algorithms is Ω(nlogn), where logn being the binary logarithm of n. But what about for the best-case scenario of the bubble sort, which takes O(n) time? Of course, n is faster than nlogn. Why is that?

However, I don't know if this bound only applies for the worst-case scenario. I haven't ever learned the lower bound for the best- or average-case scenario. Is it different from the other?

(This question comes from the http://cstheory.stackexchange.com)

# Answer
> 1 votes
The lower bound of sorting algorithm comparison based is $O(nlogn)$.
The best case lower bound is $O(n)$ which comes from fact that you need to check if numbers are sorted, so you traverse all of them to find out if they are ordered.

The lower bound is applied to all instances of problem, not just lucky particular case.

---
Tags: algorithms, sorting, lower-bounds
---


# Question
Title: Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$
I want to find a near-optimal solution for a maximum weight independent set. i.e given a graph $G = (V,E)$ I want to find a set $S = \\{v\_1,v\_2,\dots,v\_n\\}$ of nodes in $V$ such that the sum of their weights is maximum (The weights are positive), under the constraint that every pair is not connected by an edge, i.e $\forall\ v\_i,v\_j \in S:(v\_i,v\_j) \not\in E$.

A common problem instance would be a graph with around $2 \times 10^5$ nodes, up to around $5 \times 10^5$. The degree of a node is bounded by ~$100$, and the number of edges will be around $10^6$.

Can anyone recommend a heuristic algorithm for finding a near-optimal solution? A runtime of hours or even days is acceptable.

I've been looking so far at articles about Tabu search and that is the current direction I am going towards.

# Answer
> 5 votes
Unfortunately, (weighted) maximum independent set is very hard to approximate. You might be able to do a bit better if you can analyze the graphs in your application (perhaps they are not truly arbitrary).

In any case, luckily your graphs are quite small (200 thousand vertices or so). A naive algorithm (say a greedy one) will run quite fast, but might be far from the optimum. Especially since several hours (or even days) of runtime is fine, I'd experiment with a genetic algorithm.

Being a rather central problem, there are studies into this as well. For a starter, one could look at \[1\]. In practice, I would expect one to be quite happy with such an approach.

---

\[1\] Hifi, Mhand. "A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems." Journal of the Operational Research Society 48.6 (1997): 612-622.

---
Tags: graphs, search-algorithms, heuristics
---


# Question
Title: Can the Hamiltonian path problem be solved by dynamic programming in $O(2^n n)$ time?
Let G(V,E) be the graph and V = {$V\_1$,$V\_2$,....,$V\_n$}. A dynamic programming approach solves the Hamiltonian path problem in $O(2^n n^3)$ time.

We can have a matrix : dp\[s\]\[i\]\[j\] : which computes for any subset (say s) of V whether there exists a hamiltonian path starting from vertex $V\_i$ and ends at vertex $V\_j$ if s includes $V\_i$ and $V\_j$.

Can we have only dp\[s\]\[i\] and say whether there exists a hamiltonian path ending at vertex $V\_i$ there by solving it in $O(2^n n^2)$ time. Can it be improved furthur?

# Answer
> 3 votes
Yes, the problem can be solved in $O^\*(1.657^n)$ time using algebraic methods. See the FOCS paper of Björklund \[1\].

---

\[1\] Björklund, Andreas. "Determinant sums for undirected Hamiltonicity." Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. IEEE, 2010.

---
Tags: algorithms, complexity-theory, graphs, dynamic-programming
---


# Question
Title: Examples of maximal paths in undirected graphs
According to me, maximal paths in a graph are those paths which cannot be included in any other larger paths. Could anyone please explain me this with some examples? Also what would happen if the graph happens to contain cycles?

# Answer
> 5 votes
We can say a path is *maximal* if you cannot add any new vertices to it to make it longer. You can contrast this with a path of *maximum length*: it is the longest path in a graph (so it is also maximal, but note the difference). A bit informally, when something is "maximal", it means you cannot add anything to it to make it larger. When something is "maximum", it is globally the largest "object" there is.

For an example, consider the tree pictured in this Wikipedia article. The path on the vertices $\\{1,2,4\\}$ is maximal; you cannot add any vertex to it to make it longer. But a maximum path (i.e., longest path) in the tree is on the vertices $\\{ 1,4,5,6 \\}$. Clearly, it is no problem if the graph you consider contains a cycle. For example, then you can see that not every vertex of the graph can be in a longest path.

---
Tags: graphs, discrete-mathematics
---


# Question
Title: If the speed of electrical charge hasn't changed, how have computers become faster?
Everyone knows computing speed has drastically increased since their invention, and it looks set to continue. But one thing is puzzling me: if you ran an electrical current through a material today, it would travel at the same speed as if you did it with the same material 50 years ago.

With that in mind, how is it computers have become faster? What main area of processor design is it that has given these incredible speed increases?

I thought maybe it could be one or more of the following:

* Smaller processors (less distance for the current to travel, but it just seems to me like you'd only be able to make marginal gains here).
* Better materials

# Answer
> 56 votes
> if you ran an electrical current through a material today, it would travel at the same speed as if you did it with the same material 50 years ago.
>
> With that in mind, how is it computers have become faster? What main area of processor design is it that has given these incredible speed increases?

You get erroneous conclusions because your initial hypothesis is wrong: you think that CPU speed is equivalent to the speed of the electrons in the CPU.

In fact, the CPU is some synchronous digital logic. The limit for its speed is that the output of a logical equation shall be stable within one clock period. With the logic implemented with transistors, the limit is mainly linked to the time required to make transistors switch. By reducing their channel size, we are able to make them switch faster. This is the main reason for improvement in max frequency of CPUs for 50 years. Today, we also modify the shape of the transistors to increase their switching speed, but, as far as I know, only Intel, Global Foundries and TSMC are able to create FinFETs today.

Yet, there are some other ways to improve the maximum clock speed of a CPU: if you split your logical equation into several smaller ones, you can make each step faster, and have a higher clock speed. You also need more clock periods to perform the same action, but, using pipelining techniques, you can make the rate of instructions per second follow your clock rate.

Today, the speed of electrons has become a limit: at 10GHz, an electric signal can't be propagated on more than 3cm. This is roughly the size of current processors. To avoid this issue, you may have several independent synchronous domains in your chip, reducing the constraints on signal propagation. But this is only one limiting factor, amongst transistor switching speed, heat dissipation, EMC, and probably others (but I'm not in the silicon foundry industry).

# Answer
> 15 votes
There are a lot of complex variables that affect overall CPU speed, but a main one is clock speed which increased into the mid 2000s and then flatlined due to physical limitations. Power consumption per chip also increased over that period to make up for chip losses/ leakage. CPU chips just got too hot and cooling technology became more important, and more wattage could not be applied (without literally melting them!).

Extremetech.com gives a nice survey that points out that Moore's law is thought to be actually mainly fueled by Dennard scaling. The latter collapsed in the mid 2000s. There are many other design factors/improvements involved in chip "speed" (where "speed" is measured as overall code execution time and not merely clock speed) that tended to mask the inflection point in hardware capability such as caches, CPU parallelism/multicore, branch prediction, etc., which were added with smaller gate widths (and therefore far more gates per chip for additional functionality). Gate widths have also tended to stop decreasing or at least decrease less quickly each generation.

Why are these limiting trends not very well known? Some of the entities that have the most knowledge of these trends "have the most to lose" and are actually the least likely to publicize them. E.g. Intel, worth billions of dollars, will not likely publish proprietary internal data pointing to limits or decreases in future performance.

There are new possibilities on the horizon which could lead to entirely new trends (but some involve almost completely different technology/manufacturing techniques) including photonic chips, 3-D chips where chips are laid down in multiple layers, quantum computing, nanotechnology such as nanotube transistors, etc.

# Answer
> 5 votes
## Delegation to Additional Processors

Another consideration (in addition to the other great answers) is the delegation of tasks to other processors. In the early computing days, there was only one processors. For graphics, the computation was shared with other computation in the same CPU. Now, we have separate processors for graphics processing.

## Multiple Cores

Many of the modern processors have multiple cores, in the same piece of silicon. Because they share the same piece of silicon, they are not affect as much by the slowing of going off chip to another core / processor. Example: Graphics Processors.

## Memory and Address Expansion

The early 8 bit microprocessors had a smaller addressing range than today's 32-bit and 64-bit processors. The modern processors have an increased memory range, which means more computation can be performed in memory rather than having to access external storage.

This also applies to on-chip memory too. The larger address space allows for bigger memories closer to the central core, while still leaving a large address space outside the silicon.

## Pipelines and Caches

With memory becoming cheaper, modern computers are now implementing more sophisticated data and instruction pipelines as well as data and instruction caches. This speeds up execution by reducing the need to fetch from slower memory (outside the silicon) to internal cache. Some processors have the capability to contain `for` loops in their instruction caches.

## Summary

Today's computers are a lot faster, not only due to the advances in transistor and silicon technologies, but also due to the delegation of tasks to other processors / cores. Memory becoming faster and cheaper allows processors to have lots of memory close to the CPU. Addressing ranges allow for more memory which means less fetches to external storage. Larger register sizes allow for more data to fetched per cycle (4 bytes with a 32-bit system, 1 byte with an 8-bit system). Multiple cores allow for paralleling operations rather than serializing them.

# Answer
> 4 votes
Almost *all* advances in computer speed come from one of these areas:

## Smaller transistors

Two things result from making transistors smaller:

1. They are physically closer together, so the time it takes for an electrical signal to travel from source to destination is smaller. So **although electrical signals don't travel any faster than 50 years ago, they often travel shorter distances now**.
2. More transistors can be included on a chip, which means more "work" can be done at the same time. The more transistors are added, the harder it is to find useful work for them to do, but many clever tricks are used (see below).

## More "useful work" per instruction

For example, some processors lack instructions to multiply or divide integers; instead this task must be performed with slow software routines. Adding multiply and divide instructions speeds things up considerably. Adding floating-point instructions can speed up software that requires floating-point numbers.

An important way of doing more "useful work" per instruction is increasing the **word size**. CPUs that can perform operations on 32-bit numbers often require far fewer instructions to perform the same task as 16-bit or 8-bit CPUs.

Some processors support instructions that do several things at once, in particular instructions that do the same operation on multiple data items (SIMD).

## More instructions per cycle

The "clock cycle" is how the processor goes from its current state to the next state. In a sense it is the smallest unit of work the processor can do at a time. However, the number of clock cycles a particular instruction takes depends on the processor's design.

With the advent of pipelined processors, it became possible for separate instructions to "overlap", i.e. one would start before the previous one finished. However, certain instructions can invalidate the next instruction, which will not be known until the next instruction has partially executed, so things can get complicated. (Pipelined processors include logic to make sure everything works out OK—but performance characteristics are more complex.)

Superscalar processors take this to the next level, literally allowing two instructions to execute at the same time, and out-of-order execution takes it one step further, allowing instructions to be executed out of order. These features require analysis of the instruction stream, working out which instructions don't clash with each other.

Although there are other such tricks (e.g. branch prediction, speculative execution), what's more important is the overall picture:

* every instruction takes a certain number of clock cycles to complete (not necessarily constant)
* but multiple instructions can be in progress at once
* so there is a measurable "instructions per cycle" which is \>1 for high-end processors
* but it depends very strongly on the workload

## More cycles per second

In other words, higher clock speed. Increasing clock speed not only increases heat generated, but also requires much more disciplined chip design, because there is a smaller time limit for the circuit to stabilise. We got a lot of mileage out of this one until the 2000s when we hit some practical limits.

## Data in the right place at the right time

Although the components within the CPU have been getting closer and closer together due to shrinking transistors, the CPU and RAM are still a good 5-10cm apart. If an instruction needs something from RAM, that instruction won't take 5 or 6 cycles to complete, it'll take around 200. This is the von Neumann bottleneck problem.

Our main weapon against this is the **cache**. Recently-accessed data is more likely to be accessed again, so it is kept in special memory (called cache) that is within the CPU chip, making it much faster to access.

However, other techniques (such as pipelining and branch prediction) help by allowing the processor to do useful work while waiting for data to arrive, and also predicting which data might soon be needed.

## Multiple and/or specialised processors

It's a lot easier to write software for a single processor than for multiple processors. However, sometimes the performance/cost/power consumption benefits make it worthwhile.

Also, certain processors are particularly well suited to certain tasks. For instance, GPUs are specifically designed for the calculations required for rendering 2D and 3D graphics and effects.

Multi-core processors are essentially multiple processors on a single chip.

# Answer
> 3 votes
When computers can do more computations per unit of time, they are seen as being faster. Each computation may not be done any faster than before, but there are more computations being done. A good analogy would be the number of steps that a runner takes. If a runner behaved according to Moore's law, the runner would be able to take twice as many steps every two years. In essence, the runner would be covering twice the distance in the same amount of time the runner did two years ago. Distance divided by time equals speed. 2 X Distance equals 2 X Speed.

# Answer
> 3 votes
The processing power of a computer/CPU it's really how fast electricity travels but rather how fast it can be turned on and off. The faster you can switch between current flowing and not flowing, the more information you can process within a cpu or transmit down the line.

# Answer
> 2 votes
For typical processors used in PCs, heat dissipation has been a limiting factor for over a decade, where air cooled processors in PC's have been limited to about 4 ghz. Water cooling raises this to about 5 ghz, and nitrogen cooling has been used to push clock rates to around 6 ghz to 6.5 ghz.

The clock rate is basically a function of voltage versus circuit logic size (how long it takes a switch to change states). The higher the voltage or the smaller the circuit logic, the faster the rate, but this presents a heat dissipation problem as densities typically increase along with reduction in circuit logic size. With the high density, there's not a lot of room left for heat conducting material to dissipate the heat. Reducing density increases cost, and also increases propagation delays due to longer lengths of the circuitry.

CPU's haven't gotten that much faster in the last few years, the current Intel i7 4790K (4.0 ghz, 4.4 ghz turbo) isn't that much faster than the second generation Intel i7 2700K (3.5 ghz, 3.9 ghz turbo), other than it's faster clock rate (about 14.3% faster). On the other hand, since 3d graphics can take advantage of parallel operations, video cards have increased in performance by a factor around 3 in the last 4 or 5 years, some have the equivalent of 3,000+ sub-cores.

# Answer
> 2 votes
Although the already given answers are good, they all seem very complicated!

The quick "TLDR" answer is "number of logic gates", and "how quickly can those logic gates fire". Think of the logic gates like 1s and 0s. This is just a transistor/vaccum tube/whatever turning on or off. 1 is on 0 is off.

Electricity doesn't move any faster or slower, but you can cram more ones and zeroes onto your chip because the ones and zeroes themselves are smaller. And you can make them flip faster over time. Does that make a little simpler answer?

# Answer
> 2 votes
The two biggest factors by far are the fact that transistors have shrunk by a ridiculous degree and therefore we have now smartphones with far over a billion transistors, and the fact that switching a transistor from one state to another has become a lot faster. The faster switching translates directly into more speed. The higher number of transistors increases speed indirectly because it is an enabler of many other improvements being mentioned: We have caches because we have more transistors. We have more and bigger registers because we have more transistors. We have vector instructions because we have more transistors. We have dual, quad core, or ten core processors because we have more transistors.

To a much smaller degree we have speed improvements because of better design. For example, a multiplier isn't just faster because we have more transistors, but because we use better methods. Branch prediction has improved beyond just having more transistors available. But all in all, this is a small effect compared to the brute power of a billion transistor.

(The processor in the first Mac was called a Motorola 68000 processor because it had 68000 transistors. A new iPad has about 20,000 times more).

# Answer
> 0 votes
I am a mechanical engineer, so I am not familiar with how much this affects the speed of a processor or whether it has become a limiting factor or not, but the physics behind it are sound. The inductance and capacitance of the circuit will affect how fast the digital voltage signals can rise and fall -- thus affecting the switching speed. Ideally, the switching signals would be nice square waves. In reality they are slightly deformed and sloped at the edges. The signals have to go high and be high long enough to be read before the next clock cycle. Essentially, the signal wave needs a "flat spot" at the top. If you switch too fast, you will get more of a pointy wave signal. Those of you who are more familiar with digital signals can clarify if needed, but the idea is right.

---
Tags: computer-architecture
---


# Question
Title: A median of an AVL. How to take advantage of the AVL?
Here is the source of my question.

> Given a self-balancing tree (AVL), code a method that returns the median.
>
> (Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is
>
> 2, 7, 4, 9, 1, 5, 8, 3, 6
>
> then the median is 5.)

I can offer the following solution:

1. Traverse the given tree, return the number of elements.
2. Traverse `n / 2 + 1` (if `n` is odd) the tree again applying an in-order tree walk. The value of the `n / 2 + 1`th element is the median.

But I can do it with a binary search tree, can't I? Is there a better algorithm for an AVL?

# Answer
> 10 votes
If you modify the AVL tree by storing the size of the subtree at each node rather than just its height, then you can find the median in time $O(\log n)$ using the fact that the tree is balanced. To accomplish this, you write a more general procedure *Select* which accepts a node $v$ and a number $k$, and finds the $k$th smallest node at the subtree rooted at $v$.

Suppose that the left subtree (if any) has $L$ nodes. If $k \leq L$ then we recurse to the left subtree. If $k = L+1$ then we return $v$. Otherwise we recurse to the right subtree, reducing $k$ by $L+1$.

The running time of this algorithm is linear in the height of the tree, which is $O(\log n)$.

# Answer
> 0 votes
AVL is binary search tree with some special property: it is self-balancing tree. It's height is always logarithmic. Ordinary binary tree in some worst scenario can be linked list (if you add sorted data) so it's height is n. AVL tree in worst scenario is fibonacci tree.

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


title: Certificates and NP?

text:
# Question
Title: Certificates and NP?
My book says a language is in NP if it can polynomially verified if a string belongs to the language with a certificate. It puts no restrictions on what the certificate can be.

For instance, for SAT, the certificate could simply be be the assignment values. We just sub them in and see if it satisfies the expression.

But can't we just let the certificate by whether the string belongs or not? So for instance, for SAT, instead of the certificate being the assignment values, we let it be whether the expression is satisfiable or not. In other words, the certificate is the "answer".

If we let the certificate be this, can't be verify any string in polynomial time? Constant in fact, because we would just be returning the certificate itself, since the certificate is the "answer" (whether the string is part of the language or not)

# Answer
You must be able to verify in deterministic polynomial time that the certificate is correct.

If your certificate for SAT is a truth assignment, you can verify that it's a satisfying assignment in deterministic polynomial time, by substituting the truth values of the variables and simplifying the expression. However, if your certificate was just "It's satisfiable, honest!", then you would only be able to verify that if you could solve SAT in **P**, which you probably can't. The certificate has to be a proof that the string is in the language, not just a claim that it is.

Indeed, if it was enough to just claim that the string is in the language, then *every* language would be in **NP**! For example, the certificate version of the halting problem would be just the set of all strings "$\langle M, w\rangle\text{ It halts, honest!}$" for all machines $M$ and inputs $w$ such that $M(w)$ halts, and all strings "$\langle M,w\rangle\text{ This one loops - too bad!}$" for all machines $M$ and inputs $w$ such that $M(w)$ doesn't halt.
> 6 votes

---
Tags: complexity-theory, time-complexity, np
---


# Question
Title: Which commercial company was the earliest adopter of Linux?
I tried reading some articles and even watched Revolution OS, but was unable to come to a conclusion. Thought this would be a better place to get the answer.

From my gathered information: It is either IBM or Dell or something else.

> Which commercial company was the earliest to adopt/port to Linux?

PS: If I am in the wrong community of StackExchange, then please comment the correct section.

# Answer
> 1 votes
It might be impossible to say conclusively which was the first.

However one good way to learn about early business adopters of Linux would be to read about companies like Redhat and SUSE, which were not only using Linux very early on, but actually had it at the core of their business.

Both companies were releasing their Linux distributions for sale in 1994 - just 3 years after Linus announced the creation of Linux (and several years before IBM became seriously involved with Linux development).

---
Tags: history
---


# Question
Title: What exactly is the LL(k) grammar condition?
I have a bit of trouble understanding the definition of LL(k) grammars.

Here it's defined as:

> for every pair of production rules $A\rightarrow α$ and $A \rightarrow β$ the following condition holds.
> $\text{FIRST}\_k$ ( $\text{α FOLLOW}\_k$ (A)) $\cap$ $\text{FIRST}\_k$ ( $\text{β FOLLOW}\_k$ (A)) $=\emptyset$

What does this mean concretely? What is the subscript $\_k$?
Why is it for a "pair of production rules"?

# Answer
> 5 votes
It's actually a definition of a *strong* LL(k) grammar.

First of all, see Raphael's comment.

In short, the condition means that while parsing $A$ you can choose the next production rule in a deterministic manner using **only** the next $k$ lookahead symbols.

An important thing is you don't need any context for that decision, i.e. you don't need to remember the previous steps in the left-most derivation that led you to the non-terminal $A$ to parse $A$ itself.

By the way, every LL(1) grammar is strong, but there are non-strong LL(k) grammars, $k \> 1$.

If you need a more detailed explanation, then I think it's better to use a book for that (it's too long for an answer here). I'd suggest "Parsing Techniques - A Practical Guide" by Dick Grune et al.

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


# Question
Title: Difference between read-only Turing machine and non-erasing Turing machine
I cannot quite feel the difference between two models.

The first one is read-only Turing machine which is basically the same as Turing machine with write protected input. See this question for example: Single-tape Turing Machines with write-protected input recognize only Regular Languages

It was said that it indeed recognizes only regular languages because there is no way to copy an input without rewriting it somewhere.

And there are non-erasing Turing machines that (in binary representation) cannot overwrite $1$ with $0$. This is equivalent to full power Turing machine as it was explained here Non-erasing Turing machines and loss of generality and in the paper http://arxiv.org/pdf/1304.0053

But what is the difference? We still cannot copy some strings like $1111$ due to lack of overwriting power.

So why it is weak when we cannot write only on input but strong when we cannot overwrite $1$ with $0$ everywhere? Why we can encode strings in one case but not the other?

# Answer
> 5 votes
A non-erasing TM has a tape alphabet $\\{0,1\\}$ where $0$ acts as blank. The $0$ can be rewritten into $1$, but that symbol cannot be "erased", i.e., written back into $0$.

This restriction seems to be equivalent to symbols that can be rewritten only a finite number of times. TM's do have the capability of interpreting a finite segment of tape as one symbol. Then $0000$ can be rewritten into $0001$ then into $0011$, into $0111$, into $1111$. A little modulo counting interprets these segments as $0,1,0,1,0$.

Recall that a TM is equivalent to a finite state machine that has a queue as basic datastructure. It can read and delete on one side, and write on the other. To see that this is equivalent to a TM a rotation trick is done: the queue holds the tape in a circular fashion, but can only move on the tape in one direction. To move into the other direction just move all the way.

This rotation trick can also be done on the tape of a TM, and needs only finite rewrites on the same position. One needs to be able to rewrite the tape from $Ax$ into say $xB$ where $A,B$ are symbols and $x$ is a string.

---
Tags: turing-machines
---


# Question
Title: Why does quantum cost on gates formed from specific qubit gates not factor swap gates into account?
I've been reading a number of quantum computation research papers that claim quantum cost's that do not add up.

For instance, in this paper \- there is a claim that the MTSG gate is a quantum cost of 6. But to actually perform the computation, you need swap gates to get the stuff into the right order!

For instance, to even perform the first gate `V(B, D)`, you'll need to do the following:

`1) U = TENSOR(ID, SWAP, ID)
 2) U = TENSOR(ID, ID, VGATE)
 3) APPLY (U, R)
 4) SWAP BACK`

Am I getting something wrong here?

# Answer
The paper just uses the swaps to make the diagram simpler. It allows the authors to represent the relevant operation as a single box covering four wires, instead of the six underlying operations, when making larger circuits.

Here is a screen capture of the definition of the "MTSG" gate from the paper (note: the $V$ gate is just a square-root-of-NOT gate):

(They managed to make them look pretty terrible...)

And here's a place where it's used:

If you expand each MTSG box in that larger circuit into the underlying 6 operations, and align the diagram onto a fixed set of wires, you'll find you can easily slide any implied swap gates out of the circuit.

(But do keep in mind that it's possible that the first practical quantum computers will have limitations like 'only nearest neighbors in a 2d grid can interact'. That would force the use of many swap gates.)
> 1 votes

---
Tags: quantum-computing
---