# Question
Title: Expressing semantics of an array as a function
An assignment questions asks the following:

> Consider an array 'var a : array\[1..10\] of real'. Express the semantics of this array as a function, defining the domain and codomain (you might also be able to write the rule). In this programming language, the subrange '1..10' is viewed as a genuine type, so we can comfortably say that 'a\[13\]' is a type error.

I've come up with a semantic that works as a function, that is: f(a\[$x$\]) -\> $y$ where $x$ is a type defined by the numbers $1$ to $10$ and $y$ is the set of all Real numbers. Does this seems correct?

Would there be any difference if I wrote the function in the opposite way, that is: f($y$) -\> a\[$x$\] ?

# Answer
> 3 votes
First of all, an array *is* and has *always been* a function. It is a function from the set of indices (1..10 in your example) to *memory locations* that hold the array elements. When we write $a\[i\]$ in the programming language, we are just using stylized notation for saying $a(i)$, i.e., apply the function $a$ to $i$ and give me the location that it represents. When we write $$a\[i\] := a\[i\] + 1$$ we are using the memory location $a(i)$ both on the left and the right hand side of the assignment statement. On the left, it means the location itself (also called an *L-value*) and, on the right, it means the contents of the location (also called an *R-value*).

So, treating is an array as a function is no big deal. It is like calling a spade a spade.

However, what your professor wants you to do is to think of the array as a function from the set of indices to *data values* (like real numbers). No memory locations in the picture. That involves a bit more thinking and some rethinking.

In this view, $a$ is a variable whose value is an entire array value (which is now a *function*) and $a(i)$ is a real number. That represents the *R-value* of what we normally write as $a\[i\]$. What do we do about its *L-value*? Well, it doesn't exist, in this view. So, we think of an assignment to a subscripted variable, like the one I have shown as above, as really meaning an assignment to the array variable $a$, like this: $$ a := a\[i: a(i)+1\]$$ Here, the right hand side means "a function $a'$ that is just like $a$, except that the value of $a'(i)$ is going to be $a(i)+1$". So, we take the old function value of $a$, tweak it little to obtain a new function value, and assign it to $a$. Remarkably, with this little bit of rewriting, everything works!

It is quite remarkable that one of our most basic data structures should allow such radically different views. When we add procedures, things get a bit more complicated in the second view, because, as I said, there are no *L-values* for subscripted variables in this view. However, there are more abstract forms of *L-values* (called "acceptors") that can be used to deal with subscripted variables as procedure parameters. So, it all works fine.

For an introductory treatment of the two views, see J. C. Reynolds, Craft of Programming, Chapter 2. In particular, the introduction of the chapter, and the section 2.2.8, cover the two views.

# Answer
> 3 votes
It makes little sense to think about how we are to encode an array as a function without explaining how we intend to implement the basic array operations. The characteristic property of an array is that we can

1. access the $i$-th element, and
2. set the $i$-th element.

In addition, certain equations must be satisfied. For example, if we look up the $i$-th element twice in a row, we will see the same value, etc. (These equations can be looked up in any standard source on the state monad.)

Now, it is quite obvious that an array can be encoded as a function. But we also have to implement `get` and `set`. Here is how we might do it in Haskell.

```
-- An array is represented as a function from integers to floats.
type Array = Int -> Float

-- create a new array all of whose elements are initialized to 0.0
new :: () -> Array
new () = \i -> 0.0

-- get a i returns the i-th element of aray a
get :: Array -> Int -> Float
get a i = a i

-- set a i x returns the array a, but with i-th element set to x
set :: Array -> Int -> Float -> Array
set a i x = \j -> if j == i then x else a j

```

We are not checking and bounds here, which we should. It may seem a bit unusual that `set` returns a new array, but there really is no way of modifying an existing one in a purely functional setting. Haskell has the so-called "monadic style" of programming which makes it much easier to work with this sort of encoding (although I wouldn't recommend the encoding for a real appliaction).

# Answer
> 1 votes
The function is defined as follows, given array $a$, for $1 \leq i \leq 10$, $$f(i) = a\[i\].$$

The domain is thus $\text{dom}(f) = \\{1,2,3,4,5,6,7,8,9,10\\}$ and the codomain is simply $\text{codom}(f) = \bigcup\_{i=1}^{10}f(i) = \bigcup\_{i=1}^{10}a\[i\] \subset \mathbb{R}$.

---
Tags: arrays, semantics, functional-programming
---


# Question
Title: Regular expression for $\{a^k b^m c^n \mid k+m+n \text{ is odd} \}$
I have to make a regular expression from the following laguage:

> {$a^kb^mc^n : $ where *k* \+ *m* \+ *n* is odd}

Is is possible for the sum of three numbers to be odd (other than three consecutive odd numbers)?

I have this so far:

> {(abbbccccc) + (abbbbbccc) + (aaabccccc) + (aaabbbbbc) + (aaaaabccc) + (aaaaabbbc)}

but I am realizing that there are way more possibilities to this pattern... How can I formulate a string that encompasses all of this?

# Answer
What you need is that either exactly two of $k$, $m$, $n$ even, or all three odd, because two odds and an even make an even; and three evens make an even.

An odd number of $a$'s translates to the regular expression $a (a a)^\*$, an even number to $(a a)^\*$.

Pulling the above together: $$ a (a a)^\* (b b)^\* (c c)^\* \mid (a a)^\* b (b b)^\* (c c)^\* \mid (a a )^\* (b b)^\* c (c c)^\* \mid a (a a)^\* b (b b)^\* c (c c)^\* $$
> 7 votes

# Answer
$a(aa)^\ast (bb)^\ast (cc)^\ast + (aa)^\ast b(bb)^\ast (cc)^\ast + (aa)^\ast (bb)^\ast c(cc)^\ast + a(aa)^\ast b(bb)^\ast c(cc)^\ast $
> 2 votes

# Answer
There are 6 possibilities which is easy to express as a regular expression $\\{a(aa)^\*b(bb)^\*c(cc)^\*|a(aa)^\*(bb)^\*(cc)^\*|(aa)^\*b(bb)^\*(cc)^\*|(aa)^\*(bb)^\*c(cc)^\*\\}$

which correspond to the cases all three odd, or two even and one odd. No other case is possible.
> 0 votes

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


# Question
Title: Path on an edge-colored DAG using exactly $k$ colors
I have the following problem:

> Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$,
> does there exist a path from $s$ to $t$ using exactly $k$ distinct colors?

Can anyone provide pointers to the complexity of this problem? More specific, is it $\mathsf{NP}$-complete or in $\mathsf{P}$?

# Answer
> 8 votes
Here is a reduction of CNF-SAT.

In a given CNF formula, assume we have variables $x\_1, \dots, x\_n$ and clauses $C\_1, \dots, C\_m$.

We construct a DAG with edge colors as follows.

We have $m$ colors, and each color corresponds to a clause. In our DAG, we have vertices $v\_0$, $v\_1$, ..., $v\_n$, and $v\_0$ is the source and $v\_n$ is the sink. (There will be more vertices in our DAG.)

From $v\_{i-1}$ to $v\_{i}$, we have a pair of vertex-disjoint paths (you may think they are parallel), one for TRUE and one for FALSE corresponding to the assignment to $x\_i$. On the path for TRUE, we have edges with the colors corresponding to the clauses with $x\_i$ appearing as positive literals. On the path for FALSE, we have edges with the colors corresponding to the clauses with $x\_i$ appearing as negative literals.

A path exists from $v\_0$ to $v\_n$ with $m$ colors if and only if the given formula is satisfiable.

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


title: Interesting problem on sorting

text:
# Question
Title: Interesting problem on sorting
Given a tube with numbered balls (random). The tube has holes to remove a ball. Consider the following steps for one operation:

1. You can pick one or more balls from the holes and remember the order in which you picked the balls.
2. You need to tilt the pipe towards left side so that remaining balls in the pipe shifts towards left and occupy the empty space created by removing the balls.
3. You are not supposed to change the order in which you picked the numbered balls from the pipe. Now you put them back again in the pipe using the vacant space created by movement of balls.

Steps 1 to 3 is considered as one operation.

Find out the minimum operations required to sort the numbered balls in the ascending order.

For example: If tube contains: $\[1\ 4\ 2\ 3\ 5\ 6\]$

Then we can take out $4$ and $5$ and $6$, and if we tilt pipe to the left, we get $\[1\ 2\ 3\]$, and we insert $(4\ 5\ 6)$ in that order to the end of pipe to get $\[1\ 2\ 3\ 4\ 5\ 6\]$.

So minimum number of steps required is 1. I need to find minimum operations to sort the pipe.

Any ideas or hints on how to solve this problem?

# Answer
Define the *run-partition number* of a permutation $\pi$, denoted $r(\pi)$, using the following process. Let $k$ be the maximal integer such that the numbers $\min(\pi),\ldots,k$ appear in increasing order in $\pi$. Remove them from $\pi$, and repeat the process. The number of rounds it takes to consume the entire permutation is $r(\pi)$.

For example, let's compute $r(62735814)$. We first set aside $1$, to get $6273584$. Then we set aside $234$, to get $6758$. Then we set aside $5$, to get $678$. Finally, we set aside $678$ to get the empty permutation. This takes four rounds, so $r(62735814) = 4$.

How is this representation useful for sorting $62735814$? Take every second run, i.e. $234,678$, and move these numbers to the right to get $51627384$ (edit: in the order they appear in the permutation, i.e. $627384$). Now there are only two runs, namely $1234,5678$, and we can sort the list by moving $5678$ to the right.

Now let me make the following conjecture: For a permutation $\pi$, let $\Pi$ be the set of all permutations that are reachable from $\pi$ within one move. Then $\min\_{\alpha \in \Pi} r(\alpha) = \lceil r(\pi)/2 \rceil$.

Given this conjecture, it is easy to show that the minimal number of moves needed to sort a permutation $\pi$ is $\lceil \log\_2 r(\pi) \rceil$, and I have verified this formula for all permutations in $S\_n$ for $n \leq 8$.

Edit: Here is a different interpretation of the *run-partition number* which gives a linear time algorithm for computing it, and allows me to sketch a proof of my conjecture, thus verifying the formula $\lceil \log\_2 r(\pi) \rceil$.

Consider the permutation $62735814$ again. The reason that the first run ends in $1$ is that $2$ appears before $1$. Similarly, the second run ends in $4$ since $5$ appears before $4$, and so on. Therefore the run-partition number of a permutation is the number of $i$s such that $i+1$ appears before $i$.

We can state this more succinctly if we look at the inverse of the permutation. Consider again $\pi = 62735814$. Take $\pi^{-1} = 72485136$. This permutation has three descents: $7\mathbf{2}48\mathbf{5}\mathbf{1}36$ (a descent is a position smaller than the preceding one). Each of the descents corresponds to the start of a new run. So $r(\pi)$ is equal to one plus the number of descents in $\pi^{-1}$.

What does the operation look like in terms of $\pi^{-1}$? let $B$ be the set of numbers that we move to the right, and $A$ be the set of numbers that stay to the left. We replace the numbers in $A$ with a permutation on $\\{1,\ldots,|A|\\}$ representing their relative order, and replace the numbers in $B$ with a permutation on $\\{|A|+1,\ldots,|A|+|B|\\}$. For example, consider the move $\mathbf{6273}5\mathbf{8}1\mathbf{4} \mapsto 51\mathbf{627384}$. In terms of the inverse permutations, it's $7\mathbf{248}5\mathbf{136} \mapsto 2\mathbf{468}1\mathbf{357}$. So $75$ was mapped to $21$ and $248136$ was mapped to $468357$.

A descent $\ldots xy \ldots$ in $\pi^{-1}$ is lost after the operation only if $x \in A$ and $y \in B$. Conversely, in terms of $\pi^{-1}$, the partition into $A$ and $B$ corresponds to $A$-runs and $B$-runs; every time a $B$-run ends and an $A$-run begins, there is a descent. In order to "kill" a descent, we have to switch from an $A$-run to a $B$-run. If we kill two descents, we will have switched in the middle from a $B$-run to an $A$-run, incurring a descent.

This argument can be formalized to show that if $\alpha$ arises from $\pi$ via an operation, then $d(\alpha^{-1}) \geq \lfloor d(\pi^{-1})/2 \rfloor$, where $d(\cdot)$ is the number of descents. This is equivalent to $r(\alpha) \geq \lceil r(\pi)/2 \rceil$, thus proving one direction of my conjecture. The other direction is easier, and was already outlined above: we simply take every second run and push these runs to the right to get a permutation $\alpha$ satisfying $r(\alpha) = \lceil r(\pi/2) \rceil$.
> 10 votes

---
Tags: sorting, permutations
---


title: Simplifying regular expressions

text:
# Question
Title: Simplifying regular expressions
This is the homework question:

> $ \\{w \in \\{a, b, c\\}^\* : \text{(no symbol occurs twice in succession in w)}\\} $

This is my answer:

> $$\\{((abc)^\*| (acb)^\*| (ab)^\* | (ac)^\*)^\* | (bac)^\* | (bca)^\* | (ba)^\* | (bc)^\*)^\* | ((cab)^\* | (cba)^\* | (ca)^\* | (cb)^\*)^\* | ((\epsilon +a) | (\epsilon + b) | (\epsilon+c)) \\} $$

