title: Randomizd String Searching

text:
# Question
Title: Randomizd 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

I want to state an algorithm that runs in time O(n) where we assume that arithmetic operations on O(log2n) 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−1n otherwise.

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

# Answer
> 1 votes
The average complexity of the search from the back to the front is equal to $$ \sum\_{i=1}^n \frac{2i}{n(n+1)}(n-i+1) = \frac{2}{n(n+1)}\sum\_{i=1}^n i(n-i+1) = \frac{2}{n(n+1)} \frac{1}{6}n (n+1) (n+2) = \frac{1}{3}(n+2) $$ which is indeed linear.

# Answer
> 0 votes
Well, a common-sense heuristic would be to check the next most likely place first. This would suggest checking the array from the back to the front is optimal, since the target is more likely to be in higher positions.

The best and worst cases are the same as for vanilla linear search: in the best case, it's always the first element you check, and in the worst case it's always the last. The average case for linear search is also linear time, since you have to check roughly half of the elements (on average) to find the target. So the question we need to ask is the following: by checking the positions with highest probability, how many do we need to check to have at least a 50% chance of finding the target? It's a bit easier to answer this if we ask the question differently: how many positions can we check from the front, before we have a 50% chance of finding the target?

---
Tags: searching
---


title: Clarification about big Oh calculation

text:
# Question
Title: Clarification about big Oh calculation
Say you have a loop that iterates over an array,

```
for i in someArray:
    //some code

```

This basic example would have a running time of $O(n)$. Say that you added a nested loop with equal number of operations, this then would be $O(n^2)$. My question is, is it safe to do this kind of simplication in general? For example,

Say your outer loop had worst case complexity of $O(n^2)$ and your inner loop has worst case complexity of $O(\log n)$. Can the total time complexity be said as $O(n^2\log n)$?

# Answer
Yes, that's correct. Big O is all about the upper bound on the number of executions of an algorithm.
> 3 votes

# Answer
Your first generalisation is wrong, it depends on what's the complexity of loop content. However if that 'some code' is of constant complexity \[something like $O(1)$\], the whole complexity will be $O(n)$.

Your second example is correct.
> 4 votes

# Answer
heres a very nice general/introductory online ref/chapter on the subj by an expert that will answer your question and give you a firm beginning foundation, with lots of exercises.

from his book free online
> 1 votes

---
Tags: asymptotics
---


title: Carry-free multiplication operation

text:
# Question
Title: Carry-free multiplication operation
In long-multiplication, you shift and add, once for each $1$ bit in the lower number.

Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication, the addition does not carry. Essentially you bitwise-**xor** the shifted numbers.

Like so:

$$ \left\[\begin{matrix} &&p\_n & ... & p\_i & ... & p\_2 & p\_1 \\ &&q\_n & ... & q\_i & ... & q\_2 & q\_1 & \otimes\\ \hline\\ &&q\_1 \cdot p\_n & ... & q\_1 \cdot p\_i & ... & q\_1 \cdot p\_2 & q\_1 \cdot p\_1\\ &q\_2 \cdot p\_n & ... & q\_2 \cdot p\_i & ... & q\_2 \cdot p\_2 & q\_2 \cdot p\_1\\ &&&&&&&...\\ q\_i \cdot p\_n & ... & q\_i \cdot p\_i & ... & q\_i \cdot p\_2 & q\_i \cdot p\_1 & \stackrel{i}{\leftarrow} &&{\Huge{\oplus}} \\ \hline \\ \\r\_{2n}& ... & r\_i & ... &r\_4& r\_3 & r\_2 &r\_1 & = \end{matrix} \right\] $$

Using the long-multiplication-style formulation, this takes $\mathcal O\left(\max\left(\left|p\right|,\left|q\right|\right)^2\right)=\mathcal O\left(\left|r\right|^2\right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.

---

## Followup: Shift-and-or multiplication operation

# Answer
> 5 votes
Your operation is multiplication of polynomials over $GF(2)$, i.e., multiplication in the polynomial ring $GF(2)\[x\]$.

For instance, if $p=101$ and $q=1101$, you can represent them as $p(x)=x^2+1$, $q(x)=x^3+x^2+1$, and their product as polynomials is $p(x) \times q(x) = x^5+x^4+x^3+1$, so $p \otimes q = 111001$.

If $p,q$ are $r$ bits long, this polynomial multiplication operation can be computed in $O(r \lg r)$ time using FFT techniques, but in practice this may not be a win unless your polynomial is extremely large. There is also a Karatsuba-style algorithm, whose complexity is something like $O(r^{1.6})$, as well as other options. The situation is somewhat analogous to integer multiplication, in that many of the same fast algorithms can be applied, but not identical.

See, e.g.,

# Answer
> -1 votes
here is a nice/comprehensive survey of standard/best techniques in the area esp from the pov of implementation in logic gates, which shows basic optimizations including Schonhage and Strassen, but there is also an issue of practicality in the implementation.

> Schonhage and Strassen \[302\] have described a circuit to multiply integers represented in binary that is asymptotically small and shallow. Their algorithm for the multiplication of n-bit binary numbers uses $O(n \log n \log \log n)$ gates and depth $O(\log n)$. It illustrates the point that a circuit can be devised for this problem that has depth $O(\log n)$ and uses a number of gates considerably less than quadratic in $n$. Although the coefﬁcients on the size and depth bounds are so large that their circuit is not practical, their result is interesting...

---
Tags: algorithms, integers, number-theory, multiplication
---


title: Lines intersections with a point in 1D

text:
# Question
Title: Lines intersections with a point in 1D
I have an array of lines in 1D represented by coordination and weight, it can be only positive weight. I want to find all the lines that intersect a point in a given range.

Is there any efficient way of doing it?

# Answer
> 2 votes
You can do the trivial scan in $\mathcal{O}(n)$ time where $n$ is the number of intervals (just check for each interval whether your value is in it) or you can use an interval tree; those allow for querying in logarithmic time, see for example here.

# Answer
> 3 votes
If you store all of the intervals in a segment tree, then the operation "find all intervals that contain the point $x$" is known as a stabbing query. Building a segment tree from $n$ intervals takes $O(n \lg n)$ time, but once it is built, you can answer a stabbing query in $O(\lg n + k)$ time, where $k$ is the number of intervals that intersect the point $x$ (i.e., the length of the output of the operation).

In comparison, a linear scan (as described in G. Bach's answer) requires no preprocessing but takes $O(n)$ time to answer each stabbing query. Thus, if you plan to make many stabbing queries on the same set of intervals, it may be faster to build a segment tree in advance, as each stabbing query can then be answered much faster.

See also interval trees, which have similar properties.

---
Tags: algorithms
---


# Question
Title: Best, worst and average cases for a function that uses random number generator
For the following function (not in particular coding style or programming languange)

```
f (N, y)                // y is an integer such that 0 <= y < N
{

    x = rand (N)            // rand (N) returns a random integer x satisfying 0 <= x < N

    if (y == rand (N))
        return
    else f (N, y)

}

```

I need to find best, worst and average cases using O-notation. So my assumption is that the line

```
x = rand (N)

```

does nothing particular but in each recursion it takes O(1) (correct me if my assumption is wrong).

Now, the best case is quite obvious - rand() will give y or O(1).

The thing that I have stuck in are the worst and average cases. In the worst case it will just go into infinite iteration, but what is the complexity for a function that does not halt? And what is the average case? My assumption about the average case is that it will go through all N integers and then find y.

# Answer
To answer your first question, the average-case complexity of an algorithm that does not halt is, well, infinite ($\infty$).

The second question is a reasonable exercise, so I'll let you solve it yourself. A hint: you might want to review the definition of average-case complexity. Also, you might want to compute the probability that this function returns on the first iteration, and you might want to review the expected value of a geometric random variable.
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: What is the definition of Computer Science, and what is the Science within Computer Science?
I am pursuing a BS in Computer Science, but I am at an early point of it, and I am pretty sure I will be happy with my choice given that it seems like an academically and career flexible education to pursue.

Having said that, there seems to be a variety of definitions about what Computer Science really is in respects to academia, the private-sector, and the actual "Science" in "Computer Science" I would love to have answers(Or shared pondering) as to the breadth of things an education in Computer Science can be applied to, and ultimately the variety of paths those within Computer Science have pursued.

# Answer
> 39 votes
Computer science is a misnomer - there is actually no "science" in computer science, since computer science is not about observing nature. Rather, parts of computer science are *engineering*, and parts are *mathematics*.

The more theoretical parts of computer science are purely mathematical. For example, what is a good algorithm for sorting? How do we define the semantics of programming languages? How can we be sure that a cryptographic system is secure?

When computer science gets applied, it becomes more like engineering. For example, what is the best way to implement a matrix multiplication algorithm? How should we design a computer language to facilitate writing large programs? How can we design a cryptographic system to protect online banking?

In contrast, science is about *laws of nature*, and more generally about *natural phenomena*. The phenomena involved in computer science are man-made. Some aspects of computer science can be viewed as experimental in this sense, for example the empirical study of social networks, the empirical study of computer networks, the empirical study of viruses and their spread, and computer education (both teaching computer science and using computers to teach other subjects). Most of these examples are border-line computer science, and are more properly multidisciplinary. The closest one gets to the scientific method in computer science is perhaps the study of networks and other hardware devices, which is mainstream in the subarea known unofficially as "systems".

These examples notwithstanding, most of the core of computer science is not science at all. Computer science is just a name - it doesn't need to make sense.

As for the scope of computer science, the best definitions is perhaps: that which computer scientists do. Computer science, like every other academic discipline, is a wide area, and it is difficult to chart completely. If you want a sampling of what people consider computer science, you can look at the research areas of your faculty.

# Answer
> 12 votes
Let us start with a quote from one of the fathers of modern Computer Science: “Computer Science is no more about computers than astronomy is about telescopes” - Edsger Wybe DIJKSTRA

So in reality if what you are interested in is computers and programming then you are not truly interested in computer science :-)

I think Wikipedia has one of the best descriptions: "Computer Science (abbreviated CS or CompSci) is the scientific and practical approach to computation and its applications. It is the systematic study of the feasibility, structure, expression, and mechanization of the methodical processes (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information, whether such information is encoded in bits and bytes in a computer memory or transcribed engines and protein structures in a human cell. A computer scientist specializes in the theory of computation and the design of computational systems"

But in reality as Yuval has stated, most universities/colleges have moved away from the theoretical/pure computer science and computer science is now a mixture of science, mathematics, engineering. Teaching us not only the pure computer science, but also the practical skills to solve those and other problems using modern computers, programming languages, operating systems and software applications.

# Answer
> 12 votes
It might be worth mentioning that the German term for "Computer Science" is *Informatik*, which melts *Infomation* and *Mathematik*. I think that's a nice and short description of what Computer Science is all about. (the Italian term is *informatica*, and I'm sure there are quite a few more languages that follow the same line).

# Answer
> 6 votes
You might be interested in a discussion we had on meta. In particular, I stand by my answer, reproduced here:

