# Question
Title: Can we show a language is not computably enumerable by showing there is no verifier for it?
One of the definitions of a computably enumerable (c.e., equivalent to recursively enumerable, equivalent to semidecidable) set is the following:

> $A \subseteq \Sigma^\*$ is c.e. iff there is a decidable language $V\subseteq \Sigma^\*$ (called verifier) s.t. for all $x\in \Sigma^\*$,
>
> $x\in A$ iff there exists a $y\in\Sigma^\*$ s.t. $\langle x, y \rangle \in V$.

So one way to show that a language is not c.e. is to show that there is no decidable verifier $V$ for it. Is this method useful to show that languages are not c.e. in practice?

# Answer
> 4 votes
In practice, we don't usually prove just that a language is r.e. or not r.e.. If the language is r.e., we want to know whether it is recursive. If it is not r.e., we want to know what sort of Turing degree it has, not just that the Turing degree is not r.e..

For example, if $P$ is a problem with $P' \equiv\_T 0'''$ then $P$ is not r.e., but that fact about the Turing jump is more informative than just knowing $P$ is not r.e.

So while, in principle, you could show that a language is not r.e. by proving there is no verifier, in practice it is more informative to prove that the language is not r.e. by showing that it computes something that no r.e. set can compute; the nature of that 'something" typically gives useful information about the problem being studied.

# Answer
> 3 votes
To make the terminology I use clear: decidable = recursive = computable, semidecidable = recursively enumerable = computably enumerable, co-semidecidable = co-recursively enumerable = co-computably enumerable.

In practice, a common method to show that a language is not semidecidable is to show it is not decidable and that it is co-semidecidable. You then make use of the fact that any language that is both semidecidable and co-semidecidable is also decidable to conclude that your language is not semidecidable. (note that this only works in one direction: a language can be neither semidecidable nor co-semidecidable, in which case you need some other method)

As an example: we know that deciding whether a $\mathrm{CFG}$ is ambiguous is undecidable, but it is easy to co-semidecide: you just give a string that has two different parses. This implies that it is not semidecidable whether a $\mathrm{CFG}$ is ambiguous.

Another method is to show that the language is complete for some higher level of the arithmetic hierarchy.

It is of course possible to directly prove there is no verifier, but this is often tedious, as it usually repeats the proof that the halting problem is undecidable. Note though that the above argument essentially implicitly proves there can be no verifier, so I guess that you could say it is a method to prove there is no verifier, but then you could consider any proof of non-semidecidability as a proof that there is no verfier.

---
Tags: computability, proof-techniques, undecidability
---


# Question
Title: Turing reducibility implies mapping reducibility
The question is whether the following statement is true or false:

$A \leq\_T B \implies A \leq\_m B$

I know that if $A \leq\_T B$ then there is an oracle which can decide A relative to B. I know that this is not enough to say that there is a computable function from A to B that can satisfy the reduction.

I don't know how to word this in the proper way or if what I'm saying is enough to say that the statement is false. How would I go about showing this?

EDIT: This is not a homework problem per se, I'm reviewing for a test. Where $\leq\_T$ is Turing reducibility, and $\leq\_m$ is mapping reducibility.

# Answer
> 11 votes
The statement is false.

Say B is the Halting problem and $A = \overline B$. Then, given oracle to the halting problem we can easily decide its complement.

However it is not true that $A \le\_m B$ since $B\in RE$ and $A\in coRE$ but both are undecidable (i.e., if $A \le\_m B$ was true, then $B=HP$ is both in $RE$ and $coRE$, that is, $B\in R$ which is a contradiction).

# Answer
> 7 votes
It is false: take $Diag = \\{\langle M \rangle \mid M \notin L(M) \\}$ and its complement.

Generally $\leq\_T$ can be used to reduce a problem to its complement while $\leq\_m$ cannot.

If you want to know see more kinds of reductions and examples that they are different I suggest having a look at "Classical Recursion Theory" by Odifreddi.

# Answer
> 2 votes
There is a general fact that every noncomputable Turing degree contains infinitely many distinct $m$-degrees.

(This result follows at least from results of Jockusch, "Relationships between reducibilities", Trans. Amer. Math. Soc. 142 (1969), 229-237. It might have been known before that.)

---
Tags: computability, reductions, turing-machines
---


# Question
Title: How to scale down parallel complexity results to constantly many cores?
I have had problems accepting the complexity theoretic view of "efficiently solved by parallel algorithm" which is given by the class NC:

> NC is the class of problems that can be solved by a parallel algorithm in time $O(\log^cn)$ on $p(n) \in O(n^k)$ processors with $c,k \in \mathbb{N}$.

We can assume a PRAM.

My problem is that this does not seem to say much about "real" machines, that is machines with a finite amount of processors. Now I am told that "it is known" that we can "efficiently" simulate a $O(n^k)$ processor algorithm on $p \in \mathbb{N}$ processors.

What does "efficiently" mean here? Is this folklore or is there a rigorous theorem which quantifies the overhead caused by simulation?

What I am afraid that happens is that I have a problem which has a sequential $O(n^k)$ algorithm and also an "efficient" parallel algorithm which, when simulated on $p$ processors, also takes $O(n^k)$ time (which is all that can be expected on this granularity level of analysis if the sequential algorithm is asymptotically optimal). In this case, there is no speedup whatsover as far as we can see; in fact, the simulated parallel algorithm may be *slower* than the sequential algorithm. That is I am really looking for statements more precise than $O$-bounds (or a declaration of absence of such results).

# Answer
If you assume that the number of processors is bounded by a constant, then you are right that a problem being in NC does not mean much in practice. Since any algorithm on a PRAM with *k* processors and *t* parallel time can be simulated with a single-processor RAM in O(*kt*) time, the parallel time and the sequential time can differ only by a constant factor if *k* is a constant.

However, if you assume that you can prepare a computer with more processors as the input size grows, then a problem being in NC means that as long as you can prepare more processors, running time will be “very short” or, more precisely, polylogarithmic in the input size. If you think that this assumption is unrealistic, compare it to the assumption of unbounded memory: actual computers have only finite amount of space, but in the study of algorithms and complexity, we almost always assume that a computational device does not have a constant upper bound on space. In practice, this means that we can prepare a computer with more memory as the input size grows, which is how we usually use computers in the real world. NC models an analogous situation in parallel computation.
> 13 votes

# Answer
I agree with you that $NC$ is not the best way to characterize efficient parallel algorithms.

Indeed, by definition NC also includes lots of problems which are not efficiently parallelizable. A common example is parallel binary search. The problem arises because parallel binary search has polylogarithmic time complexity even for $p = 1$. Any sequential algorithm requiring at most logarithmic time in the worst case is in $NC$ regardless of its parallel feasibility.

But wait, there is more.

$NC$ algorithms assume parallel machines with a polynomial number of processors to solve in polylogarithmic time moderately sized problems. However, in practice we use moderately sized machines (in terms of processors) to solve *large* problems. The number of processor tends to be sub polynomial, even sublinear.

Finally, there are problems in $P$ with sublinear parallel time $O(n^\epsilon), 0 \< \epsilon \< 1$.Therefore, these problems do not belong to $NC$. Now, sublinear functions may have a relevant asymptotic behavior only for impractically large values of $n$, and may be instead much less progressive for practical values of $n$. As an example, $\sqrt n \< \lg^3 n$ for $n \leq 0.5 \times 10^9$. It follows that sublinear parallel time algorithms *may* run faster than $NC$ algorithms.

In one of the answer, it has been observed that "In practice, this means that we can prepare a computer with more memory as the input size grows, which is how we usually use computers in the real world. NC models an analogous situation in parallel computation".

I partially agree with this point of view. We buy a new parallel computer with more memory when an older supercomputer is decommissioned also because DRAM chips are less expensive upon time and to somewhat balance the parallel computer with regard to its main components (processors, memory, interconnect etc).

However, since memory is a finite resource, there has been a lot of research about using it efficiently, without requiring adding more memory to a supercomputer to solve larger instances of a problem. For instance, Sun and Ni proposed the notion of memory-bounded speedup, and Quinn proposed the so-called scalability function that measures how the amount of memory per processor must grow in order to maintain a constant level of efficiency. In general, since parallel overhead increases when the number of processors increases, we maintain efficiency increasing the size of the problem being solved. But the maximum problem size is limited by the amount of main memory (which is linear in $p$). The scalability function uses the isoefficiency function and another function which denotes the amount of memory required to store a problem of size $n$ to determine how the amount of memory per processor must grow in order to maintain a constant level of efficiency. When this function is a constant, the parallel algorithm is perfectly scalable (from the use of memory perspective). While memory is available, it is possible to maintain the same level of efficiency by increasing the problem size. However, since the memory used per processor increases linearly with $p$, at some point this value will reach the memory capacity of the system. Efficiency cannot be maintained when the number of processors increases beyond this point.

Therefore, it is increasingly important to design memory scalable parallel algorithms, since these are practical for large problems.

A final note on scaling down of parallel algorithms. This only make sense if the parallel algorithm we want to scale down is cost-optimal. Scaling down a cost optimal algorithm still produces a fast (if slower than the original) algorithm. But scaling down a non cost-optimal algorithm may lead to a parallel algorithm which is slower than the best sequential run time (consider scaling down an $n^3$ processor constant time sorting algorithm to $n$ processors). The degree to which cost-optimality is missed impacts upon the range of problem and machine sizes over which an algorithm is useful and is well described in the textbook by Grama, Gupta, Karypis and Kumar.
> 10 votes

---
Tags: complexity-theory, reference-request, parallel-computing
---


# Question
Title: The operator $A(L)= \{w \mid ww \in L\}$
Consider the operator $A(L)= \\{w \mid ww \in L\\}$. Apparently, the class of context free languages is not closed against $A$. Still, after a lot of thinking, I can't find any CFL for which $A(L)$ wouldn't be CFL.

Does anyone have an idea for such a language?

# Answer
> 10 votes
As an amplification of sdcvvc's hint: You can find a context-free language $L$ such that $A(L) = \\{a^m b^m c^m \mid m\geq 0\\}$, which as you probably know is not context-free.

So we want to find $L$ such that if $ww\in L$, then $w$ has the form $a^m b^m c^m$. We might as well have $L$ be a sublanguage of $a^\*b^\*c^\*a^\*b^\*c^\*$. Now we just need to put enough restrictions on the words in $L$ so that words of the form $ww$ in $L$ will have the form we require, while ensuring $L$ is still context-free.

Partial spoiler:

> A word $a^{m\_1} b^{m\_2} c^{m\_3} a^{m\_4} b^{m\_5} c^{m\_6}$ has the form $ww$ if and only if $m\_1 = m\_4$, $m\_2 = m\_5$ and $m\_3 = m\_6$. Now we can add some restrictions on the $m\_i$ for words in $L$ to force them to all be equal in words of the form $ww$. (Hint: we can require $m\_1 = m\_2$, but then we can't require $m\_1 = m\_3$ or $m\_2 = m\_3$, because then $L$ wouldn't be context-free anymore. This isn't a problem though, because we can make use of some of the equalities we already have between the $m\_i$.)

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


# Question
Title: Reason to learn propositional & predicate logic
I can understand the importance that computer scientists or any software development related engineers should have understood the study of basic logics as a basis.

But is there any tasks/jobs that explicitly require the knowledge about these, other than the tasks that require any kind of knowledge representation using `Knowledge Base`? I want to hear the types of tasks, rather than conceptual responses.

The reason I ask this is just from my curiosity. While CS students have to spend certain amount of time on this subject, some practicality-intensive courses (e.g. AI-Class) skipped this topic entirely. And I just wonder that for example knowing `predicate logic` might help drawing `ER diagram` but might not be a requirement.

---

Update 5/27/2012) Thanks for answers. Now I think I totally understand & agree with the importance of `logic`in CS with its vast amount of application. I just picked the best answer truly from the impressiveness that I got by the solution for `Windows`' blue screen issue.

# Answer
> 22 votes
I tend to like Unification and anything related to it. If you don't know propositional & predicate logic, then you are skipping the basics of logic. If you have an interest in anything listed, then it would be like having an interest in math and skipping addition and multiplication. Logic is not just for AI.

As a practical answer, remember the Intel floating point problem and how you never see them anymore? Thanks to the use of theorem provers they are a thing of the past. Remember the Microsoft blue screen of death. Thanks to SAT solvers, model checking and other logic based solution, they are an endangered species.

# Answer
> 21 votes
There are extremely *deep* and *pervasive* connections between logic and computer science. In understanding what they might be, keep in mind that computer science is also called "information technology" or "informatics", meaning that computer systems capture, process and deliver information. Well, logic is a similar thing. It studies how information is captured in sentences and how it is possible for one statement to be a *consequence* of another, i.e., how its information content is already present in another statement (or collection of statements). In that sense, logic and computer science are essentially the *same* discipline, focusing on different aspects. Logicians (Church, Kleene, Turing, Post and their students and colleagues) created the discipline of Computer Science, and many logicians continue to make contributions to Computer Science, most notably Jean-Yves Girard and his students.

Here are some standard applications of logic in Computer Science:

* The design of **digital circuits** is entirely based on proposal logic, so much so that its engineers call it "logic design" rather than "circuit design". Even writing a computer program is often thought to involve devising its "logic". (Note that "logic" in the latter sense is an informal idea rather than formal logic, used to refer to the flow on information through the program and whether it is being processed correctly.)
* Predicate logic and its mathematical cousin, set theory, are used in a variety of **computing languages**, e.g., the language SQL for relational database queries. There are also programming languages based on logic, called "logic programming languages".
* **Knowledge representation**, which you have already mentioned, has many formalisms based on logic. Even if it uses non-logical formalisms, many of them still have a logical *meaning*, and hence are based on logic.
* Probabilistic logic, where statements do not have just true/false values, but levels of certainty/uncertainty, is increasingly the foundation for **machine learning systems**.
* If you want to formally state what a program does, i.e., giving a program **specification**, you will end up using some form of a logical language. Indeed, there are many program specification languages, like Z and B, which are based on predicate logic and set theory. There are also specification languages based on equational logic, such as Larch. Computer Scientists often invent new logics to represent the needs of computer science, e.g., Hoare Logic and Separation Logic, or they pick up and develop various underused forms of traditional logics, such as temporal logic and modal logic, and develop them further.
* If you want to **verify** whether a program does what it is supposed to do, then you end up using not only the language of logic, but the entire *machinery* of logic: proof theory, model theory and decision procedures. Verification technology is now growing by leaps and bounds and I expect that, in another decade or so, they would be routinely used for almost all software development.

In fact, the connections between logic and computer science are so deep and pervasive that I would say it is a hard to be a good computer scientist without a thorough understanding of logic.

The reason some AI scientists underrate logic at this time is that some of the early developers of AI had proposed off-the-shelf logic as a *tool* rather than a foundation. AI, by its very nature, promises to deliver magic. We don't have to do the hard job of programming systems to deliver results. They would be able to figure out on their own how to produce solutions because they would be "intelligent". Logic seemed to point the way because if computer systems understood logic and knew how to process information using the rules of logic, they would be able to deliver magic. That kind of faith in logic was, in retrospect, misplaced. In the first place, off-the-shelf logic is too strong and too weak at the same time. It is too strong in the sense that the rules of logic are too general to devise effective procedures. It is also too weak because it is the logic devised by mathematicians for the needs of mathematics and it doesn't have the vocabulary needed to deal with a lot of other kinds of real-world information that AI systems must handle (such as uncertainty, contextual information like time, change, knowledge, agency and so forth). So, AI is currently undergoing a backlash against logic. But I think that, when they get over that backlash, AI scientists will realize that all the newer methods are still based on *logic, broadly construed*.

# Answer
> 16 votes
Logic is fundamental to all theoretical computer science. Without learning these, you won't be able to properly grasp programming language semantics, Turing machines, logic programming, computability, and so on. Even reasoning about your programs will be more difficult without it. Certainly, trying to do a mathematical proof of some CS concept with be virtually impossible.

Or maybe you are asking about uses in industry. Learning logic forms the basis for learning how to reason clearly and see holes in other people's arguments. Logic is fundamental, whether you use the formal symbols or not.

# Answer
> 9 votes
One of the repeating tasks CS practitioners and theorists face is gaining confidence in the correctness of their code.

There are two main approaches:

1. Proof: Devise a logical proof that part of a system has certain properties, possibly aided by preconditions, design-by-contract, code checkers.
2. Testing: Test that certain properties hold for a variety of inputs and then induce that that property holds for other inputs.

The first, based on logical methods, is often the only option when

1. There is no typical input. For example, when testing security properties, it is the atypical inputs that you have to worry about so unless you can logically reason about which inputs are atypical, you are unlikely to get good coverage.
2. The configuration space is very large, so you have to decompose it into parts by logically reasoning about which parts can affect which other parts before testing locally.
3. You have only documentation describing edge-case behavior of systems outside your control. You might be able to simulate them but can't test what happens when an external dependency fails because you are not capable of causing it to fail for legal or ethical reasons.

Empirical testing in the absence of a proof is basically a substitute for proof. When you're designing a system to be testable, you are building up a proof sketch where you fill in parts of the proof with "test X,Y, and Z here." The ability to reason logically is essential to be able to architect a testable system. If the system is not testable or provable then its designer/architect has no business saying it is fit for its intended use.

# Answer
> 6 votes
Two most important fields that logic plays vital role are:

1. Formal Language specification and verification.
2. Fixed parameter tractable classes.

---

Seems needs some clarification, in formal languages you need to extremely work on logic, for clarification take a look at: 1. Formal language. 2. Introduction to $Z$.

In short: 1. Definition of language needs logic, 2: Justice of it's procedures needs logic, 3. verification procedures need logic.

I should mention that this is different from compiler design or ..., This is "Formal" definition of languages, main reason to do this is proving correctness of language or model, also having a formal proof. This can be used in verification of software models, finding errors before implementing, finding deadlocks again before implementing, ...., For software which simulate this you can take a look at NModel.

Now why in Fixed parameter tractable problems you need to work with logic, You can divide classes of Fixed parameter tractability with different levels of logic, they can be converted to each other : logic to automata, automata to graph, and vice verse, But if you be an expert in logic you can divide and decide on them simply, most important theorem (after Robertson and Seymour theorem), in this field is Courcelle's theorem. for more information read Meta Algorithmic Theorem survey.

---
Tags: logic
---


# Question
Title: How can we assume that basic operations on numbers take constant time?
Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting is $O(n\log n)$, but when numbers are too big to fit into registers, we normally represent them as arrays so basic operations require extra calculations per element.

Is there a proof showing that comparison of two numbers (or other primitive arithmetic functions) can be done in $O(1)$? If not why are we saying that comparison based sorting is $O(n\log n)$?

---

*I encountered this problem when I answered a SO question and I realized that my algorithm is not $O(n)$ because sooner or later I should deal with big-int, also it wasn't pseudo polynomial time algorithm, it was $P$.*

# Answer
For people like me who study algorithms for a living, the 21st-century standard model of computation is the *integer RAM*. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not *arbitrary* integers, but (because word sizes grow steadily over time) not *fixed size* integers, either.

The model depends on a single parameter $w$, called the *word size*. Each memory address holds a single $w$-bit integer, or *word*. In this model, the input size $n$ is the number of *words* in the input, and the running time of an algorithm is the number of operations on *words*. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time *by definition*.

Formally, **the word size $w$ is NOT a constant** for purposes of analyzing algorithms in this model. To make the model consistent with intuition, we require $w \ge \log\_2 n$, since otherwise we cannot even store the integer $n$ in a single word. Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because those algorithms don't care about the underlying binary representation of their input. Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case. One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model. But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model. The only serious difficulty comes from nested multiplication, which can be used to build *very* large integers *very* quickly. If we could perform arithmetic on *arbitrary* integers in constant time, we could solve any problem in PSPACE in polynomial time.

**Update:** I should also mention that there are exceptions to the "standard model", like Fürer's integer multiplication algorithm, which uses multitape Turing machines (or equivalently, the "bit RAM"), and most geometric algorithms, which are analyzed in a theoretically clean but idealized "real RAM" model.

Yes, this is a can of worms.
> 85 votes

# Answer
It just depends on the context. When dealing with bit level complexity of algorithms, we do not say that the addition of two $n$ bits numbers is $O(1)$, we say it is $O(n)$. Similarly for multiplication etc.
> 29 votes

# Answer
To answer the question as stated: algorithmists just do it, fairly often, by using the RAM model. For sorting, in many cases, people even analyze the simpler comparison model, which I discuss a little more in the linked answer.

To answer the implicit question about *why* they do it: I would say that this model has pretty good predictive power for certain types of combinatorial algorithms, in which the numbers are all "small" and, on real machines, fit in registers.

To answer implicit follow-up about numerical algorithms: No, the plain old RAM model is not the standard here. Even Gaussian elimination can require some care. Typically, for rank computations, the Schwartz Lemma will enter (e.g., Section 5 here). Another canonical example is the analysis of the Ellipsoid Algorithm, which requires some care to analyze.

And finally: People have thought about string sorting before, even recently.