Is there a way to simplify this expression?

# Answer
> 4 votes
Let's solve this exercise "by induction". Suppose first that the alphabet is only $a,b$. In this case, the only possible words are $ababab\ldots$ and $bababa\ldots$, and you can write a simple regular expressions for them. Now take such a word over the alphabet $a,b,c$. You can break it apart as $w\_1 c w\_2 c w\_3 c \ldots$, in which $w\_i \in \\{a,b\\}^\*$. We already have a regular expression describing the $w\_i$, so we can write one for the language in question. This approach is general, and you can apply it to any alphabet size.

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


# Question
Title: Can a CFG end have a non-terminal symbol in the middle of it?
What is the correct way to write a CFG?

```
A -> B C' E
C' -> C
C' -> null

```

or

```
A -> B C'
C' -> C E
C' -> E

```

# Answer
Both of those are valid context-free grammars. (For the same language.) The requirement for a context-free grammar is just that the left side of the production must have exactly one non-terminal, which both of them satisfy. (Usually, to make this more clear, we'd have a convention like non-terminals are uppercase and variables are lower-case, and we'd specify the start symbol. But it looks clear that you have $A$ and $C'$ as nonterminals and the rest terminals, with $A$ being the start symbol.)
> 6 votes

# Answer
Conditions for Famous Grammars: (YOU MUST NEVER FORGET THE FOLLOWING)

1) Regular Grammars : Grammar That is either Right linear or Left Linear Grammar

This is also called Type 3 Grammar

2) Context Free Grammar : LHS must be exactly 1 Non-terminal , RHS can be any String of terminals and Non--Terminals.

This is also called Type 2 Grammar

3) Context Sensitive Grammar : LHS can be any String , RHS can be any String of terminals and Non--Terminals such that for each production , length of LHS string must be less than or equal to length of RHS string

This is also called Type 1 Grammar

4) Recursively Enumerable Grammar : LHS can be any String , RHS can be any String of terminals and Non--Terminals

This is also called Type 0 Grammar

:)
> 2 votes

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


title: 0 and 1 Queries in tables of N*N cells

text:
# Question
Title: 0 and 1 Queries in tables of N*N cells
There is a square table composed of `N*N` Cells. Initially all cell is filled with a number `0`. Two types of Operations can be performed on the table.

R i k: All the numbers in the cells on ith row has been changed to k.

C i k: All the numbers in the cells on ith column has been changed to k.

Please Note : **k ∈ {0, 1} (ie k = 0 or 1).**

At any time ,Alice is interested to know the total number of 0's on some row or total number of 0's on some column.

Our task is to answer Alice Query.

***Input***

First line contains a single integer N as described above.Next line contains a single integer Q representing the total operations and queries from Alice. Then Followed Q lines , containing operations or queries in following format:

```
R i k: All the numbers in the cells ith row has been changed to k.

C i k: All the numbers in the cells ith column has been changed to k.

qc i :How many 0's are there in ith row?

qr i:How many cols are there in ith col?

```

**Examples**: Input:

```
3

6

qr 1

C 1 1

qr 1

qc 1

R 1 0

qc 1

```

Output:

```
3

2

0

1

```

I tried a Naive solution.But it got time out. The constraint is quite large and the time limit is just 0.55 Seconds.

\**1 ≤ N, Q ≤ 500000 (6 * 10^5)

How can i solve this problem within the given time-limit?

P.S: *This is not a homework*.

# Answer
> 1 votes
My solution uses 2 arrays (R and C) to store the zero-counts and a 1D array (Grid) to represent the grid of zeros and ones as a sequence of numbers. All 3 arrays are of size $N$. Queries take constant time (you return the value in the i'th col/row). An update operation takes linear time in $N$ because you have to set the i'th col to $N$ or 0 and update all of the rows (likewise for the i'th row). Here is a Python implementation and a test case (yours):

```
N = 3
R = []
C = []
Grid = []

for k in range(N):
    R.append(N)
    C.append(N)
    Grid.append(0)

def qr(k):
    print R[k - 1]

def qc(k):
    print C[k - 1]

def r(i, k):
    R[i - 1] = (1 - k) * N
    for l in range(N):
        bit = ((Grid[i - 1] & (1 << l) >> l)
        if bit != k:
            if k == 0:
                C[l] = C[l] + 1
            else:
                C[l] = C[l] - 1
        Grid[i - 1] = Grid[i - 1] | (k << l)

def c(i, k):
    C[i - 1] = (1 - k) * N
    for l in range(N):
        bit = ((Grid[l] & (1 << (i - 1))) >> (i - 1))
        if bit != k:
            if k == 0:
                R[l] = R[l] + 1
            else:
                R[l] = R[l] - 1
        Grid[l] = Grid[l] | (k << (i - 1))

qr(1)
c(1, 1)
qr(1)
qc(1)
r(1, 0)
qc(1)

```

You have to complete this with code that parses the input file and interprets the commands.

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


title: Is NAE-HORN-SAT in P or NP-hard?

text:
# Question
Title: Is NAE-HORN-SAT in P or NP-hard?
I am interested to know the complexity of the NAE-HORN-SAT problem (not all equal). We know that HORNSAT is $\mathsf{P}$-complete, but on the other hand, NAE-SAT is $\mathsf{NP}$-complete. I want to know what can we say about NAE-HORN-SAT problem. Let me define the problem formally:

> Given: One Boolean formula $\phi$ is given to us in CNF where each clause has at most one positive literal (HORN-property).
> Question: Is there any assignment for the input variables of $\phi$ such that any clause has at least one False and at least one True literal (NAE-property) ?

N.B.:

* Positive literal: any variable directly,
* Negative literal: negation of any variable.
* True literal: literal is assigned to Boolean True by any assignment,
* False literal: literal is assigned to Boolean False by any assignment.

According to Schaefer's dichotomy theorem, this problem must be either in $\mathsf{P}$ or $\mathsf{NP}$-complete. I can just find one polynomial reduction from HORNSAT to this problem, which proves actually nothing. Is there a polynomial time algorithm to solve this problem?

Or, is there any way to prove this problem to be $\mathsf{NP}$-hard? Any thoughts about this ?

# Answer
Your problem, NAE-HORN-SAT is $NP$-complete. Monotone NAE-SAT is $NP$-complete and it is a special case of your NAE-HORN-SAT. Literals in monotone SAT formula are either all positive or all negative.

Take any instance of Monotone NAE-SAT problem (all its literals are negative) then this formula is an instance of NAE-HORN-SAT problem.
> 8 votes

# Answer
Schaefer's dichotomy theorem actually doesn't necessarily apply in this case, since the width of clauses in a NAE-HORN-SAT formula isn't bounded. What Schaefer's theorem does give you is an algorithm which decides, for each $k$, whether the restriction of NAE-HORN-SAT to clauses of width $k$ (or up to $k$) is in P or NP-complete. The algorithm appears in the Wikipedia page, and you can look up some of the references (e.g. the recent survey by Chen) for more explanations.

In your case, there are two possibilities. The first possibility is that for some $k$, NAE-HORN-SAT is NP-complete for clauses of width $k$. The second possibility is that for all $k$, NAE-HORN-SAT is in P. In the latter case, you will have to look at the algorithm which solves NAE-HORN-SAT for each bounded $k$ (there is an algorithm for each of the six easy cases listed in the theorem, and you will end up with one of them), and check whether it generalizes to unbounded width. If it doesn't, then come back to us and ask the question again. Edit: we don't expect this to happen, see this question.

Note that if the clause width is unbounded, then the general CSP problem isn't guaranteed to be in NP (or even computable), though in your case it is.
> 5 votes

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


# Question
Title: Studies of file access patterns in embedded systems
I am considering what elements an operating system for Network On Chip systems might have and the issue of file systems looms large. NoCs have an embedded heritage, and their domain of use (at least initially) is likely to be similar tasks to embedded systems.

But I cannot find any studies of embedded system file access patterns - there are a number of published studies on scientific and super computing file access patterns I have been able to read but nothing on embedded systems.

Can anyone point me to some good papers on this?

# Answer
> 1 votes
There is a good paper titled "The Case for Efﬁcient File Access Pattern Modeling" by Thomas M. Kroeger and Darrell D. E. Long. It reviews two classic model for file access pattern "The ﬁrst model is based on a graph, that keeps frequency counts for all ﬁles accessed within a window following an access to each ﬁle. The second model was adapted from the text compression technique ***ﬁnite multi-order context modeling*** (FMOC), to track ﬁle access patterns. It uses a tree to keep frequency counts of access patterns, tracking a ﬁnite number of multiple-order patterns."

I think these techniques could be applied for different small scale file systems such as hard disk, flash memory, etc on pc or embeded systems.

This paper "Analysis of Disk Access Patterns on File Systems for Content Addressable Storage" written by Kuniyasu Suzaki, Kengo Iijima, Toshiki Yagi, and Cyrille Artho is also very useful, while the OS of many embedded systems are ***Linux-based***.

---
Tags: reference-request, parallel-computing, filesystems
---


title: Infinite chain of big $O's$

text:
# Question
Title: Infinite chain of big $O's$
First, let me write the definition of big $O$ just to make things explicit.

$f(n)\in O(g(n))\iff \exists c, n\_0\gt 0$ such that $0\le f(n)\le cg(n), \forall n\ge n\_0$

Let's say we have a finite number of functions: $f\_1,f\_2,\dots f\_n$ satisftying:

$O(f\_1)\subseteq O(f\_2)\dots \subseteq O(f\_n)$

By transitivity of $O$, we have that: $O(f\_1)\subseteq O(f\_n)$

Does this hold if we have an infinite chain of $O's$? In other words, is $O(f\_1) \subseteq O(f\_\infty)$?

I'm having trouble imagining what's going on.

# Answer
We first need to clarify what we mean by "does this hold if we have an infinite chain?". We interpret it as an infinite sequence of functions $\\{f\_i:\mathbb{N}\to\mathbb{N} \mid 1\leq i\\}$ such that for all $i$ we have $f\_i(n) = O(f\_{i+1}(n))$. Such a sequence might not have a last function.

We can look at the limit of the functions in the sequence, i.e. $f\_\infty(n) = \lim\_{i\to \infty} f\_i(n)$. However it is possible that the limit does not exists. And even in the case that it exists we might not have $f\_1(n) = O(f\_\infty(n))$. For example consider the sequence of functions $f\_i(n) = \frac{n}{i}$. For each $i$, $f\_i(n)=\Theta(n)$ and therefore $f\_i(n) = O(f\_{i+1}(n))$. However $f\_\infty(n)=\lim\_{i\to\infty}f\_i(n)=0=\Theta(1)$ thus $f\_1(n) \neq O(f\_\infty(n))$.

On the other hand we can look at *the limit of the sequence of the classes* which doesn't need to be equal to *the class of the limit of the functions*. We have $f\_i \in \mathcal O(f\_{i+1})$, therefore $\mathcal O(f\_i) \subseteq \mathcal O(f\_{i+1})$ and $f\_j \in \lim\_{i\rightarrow\infty} \mathcal O(f\_i) = \limsup\_{i\rightarrow\infty} \mathcal O(f\_i) = \liminf\_{i\rightarrow\infty} \mathcal O(f\_i) = \bigcup\_{n \in \mathbb{N}}\bigcap\_{k\>n}\mathcal O(f\_k)$ for all $j$. The limit superior contains all elements (functions in this case) which occur infinitely often and the limit inferior contains all elements which occur in all $\mathcal O(f\_i), i \ge n\_0$ for some $n\_0$ (which may depend on the element). Since the sequence of classes is monotonically increasing both exist and they are equal. This justifies the usage of $\lim$.
> 15 votes

# Answer
Yes, it's possible to have an infinite chain.

I'm sure you're already familiar with some examples: $$ O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots $$ You have an infinite chain here: polynomials of growing degree. Can you go further? Sure! An exponential grows faster (asymptotically speaking) than any polynomial. $$ O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O(x^{42}) \subseteq \ldots O(e^x) $$ And of course you can keep going: $O(\mathrm{e}^x) \subseteq O(x\\,\mathrm{e}^x) \subseteq O(\mathrm{e}^{2x}) \subseteq O(\mathrm{e}^{\mathrm{e}^x}) \subseteq \ldots$

You can build an infinite chain in the other direction too. If $f = O(g)$ then $\dfrac{1}{g} = O\left(\dfrac{1}{f}\right)$ (sticking to positive functions, since around here we discuss asymptotics of complexity functions). So we have for example:

$$ O(x) \subseteq O(x^2) \subseteq \ldots \subseteq O\left(\dfrac{e^x}{x^2}\right) \subseteq O\left(\dfrac{e^x}{x}\right) \subseteq O(e^x) $$

In fact, given any chain of functions $f\_1, \ldots, f\_n$, you can build a function $f\_\infty$ that grows faster than all of them. (I assume the $f\_i$'s are functions from $\mathbb{N}$ to $\mathbb{R}\_+$.) First, start with the idea $f\_\infty(x) = \max \\{f\_n(x) \mid n \in\mathbb{N}\\}$. That may not work because the set $\\{f\_n(x) \mid n \in\mathbb{N}\\}$ can be unbounded. But since we're only intersted in asymptotic growth, it's enough to start small and grow progressively. Take the maximum over a *finite* number of functions. $$ f\_\infty(x) = \max \\{f\_n(x) \mid 1 \le n \le N \\} \qquad \text{if \\(N \le x \lt N+1\\)} $$ Then for any $N$, $f\_N \in O(f\_\infty)$, since $\forall x \ge N, f\_\infty(x) \ge f\_N(x)$. If you want a function that grows strictly faster ($f\_\infty = o(f\_\infty')$), take $f\_\infty'(x) = x \cdot (1 + f\_\infty(x))$.
> 5 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Are link-cut trees ever used in practice, for max flow computation or other applications?
Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as link-cut trees).

