# Question
Title: What is the difference between Multiprogramming and Multitasking
I am finding it difficult to clearly differentiate between Multiprogramming and Multitasking.

My primary source has been Wikipedia, but the WP article seems to be a little at odds with some less reputable sources (like my college professor).

As I read WP, *multiprogramming* is a rudimentary way of increasing CPU throughput, by context-switching when a process waits for I/O.

> Multiprogramming doesn't give any guarantee that a program will run in a timely manner. Indeed, the very first program may very well run for hours without needing access to a peripheral.

*Cooperative Time-sharing*, synonymous with *Cooperative Multitasking*, is an improvement on multiprogramming (with which it is not synonymous). The CPU context-switches regularly to give the impression of simultaneous execution, but processes are still required to yield - and poorly designed programs can starve the rest of the system.

*Preemptive Multitasking* takes more aggressive control of scheduling, giving priority to some processes over others, etc.

1. Is this overview correct? If not is that because WP is incorrect or because I read WP wrong?
2. Why do some sources seem to conflate multiprogramming and multitasking?

# Answer
> 10 votes
They are more or less synonymous. Multiprogramming is more used when one CPU is involved, that is being switched from a process to the other, processes which are residing in memory simultaneously. Along came threads, and it wasn't switching between programs anymore...

Processors, particularly the intel line, had the mechanisms for true multitasking (timer interrupt, privileged instructions) since at least the 80286. The M68000 used in the very first Mac was a processor with full-fledged multitaking capacities. This isn't a recent development in architectures. Note that the very first time shared systems swapped the user's programs in and out, and thus weren't really multiprogramming in the sense of having several programs in memory at the same time.

The idea is to have several programs residing in memory simultaneously, so that when one yields the CPU (by finishing or by waiting) there are others ready to use the CPU, thus increasing CPU utilization (and as you can consider each CPU burst to be preparing for a use of I/O, increase overall usage). This gives better thoughput (important in batch systems).

Along came time sharing, several interactive users connected to the machine. Same idea, keep their programs around but switch among them fast enough so they have the ilusion of "having a computer to themselves". Requires a timer that interrupts the CPU to avoid monopolization.