*Update:* The problem with this question is that "we" and "assume" are not so precisely specified. I would say that the people who work in the RAM model are not doing numerical algorithms or complexity theory (where determining the complexity of division was a celebrated result).
> 18 votes

# Answer
I couldn't find any studies of this, but Kozen says in the introduction to "The Design and Analysis of Algorithms" that the $O(1)$ model "reflects experimental observation more accurately \[than the log-cost model\] for data of moderate size (since multiplication really does take one unit of time)." He also gives a reference to this paper as an example of how the $O(1)$ model can be abused.

This is absolutely not a legit evaluation (not least because it's Python), but here's some numbers from running `python -mtimeit "$a * $b"` for `$a` in $10^{\\{1,2,...,66\\}}$ and `$b = 2*$a`. (I stopped at 66 because that's when Python syntax stops accepting integer literals and I'd have to slightly switch my evaluation code, so I didn't. :p)

Each number is the mean of 10,000,000 loops, where it takes the best time of 3 runs in each loop. I'd do error bars or something but that'd be more effort. :p In any case, it looks pretty constant to me, even out to $10^{50}$ -- slightly surprising, since $\log\_{10}(\tt{sys.maxint})$ is 43, which reinforces my suspicion that maybe this evaluation is particularly bogus and I should do it in C.
> 9 votes

# Answer
You are right, in general we cannot assume they are $O(1)$.

Strictly speaking, if we want to sort an array with N numbers using comparisons, and the largest number is M, then on the worst case, each comparison may involve $O(\log M)$ comparisons on the bit level. And if our algorithm does $O (N \log N)$ comparisons, then its total complexity will be $O (N \log N \log M)$.

However, you will notice the difference only for very large values of $M$, that cannot be stored in a single register, as you can see from Dougal's experiment.
> 9 votes

# Answer
I would say that we typically assume O(1) arithmetic operations because we're usually doing things in the context of 32-bit integers or 64-bit integers or IEEE 754 floating point numbers. O(1) is probably a pretty good approximation for that kind of arithmetic.

But in general, that's not true. In general you need an algorithm to perform addition, subtraction, multiplication and division. Boolos, Burgess and Jefferies' Computability and Logic springs to mind as a way to understand the proof(s) of that, in terms of a couple of different formal systems, Recursive Functions and Abacus Machines, at least, in my 4th Edition copy.

You can look at the lambda-calculus terms for subtraction and division with Church Numerals for an easy-to-see explanation of why those two operations aren't O(1). It's a bit harder to see for addition and multiplication and exponentiation, but it's there if you consider the form of Church Numerals themselves.
> 5 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, time-complexity, reference-question
---


# Question
Title: Why are lambda-abstractions the only terms that are values in the untyped lambda calculus?
I am confused about the following claim: "The only values in the untyped lambda calculus are lambda-abstractions".

Why are the other terms not values? What does it mean for a lambda-abstraction to be a value? The first thing that came to my mind was that maybe lambda-abstractions are the only possible normal forms, but this is not true of course, e.g. $(\lambda x.\\; x)\\;y \to y$.

Can someone enlighten me?

# Answer
> 10 votes
There are a number of things going on here:

* The language you are talking about has no additional data types, otherwise there would be other kinds of values.
* The reduction strategy of the language does not reduce inside lambda abstractions. Both call-by-value and call-by-name conform to this. Otherwise, not every lambda abstraction would be a normal.
* One generally considers closed expressions as programs, so there are no free variables, hence the example you present is not considered.

Other terms are not values because they can be reduced or they do not appear in closed programs.

That a lambda abstraction is a value means that it cannot be reduced any further (depending on the reduction strategy).

For open terms, variables are also values.

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


title: Frame Pointers in Assembler

text:
# Question
Title: Frame Pointers in Assembler
I am currently learning assembly programming on wombat 4, I am looking at Frame pointers. I understand exactly what a frame pointer is: it is a register and are used to access parameters on a stack. But i'm confused on how they affect the program counter and why they are preferred over normal registers.

Could some one explain, please.

# Answer
As the stack pointer may change while a function is executed, access to the stack is less confusing with a static frame pointer, that is set upon the entry to the function, so relative addressing becomes simpler.

On reason for using the stack to store parameters is that there is usually more memory available than registers. What would you do with a function g(a,b,c,d,e,f) where you have enough registers free to store a–e, but non for f? You would put f on the stack. As the size of the stack is only limited by the available memory using the stack still works for functions with even more parameters.

Modern compilers typically have a flag that controls whether the use of registers for parameter passing is allowed or not.
> 8 votes

---
Tags: computer-architecture, compilers
---


# Question
Title: Runtime of the optimal greedy $2$-approximation algorithm for the $k$-clustering problem
We are given a set 2-dimensional points $|P| = n$ and an integer $k$. We must find a collection of $k$ circles that enclose all the $n$ points such that the radius of the largest circle is as small as possible. In other words, we must find a set $C = \\{ c\_1,c\_2,\ldots,c\_k\\}$ of $k$ center points such that the cost function $\text{cost}(C) = \max\_i \min\_j D(p\_i, c\_j)$ is minimized. Here, $D$ denotes the Euclidean distance between an input point $p\_i$ and a center point $c\_j$. Each point assigns itself to the closest cluster center grouping the vertices into $k$ different clusters.

The problem is known as the (discrete) $k$-clustering problem and it is $\text{NP}$-hard. It can be shown with a reduction from the $\text{NP}$-complete dominating set problem that if there exists a $\rho$-approximation algorithm for the problem with $\rho \< 2$ then $\text{P} = \text{NP}$.

The optimal $2$-approximation algorithm is very simple and intuitive. One first picks a point $p \in P$ arbitrarily and puts it in the set $C$ of cluster centers. Then one picks the next cluster center such that is as far away as possible from all the other cluster centers. So while $|C| \< k$, we repeatedly find a point $j \in P$ for which the distance $D(j,C)$ is maximized and add it to $C$. Once $|C| = k$ we are done.

It is not hard to see that the optimal greedy algorithm runs in $O(nk)$ time. This raises a question: can we achieve $o(nk)$ time? How much better can we do?

# Answer
> 7 votes
The problem can be indeed viewed geometrically in a way that we would like to cover the $V$ points by $k$ balls, where the radius of the largest ball is minimized.

$O(nk)$ is indeed quite simple to achieve but one can do better. Feder and Greene, Optimal algorithms for approximate clustering, 1988 achieve a running time of $\Theta(n \log k)$ using more clever data structures and further show that this is optimal in the algebraic decision tree model.

# Answer
> 1 votes
> My question: Is there a way I can make the greedy picking strategy run in $o(|V|^2)$ time?

It seems to me that you described it. In case I read too far in your description, here is what I've understood. Have an associative data structure associating each element of $V$ with the sum of the distance to elements of $S$. This data structure can be initialized at a cost $O(|V|)$ with the distance to $p$ and this initialization can produce the next element as a side effect without increasing the complexity. It can be updated after the selection of a new element at a cost of $O(|V|)$, again producing the next element as a side effect. Repeat to get $S$. The resulting complexity is $O(k |V|)$.

---
Tags: algorithms, computational-geometry
---


# Question
Title: Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$
I read on the site on how to use the pumping lemma but still I don't what is wrong with way I'm using it for proving that the following language is not a regular language:

$L = \\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \\}$

for $i\neq1$ the language is obviously regular but in the case which $i=1$ , we get that the language is $a^1b^nc^n$, now for every division $w=xyz$ such that $|y|\>0 , |xy|\< p$ where p is the pumping constant I get the word $a^1b^pc^p$ would be out of the language. since $|xy|\< p$ , $y$ may contains only $a's$ or $b's$ or both. if $x= \epsilon$ and $y=a$, pump it once and you're out of the language, if it contains only $b's$, pump it once and your'e out of the language, and if it contains both, pump it and you're out of the language again.

so, why does this language considered as not regular and cannot be proved for its irregularity by the pumping lemma? please point out my mistake.

# Answer
The pumping lemma provides a sufficient condition for a language to be non-regular, it is not a necessary condition. This is an example of a language for which the pumping condition holds, so you cannot prove that it is non-regular with (the basic version of) the pumping lemma.

When you see this language definition, you should immediately think of breaking it up: $$ \begin{align\*} L &= \\{ a^i b^j c^k \mid \text{if \\(i=1\\) then \\(j=k\\)} \\} = \\{ a^i b^j c^k \mid i \ne 1 \vee j=k \\} \\ &= \\{ a^i b^j c^k \mid i \ne 1 \\} \cup \\{ a^i b^j c^k \mid j = k \\} = (b^\*c^\* \cup aaa^\*b^\*c^\*) \cup \\{ a^i b^j c^k \mid j = k \\} \\ \end{align\*} $$ This is taking shape: we've expressed $L$ as the union of a regular language with a language that doesn't look regular (it looks a lot like the classical example of a non-regular language ${b^j c^k \mid j=k}$). We need to work a little more if we can hope to prove that $L$ isn't regular, however: the union of a regular language and a non-regular language can be regular (the union operation can “absorb” the irregularity).

So let's take a step back: what's the problem? In the decomposition above, we have the regular case, with words that begin with no $a$ or with $aa$; and we have the irregular case, where we don't know anything about the initial number of $a$'s. Really, the trouble comes from words that begin with a single $a$. If $L$ is regular, then its intersection $L'$ with the regular language $a(b|c)^\*$ would also be regular. Well, $$L' = L \cap (a(b|c)^\*) = \\{ a b^j c^k \mid j = k \\}$$ If we prove that this language is not regular, then we'll know that $L$ isn't regular either.

To prove that $L'$ is not regular, the pumping lemma works well, just like for $\\{b^j c^k \mid j=k\\}$. We no longer have this problem with the unbounded number of $a$'s. If $L'$ is regular, then we can find a pumping decomposition for $a b^p c^p$ where $p$ is the pumping length: $a b^p c^p = xyz$ with $y \ne \epsilon$, $|xy| \le p$ and $\forall i, x y^i z \in L'$.

* If $y$ contains the $a$, then $x z$ contains no $a$, which contradicts $x z \in L'$.
* If $y$ contains an unequal number of $b$'s and $c$'s, then $x z$ does not contain an equal number of $b$'s and $c$'s, which contradicts $x z \in L'$.
* If $y$ contains equal numbers of $b$'s and $c$'s and is not $a$, then $y = b^m c^m$ with $m \gt 0$ since $y$ is not empty. Then $x y^2 z$ contains the substring $c b$, which contradicts $x y^2 z \in L'$.

Applying the pumping lemma to $L'$ leads to a contradiction. Therefore the assumption that $L'$ is regular does not hold. Thus $L$ is not regular.

If you are willing to assume that $\\{b^j c^k \mid j=k\\}$ is not regular, another method to prove that $L'$ is not regular is to read it off an automaton. Suppose that $L'$ is regular; then there is a finite automaton $\mathcal{A}$ that recognizes it. Let $q$ be the state reached by this automaton on the input $a$, and let $\mathcal{A}'$ be this $\mathcal{A}$ with the initial state changed to $q$. If a word is of the form $a w$, then it is accepted by $\mathcal{A}$ if and only if $w$ is accepted by $\mathcal{A}'$. So the language recognized by $\mathcal{A'}$ is $\\{w \mid a w \in L' \\} = \\{b^j c^k \mid j=k\\}$. Since this language is known not to be regular, we have a contradiction; the assumption that $L'$ is regular must be false.
> 3 votes

# Answer
The pumping lemma can only be used to show that a language is not regular, not that it is regular. This is, I think, the fundamental misunderstanding here... that you are unable to use the pumping lemma to prove a language irregular does not constitute a proof of irregularity.

A language is regular if, equivalently,

* it can be accepted by an NFA
* it can be generated by a regular grammar
* it can be described by a regular expression
* it can be partitioned into finitely many equivalence classes under the indistinguishability relationship (as per the Myhill-Nerode theorem)

This last point can usually be pretty helpful in cases where the pumping lemma fails. Here, you merely need to demonstrate that there are infinitely many equivalence classes for strings in your language; you could argue that strings of the form $ab^nc$ constitute separate classes for all $n$.

Furthermore, as pointed out in the comments, you can often use closure properties of language classes in order to demonstrate that a particular language isn't in the class. For instance, you know that regular languages are closed under intersection. Using that fact, you could show that your language can't be regular, since if it were, the language $ab^nc^n$ would be regular (a contradiction, since you know that language isn't regular... you could even prove this easier version with the pumping lemma).

EDIT: Just in case how to apply the pumping lemma here is unclear, I'll give an example.

Choose the string $uvw = ab^pc^p$. Since $|uv| \< p$ and $v \> 0$, $v$ must be some non-empty string possibly beginning with a single $a$, followed by multiple $b$'s. If $v$ contains the $a$, pumping will cause there to be a different number of $a$'s, so we get a string not in the language. If the string does not contain the $a$, it consists only of $b$'s, and pumping will cause the number of $b$'s to be different from $n$. The resulting string is not in the language since the number of $b$'s is not equal to the number of $c$'s. Therefore, this string cannot be pumped to another string in the language, a contradiction of the assumption the language was regular; hence, the language is not regular.
> 7 votes

# Answer
I'm assuming that the language is like David Lewis posted in the comments. $$L=\\{ a^ib^jc^k : (i=1 \text{ & }j=k\>=0) \text{ | } (i \neq 1 \text{ & } j,k \>= 0)\\}$$

This language is not regular, but **cannot** be proven non-regular using the standard version of the regular pumping lemma (as seen in the Sipser text or on wikipedia) because you can always pump the first character. If your division is $w = xyz$, let $x = \epsilon$ and $y$ be the first character. This division will always meet the constraints of the pumping lemma, since:

* If $y = b$, pumping doesn't matter because the number of $a$'s is zero so $j$ can be different than $k$.
* If $y = a$, pumping doesn't matter because turns the string from the case $(i=1 \text{ & }j=k\>=0) $ to $(i \neq 1 \text{ & } j,k \>= 0)$.

(This is why the pumping lemma is not an "if and only if" statement. There are languages that meet the pumping lemma's criteria but are still not regular.)

---

To prove that the language is not regular, use closure properties. An intersection and a homomorphism / substitution will turn it into $\\{0^n 1^n ~:~ n \geq 0\\}$ easily.

Alternatively, you can use a generalized version of the pumping lemma that allows you to focus on a chosen substring of length $p$ or more.
> 6 votes

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


# Question
Title: Invariant For Nested Loop in Matrix Multiplication Program
I'm making a graduate thesis about proving correctness of program for multiplying 2 matrices using Hoare logic. For doing this, I need to generate the invariant for nested loop for this program:

```
for i = 1:n
    for j = 1:n
        for k = 1:n
            C(i,j) = A(i,k)*B(k,j) + C(i,j);
        end
    end
end

```

I've tried to find the invariant for inner loop first, but I can't find the true one until now. Is there someone can help me for finding the invariant for above program?

# Answer
You need the line `C(i:j) = 0` just before the innermost loop; otherwise, the code is incorrect.

Assuming that line is in place, here is the (strongest possible) invariant just *before* the assignment in the innermost loop: \begin{align\*} C\_{IJ} &= \sum\_{k=1}^{n} A\_{Ik}B\_{kJ} & \text{for all $I$ and $J$ such that $1\le I \< i$ and $1\le J\le n$} \\ \text{and}~~~ C\_{iJ} &= \sum\_{k=1}^{n} A\_{ik}B\_{kJ} & \text{for all $J$ such that $1\le J\< j$} \\ \text{and}~~~ C\_{ij} &= \sum\_{K=1}^{k-1} A\_{iK}B\_{Kj}. \end{align\*} (Yes, the whole thing.) The invariant just *after* the assignment has $k$ in place of $k-1$ in the last sum, but is otherwise identical.
> 11 votes

# Answer
There is no such thing as “the” invariant: any loop has plenty of invariants. You need to find an interesting invariant. Since you're trying to prove that the loop computes a matrix multiplication, your invariant must imply that when $i=j=k=n$, the coefficients of $C$ are those of the matrix product $A \times B$, i.e. $$\forall i \in \[1,n\], \forall j \in \[1,n\], C(i,j) = \sum\_{k=1}^n A(i,k) \cdot B(k,j)$$ It is rather natural to specialize this property of $i$ and $j$ to conjecture an invariant for the outer and middle loops:

* $\forall j \in \[1,n\], C(i,j) = \sum\_{k=1}^n A(i,k) \cdot B(k,j)$ on the outer loop
* $C(i,j) = \sum\_{k=1}^n A(i,k) \cdot B(k,j)$ on the middle loop

Each run of the inner loop adds the $k$th term to the sum, which leads to the proposed invariant: $$C(i,j) = \sum\_{l=1}^k A(i,l) \cdot B(l,j)$$ It's easy to see that if this invariant holds, then the proposed invariant for the middle loop holds, and from that, the proposed invariant for the outer loop holds, and the program does what is expected.

What remains to be proved is the initial condition. You need to prove that $\forall i, \forall j, C(i,j) = \sum\_{l=1}^0 A(i,l) \cdot B(l,j)$, i.e. $\forall i, \forall j, C(i,j) = 0$ on entry to the program. You had better initialize $C$ so that this is so. Alternatively, you can achieve this property by doing the initialization inside the middle loop, just before entering the inner loop.
> 2 votes

---
Tags: algorithms, loop-invariants, correctness-proof
---


# Question
Title: Solving Recurrence Equations containing two Recursion Calls
I am trying to find a $\Theta$ bound for the following recurrence equation:

$$ T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42 $$

I figure Master Theorem is inappropriate due to differing amount of subproblems and divisions. Also recursion trees do not work since there is no $T(1)$ or rather $T(0)$.

# Answer
Yes, recursion trees do still work! It doesn't matter at all whether the base case occurs at $T(0)$ or $T(1)$ or $T(2)$ or even $T(10^{100})$. It also doesn't matter what the actual value of the base case is; whatever that value is, it's a constant.

Seen through big-Theta glasses, the recurrence is $T(n) = 2T(n/2)+T(n/3)+n^2$.

* The root of the recursion tree has value $n^2$.
* The root has three children, with values $(n/2)^2$, $(n/2)^2$, and $(n/3)^2$. Thus, the total value of all children is $(11/18) n^2$.
* Sanity check: The root has nine grandchildren: four with value $(n/4)^2$, four with value $(n/6)^2$, and one with value $(n/9)^2$. The sum of those values is $(11/18)^2 n^2$.
* An easy induction proof implies that for any integer $\ell\ge 0$, the $3^\ell$ nodes at level $\ell$ have total value $(11/18)^\ell n^2$.
* The level sums form a descending geometric series, so only the largest term $\ell=0$ matters.
* We conclude that $T(n) = \Theta(n^2)$.
> 16 votes

# Answer
You can use the more general Akra-Bazzi method.

In your case, we would need to find $p$ such that

$$ \frac{1}{2^{p-1}} + \frac{1}{3^p} = 1$$

(which gives $p \approx 1.364$)

and we then have

$$T(x) = \Theta(x^p + x^p\int\_{1}^{x} t^{1-p} \text{d}t) = \Theta(x^2)$$

Note that you don't really need to solve for $p$. All you need to know is that $1 \lt p \lt 2$.

A simpler method would be to set $T(x) = x^2 g(x)$, and try proving that $g(x)$ is bounded.
> 14 votes

# Answer
Let $f(n) = 2T(n/2) + T(n/3) + 2n^2 + 5n + 42$ be a shorthand for the right-hand side of the recurrence. We find an lower and upper bound for $f$ by using $T(n/3) \leq T(n/2)$:

$$ 3 T(n/3) + 2n^2+ 5n + 42 \quad \le\quad f(n) \quad\leq \quad 3 T(n/2) + 2n^2+ 5n + 42 \quad$$

If we use the lower resp. upper bound as right-hand side of the recurrence, we get $T'(n) \in \Theta(n^2)$ in both cases by the Master theorem. Thus, $T(n)$ is bounded from above by $O(n^2)$ and from below by $\Omega(n^2)$ or, equivalently, $T(n) \in \Theta(n^2)$.

---

1. For a complete proof, you should prove that $T$ is an increasing function.
> 14 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Is WPA2 with pre-shared key an example of a zero-knowledge proof?
When setting up an access point and selecting WPA2, one must manually enter a pre-shared key (a password), PSK, into both the AP and the STA.

Both parties, AP and STA, must authenticate each other. But they have to do so without revealing the PSK. Both have to proof to the other party that they know the PSK without actually sending it.

Is that an example of a zero-knowledge proof?

I thought it was, but nothing legit shows up when I google for zero-knowledge proof and WPA2 or EPA-PSK (the authentication method used).

# Answer
> 7 votes
In authentication you often come accross zero-knowledge password proof (ZKPP). EAP itself is a rather generic framework and it might involve revealing the identity of the client for instance to transfer it to the next layer of authentication such as RADIUS.

PACE (BSI TR-03110) is one example of ZKPP protocols used for authentication. EAP-SPEKE is another.

The security of the key relies on the use of only parts of the key in the exchange between the client and the server. The client offers a nonce encrypted with the key to the server. Therefore a rogue server receives a encrypted nonce and holds its plaintext version. This is not zero-knowledge, since in a finite time a rogue server might accumulate enough information to break the AES-128 encryption.

Hence EAP-PSK may not be considered an example of zero-knowledge password proof, though other proposed authentication schemes based on EAP such as EAP-SPEKE have this property.

To illustrate the problematic part of the EAP-PSK protocol consider the message flow as presented in RFC 4764.

> The first message is sent by the server to the peer to:
>
> ```
>   *  Send a 16-byte random challenge (RAND_S).  RAND_S was called RA
>      in Section 3.2
>
>   *  State its identity (ID_S).  ID_S was denoted by A in
>      Section 3.2.
>
> ```
>
> o The second message is sent by the peer to the server to:
>
> ```
>   *  Send another 16-byte random challenge (RAND_P).  RAND_P was
>      called RB in Section 3.2
>
>   *  State its identity (ID_P).  ID_P was denoted by B in
>      Section 3.2.
>
>   *  Authenticate to the server by proving that it is able to
>      compute a particular MAC (MAC_P), which is a function of the
>      two challenges and AK:
>      MAC_P = CMAC-AES-128(AK, ID_P||ID_S||RAND_S||RAND_P)
>
> ```
>
> o The third message is sent by the server to the peer to:
>
> ```
>   *  Authenticate to the peer by proving that it is able to compute
>      another MAC (MAC_S), which is a function of the peer's
>      challenge and AK:
>      MAC_S = CMAC-AES-128(AK, ID_S||RAND_P)
>
> ```

Here AK is a part of the secret key that is used at this stage and may be revealed to the rogue server that is able to decrypt AES-128.

---
Tags: cryptography, security, authentication
---


title: Line separates two sets of points

text:
# Question
Title: Line separates two sets of points
If there is a way to identify if two sets of points can be separated by a line?

> We have two sets of points $A$ and $B$ if there is a line that separates $A$ and $B$ such that all points of $A$ and only $A$ on the one side of the line, and all points of $B$ and only $B$ on the other side.

The most naive algorithm I came up with is building convex polygon for $A$ and $B$ and test them for intersection. It looks time the time complexity for this should be $O(n\log h)$ as for constructing a convex polygon. Actually I am not expecting any improvements in time complexity, I am not sure it can be improved at all. But al least there should be a more beautiful way to determine if there is such a line.

# Answer
> 19 votes
Both uli and Dave Clarke correctly observe that this is a linear programming problem, even in higher dimensions (Can these two point sets be separated by a hyperplane?) and so it can be solved in polynomial time. But because your points lie in the plane, your problem can actually be solved in $O(n)$ time, where $n$ is the total number of points.

The simplest solution is probably Seidel's randomized algorithm. Choose an input point $p$ uniformly at random, and recursively compute a separating line $\ell$ for all the points *except* $p$.

* If no such line exists, then the original points are not separable.
* If $p$ is on the correct side of $\ell$, then $\ell$ separates the original points.
* If $p$ is on the wrong side of $\ell$, then either the original points can be separated by a line through $p$, or the original points are not separable at all. This condition is easy to check in $O(n)$ time \[exercise\].

This algorithm runs in $O(n)$ time with high probability (with respect to the algorithm's random choices). For more details, see the original paper or any number of online lecture notes.

# Answer
> 10 votes
The property of your two data sets is that of linear separability, simply, that there is a line that separates them. A lot of machine learning is devoted to finding linear classifiers, which are lines that perform the separation you are interested in.

As you are talking about lines, I'll assume that your points lie in the plane. What you want to do is find values $w\_1$, $w\_2$ and $w\_3$, such that for all points $(a\_1,a\_2)$ in set $A$, $w\_1 a\_1+w\_2a\_2\ge w\_3$ and for all points $(b\_1,b\_2)$ in $B$, $w\_1 b\_1+w\_2b\_2\<w\_3$. Thus, the inequality $w\_1 x+w\_2y\ge w\_3$ can be seen as a classifier for set $A$.

There are loads of machine learning algorithms for determining an optimal line (linear regression, logistic regression, and so forth). These will find values for $w\_1,w\_2,w\_3$ based on some error metric. Then you can test whether all of the points are correctly classified. That is, whether all of the values in $A$ satisfy the equation above and similarly for $B$.

As you are only interested in whether such a line exists, you needed use existing techniques (though that probably would be simpler). Simply set up the following collection of equalities in terms of free variables $w\_1,w\_2,w\_3$.

$w\_1 a^i\_1+w\_2a^i\_2\ge w\_3$ for each $i=1,..,|A|$, where $A=\\{(a^1\_1,a^1\_2),\ldots,(a^{|A|}\_1,a^{|A|}\_2)\\}$.

$w\_1 b^j\_1+w\_2b^j\_2\< w\_3$ for each $j=1,..,|B|$, where $B=\\{(b^1\_1,b^1\_2),\ldots,(b^{|B|}\_1,b^{|B|}\_2)\\}$.

If these constraints are consistent, then a line exists.

# Answer
> 5 votes
If I remember correctly support vector machines construct seperating hyperplanes. If you choose dimension $2$ the hyperplane becomes of course a line. You might have to check if there are additional assumptions to be met. In two dimensions the whole approach might simplify considerably so the runtime might be better than for the general approach.

---
Tags: algorithms, machine-learning, computational-geometry
---


# Question
Title: Is it possible to use dynamic programming to factor numbers
Let's say I am trying to break all the numbers from 1 to N down into their prime factors. Once I have the factors from 1 to N-1, is there an algorithm to give me the factors of 1 to N using dynamic programming?

# Answer
You can try to find the smallest divisor $d\>1$ of $N$ by trial divison. Then the factorization of $N$ is given by that of $d$ and that of $N/d$. Since $N$ is either a prime number or has a divisor $1 \< d \< \sqrt{N}$, this would solve the problem. Of course, this is a dynamic solution in a very vague sense only - the table of partial results is only used as a cache, not like in "real" dynamic programming algorithms.
> 2 votes

# Answer
An algorithm using dynamic programming for factoring $N$ which proceeds by factoring all integers $1$ to $N$ in order takes time at least $\Omega(N)$. There's a known algorithm that factors integers in $\tilde{O}(N)$, namely trial division. So it doesn't seem worthwhile to pursue the dynamic programming approach as stated.
> 1 votes

---
Tags: algorithms, dynamic-programming, factoring
---


title: Prove fingerprinting

text:
# Question
Title: Prove fingerprinting
Let $a \neq b$ be two integers from the interval $\[1, 2^n\].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that $$\text{Pr}\_{p \in \mathsf{Primes}}\\{a \equiv b \pmod{p}\\} \le c \ln(n)/(n^{c-1}).$$

Hint: As a consequence of the prime number theorem, exactly $n/ \ln(n) \pm o(n/\ln(n))$ many numbers from $\\{ 1, \ldots, n \\}$ are prime.

Conclusion: we can compress $n$ bits to $O(\log(n))$ bits and get a quite small false-positive rate.

My question is how can i proove that $$\text{Pr}\_{p \in \mathsf{Primes}}\\{a \equiv b \pmod{p}\\} \le c \ln(n)/(n^{c-1})$$?

# Answer
The probability $P$ that a uniformly chosen random prime between $1$ and $n^c$ satisfies $a \equiv b \mod{p}$ is the number of primes in this range that satisfy $a \equiv b \mod{p}$ divided by the total number of primes in this range. Writing $\[C\] = 1$ if $C$ is true and $\[C\] = 0$ if $C$ is false, and $\pi(x)$ for the number of primes less than $x$: $$P = \dfrac{\sum\limits\_{p\le n^c} \[p\text{ prime}\] \[p \mid (a-b)\]}{\pi(n^c)}$$

Since $|a-b| \le 2^n$, there are at most $n$ distinct primes that divide $a-b$. The prime number theorem directly gives an upper bound for the denominator. Thus: $$ P \le \dfrac{n}{n^c/\ln(n^c) + o(n^c/\ln(n^c))} = \dfrac{c \ln(n)}{n^{c-1}} (1+o(1))$$

You won't get an exact bound from an asymptotic version of the prime number theorem. An exact bound, if I am not mistaken, is $\pi(x) \gt \dfrac{x}{\ln(x)}$ for $x \ge 11$. Using this bound, we see that if $n^c \ge 11$ then $$ P \le \dfrac{c \ln(n)}{n^{c-1}} $$

Application: we can compress $a \le 2^n$ (which takes $n$ bits to represent exactly) approximately by storing $a \mod p$ for several random prime numbers $p\_i$. If we use $k$ primes chosen independently of the value of $a$, then the representation requires $k \\, \lceil c\\,\log\_2(n) \rceil = O(k \log(n))$ bits to store the values modulo every chosen prime. The probability of a collision on each prime is at most $c \ln(n) / n^{c-1} = O(\ln(n)/n^{c-1})$. To evaluate how the precision increases with $k$ would require further analysis.
> 4 votes

---
Tags: probability-theory, information-theory, coding-theory, number-theory
---


# Question
Title: What is meant by interrupts in the context of operating systems?
I've decided to read Operating Systems Concepts by Silberschatz, Galvin Gagne (8th edition) over the summer. I've gotten to a topic that's confusing me - interrupts and their role as it relates to operating systems.

The text says that an operating system will begin a first process such as "init" and then wait for an "event" to occur and this event is usually signaled by an interrupt. The text also says that the interrupt can come from either the hardware or the software. How does this work, in a little more detail? Is the operating system driven by interrupts?

I am just looking for some big picture understanding.

# Answer
When the OS runs a process such as "init", it would have sent signals to other sub-systems/device managers etc, like the memory, I/O devices, etc. The interrupt is just a way of telling the processor or the OS that it is ready, or it has new input, etc. So sometime during init, the OS is waiting for sub-systems to be ready, and an interrupt from these sub-systems would indicate exactly that. So that is what the "event" relates to.

In regard to hardware or software interrupts, hardware interrupts are those which come from the hardware. Eg. I/O devices like keyboard, etc. A hardware interrupt causes the processor to save its state and begin execution of interrupt handler. On the other hand, software interrupts are instructions in the instruction set, which causes the processor to change its privilege level from user-supervisor, also known as context-switch. These details will be covered later on in the text book.
> 9 votes

# Answer
Interrupts allow the operating system to take notice of an external event, such as a mouse click. Software interrupts, better known as exceptions, allow the OS to handle unusual events like divide-by-zero errors coming from code execution.

The sequence of events is usually like this:

1. Hardware signals an interrupt to the processor
2. The processor notices the interrupt and suspends the currently running software
3. The processor jumps to the matching interrupt handler function in the OS
4. The interrupt handler runs its course and returns from the interrupt
5. The processor resumes where it left off in the previously running software

The most important interrupt for the operating system is the timer tick interrupt. The timer tic interrupt allows the OS to periodically regain control from the currently running user process. The OS can then decide to schedule another process, return back to the same process, do housekeeping, etc. The timer tick interrupt provides the foundation for the concept of preemptive multitasking.
> 4 votes

# Answer
An interrupt is an "unusual" event that happens which needs to be processed *immediately*, regardless of whatever else is going on. I say "unusual" in quotes, because they're not necessarily unexpected or bad, but "unusual" from the point of view of the CPU because they "just happen" while it's busy executing code that may be unrelated.

The CPU has some mechanism for listening to interrupts, and some way of configuring "what to do" when interrupts of various kinds occur. This allows the operating system to arrange that it will be notified when hardware devices do things (including the all-important hardware clock, which simply generates interrupts at regular intervals). Through the CPU's interrupt handling configuration, designated code in the OS will gain control whenever interrupts happen.

The computer is in a very unpleasant state (to an application programmer) when an interrupt handler starts running; the machine was busy doing something else (which could be *anything*) and now the OS has been notified that "something has happened". It has to gather any other information needed to actually handle the interrupt from wherever in the machine it should be lying around and do whatever processing is required without disturbing that "could be anything" that was running on the CPU. If the OS wants to switch which application process is currently running it will have to save enough of the context to be able to restore it later (again, without disturbing that context), then load some other context, and then let the CPU resume normal execution in that context.

As mentioned, interrupts are used for getting notifications from hardware devices (the only alternative would be to periodically check them), keeping track of time and getting the guaranteed opportunity to regain control from an application process (in order to switch which application is running), recovering from application processes executing invalid instructions, and also to enable applications to make requests of the OS. These last are known as system calls. To prevent the applications from messing up the machine and each other, they normally run with the machine in "user mode", which prevents the application from doing basically anything other than reading and writing (virtual) memory already allocated to it. This means that to do *anything* else (reading/writing files, asking for more memory, accessing devices, etc) the application has to make a system call; it does so basically by leaving some information about what it wants to do somewhere it knows the OS will look for it, then executing a CPU instruction that causes an interrupt of the right kind. The OS can then see what the application was trying to do and determine whether it should carry out that request. This guarantee that the OS will be involved in any process' attempt to do anything that affects anything outside the process is the only way that access policies can be enforced.

So essentially, yes, the OS is driven by interrupts. An "abstract" OS bootstraps the machine into a "normal operation" state and at some point hands off control to a "normal" process. Under normal circumstances, the OS will then only regain control by handling interrupts; but since pretty much nothing interesting happens without an interrupt, the OS basically has control of everything all the time.
> 4 votes

# Answer
The operating system is driven by interrupts. This means that:

If there are no processes to execute, no I/O devices to service, and no users to whom to respond, an operating system will sit quietly, waiting for something to happen. Events are almost always signaled by the occurrence of an interrupt or a trap, a trap is a hardware interrupt generated when an invalid instruction is given, and then it returns control to the OS.

An example of an invalid instruction is when a program is trying to access another program's memory space without having a permission.
> 3 votes

---
Tags: operating-systems, computer-architecture, process-scheduling
---


title: Why is this example a regular language?

text:
# Question
Title: Why is this example a regular language?
Consider this example (taken from this document: Showing that language is not regular):

$$L = \\{1^n \mid n\text{ is even}\\} $$

According to the Pumping Lemma, a language $L$ is regular if :

* $y \ne ε$
* $|xy| \lt n$
* $\forall k \in N, xy^kz \in L$

In the above example, $n$ must be even. Suppose we have $n = 4$, we can express: $$xy^kz$$ such that: $x = 1$, $z = 1$, and with $k = 2$, we have $y^k = y^2 = 11$, so we get the string $1111$. However, since all $k$ must be satisfied, if $k = 1$, the string is $111$, it does not belong to $L$. Yet, I was told that the above example is a regular language. How can it be?

# Answer
> 11 votes
1. Pumping lemma is not a sufficient condition for being regular, it is only a necessarily condition. Satisfying it does not imply that the language is regular.
2. In the pumping lemma, some parameters are chosen adversarily, i.e. you don't have control over them. If a language is regular then pumping lemma says that "for a long enough string in the language *there is a partition* s.t. ...". To show that a language is not regular you should show that for all ways of partitioning the conditions will not hold. Your argument does rule out $y=11$ for example, you are only talking about a particular way of partitioning and that does not imply anything.
3. The language is indeed regular, it is (11)\*.

# Answer
> 1 votes
The language is regular. Consider this (rule set of a) simple regular grammar that obviously generates $L$:

$\qquad \displaystyle S \to 11S \mid \varepsilon$

---
Tags: formal-languages, regular-languages, proof-techniques
---


title: Randomized String Searching

text:
# Question
Title: Randomized String Searching
I need to detect whether a binary pattern $P$ of length $m$ occurs in a binary text $T$ of length $n$ where $m \< n$.

I want to state an algorithm that runs in time $O(n)$ where we assume that arithmetic operations on $O(\log\_2 n)$ bit numbers can be executed in constant time. The algorithm should accept with probability $1$ whenever $P$ is a substring of $T$ and reject with probability of at least $1 - \frac{1}{n}$ otherwise.

I think fingerprinting could help here. But I can't get it.

# Answer
The Knuth-Morris-Pratt algorithm does this in linear time without any error.
> 9 votes

---
Tags: algorithms, strings, searching, probabilistic-algorithms
---


# Question
Title: Organisation and Architecture of Quantum Computers
What are devices and their interconnections used alongwith Quantum Processors? Are they compatible with hardware devices like Cache, RAM, Disks of current computers?

# Answer
What you describe as current computers is known as the von Neumann architecture. This approach is one of many ways to think about classical computation and there are other classical approaches that might or might-not have relevant generalizations to quantum computing. The von Neumann architecture seems to be unlikely to be relevant to quantum computing, due to its difficulty from both the theoretical and implementation side.

However, as I mentioned on cstheory there is an article on implementing a quantum von Neumann architecture. They do this via superconducting qubits, of course the implementation is very small, with only 7 quantum parts: two superconducting qubits, a quantum bus, two quantum memories, and two zeroing registers. This allows their quantum CPU to perform one-, two-, and three-qubit gates on qubits, and the memory allows (data) qubits to be written, read out, and zeroed. Implementing a quantum superposition of gates is very difficult, and so the program is stored classically.

More likely models of quantum computing to be implemented include: measurement-based, topological, and adiabatic models. Typical implementations of these models look more like physics experiments (which they are!) than computers. Some of the common strategies for implementation include trapped ions, quantum optics, and superconducting circuits.

The circuit approach has been placed on chips and in fact D-Wave (a spin-off from UBC in Vancouver) claims to have built quantum-like computers using the adiabatic model to implement quantum simulated annealing. They have managed to sell this computer to Lockheed Martin but their approach has been met with heavy skepticism.

Lastly, the NMR approach mentioned by @RanG. is interesting, but suspected to be not equivalent to full quantum-computing. It is equivalent to the one-clean qubit model (also known as DQC1) and suspected to be strictly weaker than full quantum computing.
> 13 votes

# Answer
Not really. Quantum-computers will need to be able to process quantum-bits (qubits) rather than "classical" bits.

Current devices (RAMs, disks) use nowdays technology to maintain classical bits: for instance, a memory cell (say, a capacitor) with high-voltage is "holding" the bit value "1"; if the voltage is low the bit is "0".

Qubits are "implemented" via very small "particles": photons, atoms, small molecules, and their "state" (energy level, etc.) is the "value". Those cannot be saved via a capacitor, for instance.

However, a quantum-computer will definitely have "classical" parts (like having two computers connected, one is classical and one quantum; if there is a computation to make, the classical part will be active; when a quantum effect is needed, the quantum part will be active). So quantum-computer will use standard RAMs, DISKs as well as other quantum-devices.

For the quantum-devices themselves: this depends much on the implementations. Optical devices will be used to manipulate photons. NMR computers will need to have a giant magnets, etc. (I'm not really familiar with implementation, but wikipedia seems to have several examples that you can start with).
> 7 votes

---
Tags: computer-architecture, quantum-computing
---


# Question
Title: Expected space consumption of skip lists
What is the expected space used by the skip list after inserting $n$ elements?

I expect that in the worst case the space consumption may grow indeﬁnitely.

Wikipedia says space $O(n)$.

How can this be proven one way or another?

# Answer
> 8 votes
In this paper it is proven that there exists a constant $\alpha$ such that the probability of the space exceeding $\alpha n$, is less than $1/2^{\Omega(\sqrt{n})}$. Thefore, the more elements there are, the less likely it is to exceed this space bound.

# Answer
> 4 votes
If you really want worst case bounds, and not expected bounds, then take a look at the deterministic skip list which has better space performance than popular balanced binary tree implementations (i.e. $\theta(n)$ with better constants).

However, if you want a random skip list, then technically the worst-case space consumption used by a random skip-list is in fact unbounded. However, the probability that we need a large amount of space is vanishingly small. For large $n$, it would be more likely that you have a hardware failure and simultaneously win the lottery than the skip-list would use, say $n^2$ space.

In more concrete terms, we can evaluate the tail bounds on the expected space consumption of the skip-list. How likely is it that the space used differs significantly from the mean of $\theta(n)$?

Recall that a skip-list (original paper) is made up of several layers. We begin with all elements in the first layer, and for each element, we flip a coin, and promote it to the next layer with probability $1/2$. We continue promoting elements until we reach a layer from which no elements are promoted. Therefore each element belongs to layer $L\_i$ with probability $1/2^i$, since each promotion is an i.i.d. coin flip with probability $1/2$.

Furthermore, note that the total number of elements in all layers is distributed according to the negative binomial distribution with parameters ($n$, $1/2$). That is, the number of successes (heads) in a sequence of Bernoulli trials (coin flips) until we have $n$ failures (tails) corresponds exactly to the total number of promotions when constructing the skip list. Therefore, the expected number of promotions is $n$.

In these lecture notes, they give tail bounds for the number of trials $Y$ in a negative binomial distribution (until we see $n$ tails) where $k = \frac{n}{(1-\delta)p}$.

$$ P(Y \> k) \leq e^{-\delta^2n/(3(1-\delta))} $$

Letting $\delta = 1/3$ and $p = 1/2$, we see that $$ P(Y \> 3n) \< e^{-n\cdot(2/81)} = 1/e^{\theta(n)} $$

Thus, the probability that there are more than $3n$ elements in the skip-list is $o(2^{-n})$. When we have a tail bound like this, we say that the space consumption is linear with *very high probability*.

---
Tags: data-structures, space-complexity
---


# Question
Title: how do you prove that SAT is NP-complete?
As it is, how do you prove that SAT is NP-complete?

I know what it means by NP-complete, so I do not need an explanation on that.

What I want to know is how do you know that one problem, such as SAT, is NP-complete without resorting to reduction to other problems such as hamiltonian problem or whatever.

# Answer
I believe 3-SAT was originally reduced from the more general SATISFIABILITY in Karp's paper that outlined 21 NP-complete problems.

Wikipedia has a description of how to show that SATISFIABILITY is NP-complete, a result that's known as the **Cook-Levin theorem**. The idea of this proof is to show that any polynomial time nondeterministic Turing machine can be modeled as a boolean expression with polynomial size. The boolean expression has terms to represent the valid configuration space of the Turing machine: where the tape head is, what the current state is, what symbols are written on the tape, and what transitions are valid at every position. Because the NTM will halt in polynomial time, the configuration space is bounded and we can make a (large) polynomial expression to represent it.
> 15 votes

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Find the minimal number of runs to visit every edge of a directed graph
I am looking for an algorithm to find a minimal traversal of a directed graph of the following type. Two vertices are given, a start vertex and a terminating vertex. The traversal consists of several runs; each run is a path from the start vertex to the terminating vertex. A run may visit a node more than once. The length of a traversal is the total number of vertices traversed by the runs, with multiplicity; in other words, the length of a traversal is the number of runs plus the sum of the lengths of the runs.

If there are edges that are not reachable (i.e. the origin of the edge is not reachable from the start vertex, or the terminating vertex is not reachable from the target of the edge), they are ignored.

To illustrate my needs, I give a simple graph and post the result, I would like to receive by the algorithm (start vertex $1$, terminating vertex $4$):

Graph edges:

* $1 \to 2,3$
* $2 \to 1,3,4$
* $3 \to 4$

Result:

* Run A: $1, 2, 1, 3, 4$
* Run B: $1, 2, 4$
* Run C: $1, 2, 3, 4$

Each edge (also each direction) has been covered. Each run begins with vertex $1$ and ends with vertex $4$. The minimum total number of visited vertices is searched. In the given example, the minimum number is $5+3+4=12$. There is no unreachable edge in this example.

# Answer
This looks like a minimum-cost flow problem, but with demands instead of capacities.

A *flow* in a directed graph $G = (V,E)$ is a function $\phi: E\to \mathbb{R}\_{\ge 0}$ that assigns a non-negative real value to every edge, such that for every vertex $v$ *except* $s$ and $t$, the total flow into $v$ is equal to the total flow out of $v$, or more formally, $ \sum\_u \phi(u\mathord\to v) = \sum\_w \phi(v\mathord\to w). $ (This equality is usually called the *conservation* constraint.)

It's useful to think of a flow as a weighted sum of paths from $s$ to $t$. In particular, suppose $P$ is a set of simple $(s,t)$-paths, and for any edge $e$, let $\\#P(e)$ denote the number of paths in $P$ that use edge $e$. Then the function $\\#P$ is a flow.

In most traditional flow problems, each edge $e$ also has a capacity $c(e)$, and a flow is feasible if and only if $\phi(e) \le c(e)$ for every edge. However, in your case, you want to *force* the flow to use every edge; so instead, you have a *demand* constraint $\phi(e) \ge 1$ at each edge.

Finally, we can define the *cost* of a flow $\phi$ to be the sum of the flow values: $\\$(\phi) = \sum\_{e\in E} \phi(e)$. Possibly up to some off-by-one errors, your goal is to find a flow $\phi$ of minimum cost that satisfies all the conservation and demand constraints.

This problem can be solved in polynomial time using textbook flow algorithms. Your specific problem is unlikely to appear in any textbook, but all the necessary components are described in Kleinberg and Tardos' *Algorithm Design*. You may also find my lecture notes on flow algorithms (groundwork, basic algorithms, and extensions) helpful.
> 5 votes

# Answer
You wish to find the minimal set of ($s$-$t$)-paths such that each edge is covered. I believe this problem is very similar to the chinese postman problem. First, add a directed edge from $t$ to $s$ to make a new graph $G'$. If $G'$ is eulerian the solution happens to be a simple eulerian tour. Otherwise there exists a subset of vertices $T \subseteq V(G')$ that have odd degree. We can resolve this issue by finding something called a $T$-join.

We know there are an even amount of odd-degree vertices by the Handshaking lemma. We then find a minimal $T$-join by finding a minimal matching over the odd-degree vertices. After this we 'double' the $T$-joined vertices to make our final graph $G''$ and then find a eulerian tour under this graph.

Once the tour has been found, simply remove the $(t,s)$ edge, and you will have your set of $(s,t)$-paths. Both finding the minimal $T$-join and finding the minimal eulerian tour take $O(n^3)$ steps. While a flow formulation certainly works fine, this may be a bit faster in practice.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: How will broadcast behave with a certain capacity?
I wanted to confirm something and will appreciate your help. Suppose we have three nodes called A,B and C. All are connected to a switch whose port supports 1 Gbps. Now suppose, Node's A network card is 100 Mbps while the the remaining have a 1 Gbps. Following are the constraints;

1. A can send B only with a maximum of 100 Mbps.
2. A can send C only with a maximum of 80 Mbps.

Now if I were to broadcast a 2 GB file;

1. It would reach B after approx 2.73 minutes.
2. It would reach C after approx 3.41 minutes.

Now even if I replace node A's network card with 1 Gbps with the same constraints, I would still get the same results. Have I got it right?

# Answer
I assume you want to broadcast from A.

The fastest is probably to broadcast at 80 Mbps and the end of the broadcast is then at 200 seconds (3.33 minutes) for both B and C.

Broadcasting at 100 Mbps will prevent C for receiving your file, since your switch can't store the exceeding 400 MB.

But I don't understand where do your constraints come from? Would it be possible to make C and B communicate? Also I don't quite understand how you did your calculations.
> 2 votes

---
Tags: computer-networks
---


title: DFA with limited states

text:
# Question
Title: DFA with limited states
Lets $L\_z \ := \\{ a^i b^i c^i : 0 \leq i \< z \\}$

$\\{a,b,c\\} \in \sum^\*$

there is a DFA with $\frac{z(z+1)}{2}+1$ states - How can I prove this?

And I need largest possible number $n\_z$, for which i can prove that every NFA, which accepts $L\_z$, have $n\_z$ states, at least!

But first I need to show that $n\_z = \frac{z(z+1)}{2}$ right?

# Answer
### Constructing a DFA

There is an algorithm to construct a minimal DFA for a regular language. In this case, it isn't too hard to come up with a DFA with $z(z+1)/2$ states.

Observe that $L\_z = \\{\epsilon, abc, aabbcc, \ldots, a^{z-1}b^{z-1}c^{z-1}\\}$. Once you know the number of $a$'s at the beginning of the word, you know how many $b$'s and $c$'s to expect. Here's a simple DFA built from this observation (with $z' = z-1$):

<sup>\[source\]</sup>

Following the usual convention, if there is no transition for a particular letter from a particular node, the automaton goes to a sink state.

This automaton has $n$ states reached after reading $0$ to $z-1$ letters `a` ($k,0,0$ for $0\le k\le z-1$), and branches of length $2k$ for $0 \le k \le z-1$ to read the right number of `b`'s and `c`'s ($k,i,0$ and $k,k,i$ for $1 \le i \le k \le z-1$). That's a total of $z + \sum\_{k=0}^{z-1} (2k) = z^2$ states, plus one to account for the implicit sink state.

It's possible to compress this automaton a bit.

> Notice that every side branch finishes by counting the `c`'s. Instead of tracking how many `c`'s have already been seen, think in terms of how many `c`'s are left to read. You can merge all the states of the form $k,k,k-n$, for all $k \ge 1$, into a state $-,n$ from which $n$ occurrences of `c` must be read. In particular, there will be only two final states: one for the empty word, and one after reading the right number of `c`'s. In this automaton, the $k$th side branch has $k$ edges to read the `b`'s (so $k-1$ states, as the start state belongs to the `a` trunk, and the end state belongs to the `c` collector), and there are $z-1$ transitions to count the `c`'s (so $z$ states, corresponding to $0$ through $z-1$ `c`'s left).

The total number of states in this automaton (including the sink state) is $z + \sum\_{k=1}^{z-1} (k-1) + (z-1) + 1 = z(z+1)/2 + 1$.

### Constructing an NFA

In other words, $n\_z$ is the number of states in a minimal NFA that recognizes $L\_z$. If you have a DFA with $N$ states, that's an NFA with $N$ states. So $n\_z \le z(z+1)/2+1$. For most languages, a minimal NFA is smaller than a minimal DFA: nondeterminism adds expressive power in terms of how much you can accomplish with a number of states.

In this particular case, it happens that the minimal DFA above is also a minimal NFA (if I didn't make a mistake). Here's an informal proof.

> Consider the states in the middle of reading the `b`'s. When reading $a^k b^i | b^{k-i} c^k$, where $|$ represents the current position, the state must account for both $k$ and $i$, to remember both the number of seen `a`'s (which is necessary, because we'll need to count the `c`'s later) and the number of seen `b`'s (or, equivalently, the number of `b`'s still required). This requires distinct states for every $(i,k)$ such that $1 \le i \lt k \le z-1$. In addition, there must be $z-1$ states to count the `a`'s at the beginning, and $z-1$ states to count the `c`'s at the beginning, plus a sink state. That's a total of $z(z+1)/2+1$ states.
> 9 votes

# Answer
I will give you an indication: first, write an automaton which recognizes exactly the language $M\_n=\\{b^nc^n\\}$. How many states has this automaton?

Now use the pumping lemma to prove that this is the minimum number of states for $M\_n$. The pumping lemma can be refined for automata with fixed number of states which is exaclty wikipedia's $p$ in "there exists $p$ such that ...".

Use the automata for $M\_n$ to build your DFA for $L\_z$.

EDIT: I removed the last part: you can use the pumping lemma to prove the minimum size for $M\_n$ but not (at least not directly) for $L\_z$.

To prove that you got the minimum size for the automaton, you can reason about the languages corresponding to each state, corresponding to the residual languages $w^{-1}L\_z$. The number of such residual languages is a lower bound on the number of states for $L\_z$.
> 5 votes

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


# Question
Title: Hashing using search trees instead of lists
I am struggling with hashing and binary search tree material. And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And I try to understand what the worst-case and average-case running time for the operations

1. `insert`,
2. `find` and
3. `delete`

is in worth- resp. average case. Do they improve with respect to lists?

# Answer
> 4 votes
For lists, insertion, find and delete are respectively in $O(1)$, $O(n)$, $O(n)$. Sorted list are worse. Binary search itself is for sorted arrays, in which the operations are in $O(n)$, $O(\log n)$, $O(n)$. If you want "insertion" and "delete" operations then you need more than just binary search.

You probably want something like binary search trees. It is a lot easier to find references about it once you have the proper terminology. These operations are in $O(\log n)$ worst-case time, for example for the implementations using AVL trees and red-black trees.

# Answer
> 4 votes
In the worst case, if you happen to store only elements with the same hash values, a hash table stores every element in the same bucket. If you use lists to store the elements of a bucket, then lookup is $O(n)$ in the worst case (where $n$ is the number of elements in the table — more generally, $n$ is the number of elements in the largest bucket), because you need to traverse the whole list if you're looking up an element that isn't in the table. Positive lookup (where you know the element is present) has the same complexity: you need $n-1 = \Theta(n)$ if you're looking up the last element of the list. Deletion has the same complexity (you need $n-1$ lookups if you happen to be deleting the last element). Insertion is also $O(n)$ if you need to check for an existing element, or $O(1)$ if you allow duplicates (in which case you can insert the element at the beginning of the list).

With *balanced* binary search trees, the worst-case complexity is reduced to $O(\log n)$, because the depth of a balanced search tree grows logarithmically in the size of the tree by definition of balancing.

With an average distribution of data, the elements are spread across different buckets and there are few collisions, so the complexity is close to $O(1)$ regardless of the data structure used in case of collisions.

With random lookups in an adversarially-chosen data distribution in which all $n$ elements are in the same bucket, the average length of list that must be traversed is $n/2$, so the average lookup complexity in this situation is $\Theta(n)$. With a tree, the average is $\Theta(\log n)$, like the worst case.

---
Tags: data-structures, time-complexity, runtime-analysis, search-trees, hash-tables
---


# Question
Title: Recursion for runtime of divide and conquer algorithms
A divide and conquer algorithm's work at a specific level can be simplified into the equation:

$\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$

where $n$ is the size of the problem, $a$ is the number of sub problems, $b$ is the factor the size of the problem is broken down by at each recursion, $k$ is the level, and $d$ is the exponent for Big O notation (linear, exponential etc.).

The book claims if the ratio is greater than one the sum of work is given by the last term on the last level, but if it is less than one the sum of work is given by the first term of the first level. Could someone explain why this is true?

# Answer
The total work is given by the sum of a geometric progression. In particular, let $r = a/b^d$, then total work = $O(n^d)\times (1+r+r^2+\ldots+r^p)$, where $p$ is the maximum depth.

Let $S = (1+r+r^2+\ldots+r^p)$.

If $r\>1$, then $S = \frac{r^p-1}{r-1}+r^p = O(r^p)$.

If $r\<1$, then $S \leq 1+r+r^2+\ldots = \frac{1}{1-r} = O(1)$.
> 7 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, recursion, mathematical-analysis
---


# Question
Title: Explain $\log_2(n)$ squared asymptotic run-time for naive nested parallel CREW PRAM mergesort
On from Page 1 of these lecture notes it is stated in the final paragraph of the section titled CREW Mergesort:

> Each such step (in a sequence of $\Theta(\log\_2\ n)$ steps) takes time $\Theta(\log\_2\ s)$ with a sequence length of $s$. Summing these, we obtain an overall run time of $\Theta((\log\_2\ n)^2)$ for $n$ processors, which is not quite (but almost!) cost-optimal.

Can anyone show explicitly how the sum mentioned is calculated and the squared log result arrived at?

# Answer
You want to compute this sum: $$ \sum\_{i=1}^{\mathrm{log}\left( n\right) }\mathrm{log}\left( \frac{n}{{2}^{i}}\right) $$

This can be easily rewritten to: $$ \sum\_{i=1}^{\mathrm{log}\left( n\right) }\mathrm{log}\left( n\right) - \sum\_{i=1}^{\mathrm{log}\left( n\right) }i $$

The first term is clearly $(\log(n))^2$. The second term is $(\log(n))^2/2+o((\log(n))^2)$. Summed, the result is $\Theta((\log(n))^2)$.
> 5 votes

---
Tags: algorithms, complexity-theory, parallel-computing
---


title: Non-regular Languages?

text:
# Question
Title: Non-regular Languages?
> **Possible Duplicate:**
> How to prove that a language is not regular?

Why $L\_a$ and $L\_b$ are not reguluar?

$L\_a = \\{ e^i f^{n-i} g^j h^{n-j} : n \in N, 1 \leq i, j \leq n \\}$.

$L\_b= \\{nm^{i\_1} nm^{i\_2}...bn^{i\_z}: z \in N, (i\_1,...,i\_n) \in N^z, 1 \leq j \leq z, i\_j ≠ j \\}$.

# Answer
> 4 votes
Hints...

$L\_a$ can be transformed into an well-known non-regular language by a very simple homomorphism that basically "loses" information.

For $L\_b$ you might try transforming it into its "opposite" (that is, equality in place of inequality) by operations known to preserve regular languages. The "opposite" language might then be amenable to a pumping argument. Also, try "testing" your argument on a much simpler version of $L\_b$ which, although it **is** regular, will let you see the patterns to use for the full $L\_b$.

PS -- these are both techniques that might be added to the reference post that Dave Clarke points to. I will do so when this question has settled down.

---

Thinking a bit more about $L\_b$, the idea I had in mind to derive the "opposite" language may not lead directly to an easy solution. So here's a hint in a different direction. There are a lot of $m^{i\_j}$ in each string of that language. If you could "isolate" those strings of $m's$ by an appropriate regularity-preserving operation, you might get a simpler language that is amenable to a proof, perhaps by pumping or perhaps by the "opposite" idea. Also, think about what each $i\_j \neq j$ means in terms of other symbols in the string.

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


# Question
Title: Efficiently computing or approximating the VC-dimension of a neural network
My goal is to solve the following problem, which I have described by its input and output:

**Input:**

A directed acyclic graph $G$ with $m$ nodes, $n$ sources, and $1$ sink ($m \> n \geq 1$).

**Output:**

The VC-dimension (or an approximation of it) for the neural network with topology $G$.

**More specifics**:

* Each node in $G$ is a sigmoid neuron. The topology is fixed, but the weights on the edges can be varied by the learning algorithm.
* The learning algorithm is fixed (say backward-propagation).
* The $n$ source nodes are the input neurons and can only take strings from $\\{-1,1\\}^n$ as input.
* The sink node is the output unit. It outputs a real value from $\[-1,1\]$ that we round up to $1$ or down to $-1$ if it is more than a certain fixed threshold $\delta$ away from $0$.

The naive approach is simply to try to break more and more points, by attempting to train the network on them. However, this sort of simulation approach is not efficient.

---

### Question

Is there an efficient way (i.e. in $\mathsf{P}$ when changed to the decision-problem: is VC-dimension less than input parameter $k$?) to compute this function? If not, are there hardness results?

Is there a works-well-in-practice way to compute or approximate this function? If it is an approximation, are there any guarantees on its accuracy?

### Notes

I asked a similar question on stats.SE but it generated no interest.

# Answer
> 9 votes
If you are willing to constrain the problem further by letting the network be layered, then Tom Mitchell's "Machine Learning" gives an upper bound of ( $2ds \log(es)$) (section 7.4.4) where $s$ is the number of internal nodes (which must be higher than 2), $d$ is the VC dimension of the individual nodes, and $e$ is the base of the natural logarithm. If you're after a bound on the number of training examples then this information should be enough.

It's not strictly an answer to your question, but it might help you on the way. The result is due to Baum and Haussler (1989).

---
Tags: algorithms, complexity-theory, machine-learning, neural-networks, vc-dimension
---


# Question
Title: Analysis of and references for Koch-snowflake-like (and other exotic) network topologies
In computer networking and high-performance cluster computer design, network topology refers to the design of the way in which nodes are connected by links to form a communication network. Common network topologies include the mesh, torus, ring, star, tree, etc. These topologies can be studied analytically to determine properties related to their expected performance; such characteristics include diameter (maximal distance between a pair of nodes, in terms of the number of links which must be crossed if such nodes communicate), the average distance between nodes (over all pairs of nodes in the network), and the bisection bandwidth (the worst-case bandwidth between two halves of the network). Naturally, other topologies and metrics exist.

Consider a network topology based on the Koch snowflake. The simplest incarnation of such a topology consists of three nodes and three links in a fully-connected setup. The diameter is 1, average distance is 1 (or 2/3, if you include communications inside a node), etc.

The next incarnation of the topology consists of 12 nodes and 15 links. There are three clusters of three nodes fully, each cluster being fully connected by three links. Additionally, there are the three original nodes, connecting the three clusters using six additional links.

In fact, the number of nodes and links in incarnation $k$ are described by the following recurrence relations: $$N(1) = 3$$ $$L(1) = 3$$ $$N(k+1) = N(k) + 3L(k)$$ $$L(k+1) = 5L(k)$$ Hopefully, the shape of this topology is clear; incarnation $k$ looks like the $k^{th}$ incarnation of the Koch snowflake. (A key difference is that for what I have in mind, I am actually keeping the link between the 1/3 and 2/3 nodes on successive iterations, so that each "triangle" is fully connected and the above recurrence relations hold).

Now for the question:

> Has this network topology been studied, and if so, what is it called? If it has been studied extensively, are there any references? If not, what are the diameter, average distance and bisection bandwidth of this topology? How do these compare to other kinds of topologies, in terms of cost (links) & benefit?

I have heard of a "star of stars" topology, which I think is similar, but not identical, to this. If anything, this seems to be more of a "ring of rings", or something along those lines. Naturally, tweaks could be made to the definition of this topology, and more advanced questions could be asked (for instance, we could assign different bandwidths to links introduced at earlier stages, or discuss scheduling or data placement for such a topology). More generally, I am also interested in any good references for exotic or little-studied network topologies (regardless of practicality).

Again, apologies if this demonstrates ignorance of relevant research results, and any insights are appreciated.

# Answer
> 3 votes
Not really a straight answer, but I don't have the ability to comment yet. I think you are confusing the Koch snowflake with the Sierpinski gasket/triangle. A Koch topology would just be equivalent to a path. The Sierpinski triangle has the properties you describe.

A quick google shows a wealth of papers and webpages on Sierpinski networks, although there is little agreement on the exact topology.

---
Tags: computer-networks, network-topology
---