* Push relabel runs in $O(V^2E)$ or $O(V^3)$ or $O(V^2\sqrt{E})$ normally, but with dynamic trees $O(VE \log(V^2/E))$
* Dinic's algorithm runs in $O(V^2E)$, but with dynamic trees $O(VE\log(V))$

However, practical implementations of max-flow algorithms in most libraries don't seem to make use of this data structure. Are dynamic trees ever used in practice for max flow computation? Or do they carry too much overhead to be useful for real world problem sizes?

Are there any other problem domains where link cut trees are used?

This question is related to a question that I asked on cstheory: Are any of the state of the art Maximum Flow algorithms practical?

# Answer
> 7 votes
There is a paper titled "Dynamic Trees in Practice" which reviews the practical implementation.

The other categories that Link-Cut tree could be used efficiently is in **Database Indexing**. You can find this in the book "Database Index Techniques".

# Answer
> 5 votes
this paper finds at the end that a link-cut (LC) tree outperforms rake-compress (RC) trees for the Sleator/Tarjan max-flow algorithm using a standard Dimacs random graph generator.

the paper focuses on change propagation as one application of dynamic trees. eg, change propagation is similar to the way that excel spreadsheet cells have to be recomputed on changes to some cells based on cell/formula dependencies. the authors released their code as an open library.

An experimental analysis of change propagation in dynamic trees Acar, Blelloch, Vittes

> Change propagation is a technique for automatically adjusting the output of an algorithm to changes in the input. The idea behind change propagation is to track the dependencies between data and function calls, so that, when the input changes, functions affected by that change can be re-executed to update the computation and the output. Change propagation makes it possible for a compiler to dynamize static algorithms.

---
Tags: reference-request, graphs, data-structures, network-flow
---


# Question
Title: Algorithm for building a suffix array in time $O(n \log^2 n)$
I've been working with suffix arrays lately, and I can't find an efficient algorithm for building a suffix array which is easy to understand. I have seen in many sites that there is an $O(n \log^2 n)$ algorithm, but I can't understand it, as many important details are omitted. There's an example at Top Coder.

Could someone introduce me an efficient algorithm for suffix array construction, which is easy to comprehend?

# Answer
> 15 votes
You can compute the suffix array in linear time with the DC-3 Algorithm. This is a super-cool fancy algorithm that can be implemented in 50 lines of readable C++ code - one of my all-time favorites. The source code is contained in the original paper. If you can compare two characters in constant time and the alphabet size is $n^{O(1)}$, then the DC3 algorithm runs in $O(n)$ time.

Notice that you can also get the suffix-tree in linear time when you have access to the suffix-array and the LCP-array. The LCP-array can be also constructed with the DC3-algorithm.

# Answer
> 4 votes
Here's a good explanation for the $O(n\log^2n)$ algorithm: http://www.stanford.edu/class/cs97si/suffix-array.pdf. Actually, by using linear time sorting, the same approach gives $O(n\log n)$ time complexity.

If you have any specific question about it, you're welcome to ask.

I agree with A. Schultz that DC-3 is super-cool. It is also not very complicated, but the $O(n\log^2 n)$ is still simpler.

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


# Question
Title: Does reduction from an NP-complete problem to some problem $X$ imply that $X\in NP$?
I am having problems resolving the following question:

> Given some problem $X$. If there exists a polynomial time reduction from (for example) $\mbox{SAT}$ to $X$, $(\mbox{SAT} \leq\_{p} X)$ and since we know that $\mbox{SAT}$ is $\mbox{NP-complete}$, to show that $X$ is $\mbox{NP-complete}$ is it necessary to show that $X\in \mbox{NP}$ via some third party algorithm?

If yes, then why?

# Answer
the reduction only shows that X is at least as hard as SAT (NP-HARD). This could mean that X is in a class suspected to be harder than NP such as PSPACE or EXPTIME. To show that X is NP-complete you must show that it is also in NP. If you try it out you will see that you can easily reduce SAT to problems in EXPTIME that are not suspected to be in NP. The idea being that your reduction shows that X is at least as hard as SAT, but there are classes of problems harder than NP problems which X could fall into.
> 5 votes

# Answer
Here is a very general negative answer. Consider the following language: $$ L = \\{\langle M,x,o \rangle : M \text{ outputs } o \text{ on input } x\\}, $$ where $o \in \Sigma^\* \cup \\{ \bot \\}$ and $\langle \cdot,\cdot,\cdot \rangle$ is any polytime pairing function (we can even demand it to be logspace, or even weaker). Every language accepted by some Turing machine can be reduced to $L$ in polytime, yet $L$ is not computable.
> 4 votes

---
Tags: complexity-theory, terminology, reductions, np
---


# Question
Title: A dense NP complete language implies P=NP
We say that the language $J \subseteq \Sigma^{\*}$ is *dense* if there exists a polynomial $p$ such that $$ |J^c \cap \Sigma^n| \leq p(n)$$ for all $n \in \mathbb{N}.$ In other words, for any given lenght $n$ there exist only polynomially many words of length $n$ that are not in $J.$

The problem I am currently studying asks to show the following

> If there exist a dense $NP$-complete language then $P = NP$

What the text suggest is to consider the polynomial reduction to $3$-$SAT$ and then construct an algorithm that tries to satisfy the given $CNF$ formula while also generating elements in $J^c.$

What I am wondering is

> Is there a more direct proof? Is this notion known in a more general setting?

# Answer
> 6 votes
This is a nice homework problem about Mahaney's theorem.

Note that the complement of a "dense" language is a sparse language. Moreover if a language is $\mathsf{NP}$-complete its complement is $\mathsf{coNP}$-complete.

If there is a "dense" $\mathsf{NP}$-complete language, there is a sparse $\mathsf{coNP}$-complete language.

Mahaney's theorem tells us that there is no sparse $\mathsf{NP}$-complete language unless $\mathsf{P}=\mathsf{NP}$.

We can adopt the proof to show that there is no sparse $\mathsf{coNP}$-complete language unless $\mathsf{P}=\mathsf{coNP}$ which is equivalent to $\mathsf{P}=\mathsf{NP}$ (since $\mathsf{P}$ is closed under complements).

In summary, the answer is no unless $\mathsf{P}=\mathsf{NP}$. Note that if $\mathsf{P}=\mathsf{NP}$ then every nontrivial language is $\mathsf{NP}$-complete.

ps: You may want to try the following and then use Mahaney's theorem: there is a sparse $\mathsf{NP}$-complete set iff there is a sparse $\mathsf{coNP}$-complete set. However I doubt that a proof for this statement would be much easier than a proof for Mahaney's theorem.

# Answer
> 3 votes
As mentioned above according to **Mahaney's theorem**. Sparse and dense languages could not be $NP-Hard$ unless $P=NP$.

The mentioned draft contains complete proof.

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


# Question
Title: Why is the Shannon entropy 0.94 in this example?
Suppose I have a decision tree in which there is a label $L$ under which is the attribute $A$ as shown below. I am given that the Shannon entropy of label $L$ is $H(L) = 0.95$.

I must find the Shannon entropy of $L$ given $A$ ($H(L \mid A)$). Here's what I have tried.

\begin{eqnarray} H(L \mid A) &=& -(\frac{6}{8} \log\_2 \frac{4}{6} + \frac{2}{8} \log\_2 \frac{1}{2}) \\ &\approx& 0.69 \end{eqnarray}

However, $H(L \mid A) \approx 0.94$. Where did I err? Is my formula for Shannon entropy accurate?