On personal machines there was not much incentive to run several programs at a time, at least initially (one user in front of a severely limited machive didn't expect much). As machines grew, a way of working around this and allowing several programs at a time *without changing the operating system much* was "cooperative multitasking", in that every program is suposed to yield periodically to the operating system to select another one to run. As the program doing this is in full control, it can select to do this when nothing could get messed up by others. Needless to say, a program "forgetting" to fullfil its duty to yield gets an interesting boost in performance... early Mac systems worked this way, and for the above reasons this didn't last too long. On embedded systems with no or only rudimentary operating system, and a tightly controlled set of programs running, this is certainly an attactive option.

# Answer
> 3 votes
Difference between Multitasking and Multiprogramming? Multi tasking is a logical extension of multi programming. Classicaly in a multi programming environment, more than one user shares the cpu and the cpu rapidly switches from one user to another, providing a complete transparency from each other. In multitasking, the user is substituted by programs i.e more than one program shares the cpu and the cpu rapidly switches from one program to another. Actually a software residing on disk is a program. When it brought into RAM for execution is known as process or task and when it is inside the cpu and executing, is known as thread. So multiprograaming is basically for multi-users, and multitasking is for single user with multiple programs. Since most modern OS s supports both, so they are often spell interchangibly.

# Answer
> 0 votes
There are lot of differences between multitasking and multiprogramming.

Multitasking is executing more then one task at a single time. For example, you are listening to a song, printing a paper, and typing on MS-Word at the same time.

While multiprogramming, in this type of OS, we improve the CPU utilization using buffering and spooling. In sequential execution, the CPU sits idle after executing a program and loads the next program from the main memory. During i/o operations cpu also sits idel, the CPU also sits idle, but using a multiprogramming environment, the CPU switches to the next program and processes it. This is a technique used with the help of buffering and spooling.

---
Tags: terminology, process-scheduling
---


# Question
Title: Confusion about finite automata construction in Knuth–Morris–Pratt algorithm
There is one point I don't understand in the DFA construction for mismatch cases.

Here is the lecture note I watched, which describes how to handle mismatched characters during the DFA construction process.

Some information about the presentation screen shot:

`pat` is the pattern, string index starts at 0, `dfa` is the state transition table, in which the row is indexed by the character(eg, "A","B" or "C"), column by state(1,2,3,...).

---

**My question starts**:

In the place in the presentation, where starts with "*To compute dfa\[c\]\[j\]*", it says run the simulation using the last j-1 chars.

I am confused:

Why run the simulation using the last `j-1` chars, rather the last `j` chars.

What's the intuition of this design?

# Answer
> 1 votes
Say we are at state `j` (in the question's example, `j` is 5). This means that so far we have successfully matched `j` characters (characters 0 to `j-1` of the pattern). Now, we receive a new character - call it `newChar`.

**Case 1:** `newChar` is the character we wanted ('C' in the example). All is good and we have now a match of `j+1` characters (characters 0 to `j` of the pattern).

**Case 2:** `newChar` is not the character we wanted. Let's assume the most optimistic situation: that we've now matched `j` characters of our pattern. (We couldn't have a match of `j+1` characters in this case, because otherwise we would be in Case 1.) The last of these `j` characters that we matched is `newChar`. To have a total of `j` characters matched, then, we must have matched characters 1 to `j-1` of the pattern plus `newChar`.

Because a mismatch puts us in Case 2, and Case 2 only uses characters 1 to `j-1`, we need only run the simulation using the last `j-1` characters.

# Answer
> 0 votes
by "simulate" it mean just run the partially built DFA (in your mind) on the last $j-1$ characters of the pattern. When we are in state $j$ the first $j-1$ characters of the pattern have been matched but the current DFA does not know a transition for state $j$ and the character under consideration, so we decide what would be the next state. If it is B we don't want DFA to restart, but instead start from state 4. This avoids going back in the input.

The intuition is exploiting the matchings between some prefix of the pattern and the suffix of an extension of that prefix. Whenever a mismatch occurs the algorithm does not need to go back in the input since the DFA remembers all partial matchings so far.

---
Tags: algorithms, finite-automata, strings, matching
---


# Question
Title: Can we construct problems that can be solved in $\Theta(n^c)$ time, and tested in $O(n)$ time
CS sometimes seems take for granted that $\mathcal O(\text{poly}(n))$ is "easy", while $\mathcal O\left(2^{poly(n)}\right)$ is "difficult". I am interested in research into "difficult" polynomial-time algorithms, where the best-case solution to the constructed problem runs in $\Theta(n^c)$, where $c$ can be chosen to be large; but the solution could be tested in $O(n)$ time.

**Question:**

> Given an integer $c$, can we construct problems that would:
>
> * Take $\Theta\left(n^c\right)$ best-case-time to solve,
> * While taking $\tilde{\mathcal O}(n)$ time, and $\tilde{\mathcal O}(n)$ space, to test a solution?

($\tilde{\mathcal O}(n)$ is soft-big-oh, meaning $O(n \log^k n)$ for some $k$)

---

Something I note - I might be mistaken somewhere here - is that presumably, if there is a $\mathcal O(n)$ algorithm to test the solution, then perhaps there can be a $\mathcal O(n)$ reduction to $\rm k\text{-}SAT$. If so, and, if $\rm P=NP$, and there was a polynomial-time algorithm, say ${\rm S{\small OLVE}}\left(\Phi(\mathbf x)\right) \in O({|\mathbf x|}^{\alpha})$ time, then I think this might contradict our $\Theta(n^c)$ problem, if $\alpha \< c$.

---

The motivation would be to research the possibility of having a "one-way-function", that is linear(ithmic)-time computable, and best-case "difficult"-polynomial-time invert-able, where "difficult" means a high degree polynomial, instead of the usual exponential-time definition of "difficult"; perhaps this might be able to be used for cryptography even if $\rm P=NP$ (like "post-P-equals-NP-cryptography", similar to how there is a field of "post-quantum-cryptography").

# Answer
> 5 votes
If you believe in the exponential time hypothesis, then you can construct such an example by padding SAT. The ETH states that solving SAT on $n$ variables takes time $2^{\Omega(n)}$; let's say the time is $T(n)$. We can assume that SAT instances consist of at most $O(n^3)$ clauses, and so have length at most $\tilde{O}(n^3)$. Pad such an instance by adding $N = T(n)^{1/c}$ (where $c \> 1$ need not be an integer) spaces. According to the ETH, the resulting languages requires time $\Omega(n^c)$ to solve in the worst case (the "best case" time complexity of a problem is almost always $\tilde{O}(n)$, depending on your model of computation and how devious the problem is), but witnesses can be verified in time $\tilde{O}(n)$ and $O(\log n)$ space; most of these resources are spent on checking that the input is well-formed.

The same idea would work even with much weaker hypothesis, such as P$\neq$NP; I'll leave you the details.

# Answer
> 1 votes
if am understanding your question right, there are probably many examples of this based on "fixed parameters" of NP complete problems. eg finding a $k$-clique in a graph takes $O(n^{\sqrt k})$ time and can be verified in $O(n)$ time (a $k$ edge clique has $\sqrt k$ vertices).

---
Tags: algorithms, reference-request, time-complexity
---


# Question
Title: Decidability of the language that accepts a universal turing machine
Is the language $L\_{universal} = \\{ \left \langle M \right \rangle | M \textrm{is a universal turing machine} \\}$ decidable?

I'm guessing it is decidable according to the definition of a UTM, that a UTM must be able to calculate every recursive function. Since the set of recursive languages and the set of all input words are both enumerable, we are theoretically able to determine if the given $\left \langle M \right \rangle$ is a UTM. Is my logic somewhat correct?

# Answer
> 1 votes
If $L\_{u}$ would be decidable, $L\_u^\complement$ would be decidable too (the complement of a recursive language is recursive too) , but if you can build a TM that accepts $L\_u^\complement$ you can build a TM that accepts $L\_d=\\{w \mid w\_i \notin L(M\_i)\\} $ that is not RE.

In fact if $w \in L\_d \implies (w,w)\notin L\_u \implies (w,w) \in L\_u^\complement$.

So with a reduction from $L\_d$ to $L\_u$ it can be shown that $L\_u$ is not decidable.

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


title: Pumping Lemma for regular language

text:
# Question
Title: Pumping Lemma for regular language
I have a question to find out that L = {a^(2k)|k\>=1} is regular. I know that it is regular set but I was looking to find out if pumping lemma is satisfying or not. So I tried it as -

```
Let # of states in the FA be n & I select the string w = a^2n
Now let xyz = w
xy = a^n
y = a^m | m is odd number
now x(y^2)z = a^(n-m)(a^2m)(a^n)
= a(2n+m) does not belong to L

```

which says this regular set doesn't satisfy pumping property. Please let me know if I am doing something wrongly.

Thanks in advance.

# Answer
> 0 votes
The pumping lemma says that every (long-enough) string in a regular language can be divided in some way such that it can be pumped (subject to the other stated conditions).

Note that the statement is that every string *has at least one way* of dividing it up. Not every division of a string necessarily works. As you have shown, some don't work, however there is a different division (any one where $m$ is even) that does work. So the language does satisfy the pumping lemma.

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


title: NFA for right left multiplication

text:
# Question
Title: NFA for right left multiplication
Given the following multiplication table how could one construct an NFA such that it accepts all strings that have a certain product (say a) ?

The string "abcb" would be evaluated as (a(b(cb))) = a

\begin{array}{c|ccc} \times & a & b & c \\ \hline a & a & a & c \\ b & c & a & b \\ c & b & c &a \end{array}

I tried to take the transpose of the above matrix:

\begin{array}{c|ccc} \times & a & b & c \\ \hline a & a & c & b \\ b & a & a & c \\ c & c & b & a \end{array}

And build an NFA for that. I then reversed all the transitions, but I don't think that works.

# Answer
Start by checking that you would be able to build such a NFA if the multiplication table was associative. That would be a good starting point for you to work on. (If it's associative, the problem becomes very easy.) Once you've done that, the next step is:

Now to accommodate the fact that the multiplication table is in fact not associative, and that you want to group multiplications on the right first, you can use the ideas from Louis's comment. That should make it pretty easy for you to work out an answer to your own exercise, by yourself.
> 1 votes

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


title: Widest path algorithm steps

text:
# Question
Title: Widest path algorithm steps
I need to compute the bottleneck shortest paths from s to all vertices of a graph by modifying the Dijkstra’s algorithm. I found this explanation on Wikipedia(Link to Wikipedia) but I would appreciate if you can elaborate it a bit for me.

> If the edges are sorted by their weights, then a modified version of Dijkstra's algorithm can compute the bottlenecks between a designated start vertex and every other vertex in the graph, in linear time. The key idea behind the speedup over a conventional version of Dijkstra's algorithm is that the sequence of bottleneck distances to each vertex, in the order that the vertices are considered by this algorithm, is a monotonic subsequence of the sorted sequence of edge weights; therefore, the priority queue of Dijkstra's algorithm can be replaced by an array indexed by the numbers from 1 to m (the number of edges in the graph), where array cell i contains the vertices whose bottleneck distance is the weight of the edge with position i in the sorted order. This method allows the widest path problem to be solved as quickly as sorting; for instance, if the edge weights are represented as integers, then the time bounds for integer sorting a list of m integers would apply also to this problem

So I need to sort my vertex by weight starting from A? I would appreciate if you can explain me the steps in this algorithm.

Thanks

# Answer
> 0 votes
The way to use Dijkstra's algorithm to solve the $s$-to-$t$ widest-path problem (in a directed graph) is described well in the following lecture notes:

http://www.cs.cmu.edu/~avrim/451f08/lectures/lect1007.pdf

Make sure to read Sections 13.1, 13.2, and 13.3. You will see that a single-line change to Dijkstra's algorithm suffices (we change the $+$ to $\min$, and change the $\min$ to $\max$, to represent the fact that we now have a different metric for the "goodness" of a path).

The section you quoted from Wikipedia is talking about a small optimization to this variant of Dijkstra's algorithm. However, you can use the variant of Dijkstra's algorithm in Section 13.3 of those lecture notes directly, without the optimization mentioned in Wikipedia, if you like -- and that's easier to understand.

---
Tags: algorithms, graphs
---


title: Variant of the knapsack problem

text:
# Question
Title: Variant of the knapsack problem
How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant $p$ ? This is the same problem (max weight of $W$, every item have a value $v$ and weight $w$) but you can only add $p$ item(s) to the knapsack and obviously need to optimize the value of the knapsack.

Do we need a 3rd dimension or we could find an other approach without it. I tried to simply add the number of item in the knapsack in the cell and taking the max value at the end with the number of item \<= $p$ but it is not the BEST solution.

# Answer
Very nice question!

You are twice right:

1. Propagating the number of items in the knapsack does not lead to optimal solutions.
2. *One* solution consists of adding a third dimension. This is rather simple but it is necessary to take some facts into account when doing so. Note however that it is not the only alternative

In the following, I am assuming that you are familiar with the solution based in dynamic programming. In particular, **I will not discuss how to traverse the table backwards to determine the solution**.

Let us first focus on the typical case: *the number of items is unrestricted*. In this case, you just build a table $T$ where $T\_{i,j}$ contains the optimal value when the overall capacity of the knapsack equals $i$ and only the first $j$ items are considered. From here:

$T\_{i,j} =\max\\{T\_{i,j-1}, T\_{i-w\_j,j-1}+v\_j\\}$

where $w\_j$ and $v\_j$ stand for the weight and value of the $j$-th item respectively. If $C$ is the overall capacity of your knapsack and there are in total $N$ items the optimal solution is given by $T\_{C, N}$. This algorithm is known to run in pseudo-polynomial time and one of its beauties is that it only considers those combinations that fit the maximum capacity.

However, this is not enough when adding your constraint: a maximum number of items $p$. The reason is that the previous recurrence formula does not take into account different combinations of items:

1. First, if $T\_{i,j-1}\<(T\_{i-w\_j,j-1}+v\_j)$ then $T\_{i,j}=(T\_{i-w\_j,j-1}+v\_j)$ so that the $j$-th item is added to the knapsack in spite of the maximum number of items considered, $p$ ---so that you might be violating your constraint. Well, you might be tempted here to apply the preceding formula keeping track of the number of items inserted at each step and do not add others if the number of items currently in the knapsack exceeds $p$ but,
2. Second, if $T\_{i,j-1}\>(T\_{i-w\_j,j-1}+v\_j)$ then $T\_{i,j}=T\_{i,j-1}$ so that this item is not added but that might be a big mistake in case the optimal solution $T\_{i,j-1}$ already consists of the maximum number of items to insert into the knapsack. The reason is that we are not properly comparing: on one hand, to preserve the optimal solution consisting of $p$ items selected among the previous $(j-1)$; on the other hand, to insert the $j$-th item and, additionally consider the best subset with $(p-1)$ items among the previous $(j-1)$.

So that a first solution consists of adding a third dimension. For your case, let $T\_{i, j, k}$ be the optimal solution when the capacity of the knapsack is $i$, only the first $j$ items are considered and it is not allowed to put more than $k$ items in the knapsack. Now,

* If you are computing $T\_{i, j, k}$ for a number of items strictly less or equal than the number of items that can be inserted ($j\leq k$) then proceed as usual but using the same value of $k$: $T\_{i,j,k} =\max\\{T\_{i,j-1,k}, T\_{i-w\_j,j-1,k}+v\_j\\}$
* Now, if you have to compute $T\_{i, j, k}$ for a number of items strictly larger than the number of items that can be inserted ($j\> k$) then: $T\_{i,j,k} =\max\\{T\_{i,j-1,k}, T\_{i-w\_j,j-1,k-1}+v\_j\\}$

The first expression should be clear. The second works since the $(k-1)$-th layer of the table $T$ keeps track of the best combination of $(k-1)$ items among the first $(j-1)$ as required above.

An efficient implementation of this algorithm does not need to compute $T\_{i, j, k}$ for all $k$. Note that the preceding recurrence relationships relate layer $k$ with $(k-1)$ and thus, it is possible to alternate between two successive layers (e.g., if you are interested in the optimal solution with $k=4$ you just use two consecutive layers: 0 and 1, 1 and 2, 2 and 3, 3 and 4 and you're done). In other words, this algorithm takes twice the memory required by the traditional approach based on dynamic programming and thus, it can be still run in pseudo-polynomial time.

Be aware, however, that this is not the only solution! And there is another you might find more elegant. In the preceding formulae, we retrieved the optimal solution which consisted of no more than $(k-1)$ items among the first $(j-1)$ as $T\_{i, j-1, k-1}$. However, it should be clear that this is precisely equal to $\max\limits\_{p=0,j-1}\\{T\_{i, p}\\}$ just by using the original table!! ie., the optimal solution with no more than $k$ items can be also retrieved by considering the optimal solutions with 1 item, 2 items, 3 items, ... $(j-1)$ items ... To make this formulation work you should also keep track of the number of items considered in every partial solution so that you will need two integers per cell. **This memory occupation results in precisely the same memory requirements of the algorithm shown above (using a third dimension in the form of layers $k$)**.

Hope this helps,
> 9 votes

---
Tags: algorithms, optimization, dynamic-programming, knapsack-problems
---


title: BST Successor Proof

text:
# Question
Title: BST Successor Proof
I'm studying for my CS final and I can't seem to get the anywhere with one of the questions.

This is the question:

Prove that if a node in a BST has a successor, but has no right child, then its successor must be an ancestor. (We will consider only BSTs with distinct elements.)

I know that a successor is the node that replaces the deleted node, and that we only need to worry about this case when the node being deleted has two children, but I can't seem to start this proof.

Any help?

# Answer
This might depend delicately on how you define a successor. From what I understand of this and from your post, a **successor to a node `N` is the node that replaces `N` when `N` is deleted** (preserving the properties of BST). This definition doesn't necessarily mean that each node has a unique successor. Consider the following example:

```
10
  \
   14
  /
13

```

What is the successor to the node 14? It can just as easily be either `10` or `13`.

I think this might be a counter-example to your question's claim. Delete node `14` and a BST tree that results is

```
10
  \
   13

```

`14` had no right child *and* its successor is not its ancestor.

Am I not understanding something?
> 1 votes

# Answer
This is my attempt - I'm not sure if it's correct or not.

Start proof:

* A successor is the node that replaces a node when it is deleted, while preserving the properties of the BST.
* The tree is traversed in post order (Left, Right, Node).

Consider the tree:

```
    A
     \
      B
     /
    C

```

The order in which the nodes are visited to delete node B is as follows:

C, B

C has already been visited. B’s successor must be A.

End proof.
> -1 votes

---
Tags: proof-techniques, binary-trees, binary-search
---


# Question
Title: Describing a Turing machine that computes $\lceil\log_{2}(n)\rceil$
I need to describing a Turing machine that computes $\lceil\log\_{2}(n)\rceil$ I know that:

n = 1, 2, 3, 4, 5, 6, 7, 8, ...
f(n) = 0, 1, 2, 2, 3, 3, 3, 3, ...

So I'm thinking of putting $n$ on the tape. Then keeping a count of how many times I multiply 2\*2 until it is greater than than $n$. For example for n=5, 2\*2\*2=8, number of two's is 3 so then $f(n)$ is 3. I don't know how to translate this to the ticker tape of the Turing machine.

But would something like this work? Put $n$ 1's on the tape followed by a 0. Compute 1^(2^1), then check if 1's on the left of the 0 on the tape is less than or equal to the 1's on the right of the 0. If its not then repeat it for 1^(2^(1)). It keeps doing this until the left side has less than or equal number of 1's.

# Answer
> 2 votes
A simple approach is:

1. Put $i \gets 0$ on the tape (store $i$ on the tape after $n$).
2. Compute $2^i$ (store it on the tape after $i$).
3. Check if $2^i \ge n$. If yes, output $i$. If no, increment $i$ and go to step 2.

You can work out the gory details on your own -- this is your exercise, after all! This requires you to be able to compute $2^i$ (given $i$) and to be able to compute $i+1$ (given $i$), but it sounds like you already know how to do that.

# Answer
> 2 votes
You can represent n by 1's in your tape, if n = 2 then you have 11 marks the beginning and the end of the tape to make it easier. Then for every two 1's erase the first and leave the 2nd.

I think the rest will be easy to figure out :)

---
Tags: complexity-theory, turing-machines, automata
---


# Question
Title: On the minimum order of a maximal independent set in cycle graphs and path graphs
I can see from this question that a $K\_{r + 1}$-free graph with $n$ vertices and $e$ edges contains an independent set of order at least $$\frac{n}{2e/n + 1} \tag{1} $$ Since for a $C\_{n}$/$P\_{n}$ we know how many edges it contains it is easy to determine (1).

However, are there any particularities of cycle graphs and path graphs that would allow me, for such a graph $G$, to determine exactly $\min\\{\mathopen|A\mathclose| : A\text{ is a maximal independent set of } G\\}$, i.e. the minimum number of vertices that a maximal independent set of $G$ must contain.

# Answer
> 2 votes
The smallest maximal independent set in a cycle or path of length $n$ clearly has size about $n/3$. This can be seen by inspection and certainly doesn't need anything like Turán's theorem.

---
Tags: graphs
---


# Question
Title: Looking for books on creating and understanding theorems targeted at Computer Science
In studying logic to understand verifying programs I have found that there are books on logic targeted at Computer Science e.g.

With regards to books on understating theorems targeted at Computer Science I find only one that may fit. As I don't have the book I can't say for sure.

Are there any books for understating theorems targeted at Computer Science? In other words are there books for understating syntax, semantics and construction of theorems that don't rely on a heavy math background and that give examples more from the world of computer science and explain in a style more natural to a person in computer science.

EDIT

After seeking more on this topic I have come upon the phrases "informal mathematics" and "mathematical discourse" which are starting to turn up useful info from Google. In particular the following: Understanding Informal Mathematical Discourse found at Understanding Informal Mathematical Proofs

# Answer
> 4 votes
What do you expect from such a book? The comment by JeffE is a good one: sensible textbooks do this. Sorry for this is not a book recommendation, but merely a different way of thinking. Coming up with just the right properties, invariants and theorems is hard. It requires time, insight and experience. Not *everything* can be learned from a book.

Why not start with something simple and try to discover those useful theorems yourself? Math is a necessary tool for expressing yourself accurately. You don't necessarily need it right away though. Start with something simple, say your favorite sorting algorithm. Without writing any math if you don't want to, think about *why* and *how* the algorithm works.

Maybe with some thinking you'll convince yourself why it works and what the right invariant and properties could look like. If you already have some experience with program verification as you say, try to prove the program is correct. If you get totally stuck, then go to a textbook or a paper and see how it can be done. In some cases, you might even discover something new and exciting the author of the algorithm hasn't considered.

# Answer
> 4 votes
Algorithm Design, by John Kleinberg and Eva Tardos looks like it may be what you want. Here's the description on Amazon:

> Algorithm Design introduces algorithms by looking at the real-world problems that motivate them. The book teaches students a range of design and analysis techniques for problems that arise in computing applications. The text encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.

However, since the fields of computer science and mathematics are so closely related, you really should take the time to understand the math side of things. This looks like it could be a good starting point though

# Answer
> 4 votes
(in addition to all the great books that others have recommended)

For proofs, hands down:

How to Prove it: A Structured Approach by Daniel Velleman.

It has the best paced and detailed introduction into proving techniques. I read many books on the subject of proofs, but this one helped me really get the hang of it.

More introductory reading would be "How to think like Mathematician"

# Answer
> 3 votes
I personally didn't understand how to construct theorems and proofs at all until I took a proof-based calculus course my first year of college. I don't think much of it applies directly to computer science but the method of thinking has helped me along greatly.

You may have more success looking at math books rather than computer science books. Most theoretical computer science books I've seen are either fairly informal or highly technical. Someone without a good math background won't learn much about formal proofs from either. There may be some good options for you in CS, but if you're still unsatisfied, see if there are math books that are known to be particularly good at showing how to state theorems and proofs. Especially if you can get one in something like Discrete Math or Number Theory, which you'll find at least some applications for in CS. (Some Discrete Math books have chapters on theorems and proofs which you may find useful).

The other answers allude to it a bit, but to be clear: there is absolutely no substitute for experience when it comes to clearly and formally writing theorems and proofs. Whether you get it from a class, a math book, a CS book, or a book about theorems in particular is up to you, but at the end of the day reading and writing them is the only way to learn.

# Answer
> 2 votes
The more advanced an algorithm is, the heavier the required math will be. The field of (designing and analyzing) algorithms is a mathematical field. The algorithms are based on mathematical theorems and concepts, you cannot understand an algorithm without understanding the mathematical bases of the algorithm.

If you are looking for books on informal reasoning there are quite a few, I don't have any favorite ones so I will leave the book recommendation part of our question to others. You can also have a look at the lecture notes from our CSC165: Mathematical Expression and Reasoning for Computer Science.

# Answer
> 1 votes
try this comprehensive/outstanding new free online ref of over 875 pgs. Mathematics for Computer Science by Lehman, Leighton, Meyer based on MIT class 6.042

---
Tags: logic, proof-techniques, books
---


title: Data structure for map on intervals

text:
# Question
Title: Data structure for map on intervals
Let $n$ be an integer, and let $\mathbb{Z}$ denote the set of all integers. Let $\[a,b\]$ denote the interval of integers $\\{a,a+1,a+2,\dots,b\\}$.

I am looking for a data structure to represent a map $f:\[1,n\] \to \mathbb{Z}$. I want the data structure to support the following operations:

* $\text{get}(i)$ should return $f(i)$.
* $\text{set}(\[a,b\],y)$ should update $f$ so that $f(a)=f(a+1)=\cdots=f(b)=y$, i.e., update $f$ to a new map $f'$ such that $f'(i) = y$ for $i \in \[a,b\]$ and $f'(i) = f(i)$ for $i \notin \[a,b\]$.
* $\text{stab}(i)$ should return the largest interval $\[a,b\]$ such that $i \in \[a,b\]$ and $f$ is constant on $\[a,b\]$ (i.e., $f(a)=f(a+1)=\cdots=f(b)$).
* $\text{add}(\[a,b\],\delta)$ should update $f$ to a new map $f'$ such that $f'(i) = f(i) + \delta$ for $i \in \[a,b\]$ and $f'(i) = f(i)$ for $i \notin \[a,b\]$.

I want each of these operations to be efficient. I would count $O(1)$ or $O(\lg n)$ time as efficient, but $O(n)$ time is too slow. It's OK if the running times are amortized running times. Is there a data structure that simultaneously makes all of these operations efficient?

(I've noticed a similar pattern come up in a several programming challenges. This is a generalization that would suffice for all of those challenge problems.)

# Answer
> 4 votes
I believe logarithmic time for all queries is achievable. The main idea is to use an interval tree, where each node in the tree corresponds to an interval of indices. I'll build up the key ideas by starting with a simpler version of the data structure (that can support get and set but not the other operations), then add features to support the other features as well.

## A simple scheme (supports get and set, but not add or stab)

Say that an interval $\[a,b\]$ is *flat* if the function $f$ is constant on $\[a,b\]$, i.e., if $f(a)=f(a+1)=\cdots =f(b)$.

Our simple data structure will be an interval tree. In other words, we have a binary tree, where each node corresponds to an interval (of indices). We'll store the corresponding interval $I(v)$ in each node $v$ of the tree. Each leaf will correspond to a flat interval, and they'll be arranged so that reading out the leaves left-to-right gives us a sequence of consecutive flat intervals which are disjoint and whose union is all of $\[1,n\]$. The interval for an internal node will be the union of the intervals of its two children. Also, in each leaf node $\ell$ we will store the value $V(\ell)$ of the function $f$ on the interval $I(\ell)$ corresponding to this node (note that this interval is flat, so $f$ is constant on the interval, so we just store a single value of $f$ in each leaf node).

Equivalently, you can imagine that we partition $\[1,n\]$ into flat intervals, and then the data structure is a binary search tree where the keys are the left endpoints of those intervals. The leaves contain the value of $f$ at some range of indices where $f$ is constant.

Use standard methods to ensure that the binary tree remains balanced, i.e., its depth is $O(\lg m)$ (where $m$ counts the current number of leaves in the tree). Of course, $m\le n$, so the depth is always at most $O(\lg n)$. This will be helpful below.

We can now support the get and set operations as follows:

* $\text{get}(i)$ is easy: we traverse the tree to find the leaf whose interval contains $i$. This is basically just traversing a binary search tree. Since the depth is $O(\lg n)$, the running time is $O(\lg n)$.
* $\text{set}(\[a,b\],y)$ is trickier. It works like this:

1. First, we find the leaf interval $\[a\_0,b\_0\]$ containing $a$; if $a\_0 \< a$, then we split this leaf interval into the two intervals $\[a\_0,a-1\]$ and $\[a,b\_0\]$ (thus turning this leaf node into an internal node and introducing two children).
    2. Next, we find the leaf interval $\[a\_1,b\_1\]$ containing $b$; if $b \< b\_1$, we split this leaf interval into the two intervals $\[a\_1,b\]$ and $\[b+1,b\_1\]$ (thus turning this leaf node into an internal node and introducing two children).
    3. At this point, I claim that the interval $\[a,b\]$ can be expressed as the disjoint union of $O(\lg n)$ intervals corresponding to some subset of $O(\lg n)$ nodes in the tree. So, delete all the descendants of those nodes (turning them into leaves) and set the value stored in those nodes to $y$.
    4. Finally, since we modified the shape of the tree, we'll perform any necessary rotations to re-balance the tree (using any standard technique for keeping a tree balanced).

Since this operation involves a few simple operations on $O(\lg n)$ nodes (and that set of nodes can be easily found in $O(\lg n)$ time), the total time for this operation is $O(\lg n)$.

This shows that we can support both the get and set operations in $O(\lg n)$ time per operation. In fact, the running time can be shown to be $O(\lg \min(n,s))$, where $s$ is the number of set operations performed up until now.

## Adding support for add

We can modify the above data structure so that it can also support the add operation. In particular, instead of storing the value of the function in the leaves, it'll be represented as the sum of numbers stored in a set of nodes.

More precisely, the value $f(i)$ of the function at input $i$ will be recoverable as the sum of the values stored in the nodes on the path from the root of the tree down to the leaf whose interval contains $i$. In each node $v$ we'll store a value $V(v)$; if $v\_0,v\_1,\dots,v\_k$ represent the ancestors of a leaf $v\_k$ (including the leaf itself), then the value of function at $I(v\_k)$ will be $V(v\_0)+\dots + V(v\_k)$.

It is easy to support the get and set operations using a variant of the techniques described above. Basically, as we traverse the tree downward, we keep track of the running sum of values, so that for each node $x$ that the traversal visit, we'll know the sum of values of the nodes on the path from the root to $x$. Once we do that, simple adjustments to the implementation of get and set described above will suffice.

And now we can support $\text{add}(\[a,b\],\delta)$ efficiently. First, we express the interval $\[a,b\]$ as the union of $O(\lg n)$ intervals corresponding to some set of $O(\lg n)$ nodes in the tree (splitting a node at the left endpoint and right endpoint if needed), exactly as done in steps 1-3 of the set operation. Now, we simply add $\delta$ to the value stored in each of those $O(\lg n)$ nodes. (We don't delete their descendants.)

This provides a way to support get, set, and add, in $O(\lg n)$ time per operation. In fact, the running time per operation is $O(\lg \min(n,s))$ where $s$ counts the number of set operations plus the number of add operations.

## Supporting the stab operation

The stabbing query is the most challenging to support. The basic idea will be to modify the above data structure to preserve the following additional invariant:

> (\*) The interval $I(\ell)$ corresponding to each leaf $\ell$ is a maximal flat interval.

Here I say that an interval $\[a,b\]$ is *maximal flat interval* if (i) $\[a,b\]$ is flat, and (ii) no interval containing $\[a,b\]$ is flat (in other words, for all $a',b'$ satisfying $1 \le a' \le a \le b \le b' \le n$, either $\[a',b'\]=\[a,b\]$ or $\[a',b'\]$ is not flat).

This makes the stab operation easy to implement:

* $\text{stab}(i)$ finds the leaf whose interval contains $i$, and then returns that interval.

However, now we need to modify the set and add operations to maintain the invariant (\*). Each time we split a leaf into two, we might violate the invariant if some adjacent pair of leaf-intervals have the same value of the function $f$. Fortunately, each set/add operation adds at most 4 new leaf intervals. Also, for each new interval, it is easy to find the leaf interval immediately to the left and right of it. Therefore, we can tell whether the invariant was violated; if it was, then we merge adjacent intervals where $f$ has the same value. Fortunately, merging two adjacent intervals does not trigger cascading changes (so we don't need to check whether the merger might have introduced additional violations of the invariant). In all, this involves examining $12=O(1)$ pairs of intervals and possibly merging them. Finally, since a merger changes the shape of the tree, if this violates the balance-invariants, perform any necessary rotations to keep the tree balanced (following standard techniques for keeping binary trees balanced). In total, this adds at most $O(\lg n)$ additional work to the set/add operations.

Thus, this final data structure supports all four operations, and the running time for each operation is $O(\lg n)$. A more precise estimate is $O(\lg \min(n,s))$ time per operation, where $s$ counts the number of set and add operations.

## Parting thoughts

Phew, this was a pretty complex scheme. I hope I didn't make any mistakes. Please check my work carefully before relying upon this solution.

---
Tags: algorithms, data-structures, trees, intervals
---


# Question
Title: Counting the number of N-dimensional coprime integer vectors
I am looking for an efficient way to count the number of coprime vectors in a finite and bounded set of integer vectors.

The vectors in my set are $N$-dimensional integer vectors whose components are bounded on the top and bottom by an arbitrary value $K$. Let $x = \[x\_1,x\_2,\ldots,x\_N\]$ denote a vector from this set. Then $x$ is *coprime* if the greatest common denominator of all its elements is 1. That is, $\gcd(x\_1,x\_2,...,x\_N)=1$.

Some 3-dimensional coprime vectors include: $x = \[1,2, 3\] , \[6, 10, 15\] ,\[0, 1, 1\]$
Some 3-dimensional non-coprime vectors include: $x = \[2,4,6\] ,\[0, 10, 15\] ,\[0, 12, 12\]$

For fixed $N$ and $K$, my set contains a total of $(2K+1)^N$ distinct integer vectors as each of the $N$ elements can take on integer values from $-K,\ldots,0,\ldots,K$. A brute-force approach for counting the number of coprime vectors consists of iterating over each of the $(2K+1)^N$ possible vectors and checking to see whether they are coprime (using, for instance, this function). Unfortunately, this approach quickly runs into time and memory issues for large values of $N$ and $K$.

I am wondering if anyone can think of a way to smart algorithm to do this. Ideally, I am looking to implement this algorithm as a MATLAB function that can number of coprime pairs given $N$ and $K$ as its input.

# Answer
> 2 votes
For $N=2$, the problem is easy: count the number of non-coprime pairs, by expressing it as a union over all possible values for their common divisor. In particular, a pair $(x\_1,x\_2)$ is *not* coprime if there exists a $d\>1$ such that $d|x\_1$ and $d|x\_2$; for fixed $d$, it's easy to count the number of such pairs, so now just sum over all possible values of $d$.

For $N=3$, you could try using the following characterization:

* $\gcd(x\_1,x\_2,x\_3)=1$ iff either (a) $\gcd(x\_1,x\_2)=1$, or (b) $\gcd(x\_1,x\_2)\>1$ (so define $d=\gcd(x\_1,x\_2)$) and $\gcd(d,x\_3)=1$.

These two conditions are mutually exclusive, so you can count the number of type-(a) triples and the number of type-(b) triples and then sum those two numbers, to get the number of co-prime triples.

You can count the number of triples of type-(a) quickly (by reducing to the $N=2$ case). You can also count the number of triples of type-(b) quickly, by summing over all possible values of $d$ (for fixed $d$, the number of type-(b) tuples with a particular value of $d$ reduces to a smaller version of your problem with $N=2$ and a smaller value of $K$).

I think you can probably see how to generalize this to larger $N$, giving you a recursive algorithm to solve your problem for general $N$. I'll let you work out the details.

---
Tags: discrete-mathematics, counting, primes
---


title: Interpreting a Language

text:
# Question
Title: Interpreting a Language
I'm having trouble understanding some language notation, primarily what rules I can take away from it. The language is as follows:

$\qquad L = \\{a^n b^m b^p c^p b^{n-m} \mid n \> 0, m \< n, p \> 2\\}$

My goal is to create a context free grammar from this, but I can't get my ahead around the rules in place here. In plain English, it's clear that any string for this language must have a positive number of a's in it, but what is going on with the multiple b's? Do I take this as the string must be in some form like so:

$\qquad aaa-b-bbb-ccc-bb$ (n=3, m=1, p=3)

where the bunches of b's are just distinct sequences? Or is there something else I should be doing in order to satisfy this?

# Answer
First of all, note that your quest for "rules in place" is probably doomed. This looks pretty much like an exercise problem you would pose in class; there is not necessarily an intuitive rule or semantics. It's just a playground for developing your skills. Therefore, it may be more helpful to strap on theory glasses and just look at the formal object given to you.

Now, for your problem. In order to get to a context-free grammar, it can be useful to identify "phases" a grammar can work through. A good first step is to identify which parts of the word are "connected" by the restrictions in place and which are independent of each other. If you find intersecting dependency arcs, you either have a non-context-free language (which you can check) or you need to represent your language differently (sometimes restrictions are redundant or seem to imply dependencies that are not really there¹).

> Here, note that your words have the form
> $\qquad a^n b^m \dots b^{n-m}$.
> Why can I remove a part for an intuitive look? Because I cut away $b^p c^p$ which can clearly by generated by a standard grammar and independently of the rest. Now, the above is just
> $\qquad a^n b^n$
> if you remember to insert $b^p c^p$ at some point in $b^n$.
> Try to come up with a grammar along these lines. Take care about corner cases and the exact restrictions on $m,n,p$! And, of course, prove correctness.

Another strategy that can sometimes work better is to build a PDA and convert it into a(n ugly) grammar by the standard construction.

---

1. A simple example: $a^nb^nc^n$ is not context-free, so $a^na^na^n$ is not. Right? Wrong: $a^na^na^n = a^{3n}$ is clearly regular.
> 3 votes

# Answer
On your question about what the language $L$ means:

Yes, that's right, except that the dividing lines between the blocks are not provided to you. Thus, one example string in $L$ would be `aaabbbbcccbb` ($n=3,m=1,p=3$) (not `aaa-b-bbb-ccc-bb`; you're not given the dividing line). Another example string would be `aaabbbbbbccccb` ($n=3,m=2,p=4$).

If it helps understand what the notation means, here is another equivalent way to express the language $L$:

$$L = \\{a^n b^{m+p} c^p b^{n-m} | n\>0, m\<n, p\>2\\}$$

though this equivalent formulation might not make your life of finding a context-free grammar any easier (actually, it'll probably make things harder).

Finding the context-free grammar is up to you; I'm just trying to help you understand what the language $L$ is.
> 1 votes

---
Tags: formal-languages
---


# Question
Title: What happens when time slices are too short or too long?
What bad things can occur when the lengths of the time slices in a multitasking system are too small? What can happen when they are too big? How should the length of the time slice be chosen?

# Answer
> 4 votes
A context switch between two tasks takes a certain amount of time. Let's say that there are two runnable tasks on a particular system. Each context switch will take about the same time, say 0.1ms. If there is a context switch every 10ms, then each task is left to run for 9.9ms, then out of every 1ms period, 99% is spent running the tasks and 1% is spent in context switches. If we increase the frequency of context switching to be every 1ms, then context switches waste 10% of the time. In the extreme case, if we increase again to have a context switch every 0.1ms, then the whole processor time is spent in context switches, there is no time left to run the applications.

Thus, for performance, it is best to have context switches as rarely as possible. This increases the time that is available to actually run applications. However, if context switches are too rare, then there is a delay before an application can react to an external event. This is not a problem for a purely computational program, but it is a problem for a program that does input/output. For example, the frequency of context switches is only once per second, then computational tasks don't waste time, but a network server may take up to one second to reply (or more if there are more than two tasks), an interactive program may take up to one second to react to a keypress, etc.

Thus the operating system scheduler must find a balance between computational performance and reactivity. Sophisticated schedulers try to find out which tasks are computational and which ones are I/O-bound, and give I/O-bound tasks shorter but more frequent time slices and give computational tasks longer but less frequent time slices.

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


# Question
Title: Isn't Functional Programming just Imperative Programming in disguise?
A YouTube video I was watching explained the differences between Imperative and Functional programming by demonstrating how the numbers from `1` to `10` are summed up in Java and in Haskell respectively.

In Java, you must explicitly state each step and assign the result of each step to a variable - something like the following

```
int total = 0;
     for (int i = 1; i <= 10; i++){
         total = total + i;
     }
return total;

```

In Haskell, you can simply say:

```
sum(1..10)

```

**My question is:** There obviously is something going on in the background of a Functional language, and that something must be some sort of Imperative process. It seems like Functional Languages are really just some sort of Imperative-Language APIs. For example, I can create part of a functional language by defining a method `sum(int start, int end)` in Java. Did I really create a new type of language right there, or did I just define a set of Imperative method calls that hide imperative instructions from you?

I hope it's clear what I am struggling to understand.

# Answer
If we peel off the syntactic sugar on the front and the code generation on the back and compare what happens in between when converting source to running code for imperative languages, such as C or Java with functional languages such as ML or OCaml we will generally find the following differences in what, why, and how.

Mutable vs. immutable

With functional programming one tends to use immutable values which means that we don't have to worry if a value changes by a means external to our current function. When used correctly this removes any problems related to side effects.

Focus: Data versus function.

When one thinks of coding in imperative one first thinks of data structures and then what methods they need, when working with functional programming one first thinks of what functions are needed and then makes the data types needed. Most of the data types are either lazy list, (think stream or infinite list) or discriminated unions. When the discriminated union is recursive you instantly have created a tree or graph without having to write all of walking code.

Generics/Parametric polymorphism

This one is interesting, and if I have my facts correct, was invented with functional programming and then transplanted to imperative programming. So if you like generics thank the functional language designers.

Referential transparency/Parallelization

Because of referential transparency functional code can be more easily ported to parallel computing.

Higher order function/compositionality

Since functions can create new functions and return functions, creating new functions is based on other functions is as easy as creating new expressions instead of writing entire new methods. This leads to morphisms which are very useful if the problem you are solving can be expessed with math. Doing set transformations, think SQL and updates, is so much easier with functional programming. As Wandering Logic noted this is where functional programming languages excel.

Typing: Static versus inference.

Since the types are inferred as opposed being set by the programmer during writing, more checks can be to ensure the correctness of the code and often the functions will be made generic as opposed to being of a set type.

Pattern Matching vs switch statement

When combining matching with discriminated unions, your matching is checked to ensure you have covered every outcome. How many times have you had a run time error because you missed a case with a switch statement.
> 10 votes

# Answer
A functional programming *language* is notable for what it *prohibits*. It prohibits modifying an existing variable or data structure. You can program in a "functional style" in some imperative programming languages, but the language won't protect you from accidentally modifying an existing variable or data structure. For example, here is a recursive, functional, version of `sum` in Java:

```
int sum(int start, int end) {
  if (start > end) return 0;
  else {
    int total = start + sum(start+1, end);
    return total;
  }
}

```

Where functional programming languages excel is that they all have "first-class" functions. That is: a function can be used as a value, just like an integer or a data structure. Some imperative languages also have first-class functions (notably C and C++), but in Java you have to fake it with an object with a single method (usually called `apply()` or something.) First-class functions allow us to generalize the `sum` function to a function that reduces any operator:

```
interface IntegerOperator {
  int apply(int a, int b);
}

int sum(IntegerOperator op, int start, int end) {
  if (start > end) return 0;
  else {
    int total = op.apply(start, sum(op, start+1, end))
    return total;
  }
}

class AdditionOperator implements IntegerOperator {
  int apply(int a, int b) { return a+b; }
}

int total = sum(new AdditionOperator(), 1, 10);

```

If I were writing in a functional programming language I would know that every function is really a function (it returns the same value every time it is called with the same parameters), so I would know that in:

```
int total1 = sum(new ReallyStrangeOperator(), 1, 10);
int total2 = sum(new ReallyStrangeOperator(), 1, 10);

```

`total1` and `total2` have the same value (so for example, I could optimize out the second call to `sum`), whereas in an imperative programming language I have no clue about whether `ReallyStrangeOperator(1,2)` returns the same value every time or not.
> 9 votes

---
Tags: programming-languages, functional-programming, programming-paradigms, imperative-programming
---


title: Complexity of Double-Horn-SAT?

text:
# Question
Title: Complexity of Double-Horn-SAT?
On one hand, Horn-SAT is known to be tractable in linear time - where Horn-SAT is the problem of deciding whether a given set of propositional Horn clauses (with at most one positive literal) is satisfiable or not. On the other hand, Double-SAT is NP-complete (see this post : Proving Double-SAT is NP-complete) - where Double-SAT is the problem of deciding whether a given set of propositionnal clauses has at least two models.

Let Double-Horn-SAT be the problem of deciding whether a given set of propositional Horn clauses has at least two models.

What is the complexity of Double-Horn-SAT ?

# Answer
Double-Horn-SAT is polynomial-time solvable.

Given a set of Horn-clauses $X = \\{C\_1,C\_2,...,C\_n\\}$ and a solution $x\_1=b\_1,x\_2=b\_2,...,x\_n=b\_n$, $b\_i \in \\{true,false\\}$ we can observe that a second solution *must* differ in at least one variable $x\_i$. So we can run the Horn-SAT algorithm $n$ times on the augmented set $X\_i' = X \cup \\{ \lnot x\_i \\}$ if in the first solution $x\_i = true$ or on the augmented set $X\_i' = X \cup \\{ x\_i \\}$ if in the first solution $x\_i = false$. If we find a solution for one of the $X\_i'$ then it is a valid solution for the original set $X$, too and by construction it differs from the first one; otherwise the original set doesn't have a second solution, as can be easily proved by contradiction.

See also the question "Complexity of finding a second solution given a correct solution to an NP-complete problem" on cstheory and Laurent Juban, Dichotomy theorem for the generalized unique satisfiability problem (1999)
> 4 votes

---
Tags: complexity-theory, np-complete, satisfiability, complexity-classes
---


# Question
Title: Where can I find rules for source to source transformation optimization rules?
Upon reading Do source code optimizers exist? I knew that such programs existed but the ones I have worked with use a set of rules to drive a transformation algorithm. Ira Baxter provided a link to the tools running the algorithms with his answer but what I was more after from the question was the rules. In the comments Ira noted the Irvine Program Catalog.

Are there any more papers, sites, etc. that list such rules?

I will accept any answer but have a preference for rules used with functional languages.

# Answer
Martin Feather's thesis and papers (and similar theses from the 70s) are full of examples of such rules for functional languages. See http://dl.acm.org/citation.cfm?doid=357153.357154. (pdf) Most of the formal types like such (functional) rules.

More recent would be any work by Martin Ward using his functional language WSL including his thesis. See http://www.cse.dmu.ac.uk/~mward/martin/papers.

If I were you, I'd look to the Haskell community, which is always trying to optimize functional programs, and particularly to the Haskell compilers which implement many of these ideas.

But I get the impression you're looking for the *the* book of program optimization rules. There are some pretty standard ones based basic algebra as applied to integers, etc. And you can see a bunch of these coded explicitly for DMS in an example of how to define algebra to a program transformation system: Algebra as a DMS domain.

You aren't likely to find "the general book" for the following reasons:

* Every syntax formalism in which rules are represented makes a choice about how to write down the details of the rules. Nobody has agreed on a universal notation; that's not a flaw of software engineering, the mathematicians haven't figured this out yet either. So any rules you find will be cast using a particular encoding scheme. Unless you get the tool that uses this encoding scheme, you probably can't use the rules. (See the algebra example for a specific encoding scheme.)
* "Optimizations" are essentially about equivalent sequences of operations where one sequence is "cheaper" than another by some metric (smaller number of steps, less computation, less memory, less heat, less code, ...) The number of entities for which you can define operations is boundless: booleans, naturals, floats, strings, structs, crossproducts, linkedlists, arrays, arbitary compositions of the above, each with predicates possibly constraining them to a subset (eg., all naturals less than 10). The number of operations you define is equally boundless. Which ones are worth writing down?
* A variation on the above theme is that the syntax and semantics of the programming languages you want to manipulate are egregiously different (did we really need both Java and C#?), or deeply semantically different (COBOL and Prolog, for example), or just outright egregious complex (consider C++11). So your rules need to be case in a form that is dependent on your target language syntax and semantics. And there are *thousands* of those.
* Source to source transformations seem to offer nirvana, but they have limitations. In particular, most ways you can represent a transformation to be matched against code, what it can match has a limited *radius* of the match. If your optimization needs information from "far away", e.g., beyond the radius of what you can write in the rules, no single rule can realize your optimization. You can only succeed by composing more than one rule (and you can succeed spectacularly in theory because Post systems are Turing capable, and most rewrites are Post systems almost trivially). However, writing long strings of transformations to achieve an effect is much like writing long sequences of Turing machine steps: you really, really don't want to do that. So in practice transformation systems usually offer the ability to compose arbitrary code procedures, and source transformations, that make "bigger" source-to-source transformations. So now your real transformations are mixed code and rewrites. Using code from one of those thousands of programming languages. (oops).

My belief (uh-oh, opinion coming up) is that source-to-source transformation tools are really useful, because you can build program manipulation engines with them more easily (by a lot!) than with any procedural code or any other techniques I know about. The differences in syntax and semantics of the target languages means you are pretty much doomed to not find such transformations off the shelf (well, you can pray for C++ to become stable for 20 years, and then maybe you have a chance). So, what is needed is a system which will let you define the rules you need, for the language you want to manipulate, relatively easily, when you need them. (And I've spent the last 18 years of my life building such a system).

Good luck finding the universal ruleset.
> 2 votes

---
Tags: reference-request, term-rewriting
---


# Question
Title: Alternative representations for the zebra puzzle?
All of the solutions for the zebra puzzle have a variable for each of the properties and a domain with the possible values. For instance A for Nationalities, B for pets, ...

Ai with i = 1..5 and the domain for example {Dutch, Spanish, Italian, French, English}

As I've seen in the n-queens puzzle, there can always be multiple representations for a constraint problem. What could be alternative representations for the zebra puzzle?

For example, I was thinking about following representation:

* HouseOne indices 1..4 with domain {1,2,3,4,5}
* HouseTwo indices 1..4 with domain {1,2,3,4,5}
* HouseThree indices 1..4 with domain {1,2,3,4,5}
* HouseFour indices 1..4 with domain {1,2,3,4,5}
* HouseFive indices 1..4 with domain {1,2,3,4,5}

Could this work?

# Answer
One representation is as a constraint program.

Another possible representation is as SAT. One of the key steps in representing this using SAT is to encode "one-out-of-$n$" constraints (where a particular object corresponds to a unique other object, so we need it to correspond to exactly one out of the $n$ possible partners for it); these can be encoded in SAT in multiple possible ways. See Encoding 1-out-of-n constraint for SAT solvers for an overview of some technique for that.

Another possible representation is as an integer linear program (ILP).

Yet another possible representation would be to represent it in the Alloy constraint language. Alloy is especially good when you have many constraint variables that are functions or relations over finite domains, and you need to enforce some constraints on those variables. This looks attractive for the zebra puzzle, because the zebra puzzle involves relationships between (for example) houses and house-owners, and those relations could be encoded as an (unknown) relation or function.
> 1 votes

---
Tags: logic, satisfiability, constraint-programming
---


title: Algorithm to use for a TSP variant

text:
# Question
Title: Algorithm to use for a TSP variant
What type of algorithm would you suggest me to use for this problem? I want to implement an algorithm that minimize the total distance in a graph (TSP) but for only X nodes. Also, we can go as many times we want on every vertices and/or edges. Let's say, on my graph, that I want the minimum distance for visiting every blue node. What algorithm and heuristic would you recommand me? An approximation running in reasonable time would be acceptable.

For this example, this is an undirected graph, the vertices are points in the plane and the cost of an edge is the distance between its endpoints.

# Answer
The minimum weight connected subgraph that includes all the blue vertices is known to be a tree, called a Steiner tree. A depth-first search of the tree will give you a route that visits every blue vertex and whose length is twice the weight of the Steiner tree, since you walk along each edge of it exactly twice. Hence, DFS of a Steiner tree is at most twice the length of the shortest route.

However, computing Steiner trees of general weighted graphs is NP-hard (the decision version was one of Karp's 21 problems). Sanjeev Arora has shown there's a polynomial time approximation scheme for the the Euclidean version of the problem, which is close to the case you're interested in: paper. The Euclidean version corresponds to your version where every possible edge is present (i.e., you have a collection of points in the Euclidean plane and there's an edge between every pair of points, with the weight of the edge equal to the distance).
> 2 votes

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


# Question
Title: Is there a more up-to-date / wider-scope version of the 'Compendium of NP Optimization Problems'
When I was studying Comp Sci, we had Garey & Johnson as a course textbook, with a large collection of NP-Complete problems. But by that time you could also have a look at the Compendium of NP Optimization Problems, online.

However, it seems the 'Compendium' site has not seen any updates in several years. Is that indeed the case? Is there a more up-to-date compendium (perhaps in print) which accounts for further research and contains more problems in more domains?

# Answer
> 5 votes
I know of no compendium that is completely satisfactory in any regard. It seems to be too much of a thankless task maintaining these things, thus I suspect that broad answer to your question is, unfortunately, no.

However, there are several resources which, together, are at least a good start for any search.

In this case, Wikipedia is a fairly decent resource (I guess the contribution model helps overcome some of the problems with a single-curator approach, but you lose the consistency).

If you're interested in Parameterized Complexity, Marco Cesati began a compendium of problems, but like Kann, has (understandably) not kept up with the updates. There's also an online compendium, but it is less comprehensive.

A similar question was also asked on cstheory, attracting a couple of answers, one that caught my eye was the Encyclopedia of Algorithms. I cannot personally vouch for it, but it at least looks useful, or at least useful enough to convince a university library to buy.

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


title: Clarification on Tabu Search

text:
# Question
Title: Clarification on Tabu Search
I need some help in understanding the '*Tabu Search*' Algorithm. (Wikipedia)

I miss a simple explanation to Tabu Search. Anyway, I'm trying to refer to available resources and build an understanding.

***This is what I'm trying to 'digest':***

* *Tabu Search* is an improvement over the *Hill Climbing* algorithm (Ref-1).
* The problem with Hill Climbing is that it does not guarantee about reaching the global optimum, because it only searches on a subset of the whole solution space. It will find the local optimum.
* To get rid of this issue, Tabu Search maintains a 'Tabu List' of previously visited states that cannot be revisited (Ref-2).
* If the tabu list is too large, the oldest candidate solution is removed and it’s no longer tabu to reconsider (Ref-3).

***My questions are,***

1. How does Tabu Search cure the problem of getting stuck in a local optimum? Does it increase the search-space?
2. What is the need of maintaining a list (i.e. Tabu List)? Why not just remember the optimum solution found so far?
3. When the Tabu List is too large, the oldest candidate will be removed. What if this oldest candidate is the global optimum?

*If anyone could explain Tabu Search algorithm using an example, I'm sure these questions would be automatically answered.*

References:

* (Ref-1) Hill Climbing, Wikipedia Article (link)
* (Ref-2) Russell, Stuart Jonathan, et al. Artificial intelligence: a modern approach. Vol. 74. Englewood Cliffs: Prentice hall, 1995. (WorldCat)
* (Ref-3) Luke, Sean. "Essentials of Metaheuristics.". (pdf)

# Answer
> How does Tabu Search cure the problem of getting stuck in a local optimum? Does it increase the search-space?

First, the search method does not affect the size of the search space; it depends only on the problem and it simply contains all possible states. Tabu search (TS) does what local search methods often do: when you get stuck, you allow a non-improving move in the hopes of getting unstuck. TS, in particular, maintains a tabu list. When we do a non-improving move, the tabu list ensures we never move to a previously visited state.

> What is the need of maintaining a list (i.e. Tabu List)? Why not just remember the optimum solution found so far?

As explained, the need of maintaining a list is guiding the search in an "intelligent" way. If you just remembered one state (perhaps that is the best solution found so far), you would be getting out of a local optimum in a "blind way". That is, it is possible you would simply trace your steps back, and then walk into the same local optimum again!

> When the Tabu List is too large, the oldest candidate will be removed. What if this oldest candidate is the global optimum?

If the global optimum is not in tabu list, then it is possible you will find it later. In short, the tabu list (as the name implies) contains all states you for some reason do not want to backtrack to.
> 3 votes

---
Tags: optimization, artificial-intelligence, search-algorithms
---


# Question
Title: "Unusual" coupling between a decision problem and a corresponding optimization problem
There seems to usually be a tight connection between decision problems and (corresponding) optimization problems in general. However, is this always the case?

> Are there examples where the typical "tight coupling" between a decision problem and the correponding optimization problem breaks down or behaves in an unusual way, e.g. have significantly different complexity?

Or, maybe there is a case where there is a cluster of problems that are all closely related, but the "best" or "definitive" version is not obvious or apparent? Also, I am looking for any survey or broad overview or discussion of this apparent basic connection between decision and optimization problems.

A similar question was asked here, but the answers were highly theoretical and it did not seem to yield any specific or tangible examples.

# Answer
> 4 votes
The answer does indeed depend on how you define a "corresponding" problem.

For example, it is well known 2-SAT is easy ("Given a 2-SAT formula, is it satisfiable?"). However, the optimization problem MAX-2-SAT ("Given a 2-SAT formula, find an assignment maximizing the number of clauses") is NP-hard. Even MIN-2-SAT is NP-hard.

For a given decision problem, you can have "corresponding" optimization problems which are either easy or hard, depending on whether we consider a minimization or a maximization problem. The st-connectivity problem is mentioned in the comments: deciding the existence of such a path is easy, finding a shortest st-path is easy, but finding a longest st-path is hard. Another graph theoretic example is with cuts: computing a minimum cut is easy, but computing a maximum cut is again hard.

You also have decision problems that don't have a corresponding optimization problem, such as primality testing.

---
Tags: complexity-theory, reference-request, optimization, decision-problem
---


# Question
Title: Partition an infinite regular language into 2 disjoint infinite regular languages
Given any infinite regular language $L$, how can I prove that $L$ can be partitioned into 2 disjoint infinite regular languages $L\_1, L\_2$? That is: $L\_1 \cup L\_2 = L$, $L\_1 \cap L\_2 = \varnothing$, and $L\_1$ and $L\_2$ are both both infinite and regular.

So far, I thought of:

1. using the pumping lemma such that $$ \begin{gather} L\_1 &= \\{ xy^nz \mid \text{\\(n\\) is even} \\} \\ L\_2 &= \\{ xy^mz \mid \text{\\(m\\) is odd} \\} \\ \end{gather} $$ but couldn't prove that they are dijoint or covering $L$ completely.
2. Using the regular language partitions $\Sigma^\*$ into dijoint equivalence classes, but I haven't figured out how to determine if an equivalence class is regular or infinite.

# Answer
Let $S = \\{ |w| : w \in L \\}$. Parikh's theorem shows that $S$ is an eventually periodic set. Let the eventual period be $\ell$. Since $L$ is infinite, there is some offset $a$ such that $a + k\ell \in S$ for all $k \geq 0$. Thus the language $L\_1 = \\{ w \in L : |w| \equiv a \pmod{2\ell} \\}$ is infinite (it contains all words of length $a + 2k\ell$ for some $k \geq 0$), and the language $L\_2 = L \setminus L\_1$ is also infinite (it contains all words of length $a + (2k+1)\ell$ for some $k \geq 0$, as well as possibly other words). I'll let you show that $L\_1,L\_2$ are both regular.
> 5 votes

# Answer
Every regular language is accepted by some minimal DFA. For an infinite regular language $L$, let's call such a DFA $M\_L$. Consider any state $q$ which can be visited more than once while processing some string in $L$. If $q$ can be visited more than once, it follows that it can be visited any number of times. Define $$L\_1 = \\{w \in L \mid q\text{ is visited an odd number of times}\\}$$ and $$L\_0 = \\{w \in L \mid q\text{ is visited an even number of times}\\}$$ This is a DFA, so there's only one path. Any string in $L$ is accepted by the DFA, and must visit the state some number of times (maybe zero). The state can be visited an unlimited number of times; therefore, we know that there are infinitely many strings in $L\_1$ (since there are words that cause the state to be visited 1 time, 3 times, etc.) and that there are infinitely many strings in $L\_0$ (since there are words that cause the state to be visited 0 times, 2 times, etc.). Any given string is either in $L\_1$ or $L\_0$, and cannot be in both, so $L\_0 \cap L\_1 = \emptyset$. However, any word in $L$ is guaranteed to be in one of these two sets, so $L\_0 \cup L\_1 = L$.
> 9 votes

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


# Question
Title: Example of an algorithm where a low-order term dominates the runtime for any practical input?
Big-O notation hides constant factors, so some $O(n)$ algorithms exist that are infeasible for any reasonable input size because the coefficient on the $n$ term is so huge.

Are there any known algorithms whose runtime is $O(f(n))$ but with some low-order $o(f(n))$ term that is so huge that for reasonable input sizes it completely dominates the runtime? I'd like to use an algorithm like this an an example in an algorithms course, as it gives a good reason why big-O notation isn't everthing.

Thanks!

# Answer
Cryptography is an example, if a degenerate one. For example, breaking AES encryption is $O(1)$ — all you have to do is find the right key among a finite number, $2^{128}$ or $2^{192}$ or $2^{256}$ depending on the key size (assume that enough of the plaintext is known to determine the key unambiguously). However even $2^{128}$ operations would take all of the computers today (a billion or thereabouts, each doing about a billion operations per sceond) more than the lifetime of the universe (about a billion billion seconds).

---

A slightly different way to illustrate why big-O isn't everything is to remark that we sometimes use a different algorithm for small input sizes. For example, take quicksort. With the right choice of pivot (which is a tricky business!), it's $O(n \lg n)$. Quicksort operates by divide-and-conquer: every instance involves doing a lot of sorting of small arrays. For small arrays, quadratic methods such as insertion sort perform better. So for best performance, a quicksort of a large array involves a lot of runs of insertion sort for small sizes.
> 2 votes

# Answer
Two examples come to mind from the field of parameterized complexity and FPT algorithms. This might not be exactly what you are looking for, but here goes.

Consider a graph problem, such as 3-COLORING or HAM-CYCLE. Both problems can be expressed in monadic second order logic, and therefore can be decided in linear time of graphs with bounded treewidth. This is a result of Bruno Courcelle, but the resulting algorithm is far from practical.

The other example is a deep result by Lenstra, saying that integer linear programs (ILP) with a constant number of variables can be solved in linear time. By additional work made by Ravi Kannan, we have that the integer programming feasibility problem can be solved with $O(p^{9p/2})L$ arithmetic operations in integers of $O(p^{2p}L)$ bits in size, where $p$ is the number of ILP variables and $L$ is the number of bits in the input. This again gives rise to FPT algorithms, that are only practical for very small instances.
> 1 votes

# Answer
somewhat related to your question are algorithms that are known to have good performance theoretically but are not used on real problems due to impracticality on smaller instances. in other words like you request, the "advertised performance" is only possible for large inputs in theory, not seen in practical applications. this is sometimes reflected in the Big-Oh estimates, other times not exactly. some algorithms have good theoretical "performance" but are very logically complex and havent ever been implemented by anyone, and therefore the "performance" on practical instance sizes isnt even known, eg as with Maximum Flow problem.
> 0 votes

# Answer
This is kind of a joke but it has a serious side...

Quicksort. It's useful in practice because the $O(n\log n)$ terms dominate the $O(n^2)$ worst case that results from consistently choosing terrible pivots.
> -1 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: Equivalence of two lambda expressions for NOT
I've seen two different lambda expressions for the logical NOT function.
One of them just applies its parameter to constants `true` and `false` internally in a reverse order:

$NOT \\;\\;=\\;\\; \lambda x.\\; x \\; \mbox{false}\\; \mbox{true} \\;\\;=\\;\\; \lambda x. \\; x \\; (\lambda t.\lambda f.f) \\; (\lambda t. \lambda f. t ) $

and the other one which captures two more parameters instead of passing them to the returned function externally, and applies $x$ to them in reverse order too:

$NOT \\;\\;=\\;\\; \lambda x. \\; \lambda t.\lambda f.xft$

of which the other one seems a bit simpler (and it is also simpler when encoded in binary).

So my question is this:
Is there any transformation which could get me from one of these representations to the other?

I see they are equivalent "extensionally", that is, both produce the same results. But I'd like to "prove" it somehow by algebraic transformations, such as those for alpha, beta and eta conversions. Unfortunately, none of these can help me in this case: Alpha is just for renaming. Beta works only for function calls, but we don't have any function call here which could be reduced, since $x$ is free in the function body (not the whole expression, though) in all these expressions until we actually call `NOT` on something. The most close one seems to be the eta, which is related to extensional equivalence and forwarding parameters, but when the parameters are being reversed, it's not a simple forwarding anymore and eta doesn't seem to apply here.

Is there any more conversion rule I'm missing?
(Well, I guess they won't just skip two Greek letters from no particular reason, wouldn't they?)

P.S.: This question is actually a model one, since there are many other definitions for other functions which have several different forms which seem to be extensionally equivalent, but completely different with regard to the known reduction rules. I've chosen the simplest example of this problem.

**Edit:**
To better clarify what I'd like to know, here's a diagram showing the reduction steps for both versions of the `not` function: http://sasq.comyr.com/Stuff/Lambda/Not.png

As you can see, they really both reduce to the same results (contrary to what @Jonathan Gallagher was saying below). This is what I already know: that they are confluent, and so they're Church-Rosser equivalent. What I *don't* know however is if there is any conversion rule (similar to alpha, beta & eta) which could allow me to transform one form of `not` to the other. This would allow me to at least make sure if some other functions (more complicated than these two here), are also equivalent, which could be hard when they can reduce to more than just two possible answers. I'd like to know if there's some conversion rule which could allow me to convert one intensional definition into another *when* two functions are already extensionally equivalent (i.e. they give the same results for the same parameters). Or (which would be better) if some function can be converted somehow to the other even if I don't know whether they're extensionally equivalent.

# Answer
> 3 votes
In order to prove the two NOT forms are not generally equivalent, all you have to do is find a term that when each is applied, returns a different result such as:

$NOT1 \\; \lambda x.\\; x \\; \\;\\;=\\;\\; (\lambda x. \\; x \\; (\lambda t.\lambda f.f) \\; (\lambda t. \lambda f. t )) \\; \lambda x.\\; x \\;\\; =\\;\\; \lambda x. \\; x \\; $

$NOT2 \\; \lambda x.\\; x \\; \\;\\;=\\;\\; (\lambda x.\lambda t.\lambda f.xft) \\; \lambda x.\\; x\\;\\; =\\;\\; \lambda t.\lambda f. ft \\; $

# Answer
> -3 votes
Let the first not be called not1 and the second not2. Then you have the following:

$$\mathsf{not1} \\, M \to\_\beta M \\, \mathsf{false} \\, \mathsf{true}$$ and $$\mathsf{not2} \\, M \to\_\beta \lambda t \\, f . M \\, f \\, t \to\_\eta \lambda t . M \\, t \to\_\eta M$$

Now, if we suppose that $$M = \mathsf{true}$$ then the top reduction would give us false while the bottom reduction would give us true -- so that making the identification would seem to give a strange result.

---
Tags: lambda-calculus
---


title: Ball Break Point Problem

text:
# Question
Title: Ball Break Point Problem
I came across following question:

There is a building with N floors. We have a balls of same property and have a breaking point of X floor. i.e, If ball dropped from X+1 floor then the ball will break. if ball is dropped from X or less than X then it wont break. Now design an algorithm to find X if N is given.

My Solution:

Drop the ball from N/2 floor. If ball breaks then X \< N/2. Else X \> N/2. Repeat this process till X is found. but If X is N/2+1 or N/2-1 the number of steps to find X are high.

Is there a better way to Find X?

# Answer
This is the best way to Find $X$. Your algorithm is basically binary search, which is optimal in terms of comparisons.

Let $T(N)$ be the number of ball-drops required in a building with $N$ floors to find $X$. \begin{align} T(1) = & 0 & \text{(no balldrop with one floor)}\\ T(N) = & T(\frac{N}{2}) + 1& \text{(drop ball once, repeat on upper/lower half)} \\ = & T(0) + 1 + \ldots + 1 \in \mathcal{O}(\log n) \end{align}

Each floor $i$ of the $N$ floors can be represented as binary number with $\lceil \log\_2N\rceil$ bits. To identify one number out of a set of $N$ numbers, you have to look at each single bit, hence this takes you $\lceil\log\_2 N\rceil \in \mathcal{O}(\log n)$ comparsons. So in terms of complexity, there is no better way to find $X$.

Of course, you could check one floor above as well as one floor under the current floor, which covers the cases $X=\frac{N}{2}+1$ and $X=\frac{N}{2}-1$, respectively. But you this does not improve your algorithm in terms of $\mathcal{O}$ complexity. Furthermore, you can always construct another worst case for you algorithm, since $N$ is unbounded: The improved algorithm performs poorly when $X=\frac{N}{2}-2$ or $X=\frac{N}{2}+2$. So you could add those cases as well. But then $X=\frac{N}{2}-3$ and $X=\frac{N}{2}+3$ becomes a problem ...
> 0 votes

---
Tags: algorithms
---


# Question
Title: How to use Sigma Scaling in a genetic algorithm
I have a genetic algorithm in Java and I'm testing new types of selections.

For my tests I'm using the De Jong Half Sphere, my fitness function is $x^2 + y^2$.

The selection method used is Sigma scaling :

```
fscaled = S + (fraw −fmean)/2σ

```

Example using S=1

```
 - a) Fitness = 5.927822124 |  After Scaling = 0.900756351532265  | 17.74410992 %
 - b) Fitness = 3.431749363 |  After Scaling = 0.5720553077878213 | 10.27246375 %
 - c) Fitness = 8.428103101 |  After Scaling = 1.2300115637030606 | 25.22835279 %
 - d) Fitness = 2.548825744 |  After Scaling = 0.455785494144756  | 7.629554871 %
 - e) Fitness = 13.07076638 |  After Scaling = 1.841391282832097  | 39.12551868 %

```

I know that sigma scaling should be used with a proportional selection.

* Is this the right way to implement this type of selection?
* If I wanted to minimize the function instead of maximize it how can I accomplish it, should I subtract the mean to each fitness and get the percentage this way or is there a better way?

# Answer
> 2 votes
Well I just tried this :

```
(1.0/f(x,y))+1.0

a) 21.37858466 | After the reciprocate | 1.046775781
b) 1.425432689 | After the reciprocate | 1.701541369
c) 15.48548031 | After the reciprocate | 1.064576621
d) 14.56668667 | After the reciprocate | 1.068649791
e) 41.0387647  | After the reciprocate | 1.024367205

```

With these new fitness I used S=1

> fscaled = S + (fraw −fmean)/2σ

Mean = 1.181182154
Dev Std = 0.260649227

And this was my final result :

```
a) 0.742170015 | 14.8434003 %
b) 1.998198272 | 39.96396544 %
c) 0.776317134 | 15.52634267 %
d) 0.784130642 | 15.68261284 %
e) 0.699183937 | 13.98367874 %

```

These can be used with proportional selections.
I think this is the right way to use sigma scaling. And I used the reciprocate plus one to make this a minimization problem.

---
Tags: algorithms, genetic-algorithms
---


# Question
Title: LL(1) parsing table of left-recursive grammar
I have been taking a compiler course of Stanford on coursera. I have a slight misunderstanding on the parsing table of the following grammar:

S -\> Sa | b

According to the professor parsing table looks like this:

* If the leftmost nonterminal is S and the input is 'a', the production is nothing.
* If the leftmost nonterminal is S and the input is 'b', the production is both `Sa` and `b`.

So if input is just `b`, then it is correct, it will go directly to production `b`. But how will it go to production `Sa` for input `b`?

# Answer
> 7 votes
It appears you have misunderstood your professor. "If the leftmost nonterminal is S and the input is 'b', the production is both Sa and b." means that both Sa and b are correct answers if the leftmost nonterminal is S and the input is 'b'. This means that the parser does not know which production to go to and is stuck.

This means that this grammar cannot be parsed using this type of parser technology. You would either have to change the grammar or use a different type of parser.

# Answer
> 2 votes
This language is left-recursion If you try to derive using the first production, you will get some kind of infinite loop $ S \rightarrow Sa \rightarrow Saa \rightarrow Saaa ... \rightarrow Saaa...aaa$ So it cannot be parsed using LL(1). As @Alex ten Brink said, you should change the grammar.

---
Tags: formal-languages, formal-grammars, parsing, left-recursion
---


# Question
Title: What does the symbol # mean when it comes to languages
Given the following:

$$\\{ w\\#x \mid w^R \text{ is a substring of $x$, with $x$ and $w \in \Sigma^\*$} \\}$$

What does $w\\#x$ denote?

# Answer
> 5 votes
This seems to just be a case of a lack of care in the definition. The symbol $\\#$ isn't anything special, but is commonly used as a separator simply for the reason that it's not normally used for much else.

So in the language in question, all the strings in the language have two parts, $w$ and $x$, which are separated by the character $\\#$, so you can easily tell which part of the string you're processing (just by keeping track of whether you've gone past the $\\#$ or not).

Implicitly the strings $w$ and $x$ *do not* include the symbol $\\#$, but the way it's written (at least in the question) this is not clear.

So, assuming that my interpretation is correct, a more explicit definition might be:

> Let $L$ be a language over $\Sigma\cup\\{\\#\\}$, where $\\# \notin \Sigma$ such that $$L = \\{w\\#x \mid w^{\mathcal{R}}\text{ is a substring of } x, \text{ and } w,x\in\Sigma^{\ast}\\}$$

# Answer
> 0 votes
Usually $\\#$ is just a symbol of the alphabet, i.e. $\\# \in \Sigma$. And $w\\#x$ is just concatenation of the word $w$, the symbol $\\#$, and the word $x$.

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


title: array with a twist

text:
# Question
Title: array with a twist
Imagine that we have an array like structure A with n elements all of which are initially 0. ($A\[i\]=0$)

What is a data structure that supports the following operations:

1) Given an element A\[i\]=0 set A\[i\] to 1 in **O(1) worst case**

2) Given the index i return A\[i\] in **O(1) worst case**

3) Given the index i retrun the smallest $j\geq i$ such that $A\[j\]=0$ or $-1$ if there is no such index in **amortized time as small as possible**

Obviously an array supports the first 2. It doesnt not support 3). How to modify it?

# Answer
At every index of the array you should store an extra detail of the immediate index that contains a "0". Updating this index in an amortised complexity of O(1) will give the solution.

Suppose you are updating the extra detail at an index i and the immediate 0 is found at j. Then, the extra detail will have the value j for all the values between i & j.

Now the amortised cost for every operation will be O(1) for updating and retrieving the stored index is O(1).
> 2 votes

---
Tags: amortized-analysis
---


# Question
Title: Turing machine for $a^i b^j$ with $i \geq j$
I would have a brief question about how to construct a Turing machine that is accepting *only* this language:

$\qquad\displaystyle L\_2 = \\{a^i b^j \mid i \geq j \\}$.

I can't come up with any mechanism that would preserve that there are greater or equal number of 'a's than 'b's. Could you suggest me something?

# Answer
> 2 votes
I concur with the Patrick87's suggestion, so here's my version of it.

For the notation in the state diagram, I've used a slightly lazy version, to hopefully reduce some the normal clutter a little.

1. The start state is marked with the $\>$ (left side, in the middle), and I've included an explicit accept state (marked with the usual double circle and "Acc"), and an explicit reject state (marked "Rej").
2. The transitions are labelled $\alpha \rightarrow \beta,X$, where $\alpha$ is the symbol read from the current tape cell, $\beta$ is the (optional) symbol to write to the tape, and $X \in \\{L,R,S\\}$ is the direction to move the tape head - note that I've included $S$ as a "stay put" option, because it's a pain in the \[expletive\] if you *have* to move the head each time, but it doesn't really change anything.
3. I've also added some blue, numbered arrows to assist in the explanation below.
4. $\sqcup$ is the blank symbol.

Now, behold in all its glory, a Turing Machine (diagram):

Now, a couple of notes by way of explanation. Of course this is essentially Patrick87's suggestion as mentioned, so if you already get that, you don't need to read further. These correspond to the blue numbers in the image:

1. At each iteration of the basic loop (and in particular at the start) if the tape is blank, we move to the accept state, this corresponds to $i=j$ with the trivial case of $i=j=0$ if the tape is blank to start with.
2. If we see a $b$, then there must be too few $a$s, not that this also takes care of the situation where the $a$s and $b$s are out of order. This transition may make more conceptual sense after going through the main loop once, but it still applies at the start.
3. We read an $a$, and replace it with a blank - now we are on the hunt for either a matching $b$, or, if we've already used up all the $b$s, a blank at the end of the string of $a$s.
4. We also have constraints on the format of the string - all the $a$s must come before the $b$s, so to ensure this, we explicitly move past all the $a$s.
5. Once we've done that, if we see a blank, then there aren't any more $b$s, so we can accept (this is the $i \> j$ case).
6. If we do see a $b$, then we'll match it with the $a$ we matched at step 3, but we want to take the last one (otherwise we would need to shuffle the string around, or use extra symbols to denote deletions that aren't blanks or something).
7. Once we hit the end of the string, we move back one, and take off the last $b$ (note that we had to have seen at least one $b$ to get here, so there's definitely one to remove).
8. Now we've matched an $a$ and a $b$, we can return to the start of the unprocessed string - just keep going until we hit a blank. Then we're in the same situation as when we started, just with two less characters in the string.

# Answer
> 0 votes
I would definitely go for Patrick87's approach, since it seems very natural to pair each `a` with a `b` (e.g. marking the letters) and analyze the cases you have when one of them (or both) runs out.

Then you can set a state to reject when, for a marked `a`, there is no `b` to pair out. And you would accept the input on all other cases.

# Answer
> 0 votes
q0 - start state

q4 - accpetance state

B - Blank symbol

Starting from q0 state the input head is at first 'a' on the tape. Explaining regarding the states

q0 : In this state when the input head sees 'a' it replaces with 'X' and moves right changing its state to q1. But if it sees b implying that there are more b's than a's which is not required denoted by moving to state q5 which is literally dead state.

q1 : In this state all a's and b's are left as it is moving right unless it encounters a Blank symbol 'B' or 'Y'(which is the replacement for 'b'). As it encounters 'B' or 'Y' it changes its state to q2 and start moving left of the tape in turing machine.

q2: In this state if it sees 'b' it replaces it with 'Y' and continue to move left and change it's state to q3, But if it sees 'a' denoting more number of a's and is one of the case of acceptance state and if it sees 'X' it denotes equal number of both which is the other case of acceptance.

q3: This state is similar in nature to q1 but it continues to move left unless it sees 'X' which is recent replacement for 'a' identifying that 'a' has been visited.

q4: As explained in q2, if q2 state sees either 'X' or 'a' move to acceptance state and here direction is unimportant.

q5: This state identifies if the input has more number of b's than a's. Here it is not required.

---
Tags: formal-languages, turing-machines, automata
---


title: Why is this not a regular language

text:
# Question
Title: Why is this not a regular language
So I recently had a problem where I had to create a regular language. After consulting my professor on my solution he told me it was close to correct but to check my definition of a regular language. I am somewhat lost on why my solution is not regular?

From my understanding it meets the requirements of being a right regular language since there is only one non-terminal on the right side of the expression and the non-terminal is the rightmost symbol on the right side of the expression. Are pipe symbols not allowed?

# Answer
The derivation $T\_1 \to U\_1$ is not right-regular. It does not fall into the three allowed categories of rules. See Wikipedia on right-regular grammars. If you have a non-terminal on the right-hand side, it needs to be preceded by a terminal.
> 3 votes

# Answer
Since I can't comment:

I still can't get why it is not right regular. As @D.W. mentioned that

> If you have a non-terminal on the right-hand side, it needs to be preceded by a terminal.

But the same reference had another example suggesting that is not the case

A somewhat longer but more explicit right regular grammar G for the same regular expression is given by N = {S, A, B, C}, Σ = {a, b, c}, where P consists of the following rules:

```
S → A
A → aA

```

> A → B

```
B → bC
C → ε
C → cC

```

…where each uppercase letter corresponds to phrases starting at the next position in the regular expression.
> 0 votes

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


title: Right moving turing machine

text:
# Question
Title: Right moving turing machine
I am interested in simulating any turing machine with a turing machine that is allowed only to move right. I guess that it should be pretty standard material and likely it is trivial (or known to be false). Does anyone have a pointer to a reference?

# Answer
A Turing Machine that can only move right can only read its input once, hence I don't see how it could be more powerful than a DFA.

It does have the ability to write to the tape, but it can't go back to read what it wrote, so this can't be used as memory. I seems that it's essentially equivalent to a Finite State Transducer, which are DFAs that have an output tape as well as input, but are no more powerful. In this case, the TM just happens to overwrite the input as it goes, rather than having a second tape.
> 5 votes

---
Tags: computability, turing-machines, computation-models, simulation
---