# Question
Title: How Dynamic programming can be used for Coin Change problem?
As far as I can unserstand Dynamic programming stands simply for memoization (which is a fancy name for lazy evaluation or plain "caching"). Now, I read that there is we can reduce complexity of coin-change problem by truncating some search branches with caching.

Here is the problem, by the way

```
(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

```

I prefer the Scala translation

```
  def countWithoutRepetitions(s: Int, dimes: List[Int]): Int = {
    if (s == 0) 1 else
       if (s < 0 || dimes.isEmpty) 0
        else dimes match {
          case d :: ds => {countWithoutRepetitions(s, ds) + countWithoutRepetitions(s-d, ds)}
        }
  }

```

Odersky also asks for cache-based trimming algorithm in his course (pdf for those who are not enrolled). Yet, I do not understand what do people discuss at all.

The search tree never repeats itslef. It never calls the function with the same (sum, available\_coins) arguments. What are you going to cache?

# Answer
Work an example. I worked through the Scheme version with the input `35` (and with the denominations of the coins as `1`, `5`, `10`, `25`, `50`) and I'm seeing a *ton* of repetition in the search tree. `(cc 5 1)` has already come up 3 times and I'm only about half way through.

Also, memoization actually does a little more than lazy evaluation. Lazy evaluation caches the thunk for the expression assigned to a particular dynamic instance of a variable so that the thunk gets evaluated at most once. But memoization caches all expression evaluations, so if the expression is assigned to different dynamic variable instances you'll also only get a single evaluation. This requires a bit more machinery (you have to hash the arguments of the expression, and store the argument/result pair in a hash table.) If you were to rewrite the function in a lazy functional language (like Haskell) you wouldn't automatically get memoization benefits in this case.
> 3 votes

# Answer
Gasarch recently wrote up solutions to this problem using recurrence relations which presumably could be readily turned into dynamic programming form & his paper can be mined for further refs.
> 0 votes

---
Tags: combinatorics, dynamic-programming, recursion, word-combinatorics
---


# Question
Title: Problem understanding DFA & NFA equivalence in Theory of Computation
Before asking this question,I had gone through Equivalence of NFA and DFA - proof by construction

but my question is a bit different from that. I was reading Michael Sipser's `Introduction to Theory of Computation` and I came to a problem. I couldn't understand as to how he is taking his act on `equivalence between NFA and DFA`.

I have problem understanding this para :-

> Next, we determine the start and accept states of D. The start state is E({1}), the set of states that are reachable from 1 by traveling along ε arrows, plus 1 itself. An ε arrow goes from 1 to 3, so E({1}) = {1, 3}. The new accept states are those containing N4’s accept state; thus {1}, {1,2}, {1,3}, {1,2,3}.

My assumption---\> As {2} is not in the list of accepted states,so {1,2} should not be considered as new accept state in equivalent DFA.Also,{1} and {1,2,3} and {1,3} stand out as new accept states as per me because traversing from 1 to reasonable nodes lets the final accept state be reached---here,{1},accept state---\>{1,3}---accept state as on inputting `a` from node 3 makes arrive at {1} which is an accept state,hence accpeted,and similarly for {1,2,3}.

So,point at my wrong thinking PLEASE. I have understood that while making transitions only those states are considered final states which are accept states in NFA.Am I wrong???So,how come {1,2} be the new accept state in the equivalent DFA?

Secondly, why he has mentioned that

> The start state is E({1}), the set of states that are reachable from 1 by traveling along ε arrows, plus 1 itself\`.

I couldn't derive a meaning out of this statement,the reason might be my poor understanding of English language(I am non-native English speaker).Means start state is E({1})---fine upto here. Now, the set of states that are reachable from 1 by travelling along ε arrows,plus 1 itself---It doesn't make any meaning standing as an independent sentence. Someone make me understand the meaning of this line,PLEASE!

Someone please make me understand and elaborate a bit. I feel that author might be wrong there,pardon my noobiness or for any mistake!

# Answer
> 4 votes
**Motivation**. In this construction, the intent is to make a DFA equivalent to a given NFA. In the original NFA, look at what happens when we're in state 2 and we see input $a$: we could either stay in state 2 or make a transition to state 3. If we want to eliminate nondeterminism, we could say that from state 2 looking at input $a$ we move to the single new state $\\{2,3\\}$, meaning that in this case, we're either in state 2 *or* state 3. In other words, in the constructed DFA we'll have the transition $\delta'(\\{2\\}, a)=\\{2, 3\\}$. The important thing to notice is that this transition in the new FA is deterministic: from the state $\\{2\\}$ on reading $a$ we move to the *single* state denoted by $\\{2, 3\\}$. Guided by this convention, we will build the DFA by defining the states to be all possible sets over 1, 2, 3, namely $$ \emptyset, \\{1\\}, \\{2\\},\\{3\\}, \\{1, 2\\}, \\{1, 3\\}, \\{2, 3\\}, \\{1, 2, 3\\} $$

**Final States**. Let's start with an example: what does the NFA do on input $baa$? We'll have, in order

1. In state 1, looking at $b$. Go to state 2.
2. In state 2, looking at $a$. Go to state 2 or state 3.
3. Looking at the last input, $a$ we could be in either state 2 or state 3. If we're in state 2, go to state 2 or state 3 as before. If we're in state 3, go to state 1.

In other words, at this stage, after having read $baa$ we could find ourself in states 2, 3, or 1.

In the DFA, we have, equivalently, the transitions $\delta'$ defined as

1. $\delta'(\\{1\\}, b) = \\{2\\}$.
2. $\delta'(\\{2\\},a) = \\{2, 3\\}$.
3. $\delta'(\\{2, 3\\}, a) = \delta'(\\{2\\},a)\cup\delta'(\\{3\\},a) = \\{2, 3\\}\cup\\{1\\}=\\{1, 2, 3\\}$.

Now the question is, should state $\\{1, 2, 3\\}$ be considered as a final state? Sure, since the NFA, reading $baa$ has at lest one possible collection of transitions that leads to the accepting state 1. In a similar way, any state of the DFA containing 1 will be a final state, so in the DFA there will be four final states: $$ \\{1\\}, \\{1, 2\\}, \\{1, 3\\}, \\{1, 2, 3\\} $$ Now it turns out that in the DFA the state $\\{1,2\\}$ is never used, but that doesn't negate the fact that it's a final state (since it contains 1). All it means is that there is no transition that takes you there. It's what we call an unreachable state. This, I hope, answers your first question.

**Start State**. This answer to your first question has little to do with the answer to your second question. The answer for your second question is: just as we did to determine the final states of $D$, we also need to know what the start state of $D$ is, and in this case it will be the set of states containing the start state of $N\_4$, along with any other states that can be reached from that start state via $\epsilon$-moves, namely $\\{1, 3\\}$ (which of course will also be a final state, though that's not important here).

# Answer
> 3 votes
Your question is unprecise. Yous state that you have a problem understanding some parts of the text, but without any further hint as to the nature of the problem.

You should be more specific about what is bothering you in this construction of the DFA $D$. For example, what do you think is wrong with the start state of $D$ being the set $\\{1,3\\}$. Is it the fact that it is a set of states, or the fact that it is this specific set of states $\\{1,3\\}$?

I suspect it may be the former, so I will try to answer that. I do not have Sipser's book, so that I cannot relate specifically to his presentation, other than with the page you give.

The major point in this is that state names do not matter. In the example, the names of the initial NFA $N\_4$ are the integers $1$, $2$ and $3$. Now, you might wonder whether it is actually the first three natural integers, or only the three characters that represent them (or even, possibly, three strings of one character each). The fact is that it is irrelevant, that it does not matter. All you really need to describe/define your automaton is to have 3 distinct states, and to be able to distinguish them in some way so that you can tell where you start, how you can pass from one to another on some input, and which is accepting.

As usual, when you talk about something, the best way is to identify it with a name, which should refer to it only in a given context. It can be "babou" right now if I am the something. It can be the character "3" or the string "III" if it is the third natural integer, though you can also call it "third natural interger" which people will understand, or it can be the name "Joe" if you have first given the notational definition:

```
      Let Joe be a name for the third natural integer.

```

or more accurately

```
      Let "Joe" be a name for the third natural integer.