# Answer
Back to the definitions: $$H(L\mid A) = \sum\_a p(A=a) H(L \mid A=a).$$

As you compute, $P(A=true)=6/8$ and $P(A=false)=2/8$.

However, you don't compute $H(L\mid A=true)$ but instead compute $P(L=positive\mid A=true)$. \[and the same for $A=false$.\].

With standard definition of $H()$ we get,

$$H(L\mid A=true) = - 4/6\log\_2(4/6) - 2/6\log\_2(2/6) = 0.9182958$$ $$H(L\mid A=false) = H(1/2) = 1$$

And thus, $H(L\mid A) = 6/8 \times 0.918 + 2/8\times 1 = 0.938 \approx 0.94$.
> 7 votes

---
Tags: artificial-intelligence, entropy
---


# Question
Title: Finding the minimum subset of intervals covering the whole set
Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers and $a \< b$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any value within the range of any pair in $A$, the value is also within the range of any pair in $B$.

I am currently considering setting $B$ equal to $A$ and, for each pair in $B$, if removing the pair still upholds the property of $B$ described above, remove it. However, I feel this algorithm is too inefficient. Is there a more efficient algorithm?

# Answer
> 8 votes
Here's an $O(n\log n)$ algorithm, which is optimal in the algebraic decision tree model by an easy reduction from element distinctness (map each element $x$ to the interval $(x,x+\epsilon)$). We follow Kaveh's outline. Stage 1 runs in $O(n\log n)$ time, so we focus on Stage 2.

Let $I$ be the set of intervals in $C = (a,b)$. Define the intervals $l=(a,a+\epsilon)$ and $r=(b-\epsilon,b)$, and consider the interval graph over $I \cup \\{l,r\\}$ (two vertices are connected if the corresponding intervals intersect). I claim that every path from $l$ to $r$ corresponds to a cover of $C$, and vice versa.

First, consider a path $P$ from $l$ to $r$. Suppose that $P$ doesn't cover some point $x \in C$. We prove by induction that all the intervals in $P$ are to the left of $x$, which leads to a contradiction since $r$ is to the right of $x$. Clearly $l$ is to the left of $x$. Suppose some $p \in P$ is to the the left of $x$, and let $p'$ be the next interval on the path. If $p'$ were to the right of $x$, then since $p$ and $p'$ intersect, $x$ would have been covered. So $p'$ must also be to the left of $x$.

For the other direction, order the intervals in a cover of $C$ in increasing order of their starting point. If two consecutive intervals $(a,b),(c,d)$ do not intersect then the point $x = (b+c)/2$ is not covered. Similarly, the first interval must intersect $l$. While it is not generally true that the last interval must intersect $r$, one of the intervals must, and if we cut the cover short at the first such interval, then we obtain another cover of $C$ which also constitutes a path in the interval graph from $l$ to $r$.

We have reduced the problem of covering $C$ to finding the shortest path in an interval graph. This is solvable in time $O(n\log n)$ and space $O(n)$, as shown for example in An Optimal Algorithm for Shortest Paths on Weighted Interval and Circular-Arc Graphs with Applications by Atallah, Chen and Lee.

# Answer
> 6 votes
**Stage 1:** Break down the problem to that of covering a single interval.

Find the union of pairs in $A$ as follows: Sort the intervals in $A$ by their starting position. Go over them to find the first point that is not covered. Create an interval for this part. Repeat this starting from the left point of the next interval. At the end we will have a list of non-overlapping intervals. Call it $C$.

Note that we can break down the problem to the problem of covering a single interval in $C$. There are no intervals in $A$ that intersect more than one interval in $C$. So the problem is reduced to the problem of covering a given interval $\[l,r\]$ with the smallest number of intervals from $A$.

**Stage 2:** Find the smallest cover for each interval in $C$ using dynamic programming.

We use dynamic programming. Note that we only need to care about the end-points of intervals in $A$ that fall in $\[l,r\]$.

Sort the intervals in the increasing order according to their right end-points. If an interval is contained in another one remove it (remove redundant intervals).

Let $I\_1,\cdots,I\_n$ be the list of intervals in $A$. Let $l\_k$ and $r\_k$ refer to the index of the left and right end-points of interval $I\_k$. Let the end-points of intervals in $A$ be $l=p\_1\< \cdots \< p\_m=r$.

We will use the dynamic programming with the following table:

$T\[j,k\]= \text{the size of smallest cover of $\[p\_1,p\_j\]$ using the first $k$ intervals.}$

In the following we explain how to compute $T\[j,k\]$.

If $j \> r\_k$ we cannot cover the interval as it is the interval with the right most end-point among $I\_1,\cdots,I\_k$. So there is no covering and we save value $\infty$.

In case $j \leq r\_k$, we consider two cases: we use $I\_k$ or we don't use it.

If we use $I\_k$, we look for the smallest cover of $\[p\_1,p\_{l\_k}\]$ with the first $k-1$ intervals. So we look at $T\[l\_k,k-1\]$ and add one.

If we don't use $I\_k$, we look for the smallest cover of $\[p\_1,p\_j\]$ with the first $k-1$ intervals. So we look at $T\[j,k-1\]$.

$$T\[j,k\] = \begin{cases} \min \\{T\[j,k-1\] ,T\[l\_k,k-1\]+1\\} & j \leq r\_k \\ \infty & o.w. \end{cases}$$

**Analysis:** The worst-case running-time of the algorithm (on a RAM machine) is $O(n^2)$ where $n$ is the number of intervals.

---
Tags: algorithms, sets
---


# Question
Title: Finite automaton for the language of words whose second letter is b
How can I build a finite automaton that accepts only the language of all words in which `b` is the second letter?

This is my solution so far but I'm not sure if it's correct.

# Answer
> 5 votes
A finite automaton (FA) is simply a machine with limited memory. The FA reads in an input string and does one of two things: accept or reject. In many ways, FAs are realistic abstractions of computers and brains and good depictions of simple machines like vending machines and elevators. You can read more about finite-state machines on Wikipedia, though the page on deterministic finite automaton may be more useful for solving your problem. If you own it, you should also read Sipser's Introduction to the Theory of Computation; it's relatively approachable.

I don't want to simply solve your problem, so let's look instead at a related problem:

**The language of all words with at least one $a$**
Informally, we read each element from the input string and accept if we see an $a$.