Computer Science is the science of computation; that much seems clear. Less clear is how to define science and computation in a useful and meaningful way.

Generally, we might divide science according to two classifications: formal versus empirical, and pure versus applied. Whereas formal science (such as mathematics and much of computer science) relies on deductive reasoning from assumed truths, empirical scienc (such as physics and chemistry) relies on inductive reasoning from observed phenomena. Whereas the goal of pure science is to advance the state of scientific understanding, the goal of applied science is to use such understanding to harness the forces of Nature (in the broadest possible sense of the word) to achieve other goals.

We might define computation as a transformation applied to a piece of information. In the broadest possible sense, computation is, then, any process which causes a change to occur in the universe. There is no need to provide any more detailed definition than this.

Computer Science, then, consists of that part of the human endeavor which satisfies the following criteria:

* It is science, that is:

+ It is either (1) formal or (2) empirical:

    1. employs deductive reasoning from assumed truths
        2. employs inductive reasoning from observed phenomena
    + It is either (1) pure or (2) applied

    1. seeks to advance the state of scientific understanding
        2. seeks to apply scientific understanding to harness natural forces
* It studies computation, that is:

+ It studies either (1) transformations or (2) information
        1. processes which map information from one form to another
        2. entities subject to transformations

# Answer
> 5 votes
I want to add a perspective regarding the word "science" that is too long for a comment.

People say that computer science is not a *science* in the traditional way since (simplifying here) we do either mathematics or engineering. That is not quite true. We can apply the scientific method -- arguably *the* corner stone of science -- that is

> systematic observation, measurement, and experiment, and the formulation, testing, and modification of hypotheses.
> <sub>(Oxford English Dictionary via Wikipedia)</sub>

In fact, some of the earliest work in algorithms adheres to this principle. Some of the method has been "lost" for several reasons but we still *can* employ it.

The basic process¹ would look like this:

* Note a problem that we want to solve with a computer.
* Come up with an algorithm.
* Analyse (a mathematical model of) the algorithm.
* Based on your analysis, predict the algorithm's (expected) runtime (on a given set of inputs and a given machine).
* Confirm or falsify your prediction by experiments.

More generally speaking, we can evaluate how useful algorithmic models and analysis techniques are. And here we arrive at our problem: $O$-analysis is all but useless in this regard. Since most computer scientists not much else, we can't do much science, effectively and sadly. Never mind that most curricula don't seem to include any (rigorous) statistics education, *even* in more empirically oriented subfields.

Don't take my word for it, by the way. Robert Sedgewick and Philippe Flajolet have been working on putting science back into computer science, mostly by developing the formal framework of analytic combinatorics that does allow for testable hypotheses. You can find videos and MOOCs by Sedgewick that will tell you as much.

All hope is not lost.

---

1. This is, of course, only formulated w.r.t. algorithmics. You can also study whether graph models fit reality (done e.g. in work around social networks, albeit often more empirically than scientifically) or network throughput turns out as predicted, or any number of other things.

# Answer
> 3 votes
this is likely an old question long debated going back to the very origins of computer science. a natural way to study/answer this is via published literature on the subj. suspect there are many good refs on this buried in the literature which havent been cited yet. also, the answers/pov on this have likely changed over time aka Kuhnian shifts that have been somewhat common in the field, possibly more so than other scientific fields. another angle to study this is how the subject has been taught in academia and how it has fit into the existing departmental structures which has also changed over time.

here are some nice papers/essays by Denning, authority in the field, that address this question directly and are a good place to start for more refs. both published in the journal of the main academic society of the field, CACM.

> Information processes and computation continue to be found abundantly in the deep structures of many fields. Computing is not—in fact, never was—a science only of the artificial.

> Computer science meets every criterion for being a science, but it has a self-inflicted credibility problem.

# Answer
> 2 votes
working from the definition of science

> 1. a branch of knowledge or study dealing with a body of facts or truths systematically arranged and showing the operation of general laws: the mathematical sciences.
> 2. systematic knowledge of the physical or material world gained through observation and experimentation.
> 3. any of the branches of natural or physical science.
> 4. systematized knowledge in general.
> 5. knowledge, as of facts or principles; knowledge gained by systematic study.

1. computer science is closely connected to mathematics and involves significant research (eg study).
2. computer science is broad & closely connected to physics in many ways. eg physics/thermodynamics of computation, quantum computing, P=?NP as a physical law, phase transitions etc
3. it is systematized knowledge.
4. it undergoes systematic study ie research.

the terminology "computer science" emphasizes the field is not merely about application of known principles eg as in engineering. there is quite a bit of *terra incognita* around computer science, many basic questions in the field are open/unanswered. the number of researchers worldwide is difficult to estimate but numbers beyond the thousands or tens of thousands.

however, note that the more *scientific* aspects of computer science are not really taught/exposed so much at the undergraduate level, maybe leading to some perplexity. there also seem not to be very many high-profile embodiments/celebrations/proponents/advocates of it as a science eg in contrast to other fields such as the LHC & discovery of the Higgs boson etc \[despite that CS had a major role in its discovery!\], or a famous Carl Sagan or Hawking-like populizer figure. however eg see popular science books which inspire CS

---
Tags: terminology, history
---


# Question
Title: Does Reverse Polish Notation have an LL grammar?
Let L be the language of all arithmetic expressions written in Reverse Polish Notation, containing only binary operators. $\Sigma(L) = \\{n, o\\}$, n := number, o := operator.

Is there an LL grammar G so that L(G) = L?

# Answer
> 1 votes
Yes,

$ G = (\\{E,S,R\\}, \\{n,o\\}, P, E)\text{, with productions}\\ E \rightarrow n\ |\ SR \\ S \rightarrow nEo \\ R \rightarrow EoR\ |\ \epsilon \\ $

Proof:

1. Observation $(\*)$: Each word of L represents an arithmetic expression, the result of calculating such an expression is essentially again a number. So whenever we have $w \in L$, we can treat $w$ as a number.
2. Theorems:

1. $L(G) \subset L$
    2. $L(S) \subset L$
    3. $w \in L(R) \implies w=\epsilon \lor (w=w\_1 o, w\_1 \in L)$

Inductive proof of above theorems on derivation step count $n$:

1. Basis $n=1$

    1. $E \Rightarrow n\\ \land \\ n \in L $
        2. $S\text{ can't generate any words in one step. }\\ \land \\ \emptyset \subset L $
        3. $R \Rightarrow \epsilon, w=\epsilon$
    2. Basis $n=2$

    In all 3 cases nothing can be generated in 2 steps, and the theorems hold trivially.
    3. Inductive step: $n=k\>1,$ induction hypothesis (IH): assume theorems hold for $n\<k$

    1. $E \Rightarrow SR \Rightarrow^{k-1} w\_1 w\_2\\, \\ \text{where }w\_1 \in L\text{ because of IH of theorem 2,} \\ \text{and } w\_2 = \epsilon\text{ or }w\_2 = w\_3 o, w\_3 \in L\text{ because of IH of theorem 3.}$

        1. First case: $w\_2 = \epsilon$, then $w\_1 w\_2 = w\_1 \in L$.
            2. Second case: $w\_1 w\_2 = w\_1 w\_3 o =^{(\*)} nno$, which is a valid RPN expression, thus $w\_1 w\_3 o \in L$
        2. $S \Rightarrow nEo \Rightarrow^{k-1} nwo$, where $w \in L$ because of IH of theorem 1. $nwo =^{(\*)} nno$, which is a valid RPN expression, and thus $n w o \in L$
        3. $R \Rightarrow EoR \Rightarrow^{k-2} w\_1 o R$, where $w\_1 \in L$ because of IH of theorem 1. The last step can only be $w\_1 o R \Rightarrow w\_1 o \epsilon$, which satisfies theorem 3.

$\square$
3. Theorem: $L \subset L(G)$

Proof: induction on length of $w \in L$, show that $E \Rightarrow^\* w$

(I got lazy from this point on, I might fill this in later)

$\square$
4. $(1) \land (2) \implies L(G) = L$
5. Theorem: G is LL(k) grammar, $k \in \mathbb{N}$

Proof: Pick a k large enough, then show that for each non-terminal you can decide which production rule to use by looking at the k next terminals.

$\square$

$\square$

---
Tags: context-free
---


title: Shift-and-or multiplication operation

text:
# Question
Title: Shift-and-or multiplication operation
Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold):

Let $r = p \oplus q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication the columns aren't summed up, but rather **or**'d (not **xor**) together. Nothing is carried.

$$ \left\[\begin{matrix} &&p\_n & ... & p\_i & ... & p\_2 & p\_1 \\ &&q\_n & ... & q\_i & ... & q\_2 & q\_1 & \otimes\\ \hline\\ &&q\_1 \cdot p\_n & ... & q\_1 \cdot p\_i & ... & q\_1 \cdot p\_2 & q\_1 \cdot p\_1\\ &q\_2 \cdot p\_n & ... & q\_2 \cdot p\_i & ... & q\_2 \cdot p\_2 & q\_2 \cdot p\_1\\ &&&&&&&...\\ q\_i \cdot p\_n & ... & q\_i \cdot p\_i & ... & q\_i \cdot p\_2 & q\_i \cdot p\_1 & \stackrel{i}{\leftarrow} &&{\bigvee} \\ \hline \\ \\r\_{2n}& ... & r\_i & ... &r\_4& r\_3 & r\_2 &r\_1 & = \end{matrix} \right\] $$