```

Though the quotes are needed only in the definition, since the beginning of this definition is about the name, rather than what is being named, quotes are not to be used when the name stands for what is being named. The name of Mary is "Mary", and "dogs" never bites (the "s" ending "bites" is intentional) while dogs may bite.

You can play a lot with names, which is sometimes very convenient. In particular, there is no reasons that names should be only spoken utterances, or written character strings. It works as well if you take names from any set, such as integers, or sets of integers for example.

Since other things, such as integers or sets of integers, need to be named too to talk about them, it is hard to know whether you are using themselves or their names when the names is written down. We have seen that there are notational devices to make the distinction when it is important (using quotes, for example), but you can often forget about it.

So here $1$, $2$, and $3$ are the names of the states. We now see that whether they stand for the character or the integer does not actually matter muuch.

If you take a DFA and change consistently the name of a state of the initial NFA $N\_4$, but you might describe the same NFA with the names $9$, $8$, and $7$, or with $26$, $3$ and $15$, or with $1$, $2$ and $3$ assigned differently to the states so that the start state would now be $2$ (in the picture, you move $1$, $2$ and $3$, but you do not touch the start arrow or any other part of the picture), or it could even be the names *Huey*, *Dewey*, and *Louie*, or the names "foo", $2$ and "blue" (which is very useful if you describe the NFA with a poem).

In other words, in languages and automata theory, when you talk of a set of states or symbols, you can take any set of mathematical objects *that you can enumerate* (give me some time to think about sets that are countable but not recursively enumerable ... but this is no worry of yours). They do not even need to come from a consistent source. You only want them as names in order to describe and run you automaton.

But this should not encourage you to use strange naming. This naming freedom should rather be used to make things easier to understand and remember. This is probably why Sipser used $1$ for the start state.

You have exactly the same situation in programming, when you have to choose names/identifiers for variables, functions, classes or other entities, though these names are usually restricted to alphanumeric strings. Good programming practice recommands the use of identifiers that are meaningful, and help understand the program.

When building the DFA $D$, you can use any name you want for the states of $D$. However, it is convenient to use sets of names used for the states of the NFA $N\_4$. This is usually simplified into saying that each state of $D$ is a subset of the states of $N\_4$.

This choice of names is convenient, and helps understanding, because because a state of $D$ is intended to mimic (in some precise sense) the behavior of several states of $N\_4$, precisely those it contains.

A complementary or alternative view of this is to consider that automata that use different state names are defined up to a renaming of states. What one is interested in is the equivalence class up to a renaming equivalence relation, since renaming does not change the behavior of the automaton.

Understanding the use of names is not as obvious as it may seem, and it can raise sometimes thornier technical issues, though not really here.

See for example:

# Answer
> 2 votes
The following is an attempt at explaining informally the idea of the construction. There are other ways to look at it, somewhat more theoretical. I do not know how Sipser precisely does it.

The principle of the construction of the DFA $D$ from the NFA $N\_4$ is that, for a given input, the DFA $D$ simulates all the computations that $N\_4$ could follow depending on non-deterministic choices it permits. In other words, for an input string $w$, $D$ will reach a state, which is precisely the set of all states that $N\_4$ could reach for some computation with that same input $w$. That is why a state of $D$ is a set of states of $N\_4$.

For the start state, the situation is the same. For a DFA, the start state is the state you are in when you have not read any input, or to say it differently, the state you are in after reading the input $\epsilon$. For a NFA, it is possible to reach other states from the start state without reading anything, if it has an $\epsilon$-transition to them.

In the case of $N\_4$, you have $1$ as start state. But without reading anything, you have a transition to state $3$. Hence states $1$ and $3$ can both be reached by reading $\epsilon$, i.e. nothing at all. This is why the set $\\{1,3\\}$ is the start state of $D$. It means that $N\_4$ can be (non-deterministically) in state $1$ or in state $3$ before reading any input, and in no other state.

This must remain true for all other states of $D$ (which are sets of states of $N\_4$). The DFA $D$ reaches state $S$ after reading string $w$ if and only if, for each $N\_4$ state $q$ in $S$, there is at least one computation of $N\_4$ that reaches state $q$ when reading $w$. That is what the construction does.

Then, if a state $S$ of $D$ contains a state $q$ of $N\_4$ which is an accept state, it means that for any input string $w$ that brings $D$ in state $S$, there is at least one computation of $N\_4$ on input $w$ that brings $N\_4$ into state $q$, and hence accepts the string $w$.

Since $D$ is supposed to accepts all the strings accepted by $N\_4$, it follows that $S$ must be an accept state of $D$. There is no other way to accept the string $w$ since $D$ is deterministic by construction.

Hence, any state $S$ of $D$ that contains an accept state of $N\_4$ has to be an accept state for $D$. Since $1$ is the only accept state for $N\_4$, the set $\\{1,2\\}$ has to be an accept state of $D$.

**First question**

First I must say I cannot understand what you are saying in the paragraph that starts with:

> My assumption---\> As {2} is not in the list of accepted states ...

To begin with, as I said in a comment, you do not have lists of states, only sets of states. Second, you should talk of *accept states*, or *accepting states*, but not of *accepted states*.

Also, there are no new states, but only states of $N\_4$, and states of $D$ which are sets of states of $N\_4$. Accept states of $D$ are precisely those that contain an accept state of $N\_4$, for the reasons explained above.

I cannot say much more because I do not understand what you are trying to say, what is in your mind. Why would you consider that $\\{1,2\\}$ cannot be an accept state of $D$, but that $\\{1,2,3\\}$ can be an accept state of $D$?

My further attempt to explain

The fact that both $1$ and $2$ are in this set $\\{1,2\\}$ indicates that there is a string $w$ for which the NFA $N\_4$ can reach either $1$ or $2$ depending on non-deterministic choices in the computation. Of course, the computation that reaches state $2$ does not accept $w$. But the definition of acceptance for a non-deterministic machine is that it is enough if one computation accepts $w$, even if all other non-deterministically possible computations on $w$ fail to be accepted. In this case, it is enough that some computation on input $w$ can reach $1$.

**Second question**

The sentence you do not understand is apparently a problem with English. It should be read as

> The start state is E({1}) **which is** the set of states that are reachable from 1 by traveling along ε arrows, plus 1 itself\`.

I think this kind of sentence structure (with a comma instead of "which is") is called an apposition.

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


# Question
Title: Is Big-Oh notation preserved under monotonic functions?
I was just looking at the big-Oh notation. I wanted to know if the following is true in general $$f(n)=O(g(n)) \implies \log (f(n)) = O(\log (g(n)))$$

I can prove that this is true if $g$ is monotonically increasing, but am not sure if this holds in general.

# Answer
By definition, $$ f(n) \in O(g(n))$$ means there exists some *positive* constant $c$, such that for any large enough $n$, $$ |f(n)| \le c |g(n)|$$ or equivalently, $\lim\_{n\to\infty} \frac{f(n)}{g(n)} \le c \< \infty$

Taking $\log$ of both sides, for any large enough $n$ it holds that $$ \log (f(n)) \le log (c) + \log(g(n)) $$

so, $$\frac{\log f(n)}{\log g(n)} \le \frac{\log c}{\log g(n)}+ c$$

Now can this go to infinity? only if $\log(g(n)) \to 0$

So let's try, and take $f(n)=2^{-n}$ and $g(n)=1/n$. Obviously $f(n) \in O(g(n))$. Yet, taking the logs we have $\log f(n) = -n$, $\log g(n) =-\log n$, and it is clear that no constant $c'$ will satisfy $|\log f(n)| \le c' |\log g(n)|$ for large enough $n$. Yet, I always find it weird to discuss $O$ of negative functions.

**EDIT:**

Here's example w/o negative function. Get back to the requirement of $\log(g(n)) \to 0$. Take $g(n) = 1+1/n$. Thus $\log (g(n)) \to 0$.
<sub>(actually, the above example of $2^{-n}$ vs $1/n$ satisfies $g(n)\to 0$ rather than $log(g(n))\to 0$. Oops).</sub>

If we take $f(n) = 2 + 1/n$ then $\log f(n) \to 1$ (binary log, obviously).

so while $f(n) \le 3g(n)$ for every $n\ge 1$, it is not true that $\log f(n) \le c' \log g(n)$ for all large enough $n$, as the right-hand side approaches zero, while the left-hand side approaches 1.
> 5 votes

# Answer
while g(n) and f(n) are non negative , and bigger than 1, this is true for every functions.
> -1 votes

---
Tags: asymptotics, landau-notation, mathematical-analysis
---


title: Computer science for programmers

text:
# Question
Title: Computer science for programmers
I'm a self-taught programmer and have been coding for 8 years. Due to this experience, I'm already very familiar with the principles of programming (such as if-statements, classes, polymorphism, etc.).

However, I never learned "computer science," only programming. What are some good resources for someone in my position to self-study computer science - that is, resources which move at a quick pace and assume basic programming knowledge?

# Answer
Computer Science is a multifaceted discipline - and *Algorithms and Data Structures* is important part of it. You can try free video-courses, like Algorithms, Part 1, from Princeton University \- it's running right now.

Another remarkable free video-course Algorithms: Design and Analysis, Part 1, from Stanford has finished recently - hopefully it will be repeated in the future. Part 2 of this course will start this Monday.
> 11 votes

# Answer
Well, this is my first answer over here and, also, I am less experienced than you. So,consider it an answer of novice, which may be irrelevant for you or others. But, I'll try to preserve the worth of question with my answer!

Well, first of all let's discuss(only outline) the domain of computer science,or the life-cycle of one involved in learning CS. Probably, I might be missing some of them. Also, there may be ambiguity about their positioning. But,it goes as :-

1. Computer Fundamentals(General Working of computers) and introduction to computers
2. Programming language and its use to solve real life problems using the help of computers
3. Variations of programming language(functional,object-oriented,procedural) and its different principles
4. Data Structures and Algorithms // one of the most important part and the backbone of CS
5. Foundations of Computer Systems---Discrete Mathematics,some portion of Digital Electronics
6. Software Engineering // again one of the most important part and the backbone of CS
7. Operating System --- my favourite subject in CS branch, and also the most-important, core branch of CS,the whole of CS runs on this, at least.You need a machine to execute things, based even on modelling
8. Computer Architecture --- it's again one of the important subjects to know the basic functioning of working of computers
9. Databases are worth every acknowledgement! Excellent discovery.
10. Computer Networks --- a very beautiful section of CS which is related to networks(real-life connections)
11. Theory of Computation, Automata, Compilers --- my 2nd favourite subject, all in one section describing state changes and language formation and operation.
12. Data Mining & Machine Learning --- The most progressive field of Computer Science nowadays and in fact really one of the most informative
13. Artificial Intelligence & Neural Networks & Fuzzy Logics --- not to say anything,the best real-life simulation

> Now, returning to the question. I think you must give every section a chance to go deep and try to find your interested field. It takes a person a few years to decide which field is best fit for him/her.
>
> You should not directly jump to any field which involves only programming section!!! Programming Languages are not "that" worth what they are framed as, the most important part is the basic modelling, functioning and generation of ideas and new theories which enhances CS field. So, as per me you should give each field a try at once, say for a week and see of you're really getting attracted to them the most! This will first give you the subject to carry away with!

Now,coming to the online resources.There are plenty to look at.You'll find nowadays lots of tutorials,videos and lectures being available on the internet.But,the most sought out ones with brilliant showpiece are :-

1. www.coursera.org
2. www.nptel.ac.in
3. www.khanacademy.org

and so on.

Try to use these more frequent for learning CS basics.Apart from these,you always have search engines a click away to help you provide the topic you are facing difficulty with.
> 9 votes

# Answer
As a programmer, you supposed to know following things as per the basic Computer Science:

1. Basic Programming Principles
2. Data structures
3. Software Engineering Methodology
4. Different Programming Techniques (it depends on Algorithm)
5. Basic Knowledge of Testing the code

You can get these courses through MOOC.

Coursera is providing different courses with good resourses, if you want you can sign-up there.
> 2 votes

# Answer
Other courses that I studied (and I think are important):

1. Design patterns (like Singleton, Facade, Factory .etc)
2. Discrete Structures

Asymptotic complexity is a very important topic in CS as well. I would recommend "Introduction to Algorithms" as a good reference book for Data structure and Algorithms.You can then practice at Project Euler. Other than that, MIT has courses MIT Open CourseWare over at YouTube. I find their data structure courses very helpful.

Another thing I can suggest is also going through any University's CS coursebook to get the topics and see which one is of interest, and study them.
> -1 votes

---
Tags: reference-request
---


title: Complexity of Hopcroft-Karp

text:
# Question
Title: Complexity of Hopcroft-Karp
I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where $m$ is the number of edges in the graph and $n$ is the number of vertices(for example, see wikipedia or this book, among many examples - I cannot post more than two links due to reputation constraints).

What bothers me about this is that if $m$ is small (say $m=n^{1/4}$) this seems to require less than $n$ iterations, which is odd: surely you have to at least look at every node, i.e., just to see if it has any incident edges or not?

Having looked at Hopcroft and Karp's original paper, I see they quote a running time of $O((m+n)\sqrt{n})$ which makes more sense.

So my question is: what is the reason why the running time of Hopcroft-Karp is usually quoted as $O(m \sqrt{n})$? Does this reflect an assumption that the graph is connected (I never see this stated explicitly)?

# Answer
> 10 votes
The correct running time is indeed probably $O((m+n)\sqrt{n})$. However, this is a mouthful, and the expression $O(m\sqrt{n})$ looks nicer and is also more succinct. In most cases, $m \geq n/2$, since otherwise there is an isolated vertex. In fact, by finding isolated vertices, we can improve the running time of the algorithm to $O(n + m\sqrt{n})$.

An alternative way of stating the running time would be $O(m\sqrt{n})$, assuming $m \geq n$. The case of small $m$ is not so interesting (since then there are isolated vertices which can be eliminated), and so it is usually assumed that $m = \Omega(n)$.

---
Tags: graphs, algorithm-analysis, runtime-analysis, bipartite-matching, matching
---


# Question
Title: Describing explicitly the MyHill-Nerode classes created by a language
I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt:

For the language $$L=\\{\omega \in \\{a,b\\}^\* \colon \omega \text{ contains at most 1 } 'a' \\}$$ The classes are $$M\_1=\\{\omega \in b^\*\\}$$ $$M\_2=\\{\omega \in b^\*ab^\*\\}$$ $$M\_3=\\{\omega \in b^\*ab^\*a(a\cup b)^\*\\}$$

Now, the way I understand it I need to prove 2 things:

1. For each $u,v\in M\_i (1\le i\le 3)$ and for each $x\in \Sigma^\*$ $$ux\in L \iff vx\in L$$
2. There exists $u\in M\_i,v\in M\_j(1\le i \neq j \le 3)$ and $x\in \Sigma^\*$ such that $$ux\in L,vx\notin L$$

Am I right about how I described the classes, and about how to prove it?

# Answer
> 4 votes
Your classes are correct, and one can also describe them in words: words containing no $a$, words containing a single $a$, words containing at least two $a$s. When described in this fashion, it is clear that the every word belongs to exactly one class.

However, there is no reason to use the Myhill–Nerode criterion to prove that a language is regular. Instead, you can use its vast generalization and give a DFA or NFA for the language. In the other direction, there is no need to describe *all* classes, only infinitely many; this already shows the language is not regular.

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


# Question
Title: m-element random sample being equally likely ...(CLRS 5.3-7)?
I am trying to understand the following solution to CLRS 5.3-7: http://clrs.skanev.com/05/03/07.html Question description is on the page. I understood the part where m-element subset is constructed out of m-1 element subset when the m-element subset includes the last element n. But why does the probability of randomly choosing m-1 elements from a set of n-1 elements differs in the case when we don't include the last element? Doesn't the invariant state that we choose m-1 elements at random from n-1 elements?

# Answer
> 1 votes
Here is the recursive algorithm for selecting a random set $S \in \binom{\[n\]}{m}$ (the set of all $m$-subsets of $\[n\] = \\{1,\ldots,n\\}$):

1. If $m = 0$, return the empty set.
2. Generate a random set $S \in \binom{\[n-1\]}{m-1}$ recursively.
3. Let $i \in \[n\]$ be chosen uniformly at random.
4. If $i \notin S$, return $S \cup \\{i\\}$.
5. If $i \in S$, return $S \cup \\{n\\}$.

To show that this works, we prove that the probability to get any set in $\binom{\[n\]}{m}$ is exactly $1/\binom{n}{m}$, by induction on $n$. This is clear when $m = 0$, so assume $m \> 0$. Let $S \in \binom{n}{m}$ be given. We consider two cases: $n \notin S$ and $n \in S$.

Case 1, $n \notin S$. For each $i \in S$, the probability that the recursive step generates $S \setminus \\{i\\}$ is $1/\binom{n-1}{m-1}$, and so in that case $S$ is produced with probability $1/n$. In total, the probability is $$ \frac{m}{n} \frac{1}{\binom{n-1}{m-1}} = \frac{1}{\binom{n}{m}}. $$

Case 2, $n \in S$. In that case, the recursive step must generate $S \setminus \\{n\\}$, and then $S$ is produced with probability $m/n$ (since we either hit $n$ or any element in $S \setminus \\{n\\}$), obtaining the same expression as above.

---
Tags: probability-theory, randomized-algorithms
---


title: A DFA recognizing my name

text:
# Question
Title: A DFA recognizing my name
How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius}

I came with this solution:

```
>(0)--p-->(1)--u-->(2)--s-->(3)--t-->(4)--a-->(5)--i-->(6)(goto state 0)
  |
 (7)--m-->(8)--a-->(9)--r-->(10)--i-->(11)--u-->(12)--s-->((13)) (final state)