Semi-formally, we're going to have two states: (1) have not yet read an $a$ (2) have read an $a$. Then we transition from state (1) to state (2) when we read an $a$. If we read anything other than an $a$, we stay put. If the input string ends and we're left in state (1), then we reject (the word is not in the language because it doesn't contain an $a$); if we're left in state (2), then we accept (it does contain an $a$).

Formally, we need to define a 5-tuple (i.e. 5 different elements)

1. A finite set of states $(Q)$. We can name them whatever we want, so if we want to be boring, we can simply call them $q\_0$ and $q\_1$. If we want to be relevant to just this problem, we can call them $q\_\bar{a}$ (the state for which we have not read an $a$) and $q\_a$ (the state for which we have). On our picture, the states are the circles, and we label them with their names.
2. A finite set of input symbols $(\Sigma)$, which we call the alphabet. Here, let's say that the input string has just $a$, $b$ and $c$, so $\Sigma=\\{a,b,c\\}$.
3. A transition function $(\delta)$, which takes every element in the set of states $Q$ and dictates what state is transitioned into for each element in the alphabet $\Sigma$ (in notation, $Q\times \Sigma \rightarrow Q$). That is, we make a state transition table, with the states in the first column and the alphabet in the first row, and then fill in what state is transitioned to for each combination of state and input symbol. $$\begin{vmatrix} & a & b & c \\ q\_\bar{a} & q\_a & q\_\bar{a} & q\_\bar{a} \\ q\_a & q\_a & q\_a & q\_a \\ \end{vmatrix}$$ You can see that the arrows and letters on the picture represent this transition function.
4. A start state $(q\_0\in Q)$. This is where our machine starts its reading of the input string. If the string is empty, it's also where it ends. For this problem, the start state is $q\_\bar{a}$. On the picture, we depict this via an arrow coming from no other state.
5. A set of accept states $(F\subset Q)$. Here, our only accept state is $q\_a$, so the set of states is $F=\\{q\_a\\}$. We represent this via a concentric circle on each accepting state.

> **Try solving your problem again, and when you do solve it, post it as a solution**

---
Tags: finite-automata
---


# Question
Title: What is the system's mean time to failure?
I have the following homework problem:

> A 10 TB disk drive has an MTTF of 6,000,000 hours. How much data can we store in a system comprised of these disks, if we want the system MTTF to be at least 1.2M hours?
>
> If we are allowed to make it redundant (i.e., two of them operating in a parallel mode), and if the MTTR is 120 hours, what is the system MTTF?

I think it is

$\qquad \operatorname{MTTF}(\text{System}) = \frac{1}{\sum\_i \frac{1}{\operatorname{MTTF}\_i}}$.

# Answer
For part 1, its simple. You need to find the $x$ (as defined below) for which MTTF(system) = 1.20M.

So $1.20 * 10^6 = \frac{1}{\[(\frac{1}{6\*10^6})\*x\]} \implies x = 5$.

We can have 5 disks (50 TB) if we want an MTTF(System) = 1.2M.

Part 2 is homework for you.
> 2 votes

# Answer
Suppose $X,Y$ are exponential random variables with means $\lambda^{-1},\mu^{-1}$. Then $$ \Pr\[\max(X,Y) \< t\] = (1-e^{-\lambda t})(1-e^{-\mu t}) = 1 - e^{-\lambda t} - e^{-\mu t} + (\lambda + \mu)e^{-(\lambda+\mu)t}, $$ and from this one can compute $$ \begin{align\*} \mathbb{E}\[\max(X,Y)\] &= \int\_0^{\infty} t \frac{d}{dt} \[1 - e^{-\lambda t} - e^{-\mu t} + (\lambda + \mu)e^{-(\lambda+\mu)t}\] \\, dt \\ &= \int\_0^{\infty} t(\lambda e^{-\lambda t}+\mu e^{-\mu t}-(\lambda+\mu)e^{-(\lambda+\mu)t}) \\, dt \\ &= \frac{1}{\lambda} + \frac{1}{\mu} - \frac{1}{\lambda+\mu}. \end{align\*} $$ When $\lambda = \mu$, we increase the MTTF from $\lambda^{-1}$ to $(3/2)\lambda^{-1}$. A similar computation shows that by taking three drives, we increase the MTTF to $(3-3/2+1/3)\lambda^{-1} = (11/6)\lambda^{-1}$. Using four drives, we get $(25/12)\lambda^{-1}$.
> 1 votes

---
Tags: computer-architecture, reliability
---


title: Maximizing profit

text:
# Question
Title: Maximizing profit
Problem:

Given 11 numbers

```
{N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N11}

```

where

* N1:amount of profit from product A

N2:amount of profit from Product B

N3:amount of time in **hours** required to make A in factory1(F1)

N4:amount of time in **hours** required to make B in factory1(F1)

N5:maximum number of hours available in a week to make products in F1

N6:amount of time in **hours** required to make A in factory2(F2)

N7:amount of time in **hours** required to make B in factory2(F2)

N8:maximum number of hours available in a week to make products in F2

N9:amount time in **hours** required to make A in factory3(F3)

N10:amount time in **hours** required to make B in factory3(F3)

N11:maximum number of hours available in a week to make products in F3

Output:

3 numbers `{R1,R2,R3}` or `"-1"`

where:

```
R1:total number of A's to manufacture in a week

R2:total number of B's to manufacture in a week

R3:total profit which is **maximum possible profit** with the right mix of A and B

**result = `-1` if R1 and/or R2 is non integer(contains fraction)**

```

consider the Input `{10.5,13,3,7,5,6,5,11,16,11,21.6}`

```
                    PRODUCT A               PRODUCT B        total hours/Week

Profit/Piece             10.5                  13

Hours required in F1     3                     7                   5

Hours required in F2     6                     5                   11

Hours required in F3     16                    11                  21.6

```

Any Idea/Algorithm?

Thanks in Advance

# Answer
This is a basic constrained optimization problem. This will require linear programming because you have inequality constraints.

Alternatively since this is entirely linear and each factory is **independent** of each other, work out which option A/B offers the highest return per factory. Call this the chosen product. Work out how many units of the chosen product can be produced given the constraint. Look at the factory downtime, if this is bigger than required to build more unit of the non-chosen item then this must also be produced.

Then compare hour blocks to produce the object A,B (i.e. F1 is 3 or 7) to calculate how many multiples of the not-chosen product are foregone in producing the last unit of the chosen product, you must also add on any factory downtime at this stage. i.e. let the value for the chosen product be 7 and 3 for the non-chosen, then we have 2 units foregone. But if we have 2 hours downtime, then it should be (7+2) / 3 to yield 3 units foregone.

Compare if the units foregone for the last output of the chosen product at a given factory exceed in value the last unit produced (this is the remainder problem).

If true, then the factory produces this mixed output. If false, proceed with the prior output strategy for said factory.

Select highest and then move on to the next factory. Rest should be obvious.

This is my C++ code to solve the problem using my alternative method. I hope this clears up all questions.

**// Cybernex's example program in c++**

include iostream

using namespace std;

// prototypes and n11 variables setting

void announcer(int);

void calculatefactory (float, float, float, float, float);

void closingannounce();

float price1 = 10.5;

float price2 = 13;

float hourf1a = 3;

float hourf1b = 7;

float hourf2a = 6;

float hourf2b = 5;

float hourf3a = 16;

float hourf3b = 11;

float totalf1 = 5;

float totalf2 = 11;

float totalf3 = 21.6;

// total output of good a

float r1 = 0;

// total output of good b

float r2 = 0;

// total value of output

float r3 = 0;

int main(){

```
// factory 1

```

announcer(1); calculatefactory (price1, price2, hourf1a, hourf1b, totalf1);

// factory 2 announcer(2); calculatefactory (price1, price2, hourf2a, hourf2b, totalf2);

// factory 3 announcer(3); calculatefactory(price1, price2, hourf3a, hourf3b, totalf3);

// closing outputs closingannounce();

return 0; };

// for clarity in outputs

void announcer (int a){ cout \<\< endl \<\< "We are calculating for factory: " \<\< a \<\< endl \<\< endl; };

// gives final results

void closingannounce (){ cout \<\< endl \<\< endl \<\< endl \<\< endl; cout \<\< "Total quantity of A produced by all factories " \<\< r1 \<\< endl; cout \<\< "Total quantity of B produced by all factories " \<\< r2 \<\< endl; r3 = (r1 * price1); r3 = r3 + (r2 * price2); cout \<\< "Total value of output is " \<\< r3 \<\< endl; }

// main alg

void calculatefactory (float pricea, float priceb, float hoursa, float hoursb, float totaltime){

// CHECK AT LEAST 1 UNIT CAN BE PRODUCED FOR EACH GOOD

bool canamake = false; bool canbmake = false; if (hoursa \<= totaltime){ canamake = true; }; if (hoursb \<= totaltime){ canbmake = true; };

// No output possible

if (canamake == false && canbmake == false){ cout \<\< endl \<\< "No output possible at this factory" \<\< endl; };

// A is possible, B is not

if (canamake == true && canbmake == false){

// first step work out how many of A can be made

int internaloutput = totaltime / hoursa;

// We cannot use the remaining hours so this is total output for this factory

r1 = r1 + internaloutput;

cout \<\< endl \<\< "The factory produces " \<\< internaloutput \<\< " of good A" \<\< endl; cout \<\< "The factory produces 0 of good B" \<\< endl;

};

// B is possible, A is not

if (canamake == false && canbmake == true){

// first step work out how many of B can be made

float internaloutput = totaltime / hoursb;

// We cannot use the remaining hours so this is total output for this factory

r2 = r2 + internaloutput;

cout \<\< endl \<\< "The factory produces " \<\< internaloutput \<\< " of good B" \<\< endl; cout \<\< "The factory produces 0 of good A" \<\< endl;

};

// A and B are feasible

if (canamake == true && canbmake == true){

// SELECT CHOSEN OUTPUT

float internal1 = pricea / hoursa; float internal2 = priceb / hoursb;

// Chosen output is A OR if they are even we will make A anyway

if (internal1 \>= internal2){

// Work out how much of A we can make

int internaloutputa = totaltime/hoursa; int internaloutputb;

// can we make any of B with the remainer?

float internal3 = totaltime; internal3 = internal3 - (internaloutputa * hoursa);

if (internal3 \>= hoursb){ internaloutputb = internal3 /hoursb; };

// We now have our first set of solutions, which we must test for the unit foregone problem // first remove the marginal output from good a

int altinternaloutputa = internaloutputa - 1; int altinternaloutputb;

// now we look at how many more of b we can make

float internal4 = totaltime; internal4 = internal4 - (altinternaloutputa * hoursa); if (internal4 \>= hoursb){ altinternaloutputb = internal4 / hoursb; };

// Now we compare the values to work out which solution we prefer

float value1 = internaloutputa\*price1 + internaloutputb * price2; float value2 = altinternaloutputa * price1 + altinternaloutputb * price2;

// former output is more profitable

if (value1 \>= value2){ r1 = r1 + internaloutputa; r2 = r2+ internaloutputb; cout \<\< endl \<\< "The factory produces " \<\< internaloutputa \<\< " of good A" \<\< endl; cout \<\< "The factory produces " \<\< internaloutputb \<\< " of good B" \<\< endl; } if (value1 \< value2){ r1 = r1 + altinternaloutputa; r2 = r2 + altinternaloutputb; cout \<\< endl \<\< "The factory produces " \<\< altinternaloutputa \<\< " of good A" \<\< endl; cout \<\< "The factory produces " \<\< altinternaloutputb \<\< " of good B" \<\< endl; } };

// Chosen output is B

if (internal1 \< internal2){

// Work out how much of B we can make

int internaloutputb = totaltime/hoursb; int internaloutputa;

// can we make any of B with the remainer?

float internal3 = totaltime; internal3 = internal3 - (internaloutputb * hoursb);

if (internal3 \>= hoursa){ internaloutputa = internal3 /hoursa; };

// We now have our first set of solutions, which we must test for the unit foregone problem // first remove the marginal output from good a

int altinternaloutputb = internaloutputa - 1; int altinternaloutputa;

// now we look at how many more of b we can make

float internal4 = totaltime; internal4 = internal4 - (altinternaloutputb * hoursb);

if (internal4 \>= hoursa){ altinternaloutputa = internal4 /hoursa; };

// Now we compare the values to work out which solution we prefer

float value1 = internaloutputa\*price1 + internaloutputb * price2; float value2 = altinternaloutputa * price1 + altinternaloutputb * price2;

// former output is more profitable

if (value1 \>= value2){ r1 = r1 + internaloutputa; r2 = r2 + internaloutputb; cout \<\< endl \<\< "The factory produces " \<\< internaloutputa \<\< " of good A" \<\< endl; cout \<\< "The factory produces " \<\< internaloutputb \<\< " of good B" \<\< endl; }

if (value1 \< value2){ r1 = r1 + altinternaloutputa; r2 = r2 + altinternaloutputb; cout \<\< endl \<\< "The factory produces " \<\< altinternaloutputa \<\< " of good A" \<\< endl; cout \<\< "The factory produces " \<\< altinternaloutputb \<\< " of good B" \<\< endl; } }; }; };
> 1 votes

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


# Question
Title: Can someone help me understand cache conscience radix sort? (excerpt from journal article attached)
***Article:***

# CC-Radix: a Cache Conscious Sorting Based on Radix sort

**(IEEE 2003)**

I'm trying to figure out what the author means by this section:

> Explanation of CC-Radix For clarity reasons, we explain the recursive version of CC-Radix sort as shown in Figure 3. However, we use the iterative implementation of CC-Radix for the evaluations in this paper because it is more efficient. The parameters of CC-Radix are bucket, which is the data set to be sorted, and b, which is the number of bits of the key that still have to be sorted. Constant b is explained below.
>
> ```
> CC-Radix(bucket, b)
>
> ￼if fits in cache (bucket) then
>    Radix sort(bucket, b )
> ￼￼￼￼￼￼else
>    sub-buckets = Reverse sorting(bucket, )
>    for each sub-bucket in sub-buckets
>       CC-Radix(sub-bucket, )
> endfor
> ￼￼￼￼￼endif
> end
>
> ```
>
> Figure 3. Pseudocode of CC-Radix The algorithm starts by checking whether the data struc- tures to sort bucket fit in cache level Li. Those data struc- tures are vectors S and D and the counter vectors C, one for each of the digits of the key. If so, CC-Radix calls Radix sort. If the data structures do not fit in cache level , the algorithm partitions that bucket into sub-buckets by sorting the bucket by the most significant digit using the counting algorithm (explained above). Here, we call this process of partitioning, Reverse Sorting, and it takes into account the computer architecture of the machine. For each sub-bucket, the CC-Radix sort is called again. Note that the first call to the routine processes the com- plete data set. Further calls to the routine process sub- buckets. Note also that certain subsets of the data may need more Reverse sorting calls than others depending on the data skew.
>
> Now, we explain the details of Reverse sorting and the sizing of the parameters of Radix sort. Reverse sorting. After each call of Reverse sorting, the number of digits that remain to be sorted for a specific sub- bucket is decremented by one.

I don't understand the "Reverse Sorting" part of this - how is that supposed to work?

I know this is a long shot, but I'm really stuck on what they mean. Any help is appreciated!

# Answer
The naming in the pseudo-code seems to be making things more confusing than they need to be, and it also seems to be glossing over some detail, but here's what I think is going on.

Let's just jump right in on a small example. Suppose we have a data set, the integers 0-7 in binary: $000, 001, 010, 011, 100, 101, 110, 111$. But obviously they're not necessarily given to you in sorted order. Let's say the input is actually: $110, 101, 000, 010, 100, 111, 001, 011$.

If all this data fits in the cache, then you just run normal radix sort. That's the first branch of the `if` statement. For illustration, lets say that the cache can only hold two elements. Therefore, we end up in the `else` branch. The "reverse sorting" step splits the input into two sub-buckets based on the most significant bit. So we get two buckets:

$1: (10, 01, 00, 11)$ and $0: (00, 10, 01, 11)$. We recursively call our function on each of these smaller buckets. Since they are smaller, they *might* now fit inside the cache, and we could run normal radix sort.

So now we're in the recursive call on the first sub-bucket. The input is $1:(10, 01, 00, 11)$. However, our cache size is only 2. Therefore we move into the else branch again. We split the input into $11:(0,1)$ and $10:(1, 0)$. and call the function recursively. Now finally on each of these recursive calls, the input is small enough to fit in the cache, and we run normal radix sort.

The other recursive calls function similarly. Their pseudo-code seems to be missing how the partitions are pieced back together in a cache conscious way. Maybe this is obvious or covered elsewhere in the paper.
> 3 votes

---
Tags: algorithms, sorting
---


# Question
Title: Show that the Turing Machine domain can be viewed as a classical planning domain
This is one of my assignments. I am not able to comprehend how to reduce the Turing machine domain to Classical planning domain. My understanding is that we have to essentially perform complexity analysis of classical planning domain. So I have defined these two languages

a) PLAN-EXISTENCE(D) = {P : P is the statement of a planning problem that has a solution}