Using the long-multiplication-style formulation, this takes $\mathcal O\left(\max\left(\left|p\right|,\left|q\right|\right)^2\right)=\mathcal O\left(\left|r\right|^2\right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.

# Answer
This is equivalent to an operation known as *boolean convolution*. See *Models of Computation* page 419 defn 9.6.3.

Dunne states (p5):

> Weiss 1984 and Blum 1984b obtained lower bounds for the n-point boolean convolution function which is closely related to integer multiplication.
> 1 votes

---
Tags: algorithms, integers, number-theory, multiplication
---


# Question
Title: Smallest Number of Strings to Distinguish $n$ Pairwise $L$-distinguishable Strings
The following is a homework assignment. I am looking for criticism / feedback on my solution, and I have a specific question.

> Suppose $L$ is a language over $\Sigma$, and $x\_1, x\_2, ... , x\_n$ are strings that are pairwise $L$-distinguishable. How many distinct strings are necessary in order to distinguish between the $x\_i$'s? In other words, what is the smallest number $k$ such that for some set $\\{z\_1, z\_2, ...,z\_k\\}$, any two distinct $x\_i$'s are distinguished, relative to $L$, by some $z\_l$? Prove your answer.

The book gives a hint, which reads as follows:

> Here is a way of thinking about the question that may make it easier. Think of the $x\_i$’s as points on a piece of paper, and think of the $z\_l$’s as cans of paint, each $z\_l$ representing a different primary color. Saying that $z\_l$ distinguishes $x\_i$ and $x\_j$ means that one of those two points is colored with that primary color and the other isn’t. We allow a single point to have more than one primary color applied to it, and we assume that two distinct combinations of primary colors produce different resulting colors. Then the question is, how many different primary colors are needed in order to color the points so that no two points end up the same color?

I have surely addressed this question Here is my answer.

> **Solution**: Coloring $n$ points so that no two points end up the same color requires $\lceil \log\_2 n \rceil$ primary colors.
>
> First enumerate the points using binary representations, and let each digit correspond to a primary color. Then we identify the combination of colors for a given point as all primary colors whose corresponding digit is 1. Each of the points has a unique representation, so each combination of primary colors will be unique.

What do you think of this response? Do you think it needs further explanation?

Also, I am having trouble translating this argument into the context of the original question. How can I better see that the problems are the same?

# Answer
Your solution is correct but not complete.

1. You have not proven the correspondence to the colouring problem given as an intuition in the hint

You could say something on the lines of:- If z distinguishes x and y, we have xz belongs to L but not xy(or vice versa). This is homomorphic(? not sure about this, have to check) to colouring dots x and y with different primary colours, because indistinguishability is transitive, reflexive etc

1. You have only proven that you have a solution using log n strings but not that log n strings are *required*

This could be by contradiction. eg. assume that fewer than log n colours can be used to distinguish the dots. Represent the dots as binary strings consisting of the colours they have. Then you have fewer than log n bots required to represent n numbers in binary

IMHO you can skip the colouring and directly prove correspondence with binary strings
> 0 votes

---
Tags: formal-languages, computation-models
---


# Question
Title: Say that a stack frame only contains total functions: could the maximum stack size be statically determined?
Say that you have a program with only total functions, or if that is impossible, consider a subset of the program with only total functions. Is it theoretically possible to statically determine the maximum size of the stack frame at runtime? The language may have other characteristics that are relevant/necessary (such as a specific type system).

# Answer
No. That would allow you to determine the runtime of any given (recursive) program (assuming it always terminates), but that is not a computable problem.
> 3 votes

---
Tags: algorithm-analysis, compilers
---


# Question
Title: Why is the laplace transform not popular for image processing convolution?
Why is the laplace transform not popular for image processing convolution? Most textbooks only conver the Fourier transforms.

# Answer
> 4 votes
The Laplacian is indeed used in image processing routinely but, possibly not as much as Fourier transforms. Reasons (other than just the difference in span of uses, narrow vs wider) may be: Fourier transforms have been highly optimized due to their wide application, and are possibly less complicated theoretically than the Laplacian. sometimes the Laplacian of the Gaussian is taken for "blob detection".\[2\]\[3\]

From the book *Digital signal processing fundamentals* By Ashfaq A. Khan p105:

> Convolution is the primarily tool in image processing while Laplace Transform is used mainly in signal processing, such as speech and controls systems.

\[1\] Laplace filter in image processing (with edge detection and motion estimation applications)

\[2\] Laplacian in blob detection intuition (mathoverflow)

\[3\] blob detection

# Answer
> 3 votes
A Laplace transform is (in principle) a one-sided Fourier transform with expontial attenuation term. This makes it suitable for many problems with a starting condition (e.g. starting a circuit's voltage supply). For image analysis a plain Fourier transform seems to be all one needs. The Laplacian expresses the second derivate. It has nothing to do with Laplace transform.

---
Tags: history, image-processing
---


title: API - Design issues

text:
# Question
Title: API - Design issues
I'm building a GUI Desktop application that will communicate with an API(http) in a webserver.

In the client side I have a GUI Desktop application and a GSM Modem(hardware). The GUI Desktop application will make requests to the API in the webserver and will get the SMS's to send.

My question here goes on how can I design the application so that the Clients don't cheat by sending requests to the API on the webserver saying that message is send. Anyone got any ideas on how to solve this problem? The GSM modem that send SMSs is in a untrusted client. Ideas on how to protect an API dealing with this kind of environment? I've been reading about proof-of-work, this approach can help to solve my problem?

Best Regards

# Answer
> 2 votes
You can't. This is not solvable. The user controls the client, so the user can always arrange to claim that the message was sent without actually sending it.

If you want to verify that the client did not cheat, you'll need some separate way to verify that the SMS was sent. Maybe you can check with the recipient whether the SMS was actually received. Maybe you can have the recipient give a secret "receipt code" to the client when the recipient receives the SMS, and client can show you that receipt code to demonstrate that the recipient acknowledged receipt. Maybe you can audit clients (check 1% or 10% of the SMS's that they claim to have sent, to see if they were actually received), and if you detect that a client cheated, blacklist them (and maybe even penalize them somehow, such as keep a security deposit that they were required to provide in advance).

Anyway, you cannot prevent the client from cheating and lying to you. It's just not a solvable problem. Proof of work does not solve this problem.

P.S. In the future, this kind of question would be a better fit to Security.stackexchange.com. It's not that you've done anything wrong by asking here -- it is certainly permissible to ask here -- but you might get more detailed and quicker responses over there, since that's what they specialize in.

---
Tags: api-design
---


# Question
Title: 3SAT is NP-complete, however is 1SAT NP-complete?
Its is known that `3SAT (all clauses have size 3)` is NP-complete.

But how about `1SAT (all clauses have size 1)`, is it also NP-complete? I tried searching for it a lot, but couldnt find any proofs or explanations for the same.

Like 3SAT has 3 clauses, what if I consider just one clause?

Thanks for the help in advance.

# Answer
$k$-SAT is defined as the problem of finding models (assignments of either true or false to the variables appearing in the formula) to propositional formulas in Conjunctive Normal Form (CNF). A clause is defined as a disjunction of literals (variables that are either in positive or negative form) and a CNF formula is then just a conjunction of clauses.

Thus, as David Richerby already told you, it is not about formulae that have $k$ clauses.

Take the case you mention, 1-SAT. It is trivial to prove that it can be solved in linear time, $O(k)$ with $k$ being the number of clauses: you just assign value true to the propositions that are positive and false otherwise. It is also possible to prove that a formula is unsatisfiable if it appears in two different (unary) clauses in positive and negative form as you are processing the formula.

Krom showed in 1967 that 2-SAT can be solved in polynomial time.

However, 3-SAT has been known since 1972 to be NP-complete (included in Karp's 21 problems) and there is indeed a lot of work on the (2+p)-SAT where random formulae are generated with clauses of length 2 with probability $(1-p)$ and length 3 with probability $p$ showing that there is a clear transition from polynomial to exponential complexity.
> 11 votes

---
Tags: algorithms, 3-sat
---


title: What is wrong in this proof?

text:
# Question
Title: What is wrong in this proof?
I stumbled upon this wikipage that has got this proof :

I rechecked sum rule of differentiation.

And i can not understand where is this wrong.

Any Tips ?

I think that the second line

x^2 = x + x +... x times...

being used for differentiation is wrong. but i am not sure .

# Answer
The proof states that $(\underbrace{x+x+\dots+x}\_{x~ times})' = (\underbrace{1+1+\dots+1}\_{x~ times})$. Let's give it a try.

$$\lim \_{\epsilon \to 0} \frac{\underbrace{x+\epsilon+x+\epsilon+\dots+x+\epsilon}\_{x+\epsilon~ times} - \underbrace{x+x+\dots+x}\_{x~ times}} {\epsilon} =\\ \lim \_{\epsilon \to 0}\frac{ \underbrace{\epsilon+\epsilon+\dots+\epsilon}\_{x~ times} + \underbrace{x+\epsilon+x+\epsilon+\dots+x+\epsilon}\_{\epsilon~ times}}{\epsilon} = \\ \lim \_{\epsilon \to 0}\frac{ \underbrace{\epsilon+\epsilon+\dots+\epsilon}\_{x~ times} + \underbrace{x+x++\dots+x}\_{\epsilon~ times} + \underbrace{\epsilon+\epsilon+\dots+\epsilon}\_{\epsilon~ times}}{\epsilon} =\\ \lim \_{\epsilon \to 0}\underbrace{1+1+\dots+1}\_{x~ times} + \underbrace{x}\_{1 ~time} + \epsilon = 2x$$
> 3 votes

---
Tags: proof-techniques, correctness-proof
---


# Question
Title: standard sequential algorithm with polylog runtime?
At the Wikipedia article on time complexity, only a PRAM example is given for polylogarithmic time.

Let $T(n)$ denote the largest number of steps used by a machine to reach a final state on any input with size $n$ bits.

> Is there a program for a standard sequential model of computation (e.g. a Turing machine or a sequential random-access machine), solving some natural problem, so that $T(n) \in \Theta((\log n)^k)$ for some fixed $k\>1$?

# Answer
Where each operation is $ O\left(\log^kn\right)$ amortized/expected; I don't know if necessarily $\Theta\left(\log^kn\right)$:

There are also many algorithms with polylogarithmic factors; $\tilde {O}(\cdot)$ is notation that is used when hiding polylogarithmic factors. So $O\left(n\log^k n \right)\in\tilde {O}(n)$.
> 6 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Complexity of Monotone (+,2) SAT problem?
To continue this post, let us define the Monotone$(+, 2^-)$-SAT problem:

Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $F\_2^-$ defined on the same variables as $F^+$, where all variables are negated. Is $F^+ \land F\_2^-$ satisfiable ?

Is this problem NP-complete?

# Answer
This is NP-complete. In fact, it remains NP-complete when $F^+$ is restricted to be in 3-CNF form (not just CNF).

The proof is by demonstrating that this problem is at least as hard as testing 3-colorability of a graph. The correspondence is clean and elegant. Let $G=(V,E)$ be an undirected graph. Introduce variables $x\_{v,c}$, for $v \in V$ and $c \in \\{1,2,3\\}$, to represent a 3-coloring of the graph. Here $x\_{v,c}$ means that we've given vertex $v$ the color $c$.

To represent that each vertex must receive at least one color, we will introduce clauses $x\_{v,1} \lor x\_{v,2} \lor x\_{v,3}$ for each vertex $v$. This gives us $F^+$, i.e.,

$$F^+ \equiv \bigwedge\_{v \in V} (x\_{v,1} \lor x\_{v,2} \lor x\_{v,3}).$$

To represent that no two endpoints of a single edge may receive the same color, we will introduce a clause $\neg x\_{u,c} \lor \neg x\_{v,c}$ for each edge $(u,v) \in E$. And, to represent that no vertex may receive more than one color, we will introduce a clause $\neg x\_{v,c} \lor \neg x\_{v,c'}$ for each $c,c' \in \\{1,2,3\\}$ such that $c\ne c'.$ Let $F^-\_2$ denote the corresponding formula.

$$F^-\_2 \equiv \bigwedge\_{(u,v) \in E} (\neg x\_{u,c} \lor \neg x\_{v,c}) \\; \\; \land \bigwedge\_{v \in V,c\ne c'} (\neg x\_{v,c} \lor \neg x\_{v,c'}).$$

Then it is easy to see that $F^+ \land F^-\_2$ is satisfiable if and only if $G$ has a 3-coloring. In fact, each satisfying assignment of $F^+ \land F^-\_2$ corresponds immediately to a 3-coloring of $G$, and vice versa. Therefore, testing the satisfiability of this class of formulae is at least as hard as testing 3-colorability of an undirected graph, so it is NP-hard.
> 5 votes

---
Tags: complexity-theory, np-complete, decision-problem, complexity-classes
---


# Question
Title: Designing a CFG that produces as many c's as the difference of numbers of a's and b's
The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is

$\qquad\displaystyle L = \\{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}; n = |l-m|\\}$.

I have so far go to create the cfg for $(a^l)(b^m)$ but don't know how to do the one for $(c^n)$. It looks complicated as to find the value of n, we need to take the abs value for the difference between l and m. Can someone help?

And, here is the cfg I got so far for $(a^l)(b^m)$.

$S \to aS \mid bT|\epsilon $

$T \to bT \mid \epsilon$

I hope this is correct.

# Answer
Yuval's answer is headed in the right direction: consider $L\_1 = \\{a^lb^mc^n \mid n = l - m\\}$ and $L\_2 = \\{a^lb^mc^n \mid n = m - l\\}$. Also, as he points out, it's helpful to think of these conditions as $l = n+m$ and $m = n + l$, respectively.

I propose the following grammar for $L\_1$: $$S' \rightarrow aS'c \mid B' \mid \epsilon$$ $$B' \rightarrow aB'b \mid \epsilon$$

I propose the following grammar for $L\_2$: $$S'' \rightarrow A''C''$$ $$A'' \rightarrow aA''b \mid \epsilon$$ $$C'' \rightarrow bC''c \mid \epsilon$$

Now, what remains is to show these grammars generate $L\_1$ and $L\_2$, after which you can give your answer as the following: $$S \rightarrow S' \mid S''$$

(You could even use just one symbol for $B'$/ $A''$, since they have the same rules.)

To show each of the proposed grammars works, you'll need to show two things: each proposed grammar generates only strings in the target language; each proposed grammar generates all the strings in the target language.

Arguing informally, we can say the proposed grammar for $L\_1$ generates only strings in $L\_1$ since whenever we add an $a$, we add either a single $b$ or a single $a$; furthermore, we have all $b$ coming after $a$, and all $c$ coming after $b$. To show that all the strings are generated, consider that applying the rule $S' \rightarrow aS'c$ a number of times equal to $\\#\_c(w)$, then the rule $S' \rightarrow B'$, then the rule $B' \rightarrow aB'b$ a number of times equal to $\\#\_b(w)$, then the rule $B' \rightarrow \epsilon$, yields the string $w = a^{\\#\_b(w)+\\#\_c(w)}b^{\\#\_b(w)}c^{\\#\_c(w)} \in L\_1$ for any non-negative $\\#\_b(w), \\#\_c(w)$.

The arguments for the second proposed grammar are similar.
> 2 votes

# Answer
Hint: Break $L$ into two languages, $L\_1 = \\{ a^l b^m c^n : n = l-m \\}$ and $L\_2 = \\{ a^l b^m c^n : n = m-l \\}$. The conditions are probably better written as $l = m+n$ and $m = l+n$, respectively.
> 1 votes

# Answer
Note that you can as easily construct a pushdown-automaton and use the standard translation. That's not very insightful in terms of learning how to build grammars, but it works.

In this case, note that $c^+$ is the last block, so all an automaton has to do is to have $|l-m|$ symbols on the stack upon reaching the first $c$.
> 0 votes

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


# Question
Title: Myhill-Nerode style characterization of CFL?
Define the *Nerode equivalence* over a language $L \subseteq \Sigma^{\*}$ as $u \sim\_L v$ iff $uw \in L \Leftrightarrow vw \in L$ for every $w \in \Sigma^{\*}$.

The Nerode equivalence ${\sim}\_L$ has finitely many equivalence classes precisely when $L$ can be recognized by a finite-state automaton. This is the Myhill-Nerode theorem.

> Is there a similar characterization of context-free languages?

---

# Motivation:

The Nerode equivalence classes each correspond to a distinct state in any automaton that recognizes $L$. Each CFL can be recognized by an NPDA, which has a finite number of states but also a potentially unbounded stack of alphabet symbols. The stack keeps track of one possible way that a string can be parsed. The number of equivalence classes may be infinite since the stack can store an unbounded number of symbols.

I am asking: is there always a way to clump together equivalence classes so that each clump represents one state of the PDA, with each class within the clump representing equivalent states of the stack for that PDA state?

For instance, the language of properly nested parentheses only needs states to handle `pop` and `push`, as the stack will keep track of the current nesting depth. If such clumping can always be done, then whether the number of clumps is finite determines whether the language is context-free.

---

As pointed out by @sdcvvc in a comment, a form of this question was asked as https://math.stackexchange.com/questions/118362 although Yuval Filmus's answer to the related question at Example of a non-context free language that nonetheless CAN be pumped? is more relevant.

# Answer
David S. Wise provides in his paper A strong pumping lemma for context-free languages a strong pumping lemma which is *equivalent* to being context-free. He also provides an additional equivalent condition (property 3 on page 362) which he claims could be viewed as an analog of the Myhill-Nerode theorem. As an application of the latter, he shows that $\\{ a^nba^{mn} : m,n \> 0 \\}$ cannot be expressed as a finite intersection of context-free languages.

More information on the strong pumping lemma appears in one of my answers.
> 9 votes

# Answer
There is a very nice characterization of context-free languages (credited to Wechler) in the paper by Berstel and Boasson, Towards an algebraic theory of context-free languages. Let me introduce a few definitions in order to state this result (Theorem 3.1 in the paper).

The *polynomial closure* $Pol(\mathcal{L})$ of a class $\mathcal{L}$ of languages of $A^\*$ is the set of all languages that are finite unions of products of the form $L\_0a\_1L\_1 \dotsm a\_nL\_n$, where $L\_0, ..., L\_n \in \mathcal{L}$ and $a\_1, ..., a\_n \in A$.

An *algebra* is a class $\mathcal{A}$ of languages containing the language $\\{1\\}$ and such that $\mathcal{A} = Pol(\mathcal{A})$. It is *finitely generated* if $\mathcal{A} = Pol(\mathcal{F})$ for some finite set $\mathcal{F}$ of languages. It is *stable* if, for each $L \in \mathcal{A}$ and $u \in A^\*$, the language $u^{-1}L = \\{v \mid uv \in L\\}$ also belongs to $\mathcal{A}$. Note that it suffices to have $a^{-1}L \in \mathcal{A}$ for all $a \in A$.

**Theorem**. A language of $A^\*$ is context-free if and only if it belongs to a finitely generated stable algebra.

See the article for illuminating examples and many nice consequences.
> 6 votes

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


# Question
Title: Valgrind: what is the difference between a store and a modify?
I am using the Vlagrind lackey tool to examine the full memory reference string of a running computer program and wonder what the difference between a "store" and a "modify" might be - and do these differences reflect a real difference in category of memory manipulation, or are they merely a convenience for the user/programmer of Valgrind's lackey tool?

The comments on the lk\_main.c source code give these examples of (a) A store:

```
movl %eax, (%ebx)

```

And (b) a modify

```
incl (%ecx)

```

I appreciate this is a question about a specific piece of software, but what I really want to know is if it is valid to consider stores and modifies as, in effect "stores" - as much texts on memory seem to regard the two basic operations as load (read) and store (write).

# Answer
This sounds like a question about the terminology that Valgrind happens to use, more so than a question about fundamental aspects of computer science. I suggest you ask on a Valgrind support forum if you want an authoritative answer.

Based on your examples, it looks like the most likely answer is that the Valgrind folks are using the word "store" to mean "an operation that writes to memory, overwriting in a previous value with a new value that does not depend upon its previous value" while they mean "modify" to mean "an operation that writes to memory, updating its value to a new value that may depend upon the value previously stored in that location". Only Valgrind folks can confirm authoritatively whether this is actually what they mean.
> 2 votes

# Answer
Having waded through the comments in the source code it seems that a "modify" is a combined (perhaps implicit) read and a write - so in the example above, a value is incremented, which implies it is read before it is written to.

So the basic categories of the computer science literature - read and write - are sufficient, though a modify contains both.
> 1 votes

---
Tags: memory-access
---


# Question
Title: What information do we get from a compiler's parse tree?
In the compiler course by Alex Aiken on Coursera, more specifically lecture 05-02 Context Free Grammars, the professor says that CFGs give answers of the type yes/no, i.e. whether the given string of tokens is valid or not. He adds that it is also desirable to know *how* a particular string of tokens is in the language; for this purpose he introduces parse trees.

Why is the "how" part important?

# Answer
**Prelude** It might be useful to be pedantic and start with a surprising fact: compilers do **not** use context free grammars, contrary to what you've been told. Instead they use something closely related but subtly different, which might be termed **context-free transducers** (please let me know if there's an official name for it). They relate to context free grammars as Mealy-machines do to finite state machines.

The reason why CFGs are not used is that CFGs only give a yes/no answer. That's not enough for the subsequent stages of a compiler. Instead, subsequent stages need a good representation of the input program to work with. This representation is the abstract syntax tree (AST). Something similar happens in lexical analysis: contrary to what most compiler courses tell you, the lexer does **not** use a finite state machine or regular expression to nail down the lexical structure of a language, because regular expressions and finite state machines also only give a yes/no answer. We want the output of the lexical stage to be a token-list for consumption by the parser. Mealy machines deliver token lists.

If this is the case, why do compiler courses usually use regular expressions and finite state machines for the lexical analysis and CFGs for parsing? Do compiler teachers lie to us? No, they want to help us understand:

1. The concepts are really similar, e.g. a Mealy machine is just a finite state machine where every transition carries not just an input action (as they do with finite state machines) but also a corresponding output action. Likewise context free transducers are just CFGs where every production is also associated with an output.
2. Teachers don't want to be overly formal, and expect the students to bridge the gap between finite state machines and lexer / CFG and parser themselves. In practise students almost always do.

**Main point.** With this pedantic caveat we can come to the original question: what is the parse tree used for?

The parse tree contains the "how a string is in the CFG". The parse tree is used to construct the **abstract syntax tree** (AST) which is a **concise** representation of the program that is used by later phases in the compiler, in particular the type checker (for statically typed languages) and the code generator. The advantage of ASTs over other program representations such as strings is that ASTs make access to the immediate sub-programs of a program easy, e.g. the program

```
if C then P else Q

```

has three immediate sub-programs namely C, P and Q. The AST for the program has three pointers to the sub-programs:

Both, code-generation and type-checking, involve the recursive invocation of code-generation/type-checker on the immediate sub-programs (plus some glue-code). Hence ASTs provide exactly the information needed for efficient type-checking and code generation.

The relationship between parse trees and ASTs is simple. The parse tree contains the exact information about how a string 'fits' into the CFG. Every production applied when consuming the input string is noted down in the order used. This information has a natural tree shape, whence the name "parse tree". An AST is a parse-tree with redundant information removed. An example of redundant information are properly balanced brackets. Another example is the node labelling that gives the aforementioned information about what productions were used to derive the string. Such information is important for checking if the input string (or more precisely token-list) is syntactically valid, but once that has been acertained, this information is no longer needed for compilation and hence discarded.

Let us look at an example. Consider the arithmetic expression $4 \*(3+17)$ in the obvious grammar of arithmetic expressions: $$ E \ \ \rightarrow\ \ E + E \ |\ E * E \ |\ ( E ) \ |\ 0 \ |\ 1 \ |\ 2 \ |\ ... $$ Let's ignore the ambiguity and left-recursion in that grammar. Here is a plausible parse tree for $4 \*(3+17)$

(Note that the parse tree is usually not constructed explicitly, but is implicity in the structure of the recursion throughout the parsing process.) The corresponding AST is simpler, but still contains all relevant information, including precedence of the addition over the multiplication, in its pointer structure:

**Summary:** compilers construct ASTs (good representation of the program for future compiler stages) from parse trees (which tell "how" the program is in the CFG).
> 7 votes

# Answer
The parse tree will also give the meaning of the program. For example $7 + 5 * 3$ will be mapped to $7 + (5 * 3)$ because of precedence rules, and in complicated nested `if-then-else` statements it will be determined which `else` maps to which `then`.
> 1 votes

# Answer
Note that a context-free grammar can be ambiguous. Context-free does not mean "unambiguous".

Therefore, when the CFG gives us a yes-or-no answer, it is possible that the given string of symbols is in the language in more than one way: two or more different parses are possible using the same CFG, both of which confirm that the string is valid syntax.

To know which parse was used, we need the abstract syntax tree. (Or some other object, such as information representing the detailed trace of the parsing steps.)

Of course, we need the syntax tree for other purposes also, but the first thing that it gives us is how the syntax was interpreted: how the symbols group together and subordinate. If the string was `A + B * C`, the parse tree tell us whether the interpretation was `(A + B) * C` or `A + (B * C)`.

Before we can interpret meaning, we must interpret syntax. (However, we don't have to interpret all the syntax before interpreting any of the meaning. Compilers do some interpretation of meaning on what was already parsed, which guides the parsing decisions for what is yet to come.)

---

Note that *parse tree* and *abstract syntax tree* are two related but different ideas. A parse tree is concerned with the raw syntax, and so it includes punctuation tokens. Parse trees are relatively uninteresting in compilers for programming languages; it is not useful for a compiler's parser to output a parse tree, other than for debugging the low level actions of the parser: is it doing the right things with semicolons, commas, parentheses, and such. What we want is an abstract syntax tree. (In fact, some of the syntax will even disappear before tokenization: for instance, comments may disappear, and serve only to divide two tokens, like `a/*...*/b` in the C language, producing two tokens. So parse trees, chock full of irrelevant details though they be, do not have **all** the irrelevant details.)

The abstract syntax tree identifies the meaningful symbols in the utterance and their relation to each other: which feature of the sentence is the major constitutent, and which are its subordinates. For instance, the abstract syntax tree of `A * (B + C)` will tell us that this is a multiplicative expression: the root node is the `*` operator, and its children are `A`, which is a leaf-node, and `(B + C)` which is subtree consisting of the `+` node and the children `B` and `C`. The semantic actions in the parser know which parts of a phrase carry meaning and which are just punctuation marks; they pull out the meaningful pieces out of the syntax to build the tree.

In an abstract syntax tree, furthermore, what used to be raw tokens in the syntax may be replaced by richly typed objects. In a given language, a token whose lexeme looks like `123` may become an integer object in the tree; a token which looks like `abc` may turn into a symbol object, and `"xyz"` into a string and so forth.
> 0 votes

# Answer
In the abstract world, any derivation of a context-free grammar corresponds to a derivation tree; this is what compiler people call parse or syntax tree. These trees capture the *structure* of the word in some sense.

However, a compiler does not *have* to utilise it. Compiler generators like yacc allow you to specify actions that are execute upon reduction; the parse tree remains implicit.

However, we often tie *semantics* to the structure of words. For programming languages, this seems obvious: arithmetic expressions *are* for all intents and purposes trees, variable visibility and scopes are organised along tree structures, and so on. It can therefore be useful to make syntax trees explicit in a reduced form, that is as abstract syntax trees.

Once you have such a tree, static analysis, optimisations and, finally, code generation are easy to express -- because our semantics fit exactly. Attribute grammars can be used here.

A tool that focuses on AST rewriting is Antlr; here you can even specify tree grammars for AST manipulation.
> 0 votes

---
Tags: context-free, compilers, parsers
---


# Question
Title: Understanding the basic concepts in memory organisation
(Before actually proceeding to the question, I want to confess that this is a homework question, please do consider it and help me in improving my understanding a bit more.)

I have recently started learning computer organisation and architecture. I have gained fair understanding for how caches are organised, how mapping between cache and main memory takes place (direct , fully and set-associative mapping), what is a page table(what are pages, blocks etc.), i can that say I have basic knowledge of segmentation , paging, virtual address and physical addresses.( at the basic level ofcourse).

Well I have come across this question:

> A computer has 46-bit virtual address ,32- bit physical address, and a three level page table organisation. The page table base-register stores the base address of the first level table(t1), which occupies exactly one page.Each entry of t1 stores the base address of the page of second level table t2. Each entry of t2 stores the base address of the page of the third level table t3. Each entry of t3 stores a page table entry (PTE). The PTE is 32 bit in size. The processor used in the computer has a 1MB 16-way set associative virtually indexed physically tagged cache. The cache block size is 64 Bytes.

First of all I am facing difficulty in just imagining such type of a virtual computer. can any one help me by giving a simple steps on How to realize such a virtual computer on paper, or just how to understand what is given in the question. What is really asked? How would one represent a computer having a 46-bit virtual address and having three level page table?

> What is virtually indexed and physically tagged cache?

After reading what is given above, I feel that I just know the terms but I am unable to relate them together to solve problems. I will be glad If someone tries to explain how my thought process should be understand and apply these concepts practically to solve such types of problems.

Some questions based on the above paragraph:

1. What is the size of a page in KB in this computer?
2. What is the minimum number of page colours needed to guarantee that no
two synonyms map to different sets in the processor cache of this computer?

A good resource where such problems are actually taught to solve will a appreciated. Good articles and views are most welcome.

# Answer
> 2 votes
One can derive the page size from knowing that the page table has three levels, the virtual address space is 46 bits (assume byte addressing), and a PTE is 4 bytes. P bits (where P = log2(page\_size)) of the virtual address are not involved in the translation (these provide the offset within the page), so the three levels must translate a 46-P bit address value.

Each node of the page table contains page\_size/PTE\_size entries, and so each node covers log2(page\_size/PTE\_size) bits, which is P-2 bits. The page size can then be derived since 46 = (P-2)\*3 + P.

(In a simple hierarchical page table, the first level is a single page \[in the given design providing 2(P-2) entries\]. Each valid entry points to a page-sized table at the second level. Likewise each valid entry in the second level points to a page-sized table in the third level. Each valid entry in the third level provides a page translation. If all the first and second level entries were valid, there would be 2(P-2) * 2(P-2) third level tables each with 2(P-2) entries. Thus 2(P-2)\*3 entries would be available, each covering 2P (page\_size) bytes.)

With respect to page coloring, one must determine the number of bits that are not part of the page offset which are used for indexing the cache. The number of sets is equal to cache\_size/block\_size/associativity, so to index to a specific set requires log2(cache\_size/block\_size/associativity) bits. The offset within the block uses log2(block\_size) bits. Using C= log2(cache\_size), B= log2(block\_size), and A=log2(associativity), C-B-A bits are used to index the set and C-B-A+B, i.e. C-A, bits are used to address the given byte.

Since only P bits are provided as part of the page offset, C-A-P bits use *virtual address* bits. In order to avoid the problem of two different virtual addresses with the same physical address mapping to different sets, the virtual addresses of any physical pages that are so shared can be colored, i.e., share the same value for the C-A-P virtual address bits. (This forces them to map to the same set. With tagging based on physical addresses, this is sufficient to avoid aliasing issues like a write to one virtual address not updating a cached entry at the same physical address but a different virtual address.)

Each index group is called a color, so to provide C-A-P virtual address bits requires 2(C-A-P) colors.

(The above assumes an "ordinary" cache. Indexing not using simple modulo 2N, e.g., skewed associativity, would have different coloring requirements; but such complexities are typically ignored for problems like this.)

---
Tags: memory-management, cpu-cache, virtual-memory
---


# Question
Title: FFT-less $O(n\log n)$ algorithm for pairwise sums
Suppose we are given $n$ distinct integers $a\_1, a\_2, \dots, a\_n$, such that $0 \le a\_i \le kn$ for some constant $k \gt 0$, and for all $i$.

We are interested in finding the counts of all the possible pairwise sums $S\_{ij} = a\_i + a\_j$. ($i = j$ is allowed).

One algorithm is to construct the polynomial $P(x) = \sum\_{j=1}^{n} x^{a\_j}$ of degree $\le kn$, and compute its square using the Fourier transform method and read off the powers with their coefficients in the resulting polynomial. This is an $O(n \log n)$ time algorithm.

I have two questions:

* Is there an $O(n \log n)$ algorithm which does not use FFT?
* Are better algorithms known (i.e $o(n \log n)$)? (FFT allowed).

# Answer
It would seem that this problem is equivalent to integer/polynomial squaring:

**1.** **It is known that polynomial multiplication is equivalent to integer multiplication**.

**2.** Obviously, you already reduced the problem to polynomial/integer squaring; **therefore this problem is at most as hard as squaring.**

Now I will reduce integer squaring to this problem:

Suppose you had an algorithm:

$$ F(\mathbf{\vec a})\rightarrow P^2(x),\\ \text{where } P(x)=\sum\_{a\_i \in \mathbf{\vec a}} x^{a\_i} $$

This algorithm is essentially the algorithm you request in your question. Thus, if I had a magic algorithm that can do this, I can make a function, ${\rm S{\small QUARE}}\left(y\right)$ that will square the integer $y$ (**oh yes, I do love mathjax :P**):

$$ \begin{array}{rlr}\hline &\mathbf{\text{Algorithm 1}} \text{ Squaring}&\hspace{2em}&\\ \hline {\tiny 1.:}&\mathbf {\text{procedure }} {\rm S{\small QUARE}}\left(y\right):\\ {\tiny 2.:}&\hspace{2em}\mathbf {\vec a} \leftarrow () &&\triangleright~\mathbf {\vec a}\text{ starts as empty polynomial sequence}\\ {\tiny 3.:}&\hspace{2em}i \leftarrow 0\\ {\tiny 4.:}&\hspace{2em}\mathbf{while}~y\ne0~\mathbf{do} &&\triangleright~\text{break }y\text{ down into a polynomial of base }2\\ {\tiny 5.:}&\hspace{4em}\mathbf{if}~y~\\&~1~\mathbf{then} &&\triangleright~\text{if lsb of }y\text{ is set}\\ {\tiny 6.:}&\hspace{6em}\mathbf{\vec a} \leftarrow \mathbf{\vec a}i &&\triangleright~\text{append }i\text{ to }\mathbf{\vec a}~\text{(appending }x^i\text{)}\\ {\tiny 7.:}&\hspace{4em}\mathbf{end~if}\\ {\tiny 8.:}&\hspace{4em}i \leftarrow i + 1\\ {\tiny 9.:}&\hspace{4em}y \leftarrow y \gg 1 &&\triangleright~\text{shift }y\text{ right by one}\\ {\tiny 10.:}&\hspace{2em}\mathbf{end~while}\\ {\tiny 11.:}&\hspace{2em}P^2(x) \leftarrow F\left(\mathbf{\vec a}\right) &&\triangleright~\text{obtain the squared polynomial via } F\left(\mathbf{\vec a}\right)\\ {\tiny 12.:}&\hspace{2em}\mathbf{return}~P^2(2) &&\triangleright~\text{simply sum up the polynomial}\\ {\tiny 13.:}&\mathbf {\text{end procedure}}\\ \hline &\end{array} $$

Python (test with codepad):

```
#https://cs.stackexchange.com/q/11418/2755

def F(a):
    n = len(a)
    for i in range(n):
        assert a[i] >= 0

    # (r) => coefficient
    # coefficient \cdot x^{r}
    S = {}
    for ai in a:
        for aj in a:
            r = ai + aj

            if r not in S:
                S[r] = 0

            S[r] += 1

    return list(S.items())

def SQUARE(x):
    x = int(x)

    a = []
    i = 0
    while x != 0:
        if x & 1 == 1:
            a += [i]
        x >>= 1
        i += 1

    print 'a:',a
    P2 = F(a)

    print 'P^2:',P2

    s = 0
    for e,c in P2:
        s += (1 << e)*c
    return s

```

**3.** **Thus, squaring is at most as hard as this problem.**

**4.** **Therefore, integer squaring is equivalent to this problem.** (they are each at most as hard as each-other, due to (**2**,**3**,**1**))

Now it is unknown if integer/polynomial multiplication admits bounds better than $\mathcal O(n\log n)$; in fact the best multiplication algorithms currently all use FFT and have run-times like $\mathcal O(n \log n \log \log n)$ (Schönhage-Strassen algorithm) and $\mathcal O\left(n \log n\\,2^{\mathcal O(\log^\* n)}\right)$ (Fürer's algorithm). Arnold Schönhage and Volker Strassen conjectured a lower bound of $\Omega\left(n \log n\right)$, and so far this seems to be holding.

This doesn't mean your use of FFT is quicker; $\mathcal O\left(n\log n\right)$ for FFT is the number of operations (I think), not the bit complexity; hence it ignores some factors of smaller multiplications; when used recursively, it would become closer to the FFT multiplication algorithms listed above (see Where is the mistake in this apparently-O(n lg n) multiplication algorithm?).

**5.** Now, your problem is not exactly multiplication, it is squaring. **So is squaring easier? Well, it is an open problem (no for now)**: squaring is not known to have a faster algorithm than multiplication. If you could find a better algorithm for your problem than using multiplication; then this would likely be a breakthrough.

So as of now, the answer to both your questions is: **no**, as of now, all the ~$\mathcal O(n\log n)$ multiplication algorithms use FFT; and as of now squaring is as hard as multiplication. And **no**, unless a faster algorithm for squaring is found, or multiplication breaks the $\mathcal O(n\log n)$ barrier, your problem cannot be solved faster than $\mathcal O(n \log n)$; in fact, it cannot currently be solved in $\mathcal O(n\log n)$ either, as the best multiplication algorithm only approaches that complexity.
> 10 votes

---
Tags: algorithms, time-complexity, fourier-transform
---


# Question
Title: Determining whether a context-free language (CFL) described by a given grammar is regular (RL)
In my homework we're given the following problem: Determine whether the context-free language described by the following grammar is regular, showing all the reasoning steps:

S -\> T T | U

T -\> 0 T | T 0 | #

U -\> 0 U 0 0 | #.

My teacher says the pound sign (#) is just a delimiter that is in the alphabet and not epsilon.

I understand the order of operations here is to go from CFG --\> CFL --\> RL (if possible).
My problem is that I don't know how to provide a CFL given a CFG, and further, determine whether a CFL is regular.

So to ask the questions:

how do you provide a context-free language (CFL) given a context-free grammar (CFG)?

how do you determine if a context-free language (CFL) is also a regular language (RL)?

# Answer
$$\begin{align}L(T) &= \\{0^\*\\#0^\*\\} \\ L(U) &= \\{0^n\\#0^{2n}\\} \\ L(S) &= L(T) \circ L(T) \cup L(U) \end{align}$$ Where $\circ$ is concatenation. Clearly, $L(U)$ is not regular. What does that say about $L(S)$? How does $L(T)$ affect this?
> 0 votes

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


# Question
Title: Range majority queries - most freqent element in range
Given N numbers and M range queries (starting and ending points), I need to compute majority (most frequent element, if it exists) in these ranges.

I'm looking for an algorithm that would answer queries in logarithmic or even constant time.

# Answer
> 3 votes
If the $N$ items are in ascending sorted order and stored into an array, you can determine a majority candidate in $O(1)$ time for a specified range by returning the item whose index is the range median. Therefore, this will require $O(M)$ time in the worst case for $M$ range queries. Note that the item returned in each query is a *candidate*: you need to *verify* if the item actually is a majority element in the range. And, verification is linear in the number of items in the range.

EDIT: explained tradeoff between space and time

If the items are not in sorted order, than finding a candidate element requires in the worst case time linear in the number of items in the range, using the Boyer-Moore algorithm and constant space (one counter). You can not determine a candidate element in time logarithmic in the number of items in the range while using constant space. However, if you trade space for time, you can determine a majority element in $O(1)$ time at the cost of using linear space.

---
Tags: algorithms, search-algorithms
---


title: Constructing Context Free Grammar

text:
# Question
Title: Constructing Context Free Grammar
I am stuck and having a hard time with this question. I want to construct a CFG for the language $$L = \\{{a^lb^mc^n | l,m\in N, n=|l-m|\\}}$$ I know that the language consists of strings where:
1. number of a's = number of b's, so c=0
2. number of a's more than number of b's, c=l-m
3. number of a's less than number of b's, c=-(l-m)
I started with $$S-\>ab$$ $$S-\>aSb$$ This generates all of case one, where number of a's = number of b's and c=0. I know that I could increment a's and c's by having aSc but I cant put that in the second line because it could generate a(aSc)b which is not in the language.

# Answer
> 1 votes
Hint: try to do each language separately, and then your final grammar is S-\>S1|S2|S3.

To do your case 2, you can write

$S-\>aSc|X$

$X-\>aXb|\epsilon$.

I.e. you start by generating the c's and the exceeding a's, and then you generate the b's and the remaining a.

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


# Question
Title: Proof that recursive languages are closed under concatenation
I can't figure out a proof that recursive languages are closed under concatenation. I know this is easy for most of the people but unfortunately my professor is not very good at explaining the material. If anybody can provide any hints on how to do it I would greatly appreciate it.

# Answer
Imagine you have an algorithm $A$ that decides $L\_A$ and an algorithm $B$ that accpts $L\_B$. How would you write a program that checks whether any given word $w$ can we written as $w=uv$ with $u \in L\_A$ and $v \in L\_B$?

> Broad hint: how many possible choices for $u$ and $v$ are there?
> 3 votes

---
Tags: formal-languages, computability, closure-properties
---


# Question
Title: Find a continuous path filling whole 3xN grid going through certain points in given order
I've got a grid consisting of squares that is 3 squares high and N squares long. Some of the squares are filled with numbers that are not greater than 3\*N. You can move only to squares that are below, above, on right, or left from you. When you move on a square, you fill that square with a number of the amount of moves you have already taken + 1. If square is already filled with a number, you can move onto it, only if the sum steps you've have taken + 1 is equal to the number on the square.

I need to find a continous path that leads through all the squares of the grid only once and output the same grid filled with numbers corresponding to the steps of your path. In other words, a path was previously laid out on the grid and then some numbers have been erased from squares. Now I have to retrace that path.

I should be done in O(N^2), but I will be thankful for any solutions.

# Answer
Hint: if this is a homework problem that comes up in a chapter on graphs, you might want to consider forming a graph.

A common pattern in applications of graphs is to let each node in the graph represent the "state" of the world at some point in time, and then use that graph somehow.

Suppose you're following some continuous path through this grid, and at some point in time in the middle of your traversal, I yell "freeze!", temporarily pause time, and look at the state of the world at that point in time (ignoring past or future). What information do I need to record, to fully describe the state of the world (where you are) at that point in time? How many different possible states are there? Now create a graph where ..., and..... (you fill in the rest)
> 0 votes

---
Tags: algorithms, eulerian-paths, square-grid
---


title: Is MIN or MAX-True-2-XOR-SAT NP-hard?

text:
# Question
Title: Is MIN or MAX-True-2-XOR-SAT NP-hard?
**Is there a proof or reference that $\left\\{\text{MAX},\text{MIN}\right\\}\text{-True-2-XOR-SAT}$ is $NP$-hard, or that it (the decision version) is in $P$?**

Let:

$$\Phi\left(\mathbf x\right)={\huge\wedge}\_{i}^{n}C\_i,\\ \forall\_{C\_i} \left.C\_i=(p \oplus q)\right|\_{\left(p\in \mathbf x \vee\neg p\in\mathbf x\right),\left(q\in \mathbf x \vee\neg q\in\mathbf x\right)} $$

The $\text{2-XOR-SAT}$ problem is to find a satisfying assignment of $\mathbf x$ that would make $\Phi\left(\mathbf x\right)=T$. This is in $P$, as it can be encoded in a set of linear equations mod $2$.

The $\left\\{\text{MAX},\text{MIN}\right\\}\text{-True-2-XOR-SAT}$ problems are to maximize or minimize the number of true values in $\mathbf x$, respectively, subject to the constraint that $\Phi\left(\mathbf x\right)=T$.

# Answer
> 6 votes
1. Build an implication graph, in the style of solving $\text{2-SAT}$: each literal gets a $x\_i$ node and a $\neg x\_i$ node. Each clause is turned into implications, each implication gives a directed edge from the antecedent-node to the consequence-node.
2. Collect all the connected components of this graph.
3. Each connected component will have only $2$ states: since each relationship is of the forms $x\_i=x\_j$ or $x\_i \ne x\_j$; this means if you assign even a single variable, the entire component will be force-assigned. This means you only have $2$ choices for each component.
4. For each connected component, greedily choose the assignment state that will increase (for $\text{MAX}$; decrease for $\text{MIN}$) the truth values in $\mathbf x$.

---
Tags: complexity-theory, np-hard, satisfiability
---


title: Computing with the Monster

text:
# Question
Title: Computing with the Monster
The Monster **M** is the largest of the finite sporadic groups that arises in the classification of finite, simple groups in mathematics.

**M** can be realized as a (very large!) set of `196882 X 196882` matrices with nothing more than entries of 1's and 0's, so long as we compute arithmetic as follows:

`1+1=0` `1+0=1+0=1` `1*1=1` `0*0=0` `1*0=0*1=0`

I have two simple questions for the reader. What is the minimum amount of bytes needed to store a single matrix? What is the computational cost (i.e., in FLOPS) of a single matrix multiplication in the most efficient implementation (i.e., taking into account that the entries are binary, not taking into account mathematical properties about the Monster)?

*This is a question purely at the computational side of the problem. In other words, treat the matrices as general `196882 x 196882` matrices with binary entries. This is not a question about the Monster. That was just added as motivation.*

# Answer
If you are storing a matrix of 0's and 1's, you could consider using a bitvector for storage. This can pack some fixed number of bits (say, 32 bits or 64 bits) into a single integer, which decreases the required storage by a very large factor. In your case, your matrices need a total of 38,762,521,924 entries, so you'll need at least 4,845,315,241 bytes, or about 4GB, of storage per matrix. Since the Monster group has size about 8 × 1053, though, I seriously doubt you can fit everything into memory.

Another note: the arithmetic you're describing happens to have the plus operator defined as binary XOR and the multiplication operator defined as bitwise AND. Therefore, you could, in a language like C or C++, use the `^` operator to denote addition and the `&` operator to denote multiplication.

Finally, the complexity of multiplication depends on the matrix multiplication implementation. The naive method takes time O(n3), where n is the dimension of the matrix, but since the matrices are large you could probably use either the Strassen algorithm (time complexity about O(n2.8)) or Coppersmith-Winograd, the latter of which requires about O(n2.37) multiplications. You'd probably have to empirically profile these algorithms to see which is best, since the constant factors hidden here are pretty huge.

Hope this helps!
> 7 votes

# Answer
The problem amounts to compute the product of two matrices over the finite field $F\_2$. This question is discussed in details in the paper Computational linear algebra over finite fields which also contains an extensive bibliography.
> 3 votes

# Answer
This question doesn't seem to have much to do with the structure of the Monster group, but just asks what is the complexity of matrix multiplication. There's a lot written on the complexity of matrix multiplication -- I suggest you do a search. The naive algorithm is $O(n^3)$ (here $n=196882$), but there are other algorithms. Also, if the matrix is sparse, it is possible to do much better.

P.S. The number of bytes to store the matrix in the straightforward way is obvious: $196882^2/8$.
> 2 votes

# Answer
as DW answers, algorithms for fast matrix multiplication are highly relevant. however, after edits on the question, it appears that floating point arithmetic is not required to solve the problem, the solution must be integer valued. although possibly "bigNums" (arbitrary precision integers) are required.

here is a survey on Computational linear algebra over finite fields by Dumas/Pernet that is apparently relevant/closely related. there are also papers/research on eg matrix multiplcation over finite fields.

see also Computing in the monster by Norton.

> We discuss the feasibility of a general technique for computing in the Fischer–Griess Monster, and provide information on some of its subgroups which illustrates the use of computational techniques in solving a particular problem in this group.
> 2 votes

# Answer
Here is an article, also titled "Computing in the Monster" (pdf) by R. A. Wilson (different than the one by Norton cited in vzn's answer). There is also a follow-up article, "New Computations in the Monster" (pdf). In these papers, the author demonstrates algebraic constructions that allow for explicit computations in the Monster group.

Here's a neat snippet from the first paper (emphasis mine):

> The smallest matrix representations of the Monster have dimension 196882 in characteristics 2 and 3, and dimension 196883 in all other characteristics. **Thus the smallest matrices which we could conceivably use to generate the Monster would require around 5GB of storage each, and on modern workstations with the best available algorithms it would take several weeks of processor time to multiply two such matrices**.
>
> Despite these obvious difficulties, I decided some years ago to attempt an explicit construction of these matrices, with no hope of ever being able to use them for any serious calculation. With the collaboration of Richard Parker, Peter Walsh and Steve Linton, this project was eventually successful. **The generating matrices were stored in a compact way, so that all the information and special programs needed would fit onto a single 1.44MB floppy disk.**

Clever math, FTW.
> 2 votes

# Answer
To represent most $n\times n$ 0-1 matrices requires $n^2$ bits: this is a simple fact of Kolmogorov complexity. So, without using special properties of the monster group's elements, you're not going to get a more efficient representation than the naive one.
> 1 votes

---
Tags: algorithms, data-structures
---


title: Shor's Algorithm speed

text:
# Question
Title: Shor's Algorithm speed
I'm a fledgling computer science scholar, and I'm being asked to write a paper which involves integer factorization. As a result, I'm having to look into Shor's algorithm on quantum computers.

For the other algorithms, I was able to find specific equations to calculate the number of instructions of the algorithm for a given input size (from which I could calculate the time required to calculate on a machine with a given speed). However, for Shor's algorithm, the most I can find is its complexity: `O( (log N)^3 )`.

Is there either some way I can find its speed/actual complexity from its Big-O Notation? If not, is there someone who can tell me what I want, or how to find it?

# Answer
> 30 votes
The best estimate I know of can be found in Efficient networks for quantum factoring, by David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill, which gives $72 (\log N)^3$.

Having said that, a straight comparison of number of steps on a quantum computer versus number of steps on a classical computer is problematic for various reasons. First, as D.W.'s answer says, the number of steps depends on the exact architecture of the quantum computer, which we won't have until one is built. Second, the time required for a single step on a quantum computer is likely to be quite a bit slower than a single step on a classical computer.1 Again, we won't know how much slower until quantum computers exist.

1 If it was faster, you could use the same architecture to build a classical computer that would be at least as fast, and probably faster because for a classical computer, you don't need to worry about maintaining quantum coherence.

# Answer
> 3 votes
What you are asking for does not exist, for good reasons.

Today there is no existing computer that can execute Shor's algorithm. To run Shor's algorithm, you need a quantum computer, which doesn't exist yet. Therefore, you shouldn't expect precise estimates of its speed or running time, as that will depend upon the details of the computer that the algorithm is run on -- and we can't possibly know those details until we've successfully built one.

---
Tags: time-complexity, quantum-computing, factoring
---


# Question
Title: Symmetric TSP optimization by removing nodes
Please tell me if my next optimization can work:

I have symmetric, weighted, undirected graph, where it is knowen that the optimal tour, that visit all the vertices exactly once and return to the starting vertex, only contains edges with the weight of 1, it is also known that there is no edge with weight less than 1.

My goal is to find that tour.

Within this graph I want to look in to the case where there's a node, $B$ with only two edges with weight of 1 connected to it, let's call them, $AB$ and $BC$. I know that $AB,BC$ must be part of the optimal tour because there is no other way to get to $B$ and from $B$ with weight of 1. So I am removing the node $B$ and adding extra edge $AC$ between the endpoints of the removed node, and I am giving it the weight 0. Now when I find the optimal tour of that new graph(I assume that $AC$ will be part of it), I will replace it back to $AB,BC$, and I believe it will be the optimal tour of my original graph.

Do you think it will work?

# Answer
Since your TSP tour needs to visit all nodes but not all edges, replacing nodes by edges is dangerous, even in the case of degree 2 nodes. You can of course replace a node by a clique on its neighbors, but you need to add a mechanism that ensures that at least one of the edges of the clique is taken.
> 1 votes

---
Tags: algorithms, graphs, traveling-salesman
---


# Question
Title: Is the class of non-regular languages closed against Kleene star?
How to prove that if a language A is not regular then A\* isn't regular either?

I have tried the usual methods with no result.

# Answer
Hint: Suppose $L$ is any language over the alphabet $\Sigma$. If $L$ is not regular then so is $L+\Sigma$, yet $(L+\Sigma)^\* = \Sigma^\*$ is regular.
> 1 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Construct a deterministic finite automation
The question asks to:

> construct a DFA which accepts exactly $\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2}+1$ many members of $\\{0, 1\\}^n$ for every n.

I have no idea where to start to constructing the DFA, could you give some directions? By the way, how many states should this DFA have?

# Answer
Hint: Here is a regular language which "accepts" exactly $n$ members of $\\{0,1\\}^n$ for every $n$: $0^\* 1 0^\*$. For example, for $n=4$ we have the strings $0001,0010,0100,1000$. The minimal DFA for this language contains three states.
> 1 votes

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


# Question
Title: How to fool the plot inspection heuristic?
Over here, Dave Clarke proposed that in order to compare asymptotic growth you should plot the functions at hand. As a theoretically inclined computer scientist, I call(ed) this vodoo as a plot is never proof. On second thought, I have to agree that this is a very useful approach that is even sometimes underused; a plot is an efficient way to get first ideas, and sometimes that is all you need.

When teaching TCS, there is always the student who asks: "What do I need formal proof for if I can just do X which always works?" It is up to his teacher(s) to point out and illustrate the fallacy. There is a brilliant set of examples of apparent patterns that eventually fail over at math.SE, but those are fairly mathematical scenarios.

So, how do you fool the plot inspection heuristic? There are some cases where differences are hard to tell appart, e.g.

\[source\]

Make a guess, and then check the source for the real functions. But those are not as spectacular as I would hope for, in particular because the real relations are easy to spot from the functions alone, even for a beginner.

Are there examples of (relative) asymptotic growth where the truth is not obvious from the function definiton and plot inspection for reasonably large $n$ gives you a completely wrong idea? Mathematical functions and real data sets (e.g. runtime of a specific algorithm) are both welcome; please refrain from piecewise defined functions, though.

# Answer
Speaking from experience, when trying to figure out the growth rate for some observed function (say, Markov chain mixing time or algorithm running time), it is very difficult to tell factors of $(\log n)^a$ from $n^b$. For example, $O(\sqrt{n} \log n)$ looks a lot like $O(n^{0.6})$:

\[source\]

For example, in "Some unexpected expected behavior results for bin packing" by Bentley et al., the growth rate of empty space for the Best Fit and First Fit bin packing algorithms when packing items uniform on $\[0,1\]$ was estimated empirically as $n^{0.6}$ and $n^{0.7}$, respectively. The correct expressions are $n^{1/2}\log^{3/4}n$ and $n^{2/3}$.
> 23 votes

# Answer
Here is another (admittedly rather constructed) example, but still one I find remarkable. It is intended to show that plots can be very misleading for judging asymptotic growth.

The following plots show two functions $f$ and $g$ — disclosed below ;) — in different ranges. Remarkably, both functions are monotonically (strictly) increasing, (infinitely often) continuous differentiable and convex, so they are “nice” in many respects.

*Can you guess which of the functions grows (asymptotically) faster?*

The answer: $f\sim g$, i.e. the functions are *asymptotically equivalent*. The functions are $$f(x) = x^2$$ $$ g(x) = \iint \sin(\log(x))+1 \\;dx\\,dx = x^2\Bigl(1 - \tfrac{3}{5} \cos(\log(x)) \+ \tfrac{1}{5} \sin(\log(x)) \Bigr)\\;. $$

So $g$ is essentially $x^2$, i.e. the same as $f$, but its second derivative is not uniformly $2$, but oscillates between $0$ and $4$ with exponentially growing period. This oscillation is not visible in ordinary plots.

For *this* example, we can demask the oscillations by considering a log-log-plot:

Of course, this does not help, in general; for example, we might have a doubly exponential period ...
> 15 votes

# Answer
A nice example is Brzozowski's deeply magical minimal DFA algorithm. Given a finite automaton $N = (Q, S \subseteq Q, F \subseteq Q, R \subseteq Q \times \Sigma \times Q)$, we can compute a minimal deterministic finite automaton from it:

$$ \mathrm{Minimize} : \mathrm{NFA \to DFA} = \mathrm{Determinize\circ Reverse \circ Determinize \circ Reverse} $$

This is obviously a worst-case exponential time algorithm, since it can take a nondeterministic automaton and give you a deterministic one (or even more obviously, it calls the subset construction twice).

However, if you give Brzozowski's algorithm a **DFA** as an input, on many common kinds of input it can compete with and often outperform specialized DFA-minimization algorithms (which are typically $O(n^2)$, or $O(n \log(n))$ if you are hard-core and implement Hopcraft's algorithm).

This touches the "plot" part of the "plot inspection heuristic" --- we have to choose which points to sample when drawing the plot, and you can fool a naive plot if you don't choose your points carefully. This is also true for other examples, such as Quicksort and the Simplex algorith, but for pedagogy I prefer this algorithm to those two.

Quicksort's difference is "only" quadratic versus log-linear, which is less spectacular than a polynomial/exponential difference. The simplex algorithm does have a similarly spectacular difference, but it's analysis is considerably more complicated than Brzozowski's algorithm.

(Also, I feel that Brzozowski's DFA minimization algorithm is much less well-known than it deserves to be, but of course that's a matter of taste.)
> 13 votes

# Answer
The mathematical technique of curve fitting can be used to provide an infinite number of answers to your question. Given a curve and a range, one can readily find a polynomial that fits the curve to any degree of accuracy. This example from wikipedia shows how a sin wave can be fairly accurately fitted with a forth order polynomial (the blue curve).

I could use higher order polynomials, and fool the plot inspection heuristic even better than this graph does.
> 8 votes

---
Tags: asymptotics, didactics
---


# Question
Title: Data structure for finding the sum of edge weights on a path
Let $T$ be a tree, and there is a weight function on the edges $w:E\to X$. $(X,\oplus)$ is a monoid structure.

Define $f(u,v) = \bigoplus\_{i=1}^k w(e\_i)$, where $e\_1,\ldots,e\_k$ is the unique path from $u$ to $v$.

Can we preprocess the tree, such that we can use linear space (or close to linear space), so we can answer queries $f(u,v)$ in $O(\mathrm{polylog} (n))$ monoid operations? The problem become more interesting if we allow removing edges and add edge between two vertices in distinct trees.

We can also ask the question on a DAG, with weights from a commutative monoid. We want to preprocess in linear time, and query the result of $f(u,v)= \sum\_{e} w(e)$, where $e$ is in some path from $u$ to $v$, in $O(\mathrm{polylog} (n))$ time.

If we consider the very special case where the entire graph is just a path, then what we want is a dynamic version of a Fenwick tree. A finger tree can solve the problem in $O(\log n)$ time.

# Answer
**Static case.** Suppose the tree is static. Let $d$ denote the average depth of the nodes of the tree, taken over all nodes. Then you can solve this problem with $O(nd)$ preprocessing, a data structure of size $O(nd)$, and query time of $O(1)$. As a consequence, if the tree is balanced or of height $O(\lg n)$, the preprocessing and data structure size are $O(n \lg n)$ and the query time is $O(1)$.

Here's how. My solution is inspired by Yuval's, but takes into account that we do not have an inverse. Basically, you just build a map that stores mappings $(u,v) \mapsto f(u,v)$, where $u,v$ range over all pairs of tree nodes such that $u$ is an ancestor of $v$. This has $O(nd)$ entries and can be computed in $O(nd)$ time during preprocessing. Also, precompute a data structure to help you solve the least common ancestor problem. Now, to compute $f(u,v)$ where $u,v$ are an arbitrary pair of nodes (not necessarily an ancestor of the other), find their least common ancestor $p$ and compute $f(u,v) = f(p,u) + f(p,v)$ (with the convention that $f(v,v)=0$ for all $v$). Thus, queries can be solved in $O(1)$ time, using a sufficiently good algorithm for LCA.

---

It's also possible to get slightly better efficiency for the above scenario. Instead of storing all mappings $(u,v) \mapsto f(u,v)$ where $u$ is an ancestor of $v$, we'll store just a subset of them.

Let $r$ denote the root. Focusing on a single leaf $\ell$, we have a path from $r$ to $\ell$; if the leaf is at depth $d$, this path has length $d$. So, we can build a balanced binary tree $T\_\ell$ (akin to a Fenwick tree) over this path, where each node of $T\_\ell$ corresponds to a mapping $(u,v) \mapsto f(u,v)$ (where $u$ is an ancestor of $v$ in the original tree $T$). The root of $T\_\ell$ is the mapping $(r,\ell) \mapsto f(r,\ell)$, corresponding to a path of length $d$. It has two children, $(r,m) \mapsto f(r,m)$ and $f(m,\ell) \mapsto f(m,\ell)$, corresponding to two paths of length about $d/2$ (here $m$ is a node halfway along the path from $r$ to $\ell$). Each leaf of $T\_\ell$ represents a single edge in the path from $r$ to $\ell$. In this way, we get a tree $T\_\ell$ of size $O(d)$, where $d$ is the depth of $\ell$ in the original tree $T$.

Now take the union of the $T\_\ell$, over all leaves $\ell$ of the original tree $T$ (sharing common nodes in these trees). This gives us a map that stores mappings $(u,v) \mapsto f(u,v)$, but now with a smaller subset of entries in the mapping than before. Given any pair of nodes $p,v$ where $p$ is an ancestor of $v$, we can compute $f(p,v)$ in time $O(\lg d)$, where $d$ is the depth of $v$. Therefore, we can compute $f(u,v)$ for arbitrary $u,v$ in time $O(\lg d)$, where $d$ is the depth of the deeper of $u,v$.

With this "forest of trees" scheme, the time to answer a single query is slightly more, but the size of the data structure is slightly less. I don't know if this will be a win in practice, but it might be. This scheme also has the advantage that, if the weight on an edge of $T$ is updated, you can fairly efficiently update the data structure.

There might be a smarter way to choose what subset of entries $(u,v)\mapsto f(u,v)$ to store in your data structure -- I'm not sure.

---

It's possible to extend these to the case of a static DAG, if you are promised that the length of the longest path in the DAG is not too large (if it is short and bushy/wide rather than long and narrow).
> 5 votes

# Answer
On a tree you can reduce your problem to calculation of least common ancestor. For each node $v$, store the total weight $w(v)$ of the path from $v$ to the root; this can be calculated in linear time using DFS or BFS. Now given two nodes $u,v$, find the common ancestor $p$ and compute $f(u,v)=w(u)+w(v)-w(p)$.
> 2 votes

---
Tags: data-structures, graphs
---


# Question
Title: How can I prove that if $\chi(G) > k \wedge \vert\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}\vert$ then $G$ has a $k-regular$ induced subgraph?
I have found an interesting exercise in my introduction to graphs workbook:

Let $ad(G) = \frac{2\vert E(G)\vert}{\vert V(G) \vert}$ and $mad(G) = max\\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\\}$.

Given a graph $G$ and a number $k \geq 3$, prove that if $\chi(G) \> k \wedge mad(G) \leq k \Rightarrow \exists A \subseteq V(G)$ such that $\[A\]\_{G}$ is $k - regular$.

I believe this can proved by contradiction:

Given a $G$ and $k$ for which the properties hold, we assume that $G$ has no induced subgraph $H$ that is $k - regular$. We then prove that if $\nexists H$ then at least one of the property is false and thus we contradict ourselves however I can't quite figure out the connection between $H$ and the mentioned properties.

How would you go about solving this?

# Answer
Hint: It's better to prove that if $mad(G) \leq k$ and no induced subgraph of $G$ is $k$-regular then $\chi(G) \leq k$. Here is the idea of the proof:

1. Show that $G$ has a vertex $v$ of degree smaller than $k$.
2. Color $G - v$ using $k$ colors (by induction).
3. Complete this to a $k$-coloring of $G$.
> 3 votes

---
Tags: graphs
---


# Question
Title: Heuristics & Constrain Satisfaction Problem Differences
I'm currently taking an Algorithms course, and we are covering Backtracking, CSP, and heuristics. However, I'm getting confused on exactly the differences between these terms and their applications.

When using Backtracking on a problem, I understand we are calculating the set of all allowable solutions to satisfy some property. This uses the idea of some form of constraint to make sure we can reduce the problem and not have to calculate every possible permutation.

So is the Backtracking algorithm just an application of a CSP? But when I saw an example of solving a sudoku puzzle with the Backtracking algorithm, it took many more steps than a CSP description of it.

Also, how would the idea of using heuristics to solve a problem relate in with this?

There is a good chance I'm getting confused with some of the terminology so any advice would be greatly appreciated.

# Answer
CSP is a *problem*.

Backtracking is an *algorithm that searches for a solution*, basically, by trying every possibility, and backtracking as soon as it knows it is wrong. Thus it can be applied to many problems, by searching the solution space.

A heuristic algorithm is an algorithm that finds a solution using some trick to speed it up. Some heuristic algorithms might work well for particular types of problems, while remaining slow in the worst-case. Other heuristic algorithms might terminate quicker, but in the worst-case might not find a solution, or it can find an approximate solution.

From wikipedia:

> This is achieved by trading optimality, completeness, accuracy, or precision for speed.
> 2 votes

# Answer
Backtracking algorithm is a way to solve the CSP. While backtracking the algorithm may have to chose from several nodes, which will be the next one to expand. This is the point, where heuristic can be used.

Lets use the representation of the CSP as set of variables, each with its own domain of values. Here are two popular heuristics:

**Minimal Remaining Values** \- Chose the variable that has minimal remaining values it can take.

**Least Constraining Values** \- Chose a value of some variable that will be least constraining for all other variables

Using those generally(in "complex enough" CSP) will find a solution faster, because it chooses in optimal way the next node in the search tree to be expanded.

Here is a very helpful link ,that gives full description with examples.
> 1 votes

---
Tags: algorithms, heuristics
---