```

How can I know if this is implemented correctly? And about minimization of this automate I think is impossible.

# Answer
Write down *all* accepting paths, that is paths from the starting state to final states. These are all the words the given automaton can accept; if the set is the desired one, q.e.d.

This is only possible and a rigorous proof for (co-)finite languages. Once you have cycles you have to apply induction. See here for an in-depth explanation on how to do this for grammars; it's similar for automata.
> 2 votes

---
Tags: formal-languages, automata, finite-automata, proof-techniques
---


title: Relation between RAM and Turing machine

text:
# Question
Title: Relation between RAM and Turing machine
Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers in time $f(n)$, then there is a $7$-string Turing machine $M$, which computes $\phi$ in time $O(f(n)^3)$.

Consider the following example: $\phi(S)$ is a sum of first two numbers of a finite sequence $S$, or $0$, if $|S| \< 2$. It seems to me that a RAM, defined in Papadimitriou's book computes $\phi$ in time $O(1)$. Thought, any Turing machine, computing $\phi$, should work for at least linear time (we can take an input of length $n$ with only two numbers in sequence). I don't see how to cope with this contradiction.

Could you please describe me, where I am wrong? Thanks a lot.

# Answer
> 2 votes
You're right, there is a missing assumption that f(n) is at least O(n). Indeed, the last line of the proof state that the operand are of size O(f(n)), while what has been proven before is O(f(n)+l(I)+l(B)). Since l(I) is O(n), the hypothesis is needed for this simplification.

---
Tags: turing-machines, time-complexity, simulation, computation-models
---


# Question
Title: In an M/M/1 Queue, what does exponential distribution of service time mean?
I was reading about the `M/M/1 Queue` and that we assume new customers arrive according to a Poisson distribution, and each customer takes an amount of time to service that is drawn from an exponential distribution?

I understand what it means to have an arrival rate based on Poisson distribution - if an average of 10 come per hour, you'll have 9 a few times, 6 very infrequently, 11 pretty often etc - but **what does it mean that service is exponential?**

Does this mean that as you serve more customers, the *average* time it takes to service them rises exponentially? Wouldn't the system crash soon after a few customers?

# Answer
In an exponential distribution, the probability is DECREASING exponentially -- hence little risk that service time will grow. On the contrary, the mean service time is fixed, at the inverse of the rate. This distribution is actually very rare in practice, but is chosen because it is Markovian: the probability to terminate servicing a client does not depend on the past, and in particular on how much time you already spent servicing that client. That yields very nice mathematical properties.
> 4 votes

---
Tags: terminology, probability-theory
---


title: Why is SAT in NP?

text:
# Question
Title: Why is SAT in NP?
I know that CNF SAT is in NP (and also NP-complete), because SAT is in NP and NP-complete. But what I don't understand is why? Is there anyone that can explain this?

# Answer
> 2 votes
Try reading up on the Cook-Levin theorem. SAT is basically the first problem proven NP-complete. High level sketch of the proof: simulate a nondeterministic (NP-time, nondeterministic polynomial time) TM computation using a cascading circuit that computes the TM iterations, which can be converted to SAT. Loosely speaking, the "size" of the circuit is "polynomial".

# Answer
> 3 votes
CNF-SAT is in NP since you can verify a satisfying assignment in polynomial time. CNF-SAT is NP-hard since SAT is a special case of CNF-SAT, and so we can reduce the NP-hard problem SAT to the CNF-SAT. Since it is both in NP and NP-hard, we conclude that CNF-SAT is NP-complete.

# Answer
> 1 votes
Note: This is a repeat of an answer for a previous question, but the answer works better here than it did there.

There were two independent proofs that SAT is NP-hard, one by Stephen Cook in 1971 \[1\] and the other by Leonid Levin in 1973. We now know it as the Cook-Levin theorem. You can read the paper, or consult the Wikipedia article \[2\] for details, but I'll give a brief outline of the basic idea here.

Let's look at the recogniser problem. There is a language $L$, and a nondeterministic TM $M$ which recognises $L$ in polynomial time. Let $w$ be a string. The idea is to construct a boolean formula $A(w)$ in conjunctive normal form, where the number of formulas and the number of propositions is polynomial in the length of $w$ and the size of $M$ and the size of the alphabet, which is true if $M$ accepts $w$ and false if $M$ rejects $w$.

The proof depends on the fact that $M$ takes polynomial time in the length of the string. Suppose that the maximum number of steps that $M$ can take for a string of length $n$ is $Q(n)$. Then this is also an upper bound on the amount of tape that $M$ can use. We can trivially modify $M$ so that all computations take at least this time. We could, for example, modify $M$ so that it loops forever in an accepting or rejecting state, let it run for $Q(n)$ time and then see which state it was in.

We introduce the following proposition symbols:

* $P\_{i,s,t}$ is true if and only if the tape square $s$ contains symbol $i$ at time step $t$.
* $Q\_{i,t}$ is true if and only if the machine is in state $i$ at time step $t$.
* $S\_{s,t}$ is true if and only if symbol $s$ is scanned by the tape head at time step $t$.

Next, we construct formulas which model the actions of $M$ and test whether or not $w$ is accepted. We can do this using only the above proposition symbols, and in conjunctive normal form.

I encourage you to think through the details yourself by working out what the formulas might look like. The ones that Cook used are:

* At each time step $t$, one and only one square is scanned.
* At each time step $t$ and tape square $s$, there is one and only one symbol.
* At each time step $t$, $M$ is in one and only one state.
* At time step $1$, $M$ is in its start state and the tape contains exactly $w$ followed by "blank" symbols.
* At each time step transition, the $P$, $Q$ and $S$ propositions are updated correctly, according to the transition function of $M$. Remember $M$ is nondeterministic, so you need to include all possible transitions. (If you're playing along at home, use three formulas for this.)

And the final, most important, formula states that:

* $M$ enters the "accept" state at some time.

Then the conjunction of all of these formulas is true if and only if $M$ accepts $w$. Solve using your favourite SAT solver, and you're done.

---

1. The Complexity of Theorem-Proving Procedures by Stephen A. Cook (1971).
2. Cook-Levin theorem on Wikipedia.

---
Tags: complexity-theory, satisfiability, decision-problem, np
---


# Question
Title: Proof of an Optimal substructure in Dynammic Programming?
Could someone please explain how exactly the proof of optimal substructure property in dynamic programming problems works?

They usually say:

> Let's say the global optimal solution is A, and B is part of the solution. So B must the optimal solution of the subproblem, because if it weren't, then A wouldn't be the global optimal.

It makes some sense to me, but I think this would work with any non-dynamic problem (the property), or maybe it is because I still don't get how it works.

Can someone please help? How does the contradiction work?

# Answer
There is no (one) formal definition of "optimal substructure" (or the Bellman optimality criterion) so you can not possibly hope to (formally) prove you have it.

You should do the following:

1. Set up your (candidate) dynamic programming *recurrence*.
2. Prove it correct by induction.
3. Formulate the (iterative, memoizing) algorithm following the recurrence.
> 11 votes

# Answer
Most students are indeed puzzled by this property: it looks obvious when they read it, but yet they can't manage to apply it to solve problems. First note that when you express the objective by recursion on the subproblems, the expression has to be monotonic and the subproblems must be independent. For instance, in the travelling salesman problem, you cannot solve it by a call to find the best path from A to B and another from B to A: the two subproblems have to decide how to divide the nodes between them, since the salesman cannot pass two times in the same node.
> 6 votes

---
Tags: proof-techniques, dynamic-programming, correctness-proof
---


# Question
Title: Solving a variant of interval scheduling problem
I am trying to solve a problem of finding compatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.

I have a set of jobs with start and finish time and I want to find the smallest subset of this jobs such that all the jobs are incompatible with at least one job of this subset. And all the jobs in this subset are compatible

Suppose

```
job  start   end
1    1       3
2    2       11
3    4       6
4    12       14