b) PLAN-LENGTH(D) = {(P,n) : P is the statement of a planning problem that has a solution that contains no more than n actions (length ≤ n) }

And then I proceed to prove that both these are decidable in classical planning domain.

Is this the correct approach? Please help me

# Answer
> 4 votes
In order to show that the computation of a Turing machine can be modeled as a planning problem, you can encode the tape symbols, the head position and state, and the execution of a transition using states:

```
symb(i,x)   : i-th cell of the tape contains symbol x
head(i,q)   : head is over cell i in state q
exec(i,q,x) : execute the transition at i-th cell in state q over symbol x
accept      : accept the input

```

At the beginning `symb(i,x)` are true/false according to tape content; `head(1, q0)` is true; and all other states are false. The goal G is `{accept}`.

Actions are built using the transition table of the Turing machine; suppose that you have the transition:

```
 a, q0 -> b, q1, Left

```

Then for every cell i of the tape you can add the actions:

```
 symb(i,a) AND head(i,q0) => !head(i,a) AND exec(i,q0,a)
 exec(i,q0,a) AND symb(i,a) => !symb(i,a) AND symb(i,b)
 exec(i,q0,a) AND symb(i,b) => !exec(i,q0,a) AND head(i+1,q1)

```

The actions for the transitions to accepting states are similar.

Note that actions with only 2 positive preconditions and two postconditions are enough to "simulate" the behaviour of a Turing machine.

# Answer
> 0 votes
You should show that every Turing machine could be molded as a planning problem and vise versa. As a hint consider that any Turing machine consists of very simple actions (using action tables) and complex action in planning problem could be done by simple Turing machine.

---
Tags: complexity-theory, turing-machines, artificial-intelligence
---