```

My required job set J is {2,4} since all the jobs are incompatible with at least one job of the job set J. And all the jobs in the job set J are compatible. I tried using earliest deadline first and schedule but it doesn't work. Any suggestions?

Am I going the right way?

# Answer
It seems that you are looking for the minimum maximal independent set of an interval graph. A minimum maximal independent set in a graph is the same as a minimum weight independent dominating set, with all vertices weights equal to 1. Since interval graphs are a special case of chordal graphs, Martin Farber's paper *Independent domination in chordal graphs* (Operational Research Letters, 1(4):134–138, 1982; ACM Digital Library) contains the algorithm you are looking for.
> 2 votes

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


title: How to write this regular expression

text:
# Question
Title: How to write this regular expression
Consider the language over the alphabet $\sum= \\{a\\}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language

# Answer
> 2 votes
Hint: A number $n$ is a multiple of $2$ or $3$ if $n \\; \mathrm{mod} \\; 6 \in \\{0,2,3,4\\}$.

Simpler solution: Take the union of the words whose length is a multiple of 2 with the words whose length is a multiple of 3.

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Returning a random subset with length k of N strings while only storing at most k of them
Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, $k$. The subset must contain exactly $k$ strings selected uniformly at random from the entire input set.

It's easy to do this if every single string is stored in memory. (Memory proportional to N). The question is how to only store at most $k$ strings, and still ensure that the output is perfectly random.

I've tried to work it out with the following base case. Say $k = 1$.

```
> Subset 1
A
B
C

```

`A` will always be added, since the queue contains less than k items. If I only operate on what I know, which is the current number of items in the queue, the required length $k$, and the encountered strings $n$. So I've tried doing this: ($k$ - items in queue)/$n$.

Using that, the probability of `A` being replaced by `B` is $1/2$. Then the probability of `B` being replaced by `C` will be $1/3$. The problem there is that there's no way of reducing the probability of `A` being replaced before I've seen all of the strings.

I'm sure this question must have a clever answer. The problem of writing this Subset program to use memory $\<= k$ is a bonus question on an Algs course I'm taking, and I really hope they wouldn't ask something unanswerable.

# Answer
Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, you store it in memory. Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far. At the end, output whatever is stored in memory. The end result is that each string in the input is equally likely to be output. See also Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space for description of this approach (thank you, Juho!).

This extends to arbitrary $k$. See Wikipedia's description for details.
> 9 votes

# Answer
This problem is covered in *The Art of Computer Programming*. I can't recall exactly where, but the algorithm is pretty easy to understand when you know the trick.

Let $l$ be the number of lines read so far. At each stage, you read the next line from stdin. Choose $r$ to be a random integer uniformly chosen from the range $\[1,l+1\]$. If $r \le k$, then discard line number $r$ from the collection that you've kept, and replace it with the line you just read. Otherwise, drop the line.

The pseudocode looks something like this:

```
for i := 1 to k
    read a line from stdin into L[i]
end for

l := k
while there are more lines left
    read a line from stdin into x
    r := random(1, l+1)
    if r <= k then
        L[r] := x
    end if
    l := l + 1
end while