# Question
Title: Is O(mn) considered "linear" or "quadratic" growth?
If I have some function whose time complexity is O(*mn*), where *m* and *n* are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both *m* and *n*) or "quadratic" (since it's a product of two sizes)? Or something else?

I feel calling it "linear" is confusing because O(m + n) is also linear but much faster, but I feel like calling it "quadratic" is also weird because it's linear in each variable separately.

# Answer
> 22 votes
In mathematics, functions like this are called multilinear functions. But computer scientists probably won't generally know this terminology. This function should definitely **not** be called linear, either in mathematics or computer science, unless you can reasonably consider one of $m$ and $n$ a constant.

# Answer
> 14 votes
To elucidate on the discussion in the comments, it matters what you're measuring growth relative to.

As mentioned by @Kaveh, $O(mn)$ is not linear in both at the same time, but is linear if one is a constant and the other one grows.

On the other hand, $O(m+n)$ would likely be considered linear. Intuitively, if $m$ doubles, or if $n$ doubles, or even if both $m$ and $n$ double, $m+n$ cannot more than double. This is not true of $mn$; if $m$ and $n$ both double $mn$ goes up by 4. This is why in many contexts this running time would be considered quadratic. I give an example of this with string matching in a couple paragraphs.

But usually when you're using Big-$O$ notation, you're using it in reference to something in particular. Since we're mostly theorists, it's generally the size of the input to the problem.

Let's take Matrix Addition, for example. Adding two $m\times n$ matrices takes $O(mn)$ time. But each element of our input is only touched once, so this would usually be called linear. Put in other words, our input is of size $O(mn)$, so a running time of $O(mn)$ is linear in the size of the input.

Now let's look at string matching--namely, we are given a string of size $m$ and a string of size $n$ and we want to see if there is an occurrence of the smaller string within the bigger string. We can check this naively in $O(mn)$ time; this would generally be considered quadratic. Why? If $m$ and $n$ can be anything, set $m = n$. Then our running time is $O(m^2)$ and our input is of size $2m$.

On the other hand, if we use the Rabin-Karp algorithm, we get (on average) $O(m+n)$ time. Our input consisted of both strings, so our input was of size $O(m+n)$ as well. Therefore, this would generally be referred to as linear.

To sum up: $O(mn)$ is generally called linear for things like matrix multiplication because it's linear in the size of the input, but it's generally called quadratic for things like string matching because of the smaller input. Which term is appropriate depends on the context you're using it in.

# Answer
> 8 votes
If you are measuring the running time in $(m,n)$ then $O(mn)$ is **not** a linear function in $(m,n)$. If there is no relation between $m$ and $n$ this function can grow *quadraticly* in general.

However it is a linear function in each of them separately, i.e. if you fix one of them and look at the growth in the other variable then it is a linear function in other one.

# Answer
> 3 votes
To measure the complexity of the problems with **multiple inputs**, one way is to find the **dominant** variable and then bound other inputs based on that variable. With this approach you could have the complexity function based on **single variable**.

# Answer
> 0 votes
Given some Language $L = \\{w\_1\\#w\_2|w\_i \in (\Sigma\setminus\\{\\#\\})^\*,\dots\\}$ and a function $f$ such that $\min\\{|w\_1|,|w\_2|\\} \leq f(|w|)$ for every $w=w\_1\\#w\_2 \in L$ you can estimate the running time of an $\mathcal O(|w\_1|\cdot|w\_2|)$ algorithm which recognizes $L$ as $\mathcal O(f(|w|)\cdot(|w|-f(|w|))= \mathcal O(f(|w|)|w|-f(|w|)^2)= \mathcal O(f(|w|)|w|)$.

This means you get linear time, if the smaller part of your input is constant (relative to the whole input), something in between (like $\mathcal O(n\log n)$) if it's sublinear and quadratic runtime if it's linear.

---
Tags: terminology, asymptotics, landau-notation
---


# Question
Title: Independent set on cubic triangle-free graphs
I know that maximum independent set on cubic triangle-free graphs is NP-complete.

Is it still NP-complete in case we require the independent set to be of size exactly $|V|/2$?

Basiclly, YES instance of independent set problem on cubic triangle-free graphs problem must have exactly $|V|/2$ nodes. NO instance has an independent set of size less than $|V|/2$.

# Answer
Let's start by proving that the maximum independent set is of size at most $|V|/2$. Let $I$ be an independent set. For each vertex $v$, let $\alpha(v)$ be the number of its neighbors in $I$. If $\alpha(v) \geq 1$, then we know that $v \notin I$. Since the graph is cubic, $\sum\_v \alpha(v) = 3|I|$. Since $\alpha(v) \leq 3$, the number of vertices such that $\alpha(v) \geq 1$ is at least $|I|$. Hence $|I| \leq |V|/2$.

When can we have equality? We must have $\alpha(v) \in \\{0,3\\}$, so for each vertex not in $I$, all its neighbors must be in $I$. The converse is also true - for each vertex in $I$, all its neighbors are not in $I$. In other words, the graph must be bipartite. This can be checked in polynomial time.
> 7 votes

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


# Question
Title: Problems that are Cook-reducible to a problem in NP $\cap$ co-NP
Let $\mathcal{A}$ be a problem in $\text{NP} \cap \text{co}$-$\text{NP}$.

Now assume we can reduce another problem $\mathcal{B}$ to it using Cook reduction.

What conclusions can we draw about $\mathcal{B}$? Does this question even make sense?

I'm asking because from what I understand Cook reductions differ from Karp reductions (for example, $\text{NP}$ cannot be distinguished from $\text{co}$-$\text{NP}$). I'm pretty confused and can't seem to really understand the properties of Cook reductions. Any good reference about the topic would also be appreciated!

I hope this question is not too basic, but I was not able to find anything about it.

# Answer
> 8 votes
Nice question/homework!

Stated in another way: $\mathsf{NP}$ is not closed under Cook reductions (assuming $\mathsf{P}\neq \mathsf{NP}$).

How about $\mathsf{NP}\cap\mathsf{coNP}$? Is $\mathsf{NP}\cap\mathsf{coNP}$ closed under Cook reductions? Is the only reason that $\mathsf{NP}$ is not closed under Cook reductions is because it is not closed under complement so if we take those $\mathsf{NP}$ problems whose complement is also $\mathsf{NP}$ do we get around the problem?

For example, if we have a Cook reduction from a problem to Factoring, would that mean that the problem is in $\mathsf{NP}\cap\mathsf{coNP}$?

An oracle doesn't just allow us to ask about membership and non-membership in the oracle, it allows us to ask very complicated list of questions where each question can depend on the answer for the previous one.

Let's look at a problem $Q \in \mathsf{P^{NP \cap coNP}}$. We know that there is a polynomial-time algorithm $M$ and a set $A\in \mathsf{NP \cap coNP}$ such that $M^A$ solves the problem $Q$. Is $Q$ in $\mathsf{NP}$?

Hint: when does $M^A$ accept an input $x$?

Don't read the answer below if this is an assignment, the answer is not difficult, you should be able to solve it if you spend a few hours on it, and spending those hours is what makes you learn.

> Let's look at the execution of $M^A$ on an input $x$. $M$ will make a number of queries to $A$ during its computation and will receive YES and NO answers, and finally will accept or reject. If we could compute that answers to the queries in polynomial time we would have shown that the problem is in $\mathsf{P}$, we would simulate the algorithm $M$ and whenever it asked a query from $A$ we would compute the answer and give to $M$ and continue with its simulation.
> But $A\in\mathsf{NP \cap coNP}$ and we don't know how to compute the answers to queries in polynomial time. But we don't need to do this in polynomial-time! We can just guess the answers to the questions and verify our guesses in polynomial-time. To be able to verify the answers for both positive and negative answers we need $A\in\mathsf{NP\cap coNP}$, that is why this does not work for $A \in\mathsf{NP}$, that would allow only verifying positive answers.
> Let $V\_{YES}$ and $V^{NO}$ be two polynomial-time verifiers for membership and non-membership in $A$. Consider the verfier $V(x,y)$ which works as follows:
> I. check that $y$ consists of 1. a string $c$ (computation of $M$ on $x$), 2. a list of strings $q\_1,\ldots,q\_m$ (queries to the oracle in $c$), 3. a list of strings $a\_1,\ldots,q\_m$ (answers to queries from oracle), 4. a list of strings $w\_1,\ldots,w\_m$ (certificates/proofs/witnesses for the correctness of the query answers).
> II. check that the list of queries $q\_1,\ldots,q\_m$ contains all oracle queries in $c$,
> III. check that the computation $c$ is an accepting computation of $M$ on $x$ if answers to the queries are $a\_1,\ldots,a\_m$.
> IV. for all $1\leq i \leq m$, check that if $a\_i=YES$ then $V^{YES}$ accepts $(q\_i,w\_i)$ and if $a\_i=NO$ then $V^{NO}$ accepts $(q\_i,w\_i)$.
> All of these steps can be checked in polynomial-time. So we have a verifier for YES answers of $M^A$. Furthermore note that if $M^A$ accepts $x$, then there is $y$ satisfying these conditions which has polynomial-size: the computation of a polynomial-time machine is of polynomial-size and the number of queries and the size of all queries are also polynomial in the input. Moreover the size of certificates for queries are also bounded by some polynomial in the size of the queries, so again are polynomial in the size of input. In short we have a polynomial-time verifier with polynomial-size certificates for $M^A$.
> This completes the proof that $Q \in \mathsf{NP}$. A similar argument shows that $Q\in\mathsf{coNP}$. So $Q\in\mathsf{NP\cap coNP}$. In other words, $\mathsf{P^{NP\cap coNP}} \subseteq \mathsf{NP\cap coNP}$.

# Answer
> 7 votes
If $\mathcal{A} \in \mathrm{NP} \cap \mathrm{co\text{-}NP}$, then there is a witness for $x \in \mathcal{A}$ as well as for $x \notin \mathcal{A}$. In other words, if I give you a computation with oracle to access to $\mathcal{A}$, I can convince that I didn't lie about the oracle answers by giving the appropriate witnesses.

Since $\mathcal{B}$ Cook-reduces to $\mathcal{A}$, you can solve $\mathcal{B}$ in polynomial time using an oracle to $\mathcal{A}$. Connecting the dots, we conclude that $\mathcal{B} \in \mathrm{NP} \cap \mathrm{co\text{-}NP}$.

---
Tags: complexity-theory, reductions, np
---


# Question
Title: Difference between Data point, attribute, feature?
Can anyone tell me the difference between the following in data mining? I am taking a class this semester and the professor is using the terms so frequently, I don't know what these mean anymore.

* Data point
* attribute
* feature

# Answer
> 3 votes
An attribute is usually synonymous with feature, both of which refer to a single dimension. A data point probably refers to a complete record. That is, a data point is a collection of features.

For example, imagine we have a bunch of data on people and we want to classify each one as being male or female. Specifically, for each person (record), we have the following attributes (features): height, weight, and eye color. A data point would be one person's 3-dimensional record (e.g. \[74in, 200lbs, brown\] or \[61, 125, blue\]).

---
Tags: terminology, data-mining
---


title: P, NP and specialised Turing Machines

text:
# Question
Title: P, NP and specialised Turing Machines
I'm sort of new, but very interested to the field of computing and complexity theory, and I want to clarify my understanding about how to class problems, and how strongly the problems relate to the machine being used to solve them.

**My Understanding**

* Standard Turing Machine - a Turing Machine which has a finite alphabet, finite number of states and a single right-infinite tape
* Turing-Equivalent Machine - a Turing Machine which, can emulate, and be emulated by, a Standard Turing Machine (quite often with some trade-off between space and time achieved by the emulation)
* `P` \- the class of problems which can be solved in polynomial time using a Standard Turing Machine (defined above)
* `NP` \- the class of problems which can be verified in polynomial time using a Standard Turing Machine
* `NP-complete` \- the hardest problems which are still in `NP`, which all `NP` problems can be converted to in polynomial time

**My Question**

Are the complexity classes (`P`, `NP`, `NP-complete`, etc) related to the algorithm, or the algorithm and the machine?

Said in another way, if you could create a Turing Equivalent Machine (that can solve all the problems that a Standard TM can, but in a different amount of time/space) and this new machine could solve an `NP-complete` problem in time which grows as a polynomial with respect to the input, would that imply `P=NP`?

Or must the `NP-complete` problem be solvable on all possible Turing Machines in polynomial time to be considered in `P`?

Or do I mis-understand something fundamental above?

I have had a look (maybe not with the correct search terms, I don't know all the jargon quite well) but it seems most lectures/notes etc. focus on standard machines but say that custom machines often have some time/space speed up at the expense of space/time, without saying how that bears on complexity classes. I'm not really familiar enough with the jargon in this field yet to find papers which explain this.

# Answer
> 9 votes
Algorithms and machines are not defined in your question and I don't think they are needed to ask what you want to ask.

Complexity classes are defined using Turing machines. That is their definition. If you want to prove anything you have to use these definitions. Anything about any other model is unrelated unless you prove some correspondence between that model and Turing machines.

Let me add that there is a hypothesis that says that "efficient" "computation" in any "reasonable" "machine" will capture the same number theoretic functions. However it is not a provable statement unless one defines the quoted terms. We can prove it for many machines but not all machines. Being Turing machine equivalent is not sufficient, we want them to be *Strongly* so, i.e. we should be able to simulate those machines with Turing machines and vice versa efficiently. The nice thing about $\mathsf{P}$ and $\mathsf{NP}$ is that they are very robust classes, i.e. small and big differences in machine models does not change the class. However it is true all the time. For example, I can define a simple new model of computation where I have an basic operation that in constant time solves a problem that is unsolvable in $\mathsf{P}$. Then it is obvious that this model will not be strongly equivalent to Turing machines.

The example above was an artificial one. However right now we have a model of computation that seems closer to efficient computation in practice than polynomial-time Turing machines: *bounded-error probabilistic/randomized* Turing machines, efficient algorithms in that model are referred to as $\mathsf{BPP}$.

Many experts believe that $\mathsf{BPP}=\mathsf{P}$ but we are far from proving it.

We have another model of computation which some experts expect to become practicable in future: *quantum* Turing machines, efficient algorithms in that model are referred to as $\mathsf{BQP}$. We don't know if it is different from $\mathsf{P}$ but some experts conjecture that it is different and more powerful than $\mathsf{P}$.

---

In short, if you want to prove a complexity theory result about $\mathsf{P}$ and $\mathsf{NP}$, you have to use either the original definitions using Turing machines, or first prove a correspondence between them and the classes you are using based on some other model of computation. As I mentioned above it is quite easy to create machine models where polynomial "time" in them can solve an $\mathsf{NP}$ (or even arbitrarily more difficult) problem: just add a basic operation to your machine model that solves that problem and let the "time" that operation takes to be one unit of time.

# Answer
> 6 votes
Just a trivial note to underline that the *efficient simulation* of a Turing machine means not only that it can simulate the *computation* of a Turing machine and vice versa efficiently (polynomial time slowdown); but also that its *input/output must be efficiently converted* from one model to the other.

A trivial example: if you find a Turing equivalent device that can solve a SAT problem in constant time, but uses as input a heap of marbles (unary), then you cannot conclude anything. The same if your device uses a binary input but it tooks an exponential number of steps to convert an instance of SAT to the *input format* used by it.

# Answer
> 3 votes
Your understanding is very good! You can also find more info in a text if your are interested, e.g. Sipser's Intro to the Theory of Computation.

There is this idea called the Church-Turing Thesis that says anything that can be computed somehow, can be computed using a Turing Machine. (It's not provable, but just an idea, or a sort of law of nature that we think is true).

I mention this because there is also the "Extended Church Turing Thesis" that says that anything that can be computed in polynomial time somehow, can be computed in polynomial time using a Turing Machine.

There's good reason to doubt this conjecture because we know of quantum computing algorithms that get a better-than-polynomial speedup over the best known classical algorithms. However, other than that, it is thought that any classical machine you can build (certainly any variant on a Turing Machine) cannot be exponentially faster than a Turing Machine. So if your "Turing-Equivalent Machine" could run an algorithm that solved an NP-Complete problem in polynomial time, then P = NP because I could convert it to a polynomial-time algorithm for the same problem on a TM.

But if you thought up some sort of a Turing-Equivalent Machine, probably one of the first things you'd do is figure out how to simulate it with a classical TM, and that would tell you if you have a polynomial-time conversion or not. And the answer would almost certainly be yes, except maybe your could be exponentially slower (but not faster -- we think, unless it's quantum, then maybe).

---
Tags: complexity-theory, computability, terminology, turing-machines, complexity-classes
---


# Question
Title: Why does backtracking work the way it does?
I just recently started learning in a CS context (as opposed to a programming context) about simple recursive functions, along with the combinatorial applications, and techniques such as Backtracking and Divide et Impera.

The example problem that I chose for my questions is the n queens problem (given n queens and a n\*n chessboard, how do you position the queens such that they can't attack each other?). I understood that the basic idea is to generate all possible placements (by generating a cartesian product) and then simply discarding them as they come along if they are invalid (through the validation function).

Here is my sample implementation:

```
    int valid (int k)
    {
    for (int i = 1; i < k; i++)
    {
        if (sol[i] == sol[k]) return 0;
        if (abs(sol[i] - sol[k]) == abs(i - k)) return 0;
    }
    return 1;
}

void print ()
{
    for (int i = 1; i <= n; i++)
    {
        cout << sol[i];
    }
    cout << endl;
    how++;
}

void backtrack (int k)
{
    if (k == n+1) print();
    else
    {
        sol[k] = 0;
        while (sol[k] < n)
        {
            sol[k]++;
            if (valid(k)) backtrack(k+1);
        }
    }
}

```
1. Why is it that in the validation function, the checking of the solution is done progressively by checking 1 with k, 2 with k and so on. I think that the solution can be correct in pairs of (i, k) but wrong overall (for example 1 and 2 relative to 3 are placed correctly, but 1 relative to 2 is placed incorrectly)?

# Answer
> for example 1 and 2 relative to 3 are placed correctly, but 1 relative to 2 is placed incorrectly?

You have already tested that 1 and 2 are placed correctly, otherwise you wouldn't call `backtrack(3)`.

Recall that `sol[i] = j` means that the queen in column $i$ is put at row $j$. By calling `backtrack(k+1)` you have already verified that every queen in $1 \dots k$ are placed correctly (non-colliding).
> 2 votes

---
Tags: algorithms, recursion, backtracking
---


# Question
Title: Can Turing Machines solve non-decision problems?
Since TMs are equivalent to algorithms, they must be able to perform algoriths like, say, mergesort. But the formal definition allows only for decision problems, i.e, acceptance of languages. So how can we cast the performance of mergesort as a decision problem?

# Answer
Usually, Turing machines are explained to calculate functions $f:A \rightarrow B$, of which decision problems are a special case where $B = \mathbb{B}$.
> 7 votes

# Answer
You can define two kinds of Turing Machines, transducers and acceptors. Acceptors have two final states (accept and reject) while transducers have only one final state and are used to calculate functions.

Let $\Sigma$ be the alphabet of the Turing Machine.

Transducers take an input $x \in \Sigma^\*$ on an **input tape** and compute a function $f(x) \in \Sigma^\*$ that is written on another tape (called **output tape**) when (and if) the machine halts.

The are various results that link together acceptors and transducers. For example:

Let $\Sigma=\\{0, 1\\}$. Given a language $L \subseteq \Sigma^\*$ you can always define $f : L \to \\{0,1\\}$ to be the charateristic function of $L$ i.e. $$ f(x) = \begin{cases} 1 & \mbox{if $x \in L$} \\ 0 & \mbox{if $x \not\in L$} \end{cases} $$

In this case an acceptor machine for $L$ is essentially the same as a transducer machine for $f$ and vice versa.

For more details you can see Introduction to the Theory of Complexity by Crescenzi (download link at the bottom of the page). It is lincensed under Creative Commons.
> 6 votes

# Answer
We focus on studying the decision problems in undergrad complexity theory courses because they are simpler and also questions about many other kinds of computations problems can be reduced to questions about decision problems.

However there is nothing in the definition of Turing machine by itself that restricts it to dealing with decision problems. Take for example the number function computation problems: we want to compute some function $f:\\{0,1\\}^\*\to\\{0,1\\}^\*$. We say that a Turing machine compute this function if on every input $x$, the machine halts and what is left over the tape is equal to $f(x)$.
> 4 votes

# Answer
1. It is easy to define what it means for a Turing Machine to compute a function: The input is written on the tape at the beginning, and the output is whatever is on the tape when the machine halts (if it halts).
2. Most complexity classes we introduce initally, like $\mathsf{P}$, are defined for decision problems. However, there are also complexity classes for function problems, like $\mathsf{FP}$.
3. We can convert between a decision problem and function problem pretty easily in most cases. In a function problem, you are given input $x$ and want to compute $f(x) = y$. In the equivalent decision problem, you are given input $(x,y)$, you want to decide whether $f(x) = y$ or not. (Or even whether $f(x) \leq y$, or so on.) Often it turns out that we can solve the first in polynomial time if and only if we can solve the second in polynomial time, so complexity-wise, the distinction is not very important.
> 2 votes

---
Tags: terminology, turing-machines
---


# Question
Title: Analyzing programs with multiple for-loops
If they were all linked to make a condition such as ($1 \< i \< j \< k \< n$), I know how to solve, but the last loop is disconnected so I have no clue on how to do these...

the ones like

```
for(i = 1 to n);
   for(j = i to n);
      x++;

```

I can use $1 \leq i \leq j \leq n$ and use $x\_1 + x\_2 + x\_3 = n-1$ and find out the general solution which is $\frac{n(n+1)}{2}$. But disconnected loops I have no idea. Consider the following for loops.

```
    for(i = 1 to n);
       for(j = i to n);
          for(k = 1 to i*n);
              x++; (constant time)

    for(i = 1 to n-1);
        for(j = i+1 to n);
            for(k = 1 to j);
                x++; (constant time)

```

I need to find the general solution.

# Answer
From your comments, it seems that you are incorrectly calculating the number of loops. And since I do not where to start from for you, I will start from a basic level - please ignore whatever you know or find obvious. I am also going to assume that the semi-colons after each for loop are not present - otherwise in many programming languages, the variable `x` will be incremented only twice, once after each *apparently* nested loops.

Counting how many times each loop executes can be written as a discrete summation. For example, a simple `for` loop from $1$ to $n$, where $1$ operation takes place, can be seen as $\sum\limits\_{i = 1}^{n}1 = n$. That is, the loop will execute $n$ times (or the increment statement will be executed $n$ times). Nested loops can be counted as nested summations. When evaluating any summation, consider the iterating variable as the variable, and treat everything else as a constant.

Consider the first set of nested loops. The number of executions/number of times `x` is incremented can be written as: $$T\_1(n) = \sum\limits\_{i = 1}^{n}\sum\limits\_{j = i}^{n}\sum\limits\_{k = 1}^{in}1$$ Notice the upper and lower limits on each summation, and compare with your loop variables and ranges. We start evaluation from the innermost loop as follows: $$\begin{align\*} T\_1(n) & = \sum\limits\_{i = 1}^{n}\sum\limits\_{j = i}^{n}\sum\limits\_{k = 1}^{in}1 = \sum\limits\_{i = 1}^{n}\sum\limits\_{j = i}^{n}in \\ &= \sum\limits\_{i = 1}^{n}\left(in \sum\limits\_{j = i}^{n}1\right) \ \ \ \ \ \ \text{(considering $j$ as the only variable)} \\ &= \sum\limits\_{i = 1}^{n} \left(in(n - i + 1) \right) = \sum\limits\_{i = 1}^{n}((n^2 + n)i - ni^2) \\ &= \sum\limits\_{i = 1}^{n}\left((n^2 + n)i\right) - \sum\limits\_{i = 1}^{n}\left(ni^2\right) \\ &= (n^2 + n)\sum\limits\_{i = 1}^{n}i - n\sum\limits\_{i = 1}^{n}i^2 \\ &= n(n+1)\cdot \frac{n(n+1)}{2} - n \cdot \frac{n(n+1)(2n+1)}{6} \\ &= \frac{n^2(n+1)(n+2)}{6} \end{align\*} $$

You can verify that if `x` is initially 0, this will be its value after the first set of nested loops. For the second set, I will provide the the summation and answer, leaving the actual work up to you.

$$T\_2(n) = \sum\limits\_{i = 1}^{n-1}\sum\limits\_{j = i+1}^{n}\sum\limits\_{k = 1}^{j}1 = \frac{n(n-1)(n+1)}{3}$$

As others have pointed out, since the two blocks of nested loops are serial, you can just add the number of times each has executed to get the final count as $T(n) = T\_1(n) + T\_2(n)$. This will give you the number of times `x` has been incremented. This simple mechanical process should help you out in most instances of nested loops.
> 2 votes

# Answer
Hint: Consider the following program:

```
int x = 0;
x += 15;
x += 20;

```

In the end, $x = 15 + 20 = 35$. A similar idea works for disconnected loops.
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: CFG with regular expression terminals on RHS
Suppose that we expand our idea of context free grammar rules to allow regular expressions of terminals on the right hand side. For example, consider $G\_1$:

$\begin{align\*} S & \rightarrow (a \mid b) S (c \mid d) \\ S & \rightarrow (a \mid b) A (c \mid d) \\ A & \rightarrow (f \mid g)^\* \end{align\*} $

Then the language of $G\_1$ is the following:
$$L(G\_1) = \\{(a \mid b)^n (f \mid g)^\* (c \mid d)^n \mid n \> 0\\}$$

Give a standard CFG that has the same language as $G\_1$, is your grammar weakly equivalent to $G\_1'$, strongly equivalent to $G\_1'$, or both? Why?

Secondly, how can I transform any CFG with regular expressions of terminals on the right hand side to a normal context free grammar?

# Answer
The general answer is pretty straightforward: if you have a grammar rule of the form $S \rightarrow {\alpha}r{\beta}$, where $r$ is a regular expression over the set of nonterminals, change this production to $S \rightarrow {\alpha}S'{\beta}$, find a right-regular grammar with start symbols $S'$ generating $L(r)$ (there is an algorithm for this); and then your grammar will include all those productions as well. Repeat for every production containing a regular expression on the right-hand side.
> 2 votes

# Answer
A exactly grammar equivalent to **G1** is following ( say G2) :

```
S → X S Y
S → X A Y

X → a | b
Y → c | d

A → fA | gA | ^

```

Where `^` is a null symbol (epsilon)

exactly equivalent means L(**G1**) = L(**G2**) that is language of G1 and G2 are same( *every string in L(**G1**) also in L(**G2**) and vise-versa*).
> 1 votes

---
Tags: regular-expressions, automata
---


title: Big O time complexity

text:
# Question
Title: Big O time complexity
I have a question if I have my $k=300$ and my loop is like this :

```
for( int x = 0 ; x<n ; x--){
    for(int y=0 ; y<k; y++){
        ...
    }
}

```

Is this still $O(n^2)$? If no, why? Thank you :)

# Answer
Assuming that you meant `x++` rather than `x--`, the complexity is $\Theta(nk)$. Since $k = 300$, you can simplify that to $\Theta(n)$. As Ran G. mentions, since $n = O(n^2)$, then your loop is also $O(n^2)$. It's also $O(2^n)$. But the tight analysis is $\Theta(n)$.
> 4 votes

---
Tags: time-complexity, landau-notation
---


# Question
Title: Finding the minimum subset within a cycle
Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers defined in the interval $\[c,d\]$. Assume no two values are identical. For $(a,b)$, if $a \> b$, the range is $\[a,d\] \cup \[c,b\]$; otherwise, it is $\[a,b\]$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any value within the range of any pair in $A$, the value is also within the range of any pair in $B$.

There exists an $O(n \log n)$ algorithm to find the smallest subset when, for any pair, $a$ is strictly less than $b$. I can run this algorithm for each pair to determine my solution. However, what is a more efficient algorithm to obtain the smallest subset?

# Answer
> 2 votes
Using Kaveh's reduction in this related question, we only have to solve the case where the given intervals cover the entire circle $\[c,d\]$.

Here's an algorithm that almost calculates the optimum, in $O(n\log n)$. Replace each interval $\[a,d\] \cup \[c,b\]$ by the two intervals $\[a,d\],\[c,b\]$, and now solve the original problem. Let $O$ be the optimum of the original problem, and $S$ be the optimum of the new problem. I claim that $S-1 \leq O \leq S$.

First, given any solution to the new problem, we can find a solution to the old problem with the same cost, showing that $O \leq S$. For the other direction, take some optimal solution. If it doesn't use any split interval, then $S = O$. Otherwise, let $I\_\min$ be the split interval minimizing $a$, and let $I\_\max$ be the split interval maximizing $b$. If we drop all other split intervals, then whatever remains is still a cover of the circle. If $I\_\min \neq I\_\max$ then $S = O$, and otherwise all we know is that $S \leq O+1$.

It's plausible that this algorithm can be adapted somehow to actually find the optimum. (Most algorithms that work on interval graphs also work on circular-arc graphs.)

---
Tags: algorithms
---


title: Creating a logical circuit

text:
# Question
Title: Creating a logical circuit
**Task**: Design a 2 bit comparator.

Input: 2x 2 bit (I take it as 2 2-bit values, let them be unsigned for simplicity) Output: 1 if result input1\>input2 is true, 0 otherwise

Develop truth table and derive circuits.

**The problem**: I'm completely new to this so I have not even a idea where where to look for the lighthouse.

**The question**: I'M NOT LOOKING FOR COMPLETE SOLUTION, instead I'm looking for a guidance through topics/materials which I should check to be able to solve it myself.

**Done so far**: I started with understanding logical gates and those seem to be pretty straight forward.

P.S.: Purpose of posting this question is to boost the speed with which I will get to the actual solution.

**SOLUTION:** f(A,B,C,D) = !AB!C!D + A!C + ABC!D. (! - used for negation or NOR, ABC notations means A AND B AND C). I had three adjacent rectangles two of which were of unit cell size and one of 4 cells size (one cell was actually far away, but there's this toroidally connection property, not sure about terminology). A and B are MSD and LSD of the first number respectfully and B and C are same for second number. *As for the circuit image:* sorry folks my hand drawing requires strong mental stability.

# Answer
> 3 votes
Well, as the problem asks you to make a truth table, you should first make one (this is generally a good idea even if not asked explicitly). For your question, you can say assign two bits to input1, say $a$ and $b$, and two bits to the input2, say $x$ and $y$. Then you might say that if $a = 1$ and $b = 0$, input 1 is $2$.

Once you have the truth table (4 inputs, one output), you can get the corresponding boolean expression from the truth table in "sum-of-products" form. Basically, suppose for every entry where the output is 1, you form a "min-term" of the inputs. For example, say for 2 inputs $p$ and $q$, if output is $1$ when $p=1$ and $q = 0$, the min-term would be $p\bar{q}$. Get these min-terms for all inputs where the output is 1, and add them/OR-them together. This is because the output is 1 if and only if any one min-terms is true. You can read more here or here or here.

Now, once you have the boolean expression, you might want to minimize it - implement the logic using fewer gates. This is not asked in your question, but you might want to do it anyways. Karnaugh map technique, which you seem to already have read, is one technique. There is another called the Quine-McCluskey algorithm.

Once you have the boolean expression, you can generate the corresponding circuit mechanically. So, for each min-term, implement it using AND gates, and NOT gates. Connect all these to the input of a OR gate. For example, for something like $p\bar{q} + \bar{p}q$, $p\bar{q}$ means $p$ **AND** (**NOT** $q$). Do the same for the other min-term, and give them to the input of an OR gate. The above links also provide information and examples about this.

As for speed, you'll get faster with practice!

# Answer
> 1 votes
There is a methodology for implementing logical Combinational circuit

suppose your Boolean function is $f(x\_1,x\_2,...,x\_n)=(y\_1,y\_2,...,y\_m)$ in which $x\_i,y\_i \in \\{0,1\\}$

1) First make a Truth Table

2) Then write each $y\_j$ base on $(x\_1, x\_2,..., x\_n)$ using CNF or DNF

3) Then use Quine-McCluskey for function minimization.

---
Tags: logic, circuits
---