```

Of course, in a robust implementation, you should deal with the case that there are fewer lines than $k$, and so on.

Proof of correctness is left as an exercise.
> 5 votes

---
Tags: algorithms, probability-theory, sets, randomness, sampling
---


# Question
Title: What's the value of this game (rebalancing counters)?
Suppose you have the following game:

There are infinitely many counters $\\{c\_1,c\_2,\ldots\\}$, all initialized to 0.

In each step, you may choose a counter $c\_i$ and increase it's value by 1.

Unfortunately, every $T$ steps, each counter that has a positive value is decremented by 1.

Also, the values of the counters are bounded by $M$, so you can't increment a counter any further.

**Given as many steps as you like, can many positive valued counters can you reach?**

---

EDIT: As this question is unanswered for two weeks, I have posted it in CSTheory as well.

---

Detailed buildup for $\approx T\log(M)$ positive counters:

1. While you have less than $T-1$ counters at value $M$:

* Increment the minimal index counter whose value is strictly less than $M$. This has to converge as the sum of the counters are bound to increase every $T$ steps.
2. Let $r = T$.
3. While ($c\_0\>0$)

a. while ($c\_0\>c\_r$)

* Increment $c\_r$

b. $r = r + 1$

Now for the analysis: first observation is that the number of positive counters is $r$.

Now let $m\_r$ be the maximal value $c\_{r}$ have reached. For $r=T$ we get $M(1-\frac{1}{T})$. For $r=T+1$ we get $m\_r(1-\frac{1}{T})=M(1-\frac{1}{T})^2$, or in general $$\forall r\geq T:m\_r = M(1-\frac{1}{T})^{r-T+1}$$

Next we notice that when $\forall m\_r$ is achieved, $c\_0=m\_r$. This means the loop will halt when $m\_r \< 1$ (give or take integrality and end-of-game-strategies).

This gives us $$M(1-\frac{1}{T})^{r-T+1} \< 1$$ $$(1-\frac{1}{T})^{r-T+1} \< M^{-1}$$ $$({r-T+1}) \log (1-\frac{1}{T}) \< -\log M$$ $${r-T+1} \< \frac{-\log M}{\log (1-\frac{1}{T})}$$ $$r \< \frac{-\log M}{\log (1-\frac{1}{T})} + T - 1$$ $$r \< \frac{\log M}{\sum\_{k\geq 1}^{\infty} {\frac{1}{kT^k}}} + T - 1 \< T(\log M + 1) -1$$

Does this look right?

Is it possible to do better? Can anyone prove this is optimal?

# Answer
> 3 votes
Let's collect what facts we can determine:

* The sum of all counters $S$ will change by $T-P$ with each cycle of $T$ steps, where $P$ is the number of positive counters at the final step of the cycle.
* If you end a cycle with $P=T-1$, you have $S\le(T-1)(M-1)$. During the following cyle you can reach $S=(T-1)M$ after $T-1$ steps, but in the next step you will have to increase a $T$-th counter, so the decrease after that step will return to $S=(T-1)(M-1)$. So $(T-1)M$ is an upper bound for $S$ (and thus also for $P$).
* Assume there is an optimal strategy, that never reaches $S=(T-1)M$. The step where that strategy reached its highest value of $S$, has to be the penultimate step of a cycle, and the cycle before that one has to have ended with $P\le T-1$. By inserting a cycle that simply increases some or all of the nonzero counters before the cycle that reaches maximum $S$, we can increase the maximum value of $S$ for that strategy without influencing the maximum value of $P$.
Thus we can restrict our search for an optimal strategy to strategies that start by bringing $T-1$ counters up to $M$ and then try to distribute the sum amongst as many counters as possible.
* The maximum value of $P$ will be reached at the penultimate step of a cycle. (At any other point we can raise it by increasing counters that were previously 0 until that step of the current cycle.) We denote by $X$ the number of cycles (including the incomplete one) in the distribution phase.
* We can assume that any counter we increase during the distribution phase will be nonzero in the $X$-th cycle. Otherwise not spending these increases would not alter the outcome. For the same reason we can assume that each nonzero counter is at value 1 in the $X$-th cycle.
* From the previous item we can conclude that any counter increased in the 1st cycle has to be increase $X$ times, any counter increased for the first time in the 2nd cycle has to be increased $X-1$ times and so on. This implies that it is beneficial to start increasing each counter as late as possible.
* In the last cycle we cann set $T-1$ counters to 1. In the cycle before that, we can set $\frac T2$ counters to 2, and so on, until in the first $\frac XT$ cycles we can set one counter to $X$. This shows that it is beneficial to make $X$ as large as possible.
* $X\le M$, since after the $M$-th cycle all the initial counters will reach 0 (or we have to spend increase operations on them that we could instead have spent to increase other counters).

Since the optimal moves from our considerations describe exactly the strategy from the question, we can conclude that this strategy is indeed optimal.

# Answer
> 1 votes
One approach is to look at the sum of the values of all the counters. Say you have a strategy that keeps the number of positive counters at $\ge P$ for an extended period of time. Then every $T$ steps, the sum decreases by $P$; but you can only increase the sum by at most $T$ over this time period; so to sustain $P$ positive counters over a long time period, you need $P \le T$. There is a matching lower bound showing that you *can* indeed sustain $T$ counters, all at their maximum value, and sustain this situation indefinitely.

There remains the possibility of short-term strategies which bring the number of positive counters up to something large for a brief period (but cannot sustain it), presumably starting from the state where you have $T$ counters at value $M$. I think the second half of your scheme such is a short-term strategy. I don't know how to prove that there is no better short-term strategy, but at least this reasoning takes care of the long-term part of the strategy.

---
Tags: algorithms, counting, computer-games
---


# Question
Title: Why did MIPS include shamt and distinguish funct/opcode?
I'm confused as to why the MIPS designers would include 5 bits dedicated to shifting and have separate opcode and function bits.

Because MIPS is so RISC I assume that only shifting would be done in a few instructions, so those 5 bits seem like they're wasting space when they could be put in the immediate. I assume that opcodes and funct are separate for distinguishing R- and I- type instructions, but this could be done by extending the opcode by 1 bit. Both of these R-type instructions could be 22 bits long. This won't work if the I-type and J-type instructions want to keep their immediate and address, but both seem unnecessary.

# Answer
There are a few different trade-offs going on here.

First, we want the instructions to be fixed width (32-bits). This guarantees that instructions are cache-block and page aligned which simplifies cache and page presence and permission checks.

Second we want the various instruction fields (`opcode`/`source regs`/`immediates`) to be fixed width and fixed position. This makes them faster/less logic to decode and they are needed in the early stages of the pipeline. (The `destination` register isn't needed until the end of the pipeline, so it can be in different places in `R` and `I` instructions.) The position and width of the `function` field matters a little less because that needs to control the function of the ALU, but that's in the third pipeline stage, so you have a little time to work with it if needed.

But now we have a tension between number of possible instructions and the sizes of the immediates. We want the immediates in the `I` and `J` instructions to be long as possible. This is a 32-bit architecture, and the `J` instruction has only a 26-bit address. It gets two zero low-order bits added to it (another benefit of fixed width instructions) but you can still only jump a maximum distance of $2^{28}$ bytes, which makes life difficult for the linker. (A call of a procedure that is more than $2^{28}$ bytes distant needs to be done with a triple instruction: load-upper-immediate, add-immediate, jump-and-link-register, instead of just a jump-and-link.) The 16-bit immediate in `I` instructions is also nice for compiler/linker writers. (On the SPARC, where the immediate field was only 12 bits they had to add an entire special `load-high` instruction class with a 20 bit immediate.)

So we really don't want to make the opcode 7 bits (because it will cut into immediates) but with 6-bits we only have $2^6=64$ possible different instructions, which is way too few. The compromise is: there are exactly two type `J` instructions (jump and jump-and-link), and only one or two type `R` instructions, with the remaining 60-or-so opcodes being used for `I` instructions.

But that leaves some wiggle room with the `R` instructions. Aside from the 6-bit opcode, these only need 15 additional bits for register specification, which leaves 11 bits for the extended opcode and/or shift-amount.

You should think of the `function` field as being an extended opcode for the `R` instruction. There's only one `R` instruction opcode, but there are 64 different `functions` that the `R` instruction can perform.

Okay. We have 60 different `I` instructions and 64 different `R` instructions, so where should we put the shift-immediate instructions?

Well, not only are there fewer `I` instructions, but there are way more things we want to do with `I` instructions. Recall that all the branch instructions need to be `I` instructions because they have a relative (immediate) offset. Also all the load and store instructions are `I` format on MIPS. And finally we need the load-upper-immediate instruction to be an `I` instruction. Not only that, but the `R` instructions still have 5 additional unused bits, (which is what we need for the immediate of a shift-immediate on this architecture), so this gives further incentive to making the shift-immediates into special (weird) `R` instructions.

A lot of these decisions are more art than science, but there is an underlying logic that can be discerned. The key goal is *not* to make the number of instructions as small as possible, it is to make a *high-performance* pipeline fit on a single chip (so that tiny companies, like MIPS and Sun were in the 1980s, could compete with IBM and DEC). (The name RISC, invented by David Patterson, is somewhat unfortunate. It caught on because it was cute, not because "reduced instructions" is an accurate description of what the MIPS and SPARC architectures were really trying to do.) So you want the instructions fixed width (and relatively small so that you get better I-cache behavior) to make fetch, paging and decode simpler and faster. You want the parts of the instruction that need to be decoded early (the `opcode`, the two source registers, and the sign-extended immediate) to be a fixed width and in a fixed position. You want immediates to be as long as possible, and you want as many different kinds of instructions as will fit, given all those other constraints.
> 10 votes

# Answer
To understand the MIPS I instruction formats, you need to understand the MIPS pipeline and also think back to CPU implementation technology circa 1985. If you look at the diagram (you know the one), you'll see that register file reading is in the ID stage, right after IF.

For the purpose of an R-type instruction, the ID stage needs to do the following tasks:

1. Determine that it actually *is* an R-type instruction.
2. If so, tell the register file to load values from registers.

For the purpose of this discussion, it's the first task that you have to think about. If there's a lot of instruction decoding work that you have to do to even work out if you need any values from registers, this increases the delay before you can start the register reads. It also increases the complexity of the ID stage. By reserving a single opcode for all R-type instructions, you keep the complexity to a minimum.

It does seem a little strange that you dedicate five bits just to shifting. I can think of a few possible explanations. One is that it simplifies the routing (those five bits are ALWAYS fed straight into the register file, those five bits are ALWAYS fed into the barrel shifter, those six bits are ALWAYS routed through to the ALU to determine which function to perform).

They may have been thinking of introducing combined shift-left-and-add instructions in the future. This would presumably be of the form:

```
$d = $s + ($t << shamt)

```

This is a surprisingly useful instruction to have around, as any x86 assembly programmer can tell you. You can use it to implement fast multiplications by $2^s+1$ for various values of $s$, or you can use it to index arrays where the size of an element is a power of two (which is a very common case). But it's still RISC enough that you could implement it without significant penalty.

Today, we probably wouldn't think twice about having a more complex decoding stage, especially since register file accesses tend to happen later in the pipeline of a typical superscalar CPU. Many modern CPUs even do some coarse instruction decoding *at the time an instruction is inserted in the L1 cache*. You make the I-cache lines a few bits wider to store the extra information (thanks to Moore's Law, you have lots of transistors to waste) to make "proper" instruction decoding simpler and faster.

One reason why they probably wanted to keep the opcode field as small as possible is so that it didn't penalise J-type instructions unduly. As you probably know, J-type instructions use pseudo-direct addressing. For the benefit of anyone playing along at home, I'll briefly explain it.

The address field of a J-type instruction is 26 bits. Because instructions are always 4-byte aligned, you don't need to store the least significant two bits, which means you effectively have 28 bits of address. However, the address space in MIPS I is 32-bits. So the top four bits of the jump location is taken from the program counter.

This means that you can't directly jump to a location where the most significant four bits of the PC location are different. You would have to do a more expensive three-instruction jump through a scratch register instead:

```
lui $r,target >> 16
    ori $r,$r,target & 0xFFFF
    jr $r

```

That's not too bad today, but in 1985, it's a lot of clock cycles.

Stealing a bit from the address field would reduce the effective range of a direct jump even further. You can see how this might be too high a price to pay.
> 5 votes

---
Tags: computer-architecture
---


title: What is theory behind graphs relations?

text:
# Question
Title: What is theory behind graphs relations?
I have been trying to understand, what is the actual meaning of 2 graphs being:

```
Symmetric
Transitive
Reflexive
A graph being a subgraph of another graph

```

And other similar relations if let's say I have two graphs containing 1000's of nodes and edges. Then, what do these terms mean w.r.t to those 2 graphs?

# Answer
> 1 votes
I have never seen the first three properties applied to a graph in the way that you are asking, however the final property, sub graphs, is strait forward.

By definition: A subgraph of a graph G is a graph whose vertex set is a subset of that of G, and whose adjacency relation is a subset of that of G restricted to this subset.

In more plain terms, if you have graphs $H=(V\_2,E\_2)$ and $G=(V\_1,E\_1)$ where $E$ is the edge set, and $V$ is the vertex set, if H is a sub graph of G then we can pair up each of the vertex in $V\_2$ with one in $V\_1$, With this pairing in mind, if we can then pair up each edge in $E\_2$ with its counterpart in $E\_1$ then the graph is a sub graph, if edges exist within $E\_2$ which cannot have a pairing in $E\_1$ then it is not.

---
Tags: graphs, terminology
---


title: Inconsistent state of a lock

text:
# Question
Title: Inconsistent state of a lock
I'm reading The Art of Multiprocessor programming and trying to understand their concept of inconsistent locks. Specifically, on page 37, the definition 2.8.1 of an inconsistent lock is not clear to me, as well as Lemma 2.8.1.

> Definition 2.8.1. A Lock object state s is inconsistent in any global state where some thread is in the critical section, but the lock state is compatible with a global state in which no thread is in the critical section or is trying to enter.
>
> Lemma 2.8.1 No deadlock-free Lock implementation can enter an inconsistent state.
>
> Proof:
>
> Suppose the Lock object is in an inconsistent state s, where no thread is in the critical section or trying to enter. If thread B tries to enter the critical section, it must eventually succeed, because the implementation is deadlock-free.
>
> Suppose the Lock object is in an inconsistent state s, where A is in the critical section. If thread B tries to enter the critical section, it must block until A leaves. We have a contradiction, because B cannot determine whether A is in the critical section.

What I don't understand:

* Does being inconsistent just mean that if a thread is in a critical section, there's no way other threads can know about it?
* What's the contradiction in a lemma proof? Say thread A is in a critical section, and the lock is in an inconsistent state. What stops another thread from overwriting the lock's state and acquiring it?

# Answer
> 1 votes
* "inconsistent" here means basically the internal implementation is not reflecting the reality of thread activation and lock availability. aka "defective". ie its not functioning correctly as a thread lock. eg the lock may indicate "active" but no thread has acquired the lock or the lock indicates "inactive" but some thread acquired a lock.
* the contradiction is that according to "deadlock free", a lock will eventually be acquired by at least some thread that requests it. but if its in an inconsistent state then some thread is running but the lock indicates that nothing is locked. but then any new thread cannot succeed in obtaining the lock (without running at the same time as A).

note a wrinkle/subtlety from an online ref\[1\] that closely matches the book exposition (same authors):

> Note that a program can still deadlock even if each of the locks it uses satisﬁes the no-deadlock property. For example, consider threads A and B that share locks 0 and 1. First, A acquires 0 and B acquires 1. Next, A tries to acquire 1 and B tries to acquire 0. The threads will deadlock because each one waits for the other to release its lock

\[1\] Multiprocessor Synchronization and Concurrent Data Structures Maurice Herlihy / Nir Shavit

---
Tags: terminology, concurrency, threads, deadlocks
---


# Question
Title: Is FNP = FEXPTIME if and only if NP = EXPTIME?
It is very well known that if the classes $\sf FP$ and $\sf FNP$ are equal, then also the classes $\sf P$ and $\sf NP$ are equal (see e.g. FNP on Wikipedia).

Is it also true that if $\sf FNP=FEXPTIME$ then also $\sf NP=EXPTIME$? (See the exponential time conjecture.) I did find a paper constructing real functions that are in $\sf FEXPTIME$.

# Answer
Yes, vacuously, since it is trivial that $\operatorname{FNP} \neq \operatorname{FEXPTIME}$, because it takes an exponentially long amount of time to give an exponentially long output.
> 1 votes

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Find the smallest summed distances by uniquely pairing elements of one set to elements of another set
As input I have two sets of points in **R**N, typically for large N, for example N=40. Supose both sets have m elements:

S = s1 ... sm

T = t1 ... tm

Semantically both sets are equal, but due to noise (of whatever kind) on the R^N points, elements which should be semantically the same still have a distance larger than 0.

What I want to find is m tuples (si, tj) such that the sum of distance(si, tj) is minimized and such that sk and tk exactly occur once in the set of tuples for k=1...m. Basically (i,j) have to be chosen as towers on a chessboard which can not hit each other while minimizing the summed distances.

In other words, I want to find an onto one-one map between S and T which 'is sort of an identity map, but robust to noise'. We assume that the distance measure is a good indication of how similar elements are.

Basically I need to find a permutation of 1...N, and hence I think this problem is either NP-hard or NP-complete, since it 'feels' quite similar to the TSP; however I have not been able to rewrite the TSP problem to a subset of my problem here.

Is this problem realistically solvable for large N? Is there a name for this problem? What would be a feasible solution? Is there another criteria which might be better than the summed distances?

I thought of a greedy approach, let D be a matrix of the distances, dij = distance(si, tj).

```
T = {}
while D is not empty:
    (i,j) = argmin-(i,j) dij
    append (i,j) to T
    set row i and column j to infinity.

```

This does not result in the optimal solution, but finds a solution. Would this be my best bet? Should I use simulated annealing, or is it overkill?

PS: from my point of view, this is just a minor problem in a bigger ML problem, however, I am very much interested in the CS background of it.

# Answer
> 6 votes
This is the problem of finding the maximum matching in a weighted bipartite graph. There are efficient algorithms that solve this problem in polynomial time.

Basically, you have a complete bipartite graph with $2m$ vertices. $S$ forms one set of vertices; $T$ forms the other set of vertices. For each $i,j$, create an edge from $s\_i$ to $t\_j$ whose weight is equal to $-d(s\_i,t\_j)$, the negation of the distance between $s\_i$ and $t\_j$.

Now, you want to find a matching whose weight is as large as possible. This corresponds to a set of pairs $(s\_i,t\_j)$ whose total distance is as small as possible. From there, you can use existing algorithms on this graph to find the maximum-weight matching.

# Answer
> 3 votes
Here's a quick probabilistic method that might work for you.

1. Project your points onto a random line and solve the 1D matching problem in this line.
2. Repeat the process for a handful of different random lines to get a collection of candidate matchings.
3. Have your candidate matchings "vote" point by point to come up with the "best" matching.

---
Tags: algorithms, optimization
---


title: What exactly is computer science?

text:
# Question
Title: What exactly is computer science?
I have a question that, no matter how much I think about, I do not have the answer to. The question is what exactly is computer science? The reason I am asking is that I went into college thinking computer science was going to be about software engineering disciplines and deep study in the realm of application and practicality; these excited me. However, after taking core requirement classes for computer science, many so devoted to discrete mathematics (set theory, group theory (abelian properties, etc.), probability, etc.), I became disillusioned and frankly, sick of taking these abstract-concept related courses, asking myself daily when I would use these concepts in my daily life as a developer.

I've searched online for the answer, but none have satisfied me so far. Several arguments have boiled down to essentially saying something like "If you want to do gaming, you have to be good at trigonometry, which is math"; clearly, this is not what I am looking for. If someone could guide me into truly understanding why discrete math and structures is essential to the software engineer, and to the world outside the realm of the academia aspect of computer science, that would be awesome. Thank you!

# Answer
> 3 votes
"...asking myself daily when I would use these concepts in my daily life as a developer." The answer depends on the job. It sounds like you don't like math/theory, so you would not apply for/ get a job that requires a deeper understanding of CS, as many higher-level jobs do.

However, the truth is that the vast majority of software engineering jobs requires very little math or theoretical computer science, or even a good understanding in computer systems (which you didn't mention). If you just want to write code for websites or applications or do front-end, you can do that just fine without knowing most of the topics taught in a CS curriculum. Most of this knowledge is simply uneccessary, although having a degree will certainly help you get a job. However I know people who went into the software engineering profession with degrees in journalism or theater or other completely unrelated fields.

Also, there are some colleges that offer a degree in Software Engineering, which is much more focused on the practical side, including software development cycles and practices.

This is all practical advice. As for what Computer Science *is*, there is probably no universally accepted answer. It's a broad field, with many different sub-fields. However, most people would probably not consider simple software programming as Computer Science.

# Answer
> 2 votes
The most unfortunate thing about computer science it its name. CS has nothing to do with computer, it should have been called "computation science".

Every scientific field goes through below stages. NOTE: All the stages continues in parallel i.e no particular stage dies.

* Theory: Where people works on the fundamental problems of the field. You need some sort of "tool/language" to work on the theories and in most cases that tool is mathematics (the universal modeling tool). This is what CS is all about.
* Engineering: Where people start yo build tools/systems based on the theories developed in the above field (they will also use theories from other fields as well to develop these systems). This is what large scale enterprise level software engineering AND hardware development is all about.
* Commodity: In this stage the systems build in the engineering phase starts to be available to "common man" and they start to use them in their daily lives. This is what "programming" as in creating small programs/scripts, web sites etc are all about.

# Answer
> 0 votes
In my opinion why these other subject is added is to master the domain knowledge,

Consider you know java and all the technologies of java and you are perfect in java and if I give you an application to create on mathematics like take the example of Scientific Calculator if you don't know mathematics then how will you create that Calculator even though you are perfect in programming but you don't have the domain knowledge,

The same applies to others Graph theory for Designer ,Discreet Mathematics for developing logical skills, and optimization.

You know We have a subject of Accounts and financial Management which is totally related to accounts when I ask my professor he told me that you are doing Master of computer Application (MCA) you must have domain knowledge of Accounts since in future you may build application related to Accounts.

Hopes something usefull.

**Edit**

And Computer Science is really that,that you thought it before joining, But mastering computer science also need Domain Knowledge not only technology.

---
Tags: terminology
---


# Question
Title: Why is $A_{TM}$ reducible to $HALT_{TM}$?
In Sipser, there is a proof I don't understand.

First he established the undecidability of $A\_\mathrm{TM}$, the problem of determining whether a Turing machine accepts a given input.

$$A\_\mathrm{TM}=\left\\{\left \langle M,w \right \rangle\mid M \text{ is a TM and }M \text{ accepts }w\right\\}\\,.$$

Then defined $\mathrm{HALT\_{TM}} = \left\\{\left \langle M,w \right \rangle\mid M \text{ is a TM and }M \text{ halts on input }w\right\\}$, he assume that $\mathrm{HALT\_{TM}}$ is decidable and use that assumption to show that $A\_\mathrm{TM}$ is decidable, contradicting.

He assume that we have a TM $R$ that decides $\mathrm{HALT\_{TM}}$. Then he uses $R$ to construct $S$:

$S$ = "On input $\left \langle M,w \right \rangle$, an encoding of a TM $M$ and a string $w$:

1. Run TM $R$ on input $\left \langle M,w \right \rangle$.
2. If $R$ rejects, reject
3. If $R$ accepts, simulate $M$ on $w$ until it halts.
4. If $M$ has accepted, accept; if $M$ has rejected, reject."

He says "Clearly, if $R$ decides $\mathrm{HALT\_{TM}}$, then $S$ decides $A\_\mathrm{TM}$. Because $A\_\mathrm{TM}$is undecidable, $\mathrm{HALT\_{TM}}$ also must be undecidable."

I don't understand why is so obvious the problem is $R$. I mean, I don't understand why if $R$ exists, then inevitably we can simulate $M$. We know that the step number 4 is not possible because $H(\left \langle M,w \right \rangle)$ = "accept if $M$ accepts $w$ OR reject if $M$ rejects $w$" is not possible, so why is $R$ guilty?

# Answer
Step one, don't try to argue why this TM can not work: under the assumption it *does* work. But then, since everything else $S$ does *is* possible (you have to accept that separately), the existence of $R$ certainly is "the problem".

As for understanding, the proof, there are two facts you have to check (under the assumption that $R$ exists):

1. $S$ is a Turing machine (i.e. its function is computable)
2. $S$ decides $A\_{TM}$.

Arguably, 1) is clear; simulating other TMs given their indices/encodings is something TMs can do (thanks to the existence of a universal TM, which you should have seen a proof of already) and $S$ does little more. This is as close to a proof as you'll get with *this* form of "definition" of $S$; it's more of an idea, really.

For the second, note that $S$ *always halts* because $R$ always halts and

$\qquad\begin{align\*} S\langle M,w \rangle) = 1 &\iff R(M,W) = 1 \land M(w) = 1 \\ &\iff M(w)\downarrow \land M(w) = 1 \\ &\iff w \in L\_M \\ &\iff \langle M,w \rangle \in A\_{TM} \\;. \end{align\*}$

By definition, that means that $S$ decides $A\_{TM}$.

Similar arguments usually works for this kind of proof; check our reference questions and other questions tagged .
> 3 votes

---
Tags: computability, reductions, undecidability, halting-problem
---


# Question
Title: Fixed point, what does it mean in the world of computer science
I keep coming across references to fixed point in questions and answers at stackexchange and I look up the meaning on the web obviously finding reference at sites such as Wikipedia. However none of the references really answer my question of what is a fixed point and what does it mean in the world of computer science.

---

**EDIT**

After 8 years this finally popped into my head.

**How would you explain fixed point to a kindergartner?**

A fix point is when you do the same thing again and again and nothing changes. So if your room is messy and you clean it, it is now at a fixed point because if you clean it again it is still clean.

I know there is a joke or comic in there somewhere but I don't have my comedian hat on today.

# Answer
> 17 votes
In computer science, the arguably most prominent use of fixed-points is in lattice theory¹. A lattice is a partially ordered set $(S, \leq)$ with the additional property that given any two elements $x,y \in S$, the set $\\{x,y\\}$ has both a supremum and infimum (in $S$).

Now you often consider *monotone* functions $f$ on this lattice which "converge", that is for some $x \in S$ you have $f(x)=x$. Important results in this area are Kleene's fixed-point theorem and the Knaster-Tarski theorem.

A prominent example is the lattice $(2^A,\subseteq)$ for $A$ some set, and $f$ induced by an inductive definition. For example, let $A = \\{a,b\\}^\*$ and we define a language $L \in 2^{\\{a,b\\}^\*}$ by

$\qquad \begin{align} \phantom{w \in L} &\phantom{\implies} \varepsilon, a \in L \\ aw \in L &\implies baw \in L \\ bw \in L &\implies abw, bbw \in L \end{align}$

This inductive definition corresponds to the monotone function

$\qquad \displaystyle f(A) = \\{\varepsilon, a\\} \cup A \cup \\{baw \mid aw \in L\\} \cup \\{abw, bbw \mid bw \in L\\}$

By Knaster-Tarski theorem, we know $f$ has a smallest fixpoint which is a supremum of all smaller "intermediate results" (which correspond to finitely often applying the constructors of the inductive definition), and that smallest fixpoint is indeed $L$.

By the way, the *largest* fixpoint also has uses; see here for an example.

---

In recursion theory, there is another fixed-point theorem, also due to Kleene. It says²,

> Let $\varphi$ a Gödel numbering³ and $ r :\mathbb{N} \to \mathbb{N}$ a total, computable function (intuition: a compiler). Then there is $i \in \mathbb{N}$ such that $\varphi\_{r(i)}=\varphi\_i$.

In fact, there are even infinitely many such $i$; if there where only finitely many, we could patch $r$ (by table-lookup) to not have fixed-points, contradicting the theorem.

---

1. Everybody uses it every day, even if you don't realise it.
2. I don't like that Wikipedia article; you are probably better off checking a genre book.
3. A special kind of function numbering. For intuition, think of it as a (Turing-complete) programming language.

# Answer
> 13 votes
Let me elaborate a bit on meisterluk's answer: Imagine we are trying to define the factorial function: remember the definition of the factorial function:

```
fact 0     = 1
fact (n+1) = n*(fact n)

```

Now in some PL frameworks (namely the $\lambda$-calculus), it isn't immediately obvious how to define such a function. However, it may be easy to define the following *higher-order* function, so-called because it takes as input *another* function and a natural number

```
Fact f 0     = 1
Fact f (n+1) = n * (f n)

```

There is no use of recursion in this function definition. However, if there was some way of finding the *fix-point* of `Fact`, that is, a function $\phi$ such that $$\mbox{Fact}\ \phi\ n ~=~ \phi\ n$$ for every $n$, then it is easy to check that $\phi$ is indeed an implementation of the factorial function.

Now in frameworks like the $\lambda$-calculus, one can show that all fixed-points of this nature do, in fact, exist, which makes it clear that you can use it as a general programing language.

There are many other uses to the notion of fixed-points in computer science, but most boil down to the one I showed above, i.e. prove that certain fixed-points exist to be able to show that certain functions or constructs are well-defined in your framework (here we have shown that the factorial function exists).

# Answer
> 9 votes
A fixed point of a function $f: A \to A$ is an element $x$ for which $f(x)$ is equal to $x$. For example, the function $x^2$ has two fixed points, which are the values $0$ and $1$, and the function $x^3$ has three fixed points. Mathematically that is the definition.

Now, depending on the mathematical structure you are dealing with, there are very many different reasons to be interested in fixed points. For example, if you consider a dynamic system that looks at the state of the world and changes it (like a thermostat) then a fixed point corresponds to a stable configuration. If you think of games in the mathematical sense of game theory, fixed points correspond to equillibria, if you think of the the behaviour of an optimization routine that iteratively improves its solution, a fixed point corresponds to an optimal solution. So the mathematical notion of a fixed point has a lot of applications in a lot of different contexts.

A very common, and fundamental application of fixed points in computer science is to mathematically model loops and recursive programs. If we try to model a program as a mathematical function, both loops and recursion are not obvious to model. This is because the body of a loop is a program and can be represented as a mathematical function. How do we derive the function representing the loop's behaviour? It corresponds to applying the loop body repeatedly, in conjunction with the loop guard, until no further change is possible. Similarly, if we model recursive programs mathematically, we need a mathematical notion of what it means for a function to apply itself. This answer is provided by fixed points.

# Answer
> 7 votes
A function in mathematics is a map between input and output values. Fixed points are input values (for a function) which map to output values satisfying equality with the input.

For the equality function $f(x) = x$ the set of input value equals to the set of fixed points of the function. For a function $f(x) = x^2$ the set of fixed points is limited to $\\{0, 1\\}$.

As far as computer science is concerned, we are talking a lot about partial functions, but this does not change the definition of fixed points for us.

You might also be confused about a totally different topic: Fixed-point arithmetic is a concept how to represent real numbers in the memory. But the name "fixed points" does not reference to this topic in general (because there is only 1 point).

# Answer
> -2 votes
game theory is a major subarea of CS and an important concept there is the Nash equilibrium which is a fixed point theorem. it gives a means of identifying optimal game strategies given that other players are aware of each others strategies. it can be proven via Kakutani fixed point theorem or the Brower fixed point theorem. Nash won the Nobel Prize in Economics in part for developing this theory.

---
Tags: terminology
---


# Question
Title: Suffix automaton algorithm to find occurrences of substrings
Here is an attached link to a problem, the Substring query problem that I am trying to solve. It requires the use of suffix automaton,but I could not understand what is a suffix automaton. Can anybody explain.

# Answer
Given a FA $M$ accepting a language $L$, a *suffix automaton* is one which accepts the language of all suffixes of strings in $L$. In other words for a language $L$ over an alphabet $\Sigma$, $$ \operatorname{SUFFIX}(L)=\\{y\mid\exists x\in\Sigma^\* \ (xy\in L)\\} $$ For example, if $L$ is the language denoted by the regex $ab^\*a$ we'll have $L=\\{aa, aba, abba, \dots\\}$. A finite automaton accepting $L$ is illustrated below. (Note that we could eliminate state 3 and still accept the same language.)

The suffixes of $aa$ are $aa, a,\epsilon$, the suffixes of $aba$ are $aba, ba, a, \epsilon$ and we'll have $$ \operatorname{SUFFIX}(L)=\\{\epsilon, a, aa, ba, aba, bba, \dots \\} $$ in other words, the suffixes of $L$ will be denoted by the regex $ab^\*a+b^\*a+a+\epsilon$

It turn out that the suffix language of a regular language is itself regular. Given a FA $M$, it's easy to construct a FA $M'$ that accepts $\operatorname{SUFFIX}(L(M))$: just add a new start state $s$ to $M$ and connect $s$ to each state of $M$ by $\epsilon$-transitions, as in the figure below:

The idea here is that for every accepting path in $M$, we've designed $M'$ so that it jumps to an intermediate state in the accepting path and so will accept any suffix of the original language. From $M'$ the standard NFA-to-DFA construction, found in any intro theory text, can be used to construct a DFA from $M'$. Applied to our example, we obtain the following equivalent DFA:

This, by the way, isn't the smallest equivalent DFA: we could merge states 1 and 6 into one, giving a 5-state DFA whose language is the suffix language of the original FA $M$.

---

The algorithmic intricacies of eliminating $\epsilon$-moves from the suffix automaton $M'$ can be avoided by a different construction using the same idea:

```
1. M' will have all the states and transitions of M.
2. Add a new start state, s, to M'. This new state will be a final state.
3. for every state, p, of M:
      for every state, q, of M and every character, a, in the alphabet of M:
         if we have a transition in M where (q, a) --> p:
            add the transition (s, a) --> p to M'

```

Graphically, if we have an arrow labeled $a$ coming into a state $p$, and we could have reached $p$ when processing a string "$\dots a$", we'll skip all the earlier parts of the input and go directly from the new start state to $p$ on seeing an $a$.

Here's an example of the construction, using our original FA. Of course, we still might generate a NFA, as we do here, but at least we haven't used $\epsilon$-moves in the construction.
> 5 votes

---
Tags: algorithms, automata, strings, substrings
---


# Question
Title: Is there a canonical definition of “pure” function?
StackOverflow pointed me here, so the question might be a bit in a layman's terms.

Wikipedia defines pure functions as

> In computer programming, a function may be described as a pure function if both these statements about the function hold:
>
> 1. The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change as program execution proceeds or between different executions of the program, nor can it depend on any external input from I/O devices.
> 2. Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.

However it does not seem to cite any sources -- so it is hard to say whether this is an accepted definition, or who defined it this way.

When I look at what the languages do when they include a syntax/annotation for "pure" functions, there are quite a few different approaches:

1. In D the only limitation is non-mutation of global state. "Pure" functions can mutate its arguments.
2. In GCC there are two types of "pure": `pure` (no side-effects, but can read global state) and `const` (stricly pure as per wikipedia definition).
3. In C#, it is defined as "does not make any visible state changes" (whatever that is).
4. Haskell follows the Wikipedia definition.

So my question is: is there a canonical definition of pure function?
And if there is, what is its source?

# Answer
As noted in this paper Imperative Functional Programming, (1993) by Peyton-Jones and Wadler (among the group of researchers that created Haskell):

> We focus on purely-functional solutions, which rule out side effects, for two reasons. Firstly, the absence of side effects permits unrestricted use of equational reasoning and program transformation...

the focus is on absence of side-effects to enable program transformations (i.e compiler optimisations).

What are side-effects? This paper in turn points to Integrating functional and imperative programming (1986) by Gifford and Lucassen, which mentions four types of *effect classes*: Pure, Function, Observer and Procedure. So, the term "pure function" derives from this paper.

> * a PURE is referentially transparent: it does not cause side-effects, its value is not affected by side-effects, and it returns the same value each time it is evaluated.

Note, however, that Peyton-Jones and Wadler mentioned shortcomings in this approach. Worth noticing, they say, is the programming language Clean that uses linear types to introduce side-effects in a safe manner (i.e. safe for the compiler). Basically, it threads the *World* as a variable in all I/O related functions, including the *main* entry point.

With that, it is possible to have a pure functional language interacting with the *world* and having side-effects (I/O, the OS, the Windowing system, etc), contradicting partially your wikipedia definition. One can in fact say that Haskell has Clean as one of its influencers; although it departs from linear types and uses another type-level construct (monads) to guarantee linearity, i.e. a single-reference at all times.
> 4 votes

# Answer
Wikipedia's definition is canonical. The crucial two requirements are:

* The return value and behavior of the function is a deterministic function of the arguments that were explicitly passed to the function.
* An invocation of the function has no observable side effects.

Strictly speaking, D and gcc shouldn't be using the word "pure" the way they do; it's an abuse of standard terminology.
> -1 votes

---
Tags: terminology, functional-programming, semantics
---


# Question
Title: Finding hash of a substring $[i, j]$ in $O(1)$ using $O(|S|)$ pre computation
Given a string $S$ of length $n$ characters, is it possible to calculate the hash of its substring $\[i, j\]$ (from index $i$ to $j$, both inclusive) in $O(1)$ using some form of precomputation? Can we use a modification of the rolling hash?

The following is a similar problem to my question. In it the string was given in a compressed form. Example: if the string is `"aaabccdeeee"` then the compressed form is:

```
3 a
1 b
2 c
1 d
4 e

```

The data was stored in an `str[]` array as :

```
str[] = [{'a','3'}, {'b','1'}, {'c','2'}....]

```

Note that hashing was used in the solutions, which checked if the given substring is a palindrome or not. Given a substring of string $S$ as $(i, j)$, they computed the hash of substring $\[i, (i + j) / 2\]$ and the reverse hash of substring $\[(i+j+2)/2, j\]$ and checked if they were equal or not. So if they wanted to check if in string `S = "daabac"` whether substring $\[1, 5\]$ is a a palindrome or not, they computed the following :

```
h1 = forward_hash("aa")
h2 = reverse_hash("ba")
h1 == h2

```

**Code for the hashing concept**

The hash precomputation was done as follows:

```
/* Computing the Prefix Hash Table */
pre_hash[0] = 0;
for(int i = 1;i <= len(str); i++)
{
    pre_hash[i] = pre_hash[i - 1] * very_large_prime + str[i].first;
    pre_hash[i] = pre_hash[i] * very_large_prime + str[i].second;
}

/* Computing the Suffix Hash Table */
suff_hash[0] = 0;
for(int i = 1;i <= len(str); i++)
{
    suff_hash[i] = suff_hash[i - 1] * very_large_prime + str[K - i + 1].first;
    suff_hash[i] = suff_hash[i] * very_large_prime + str[K - i + 1].second;
}

```

And then the hash was computed using the following functions :

```
/* Calculates the Forward hash of substring [i,j] */
unsigned long long CalculateHash(int i, int j)
{
    if(i > j)
        return -1;
    unsigned long long ret = pre_hash[j] - POW(very_large_prime, [2 * (j - i + 1)])*pre_hash[i - 1];
    return ret;
}

/* Calculates the reverse hash of substring [i,j] */
unsigned long long CalculateHash_Reverse(int i, int j)
{
    unsigned long long ret = suff_hash[j] - POW(very_large_prime, [2 * (j - i + 1)]) * suff_hash[i - 1];
    return ret;
}

```

**What I am trying to do**

I am looking for a general approach to the above concept. Given a Pattern $P$, I want to check if the pattern $P$ is present in a string $S$. I know the index $i$ to check where it may be present. And I also know the length of pattern $P$ represented as $|P|$. In short I want to check if hash of $S\[i, i + |P|\]$ and hash of $P$ match or not in $O(1)$ using some form of precomputation on $S$. (Ignoring the time taken to compute hash of $P$ else it would be $O(1+|P|)$.)

# Answer
> 4 votes
Yes, you can solve your problem, roughly speaking, by precomputing prefix sums.

In particular, if you are willing to do $O(n)$ precomputation and to use $O(n)$ space, we can solve your problem, for most standard rolling hashes. We just need the rolling hash to have one extra property, the inverse property. Most rolling hashes do have this property, including the well-known Rabin-Karp rolling hash.

Let me explain the details, below.

Some notation: let $S\[i..j\]$ denote the substring of $S$ from index $i$ to $j-1$ (note: it doesn't include index $j$; it is a substring of length $j-i$). Let $H(S\[i..j\])$ denote the rolling hash of that substring.

## The intuition

Imagine that we used a very simple hash, which is just the sum of the bytes modulo 256:

$$H(S\[i..j\]) = S\[i\] + S\[i+1\] + S\[i+2\] + \dots + S\[j-1\] \bmod 256.$$

This is a crummy hash function (it has lots of collisions), but let's go with it, since the purpose is just to get some intuition. This is a rolling hash; given the hash of a prefix of the string, it is easy to extend it by one more byte (just add that byte to the hash value you've got so far).

Now with this hash function, we could easily solve your problem. During the precomputation, we'd fill in an array $A\[\]$ so that $A\[j\] = S\[0\] + S\[1\] + \dots + S\[j-1\] \bmod 256$ for each $j$; this can be done in $O(n)$ time. Now, we can compute $H(S\[i..j\])$ via the simple relation

$$H(S\[i..j\]) = A\[j\] - A\[i\] \bmod 256.$$

This can be computed in $O(1)$ time, given the precomputed array $A$.

Of course, you'd never use this in practice, because it's such a crummy hash function. But the same idea can be generalized to work with many other rolling hash functions, which you would want to use. (Intuitively, that's because they are based upon a binary operation that is associative and has an inverse, which is all you need for this trick to work.) I'll describe the details next.

## The inverse property

All rolling hashes have the following property:

*The accumulation property:* Given $H(S\[i..j\])$ and $S\[j\]$, we can compute $H(S\[i..j+1\])$.

We need one additional property from the rolling hash:

*The inverse property:* Given $H(S\[i..j\])$ and $H(S\[i..k\])$, where $j \< k$, it should be possible to derive $H(S\[j+1..k\])$.

Many standard rolling hashes do have this inverse property. For instance, the Rabin-Karp rolling hash has the inverse property. The same is true for hashing with cyclic polynomials (Buzhash).

## How to use the inverse property for your problem

Create an array $A\[\]$ of $n$ elements. During precomputation, we will fill in the elements of $A$ so that $A\[j\] = H(S\[0..j\])$. This precomputation can be done in $O(n)$.

Now, at some later point, you would like to compute the rolling hash of $S\[i..j\]$, i.e., to compute $H(S\[i..j\])$. How do you do that? It turns out it is easy. First, look up $H(S\[0..i\])$ and $H(S\[0..j\])$ using the array; this involves reading the value of $A\[i\]$ and $A\[j\]$. Next, use the inverse property to compute $H(S\[i..j\])$ from these two values. Done! That's all there is to it.

---
Tags: data-structures, strings, hash, rolling-hash
---


# Question
Title: How deciding if 2 deterministic finite automatas decide the same language?
Is there any polynomial procedure to decide if 2 deterministic finite automatas decide the same language?

# Answer
By Myhill-Nerode, the minimal DFA for a regular language is unique. You can minimize both and check that they are equal.
> 1 votes

# Answer
Let $D\_1,D\_2$ be the automata in question, and let $L\_1,L\_2$ be the corresponding languages. Using standard construction one can construct an automaton $D$ for $L\_1 \triangle L\_2$ (the symmetric difference of $L\_1$ and $L\_2$), and then one checks whether this automaton accepts any words.
> 1 votes

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


# Question
Title: What is the language generated by the following grammar?
Could please tell me the language generated by this grammar? S-\>iS |iSeS|ε

# Answer
$$\left\\{w\in \\{i,e\\}^\*\mid \forall v \sqsubset w\colon |v|\_i\ge |v|\_e\right\\}$$
> 1 votes

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


# Question
Title: High Level Programming Languages vs Block Programming Environments
I am looking for the opinions of more experienced programmers as to the effectiveness of writing programs in Block Programming Environments such as Scratch or App Inventor as opposed to High Level Languages such as C++, Python or Java. I have already done some research and here are some examples of links that have been helpful.

Programming : High Level Languages
An Overview of Programs and Programming Languages

I am just looking for a few other peoples opinions.

Questions that I would really appreciate if you could answer include:

Do you find using high level code easier or more difficult than using blocks?

Have you experienced any limitations of either High Level Languages or Block programming?

What advantages and disadvantages have you experienced when using the two?

Any helpful answers would really be appreciated

# Answer
> 1 votes
A Block programming environment is higher in the abstraction levels as compare to high level programming languages which basically mean that Block programming environment is easy to work with and there is less conceptual burden to carry BUT you can do "less stuff" (as it is very abstracted) where as in high level programming languages you can do "more stuff" but the conceptual burden at this level is much high.

This is how abstraction principle works. More abstract = less things to worry about BUT less ability. Less abstract = More things to worry about BUT more ability.

It is usually advised that you start at the top abstraction layer so that you can start learning things without freaking out with way too much details and as you get more and more experience you start to look at bottom abstraction layers to gain more insights and get more done.

---
Tags: programming-languages
---


# Question
Title: Efficient algorithm for extreme spread of points in a plane
Given a set $X$ of $n$ points in the real plane, designated by their Cartesian coordinates, find the extreme spread of the points, which is defined by

$\qquad\displaystyle \mathrm{ES} = \max\_{1 \leq i,j \leq n}: \sqrt{(x\_i - x\_j)^2 - (y\_i - y\_j)^2}$,

i.e. the largest Euclidian distance between any two points in the set. This measure is also known as the *diameter* of the set.

# Answer
Best answer so far is on SO which suggests using Convex Hull ($O(n \log n)$) followed by Rotating Calipers on points in the Hull, which is $O(n)$.

This problem was also posed as *TFOSS* and a number of efficient solutions can be found here.
> 1 votes

# Answer
This is called the diameter problem or the farthest pair problem. There's lots of research on the topic. You might want to go read some of the papers. It can be done in $O(n \lg n)$ time in 2 dimensions; see, e.g., here. See also Wikipedia on proximity problems.
> 1 votes

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