# Question
Title: Offline scheduling fully determined arbitrary jobs in multiprocessor setting
Let $\mathcal{J} = \\{J\_1,...,J\_n\\}$ be a set of jobs with each $J\_i = \[a\_i,r\_i,d\_i\]$ where the job becomes available at its arrival time $a\_i$, requires $r\_i$ execution time and needs to be finished at its deadline $d\_i$ (hard real time). Assume we have $m$ processors available.

Given the above, what scheduling algorithms are available to deal with this? I'm aware of a publication by Horn that gives a solution using flows; since that was in 1974 and flows are comparatively slow, I tried to find faster algorithms for this setting, but couldn't find any. The book on scheduling by Pinedo suggested in this answer on CS.SE mentions the setting and that it can be solved using flows, but unfortunately nothing else. Apart from these two sources, I have been unsuccessful.

Are there known algorithms to solve the above problem that are faster than flow networks on $\Theta(n)$ nodes?

# Answer
> 1 votes
I think it is going to be tough to find a more efficient algorithm than the one you already have. You are getting close to requiring an online algorithm.

I think a lot is known about the online version of this problem. Take a look at:

> Dertouzos and Mok: Multiprocessor On-Line Scheduing of Hard-Real-Time Tasks, *IEEE T. Software Eng.*, 15(12):1497-1506, 1979.

It is known that *least laxity first* (also known as *least slack first*) scheduling is an optimal on-line greedy scheduling algorithm for the multiprocessor case only when all the $a\_i$ are the same (basically: all the tasks arrive at the same time, but they have different execution times and deadlines.) Dertouzos and Mok show there is *no* online algorithm for the case that the $a\_i$ are not known a-priori.

What I don't know is whether there is some least-slack-first algorithm similar to list scheduling. There must be a reference about this, but I haven't found it in the small amount I've looked just now. *Slack* is a dynamic quantity. At any time $t$ for any job $i$ it is the difference between $d\_i -t$ and however much work is remaining to be done on job $i$. The slack of a job starts at the value $(d\_i - a\_i) - r\_i$ and must be monotonically non-increasing. On imagines that one could take all the jobs, sort them by their initial slack value, and then greedily schedule them in that order, and that (for the case where the processors are identical, there are no precedence constraints, the jobs are all single-threaded, and arbitrary preemption and job migration are permitted and have no cost) you might be able to prove something concrete about it.

---
Tags: asymptotics, scheduling
---


title: Unique boolean functions with one input

text:
# Question
Title: Unique boolean functions with one input
I need to write a truth table for all possible *unique* Boolean functions with one input. However, I am confused regarding the word "unique".

I thought about writing down the truth table for a NOT, since it has just one input.

# Answer
This task is simple enough if you already know exactly what a function is and how to construct a truth table; you just have to write down every possible combination of assignments to all variables and functions, e.g., $x = 0$, $f(0) = 0$, and so on. If it isn't obvious, it might be beneficial to walk through a more drawn-out reasoning, which might also be more useful whenever you want to count and/or enumerate all possible functions where the number of functions is bigger, and the functions might not be that relatable (like for example how the negation function is relatable).

First of all we can count how many functions there are.

> Given sets $A$ and $B$, there are $|B|^{|A|}$ functions $f : A \rightarrow B$.

So since we have $\mathbb B = \\{0, 1\\}$, $^\*$ and we are concerned with functions $f : \mathbb B \rightarrow \mathbb B$, we have $2^2 = 4$ functions.

The next step is to make a truth table. But first, let's look at what a function is:

> A function $f : X \rightarrow Y$ is a subset of the Cartesian product $X × Y$ subject to the following condition: every element of $X$ is the first component of one and only one ordered pair in the subset.

So we must find all sets that are subject to these constraints. An example of a set that is *not* a function is:

$S = \\{(1,0), (1,1)\\} \subset \mathbb B × \mathbb B$

since $1$ is the first component of two ordered pairs, ie. the value $1$ maps to two different values. Moreover, we don't have a mapping for the value $0$, ie. $f(0)$ is undefined.

Since we are dealing with a domain of size two, and since we have one and only one ordered pair for each member of the domain, all sets (functions) that we are considering are on the form:

$f = \\{(0,\\\_),(1,\\\_)\\}$

where $\\\_$ is either $0$ or $1$.

So then we list all possible enumerations of two ordered boolean values, and put them in the pair as the second component with the $0$ as the first component and the $1$ as the first component, respectively:

$0,0$

$1,1$

$1,0$

$0,1$

Plugging these in, we get:

$f\_1 = \\{(0,0),(1,0)\\}$ ($f(x) = 0$)

$f\_2 = \\{(0,1),(1,1)\\}$ ($f(x) = 1$)

$f\_3 = \\{(0,1),(1,0)\\}$ ($f(x) = \neg x$)

$f\_4 = \\{(0,0),(1,1)\\}$ ($f(x) = x$)

(As a sanity check, we confirm that we ended up with 4 functions, as expected.)

As a truth table:

$$\begin{array} {|c|c|c|c||c|} \hline x & f\_1(x) & f\_2(x) & f\_3(x) & f\_4(x)\\ \hline 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ \hline \end{array} $$

---

* Or $\mathbb B = \\{F,T\\}$, if you prefer.
> 1 votes

---
Tags: boolean-algebra
---


title: Rigorous Proof of Insertion Sort

text:
# Question
Title: Rigorous Proof of Insertion Sort
Currently I self study CLRS book (Outside of any course, so I got no access to an instructor)

And I am stuck proving Insertion Sort, The proof in CLRS book is not so formal.

Here's the algorithm:

```
INSERTION-SORT(A)
   for j=2 to A.length (= n)
      key = A[j]
      i = j-1
      while (0<i and key<A[i])
         A[i+1]=A[i]
         i = i-1
      end while
      A[i+1]=key
   end for
end procedure

```

I tried to formalize the proof with the following pre-post conditions:

Pre-Condition: $A=A\_{org}$ and $j=2$ (I.e. $A\_{org}$ holds the original values of $A$)
Post-Condition: The array $A$ consists of the same elements as in $A\_{org}$ but in a sorted order that is $\forall i\_1,i\_2\in\\{1..n\\}, i\_1\<i\_2\to A\[i\_1\]\leq A\[i\_2\]$.

My loop invariant is:
($p$ denotes the $p$'s iteration)

$I(p)="\text{The array $A\[1..j-1\]$ consists of the same elements as in $A\_{org}\[1..j-1\]$} \land \forall i\_1,i\_2\in\\{1..j-1\\}, i\_1\<i\_2\to A\[i\_1\]\leq A\[i\_2\] \land j=2+p"$

Now when I try to prove the inductive step I got stuck and cannot proceed because of the nested $while$ loop and because of the informal sentence "The array $A\[1..j-1\]$ consists of the same elements as in $A\_{org}\[1..j-1\]$".

Any help on how to prove Insertion Sort rigorously and how to formalize the sentence "The array $A\[1..j-1\]$ consists of the same elements as in $A\_{org}\[1..j-1\]$" will be appreciated (I want my loop invariant to contain only mathematical symbols and not informal english phrases).

(BTW: I am trying to write the proof in the same style as in Susanna. Epp's Discrete Mathematics book)

Any help will be appreciated. Thanks.

# Answer
Hint: first prove a loop invariant for the nested while, i.e. you need to prove that the nested while shifts to the right the elements as required to insert the j-element indexed by the outer for loop in its correct place. Then, prove the loop invariant for the outer for loop taking into account the suggestion by @Yuval and you are done.
> 4 votes

# Answer
The formal statement of "$A\[1\ldots j-1\]$ consists of the same elements as $A\_{\mathrm{org}}\[1\ldots j-1\]$" is "there exists a permutation $\pi\colon \\{1,\ldots,j-1\\}\to\\{1,\ldots,j-1\\}$ such that $A\[i\] = A\_{\mathrm{org}}\[\pi(i)\]$". Formal statements are in English unless you're doing formal logic.

Your induction hypothesis isn't strong enough. It only tells you something about the first $j-1$ elements in both arrays, whereas in the next step you'll have to talk about $j$ elements of both arrays. You need to mention that elements $j$ to $n$ are the same in both arrays.

Regarding formal proof, it really depends how formal you want to be. If you have a formal logic in mind for proving the correctness of programs, then you can attempts to give a formal proof. Such a system might require preconditions and postconditions for each statement; in fact, you'll need to do something for any subexpression. I'm assuming you're not going that far, however, and in that case the notion of "formal proof" depends on your level of experience and your target audience. If you're self-studying, your target audience is yourself, so you need a proof that you find convincing. It's much preferable if somebody else (an expert, say a graduate student) went over your proof, since it's hard to understand the common standard otherwise.

Another relevant question is why you're interested in a "formal" proof. Unless you're going into software verification, there's probably no need for a formal proof, but rather for a *convincing* proof. What convinces you depends on your level and experience, but I often find that overly formal proofs are *harder* to understand. But it's up to you, and perhaps it's useful to go formal at least once in your studies. For the algorithms practitioner – algorithm developer or algorithm implementer – there is usually no need for such a formal level of detail.
> 3 votes

# Answer
There is actually a simpler way to prove this. This is a quite simple algorithm. I think a good English explanation is rigorous enough.

* There is an invariant within each outer loop body. The invariant is: for all pairs of two numbers, such that none of the two number is currently the one used as `key` on line 3, then the order of the pair does not change before and after the completion of the current iteration of the main outer loop. **\[1\]**
* All numbers are preserved. If they are in the original array, they will still be in the output. **\[2\]**

Now assume the output array is not sorted, there exists at least one pair of numbers with incorrect order. We will pick the pair which has the largest difference, say $\<a\_i, a\_j\>$. At some point, $a\_j$ must be used as `key` in line 3 because every number in the array will be picked as `key`. Now, the inner loop completes when it finds another number $a\_i'$ such that $a\_i'$ \< $a\_j$ or it completes when it finds $a\_i$.

If the inner loops find $a\_i$, then it will change the order of the pair $\<a\_i, a\_j\>$ and this order will stay the same until the process completes which gives us a contradiction about the order of this pair.

If the inner loop finds another $a\_i'$ such that $a\_i' \<a\_j$, then this pair's order will stay the same when the process completes also because of \[1\]. Then the mis-ordered pair with the largest difference is not $\<a\_i, a\_j\>$, but this pair instead. This is a contradiction

You can try to translate this into formal logic too, but it will be quite tiring. Maybe it is a good practice for you.
> 1 votes

---
Tags: algorithms, sorting, correctness-proof, formal-methods
---


title: Solving a dynamic programming problem?

text:
# Question
Title: Solving a dynamic programming problem?
Alex writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?

My one friend said to me that this problem can be solved by dynamic programming.But I can't understand how to solve it by dynamic programming .Can someone explain it with great details.Here is some input and output.

1.input:m=10, n=11 and output:1

2.input:m=100,n=200 and output:22

# Answer
> 1 votes
Let $T(n)$ denote the number of noughts that are necessary to write down all numbers from $0$ to $n$ (included) in base $10$. On input $(n,m)$ ($m\>0$), the number you are looking for is then $T(n)-T(m-1)$ (i.e. count the numbers of noughts that you write to go up to $n$, then subtract the ones that you used to go up to $m-1$. The remaining number is the number of noughts that you wrote from $m$ to $n$.), and on input $(n,0)$ the output is simply $T(n)$. It remains to compute the table $T(n)$ quickly enough.

We write $T(0)=1$, and then use the relation $T(n) = T(n-1) + \mathrm{Noughts}(n)$ for $n\>0$, where $\mathrm{Noughts}(n)$ denotes the number of noughts needed to write $n$ in base $10$. Given $n$, one can compute all the values of $T$ up to $n$ in time $O(n\log n)$ (the function $\mathrm{Noughts}(n)$, that could be built by examining all the digits of $n$, takes time proportional to $\log n$). Then, for any $0\leq m\leq n$, one can give the output to the problem on $(n,m)$ in constant time!

---
Tags: dynamic-programming
---


# Question
Title: Determining Number of States in a Turing Machine
I am looking at an example Turing machine in my textbook, *Automata and Computability* by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. The example (Example 28.1, page 211) reads as follows:

> Here is a TM that accepts the non-context free set $\\{a^nb^nc^n \mid n\geq 0\\}$.
>
> Informally, the machine starts in its start state *s*, then scans to the right over the input string, checking that it is of the form $a^\* b^\* c^\*$. It doesn't write anything on the way across (formally, it writes the same symbol it reads). When it sees the first blank symbol *_*, it overwrites it with a right endmarker *\]*.
>
> Now it scans left, erasing the first *c* it sees, then the first *b* it sees, then the first *a* it sees, until it comes to the *\[*. It then scans right, erasing one *a*, one *b*, and one *c*. It continues to sweep left and right over the input, erasing one occurrence of each letter in each pass.
>
> If on some pass it sees at least one occurrence of one of the letters and no occurrences of another, it rejects. Otherwise, it eventually erases all the letters and makes one pass between *\[* and *\]* seeing only blanks, at which point it accepts.
>
> Formally, this machine has $Q = \\{s, q\_1, ... , q\_{10}, q\_a, q\_r\\}, Σ = \\{a,b, c\\}, Γ = \Sigma ∪ \\{\[, \\\_, \]\\}$

Are they simply creating states based on their informal definition? Or is there some methodology they are implementing that determines the number of states? If there is some sort of methodology, is it a general methodology that can be applied to other Turing machines?

# Answer
> 5 votes
I am afraid you cannot tell the number of states from an informal description. There may be states needed to handle trivial details or limit cases that are not obvious from that description. So the answer is usually: as many states as needed to actually implement the behavior described informally.

Better precision may be required when analyzing some complexity issues, though even then it may be up to some constant.

For simpler problems, people may give a detailed description of the TM where you can count the states. This may also happen when you study techniques for combining 2 TMs in some way. Then you may want a formula that gives you (a bound for) the number of states of the combination from the number of states of the 2 initial TM (and possibly some other parameters of the twp TM)

But describing TM in details is like programming in machine language: very tedious and highly prone to errors and bugs of all kinds. And usually you do not have a testing environent.

If there is a methodology, it is probably in combining TM that can perform some specific tasks. It is like library functions in programming languages, which implement specific algorithms that you combine to solve a problem.

So the informal description may also, to some extent, be understood as a high-level language that does not yet have a compiler. So you do not really know what machine code you will get. But do not take this last sentence too seriously.

---
Tags: turing-machines, notation
---


# Question
Title: Principles of Programming Languages: Understanding Judgements
I am taking a principles of programming languages class right now and am trying to understand the following judgement form.

```
n' = -toNumber(v)
------------------
-v --> n'

```

(Sorry, I can't post pictures yet. And Stack doesn't take LaTeX.) I think it means "n' = -v implies that -v maps to n' " or something along those lines. I guess I really just don't know what the --\> means. In math it can either mean "maps to" or "implies" and "maps to" just made more sense.

# Answer
The `-->` is the relation that the judgement rules are defining. It's usually pronounced "steps to" or "reduces to". You can think of this relation as the analogue of "showing your work" in algebra:

`(1 + 2) * 3 --> 3 * 3 --> 9`

It's used as a way of specifying the semantics of a programming language through a binary relation on programs. These kinds of semantics are called small-step semantics. Within small-step semantics, there are approaches include reduction semantics and structural operational semantics. If the program is augmented first to a "configuration" that includes extra components like environments and stores, and the relation is on these configurations instead of just plain program terms, then it's called an abstract machine semantics.

Note: Sometimes you define multiple relations and build up more complicated relations out of them, so you have different arrows.

There are other kinds of operational semantics (eg big-step semantics) and there are other kinds of semantics besides operational semantics.
> 1 votes

---
Tags: programming-languages, semantics, notation
---


# Question
Title: What's the difference between Adaptive Control and Hierarchical Reinforcement Learning?
After watching Travis DeWolf presentation on scaling neural computation, I'm a bit confused about the difference between Reinforcement Learning (whether hierarchical or not) and Adaptive Control. They both seem to be exploring environments and minimizing error through learning, but they're obviously used for very different applications. Can someone explain to me what's the difference between these two tasks and based off that difference, what would be a good way to combine them?

# Answer
> 4 votes
The difference between the two tasks really comes down to the level of continuity assumed in the models of the problem.

In adaptive control, continuity is assumed at all levels; the problem space and the actions to be executed are all continuous.

In hierarchical reinforcement learning, although the problem space is continuous, the actions to execute upon the space are discrete.

A good analogy for this is the robot arm trying to move to a certain goal. Adaptive control would work with Jacobian to find a continuous solution to this problem. Reinforcement learning would select actions (up, down, left, right) to learn the problem space and find a solution.

Hierarchical reinforcement learning and adaptive control are really complements of each other. When the problem gets too complex to compute with Adaptive Control, hierarchical learning steps in to make it discrete and more scalable.

For another perspective, especially since my explanation breaks down when you consider continuous HRL (which does exist), consider this explanation from my personal correspondence with Daniel Rasumussan:

> Practically, there are many differences between how they \[Adaptive Control and HRL in a continuous space\] are implemented; they use different algorithms, different learning rules, different representations, etc. For example, adaptive control is not typically hierarchical. You could arguably call it a hierarchy with a depth of 1 (with e.g. the "high level" being control in the x,y space and "low level" being control in the motor space). But there's no temporal abstraction in that hierarchy; the high level isn't trying to encapsulate low level decisions, the problem is how to find a nice reliable one-to-one mapping between those two spaces. Of course you could make adaptive control hierarchical, as you can make pretty much anything hierarchical, but that isn't typically what they're interested in. Perhaps a more critical difference is that in motor control typically it is assumed that the transition and reward functions are known to the agent. There may be some unknown variability in the case of adaptive control, but by and large the agent has a pretty good idea what the effects of its actions will be, and what the goal is that it is trying to achieve. It's one of the key principle of reinforcement learning that that information is not known, and must be figured out by the agent by exploring the environment. Now again here, you could come up with a motor control problem where the agent doesn't assume that information is known, but that just isn't the kind of problem those techniques are designed for, in general. So, to sum up, there certainly is a gradient between HRL and adaptive control, and by tweaking various assumptions you can bring them closer together or farther apart. But just implementing continuous actions in HRL would still leave you quite a ways from adaptive control.

As for an example combination this, one might imagine using hierarchical reinforcement learning to play a video game like Pong and then changing the physics of the game (Pong on slippery ice!) so that Adaptive Control might step in.

---
Tags: machine-learning, reinforcement-learning
---


# Question
Title: List the edges (vertex pairs) of a minimum spanning tree for this graph in the order they would be chosen by Prim's algorithm
List the edges (vertex pairs) of a minimum spanning tree for this graph in the order they would be chosen by Prim's algorithm Please help me to understand and complete this. I would very much appreciate it.

# Answer
> 1 votes
This may not be a well-formed question; Prim's Algorithm is dependent on which vertex you start with. It is possible that other sources define the algorithm differently.

Let $V$ be the set of all vertices. The basic idea is: Start with an arbitrary vertex, and add it to a new set $S$ Repeat the following until $S = V$:

* Find the lowest-cost edge $e$ that connects a $v \in S$ to a vertex $w \notin S$.
* Add that edge $e$ to a set of edges $T$ (it will become your tree).
* Add $w$ to $S$.

For example, suppose you started at vertex 4, so $S = \\{4\\}$ to start. The lowest-cost edge leading "out of" $S$ costs $2$, the edge connecting vertex 4 to 5. Now $S = \\{4, 5\\}$.

To get the full answer, you would continue this process until $S = \\{1, 2, 3, 4, 5\\}$. My issue with the problem is that the order the edges are chosen **depends on** the vertex you start with, but hopefully you are now more familiar with Prim's algorithm.

---
Tags: algorithms, graphs
---


# Question
Title: Find k maximum numbers from a heap of size n in O(klog(k)) time
I have a binary heap with $n$ elements. I want to get the $k$ largest elements in this heap, in $O(k \log k)$ time. How do I do it?

(Calling deletemax $k$ times yields a $O(k \log n)$ complexity. I'm looking for $O(k \log k)$.)

The only solution I've come up with so far is the following:

You have 2 arrays. A(largest numbers), B(to analyze).

* It's easy to find the largest number, since we already have the heap. We move the maximum number to $A$.
* We move the maximum number's children to $B$
* We sort $B$
* We add the children of the largest number in $B$
* Remove the largest number from B (first element of $B$), add it to $A$
* Repeat the procedure until there are $k$ elements in $A$

The question here is: do we get a $O(k \log k)$ complexity? we obviously repeat the procedure $k$ times, but does the sorting take $O(\log k)$ time? I guess if the array is already sorted it's easy to insert a new number in $O(\log k)$ time. However, will the length of array B always be less than or equal to $k$?

Can you please confirm or deny my solution? If it's wrong, can you please help me find a solution to this problem?

# Answer
> 0 votes
Hint: Each time you perform one iteration of your loop, how much does the size of $B$ increase? Each time you perform one iteration of your loop, how many numbers are added to $A$?

You terminate once $k$ integers have been added to $A$... so how many times will the loop iterate? What does this tell you about how large $B$ can get? What does that say about the running time of your algorithm?

(I am giving only a hint, so you can have the pleasure of working out the answer on your own.)

---
Tags: data-structures, heaps
---


# Question
Title: Is $K' = \{ w \in \{0,1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$, equivalent to the halting problem?
My professor presented the halting problem as $K' = \\{ w \in \\{0, 1\\}^\* | M\_w$ Halts on $w \\}$, where $M\_w$ is the TM whose encoding is $w$ (i.e. $w = \langle M \rangle$), and said it was equivalent to $K = \\{ \langle M,v \rangle | M $ Halts on $v \\}$.

I tried to think it through and this is my understanding so far:

$(1)$ If $w \in K'$ then we can define $f(w)= \langle M\_w,w \rangle$ then $w \in K' \Leftrightarrow f(w) \in K$ so we have that $K'$ can be reduced to $K$

$(2)$ And for the other way around, we define $g(\langle M,v \rangle) = \langle M' \rangle$ where $M'$ is the TM that simulates the TM $M$ on input $v$ and halts iif $M$ halts on that input. So we get that both languages are reducible to each other thus equivalent.

But I'm not sure about part $(2)$, is the reasoning correct? Can someone shed some light on my problem?

# Answer
The two languages aren't equal. However both $K$ and $K'$ are undecidable.

Proof:

We know that: $K = \\{ \langle M , v \rangle | M$ halts on $v$ }. Let us construct another language: $K'' = \\{ \langle M , \langle M\rangle \rangle | M$ halts on $\langle M \rangle \\}$. Note that $K'' \subset K$ because we replaced $v$ by $\langle M \rangle$ (encoding of $M$). Also note the similarity of $K'$ and $K''$.

If you prove that $K'$ is undecidable, we can conclude that $K$ is undecidable.

You might have proved that $K'$ is undecidable.
> 1 votes

---
Tags: reductions, halting-problem
---


title: Kosaraju’s Algorithm - why transpose?

text:
# Question
Title: Kosaraju’s Algorithm - why transpose?
In directed graph, to find strongly connected components why do we have to transpose adjacency matrix (reverses the direction of all edges) if we could use reversed list of nodes by they finishing time and then traverse original graph. In other words, we would find finish times of all vertices and start traversing from lowest finish time to greatest (by increasing finish time)?

Additionally, if we do topological sorting on some DAG, and then reverse edges (transpose adjacency matrix) and do topological sorting again - should we get to equal arrays, just in reversed order?

EDIT: Algorithm description from other topic: Correctness of Strongly Connected Components algorithm for a directed graph

# Answer
> 7 votes
Taking the transpose and using the list based on finishing time both together ensure that if you have edge A-\>B(in original graph) where A and B are simply connected sub-graphs than in second dfs A would have finished before start of B(See that in transposed graph edge is from B-\>A). If we do not take transpose then this is not ensured.

Example:

1-\>2

2-\>3

3-\>4

4-\>2

3-\>5

dfs(decreasing finishing time finishing times):1,2,3,5,4 Now if you start from 4 you will visit 5 through 4-\>2-\>3-\>5. But 4 and 5 are not simply connected.

For the second part you may or may not get reversed arrays depending on the order of supplying vertices.

# Answer
> 6 votes
From the definition of strongly connected components : if every vertex is reachable from every other vertex.

The first DFS is to find all the vertices that are reachable from root vertex v. The second DFS is to check the reverse , i.e to find the subset(of all the above vertices) that can reach v.

Now this may sound a bit confusing, but the question 'whether any vertex u has a path to v', can be converted to an equivalent question on the transpose graph, 'whether v has a path to u'. Further detailing,'if a vertex u can reach v, then if you reverse the edges in the path between u and v, now equivalently v can reach u, and if there is no path from u to v in the original, then in the transpose there is no path between v and u'.

So instead of testing each vertex u ( which are reachable from v) and can reach v back, the second DFS on the transpose equivalently tests, if v can reach all u. The algorithm then returns a component, which has vertices that are both in the first DFS and the second one.

---
Tags: algorithms, graphs
---


# Question
Title: Hardness and approximation of a problem with a parameter
Let $H$ be a decision problem, where we are given an integer $k$ and some object, say a graph or a formula. We know that $H$ is NP-complete for $k \geq c$, where $c$ is some constant like 3 ($H$ could be $k$-SAT, or $k$-vertex coloring, or something like that).

I have a problem $X$ I think is NP-complete as well, and I want to prove it. $X$ is a graph problem, and it has a parameter $k'$ similarly.

Given an instance of $H$ with parameter $k \geq c$ (for example let's say $c=3$), I can build an instance of $X$ (in polynomial time), where $k' = c+8$. I can now prove two things:

1. If $H$ with $k$ has no solution, $X$ has no solution with $k$. (There might be a solution for $X$ with $k'$, I don't know).
2. If $H$ with $k$ has a solution, $X$ has a solution with $k'$.

To establish hardness for $X$ with $k'$, should I be able to prove in (1) that $X$ has no solution with $k'$ as well? (Or is my current reduction pretty much useless as it is?) If I were able to do that, would my proof also tell me something about the hardness of approximating $X$? $X$ is a minimization problem.

# Answer
Yes. To show that decision problem Q is at least as hard as decision problem P (via a many-one reduction), you need to prove that a yes-instance for P maps to a yes-instance for Q, and a no-instance for P maps to a no-instance for Q. That's just what the definition of a (many-one) reduction is.

In your case, P = "X has a solution with parameter $k'$" and Q = "H has a solution with parameter $k$". Therefore, the answer to your question is yes: in (1) you need to prove that $X$ has no solution with parameter $k'$. The definition of P needs to be consistent for both kinds of instances, so it has to use the same parameter in both cases.
> 2 votes

---
Tags: np-complete, reductions, approximation
---


# Question
Title: What problem cannot be solved by a short program?
BACKGROUND:

Recently I tried to solve a certain difficult problem that gets as input an array of $n$ numbers. For $n=3$, the only solution I could find was to have a different treatment for each of the $n!=6$ orderings of the 3 numbers. I.e., there is one solution for the case $A\>B\>C$, another solution for $A\>C\>B$, etc. (the case $A\>C=B$ can be solved by any one of these two solutions).

Thinking of the case $n=4$, it seems that the only way is, again, to consider all $n!=24$ different orderings and develop a different solution for each case. While the solution in each particular case is fast, the program itself would be very large. So the runtime complexity of the problem is small, but the "development time" complexity or the "program size" complexity is very large.

This prompted me to try and prove that my problem cannot be solved by a short program. So I looked for references for similar proofs.

The first concept that I found is Kolmogorov complexity; however, the information I found about this topic is very general and includes mostly existence results.

QUESTION:

Can you describe a specific, real-life problem $P$, such that any program solving $P$ on an input array of size $n$ must have a size of at least $\Omega(f(n))$, where $f(n)$ is some increasing function of $n$?

Since the answer obviously depends on the selection of programming language, assume that we program in Java, or in a Turing machine - whichever is more comfortable for you.

Every undecidable problem trivially satisfies this requirement because it has no solution at all. So I am looking for a decidable language.

# Answer
> 2 votes
*I assume that what you actually want is an enumeration of problems such that the corresponding programs form an increasing sequence in size. Here is an exemple of such an enumeration. However, I only prove that the size increases beyond any bound, hence it is not in $O(1)$, which seemed to be your main point. I could try better, but I am wondering what in this answer might not be acceptable in your view of the question.*

If I understand correctly, you want an enumeration $P\_n$ of problems that are all decidable with an algorithm $A\_n$, such that there is no uniform decision procedure for the union of these problems, because if there was one, it would be a short program when $n$ gets large, i.e. it would be $O(1(n))$.

That implies that the enumeration $A\_n$ is not computable. If it were computable, the one would be able to compute the algorithm $A\_n$ from the knowledge of $n$, thus having a uniform procedure for the union of all the problems in the enumeration.

Hence we can only look for examples such that there is no computable enumeration $A\_n$ of algorithms such that $A\_n$ solves $P\_n$.

Before going into that, we need to define the size of a

Let $T\_n$ be a enumeration by Gödel numbers $n$ of Turing Machines. Such a Gödel enumeration is computable. Then let $P\_n$ be the following problem: if $T\_n$ halts on all inputs, then $P\_n$ consists in recognizing the recursive set recognized by $T\_n$, else $P\_n$ consists in recognizing the empty set $\emptyset$.

Since we are looking for lower bounds on the size of the algorithm $A\_n$ that solves $P\_n$, we have to define the size of a TM. For a TM, its Gödel number can be taken as the size of the machine, i.e. the corresponding algorithm. Indeed the number of states and transitions increases necessarly with $n$, if only because of the pigeon hole principle, though it is not necessarily uniform (and it depends on an arbitrary definition of size anyway).

Then, for any TM $T\_n$ that always halt, we note ${\mu(n)}$ the smallest Gôdel number of a TM $T\_{\mu(n)}$ such that it always halt and recognizes the same recursive set as $T\_n$. Hence $T\_{\mu(n)}$ is the smallest TM that actually is an algorithms to solve $P\_n$, i.e. it is $A\_n$. If $T\_n$ may not halt, then for $A\_n$ we simply use always an algorithm corresponding to a TM $T\_\emptyset$ the recognizes the set $\emptyset$, always the same one.

Each problem $P\_n$ is decidable, and $A\_n$ is a decision procedure. However, the enumeration $A\_n$ is not computable, but we have shown that it is unavoidable.

It is easy to show that, given any constant $C$, there is an $n$ such that the size $|A\_n|$ of $A\_n$ is greater than $C$. The reason is simply that the number of machines smaller than $C$ is finite, while the number of recursive sets recognized by TMs is infinite.

So that is an example of a problem (more precisely a problem enumeration) that cannot be solved by a short program, i.e. such that there is no constant bound on the length of solutions for each $P\_n$.

We can always add to each problem $P\_n$ that it requires any solution to first read an array of size $n$, so as to meet the constraint in the question. But there is little point to it.

# Answer
> 7 votes
For any given problem, you can create a programming language where a program to encode the solution to that problem is a single character. (cf. HQ9+). Kolmogorov complexity is language dependent. The answer to your question about which problems cause a blowup will depend heavily upon whichever "standard formal language" you choose.

There are some interesting results, however. Encoding of randomly generated strings will always require a cost proportional to the size of the string. Pigeonhole principle tells us there will always be some functions, in any fixed language L, that cannot be expressed in a space smaller than a complete enumeration of all the cases. And Blum's size theorem tells us that, for a total language, there are always functions you can encode larger than an *arbitrarily chosen* blowup factor compared encoding the same function in a Turing complete language.

# Answer
> 6 votes
A result of Shannon's states that there exists a sequence of functions $f\_n\colon\\{0,1\\}^n\rightarrow \\{0,1\\}$ that is so that the problem $P(n)$ of computing $f\_n(x)$ for $x\in\\{0,1\\}^n$ requires at least $\Theta(\frac{2^n}{n})$ boolean operations (i.e. the circuit complexity of computing $f\_n(x)$ is at least $\Theta(\frac{2^n}{n})$).

This theorem is not so hard to obtain, as there are $2^{(2^n)}$ $n$-ary boolean functions, while the number of circuits of the given size is strictly smaller.

---
Tags: complexity-theory, programming-languages, kolmogorov-complexity
---


# Question
Title: A problem regarding Extended Euclidean Algorithm
Alex has some (say, n) marbles (small glass balls) and he has going to buy some boxes to store them. The boxes are of two types:

Type 1: each box costs c1 Taka and can hold exactly n1 marbles

Type 2: each box costs c2 Taka and can hold exactly n2 marbles

He wants each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since he finds it difficult to figure out how to distribute his marbles among the boxes he seeks his friends' help. It is worthy of mention that the value of n,c1,n1,c2 and n2 are given.

His one friend solved this problem using extended euclidian algorithm and found out two values everytime .Thus his result for the input.

1.n=43,c1=1,n1=3,c2=2,n2=4 the result will be 13 1

2.n=40,c1=5,n1=9,c2=5,n2=12,the result will be "no valid values".

Though I understand extended euclidian algorithm I can not catch how he solved this problem. Can anyone tell me how his friend sovled it using extended euclidian algorithm. Since I'm a novice learner of extended euclidian algorithm I need better explanation.

# Answer
> 1 votes
Here are some ideas to get you started.

1. A number $n$ cannot be represented as a linear combination of $n\_1,n\_2$ unless $(n\_1,n\_2) \mid n$, since all linear combinations of $n\_1,n\_2$ are multiples of $(n\_1,n\_2)$.
2. The extended Euclidean algorithm gives you values $a\_1,a\_2$ such that $a\_1n\_1+a\_2n\_2 = (n\_1,n\_2)$, and in particular $$\frac{n}{(n\_1,n\_2)} a\_1 n\_1 + \frac{n}{(n\_1,n\_2)} a\_2 n\_2 = n.$$
3. If $n = b\_1 n\_1 + b\_2 n\_2$ then all other representations are of the form $$n = \left(b\_1 + \frac{n\_2}{(n\_1,n\_2)} t \right) n\_1 + \left(b\_2 - \frac{n\_1}{(n\_1,n\_2)} t \right) n\_2.$$

Try to use these ideas to solve the problem on your own.

---
Tags: algorithms, number-theory
---


# Question
Title: How to prove that $\{0^n 1^{5n} \mid n \ge 10000 \}$ is not a regular language?
I proved that $$ \\{ 0^n 1^{5n} \mid n \geq 0 \\}$$ is not a regular language using Pumping Lemma by following way.

Solve by contradiction that $ L = \\{0^n 1^{5n} \mid n \geq 0 \\}$ is regular language.

1. Let $0^p 1^{5p}$ be in L, where $p$ is the pumping length.
2. Now here if the language $L$ is regular language, $0^p 1^{5p}$ can be represented in the form $xyz$ where $|xy| \le p$ & $|y|\gt0$.
3. Thus, from step 2, we can say that $xy = 0^p$ and $y = 0^j$.
4. So, $xyz = (0^{p-j})(0^j)(1^{5p})$.
5. Now pumping the value of y to 2, $xyyz = (0^{p-j})(0^j)(0^j)(1^{5p}) = (0^{p+j})(1^{5p})$, which is surely not in $L$, thus not a regular language.

But how to prove for condition $\\{0^n 1^{5n} \mid n \ge 10000 \\}$ & for also $n \le 10000$, we can just prove that one of them is not regular and obviously by rules the complement will also be not regular.

# Answer
> 3 votes
The condition $n\>10\\,000$ makes no real difference. If the pumping length is greater than $10\\,000$, your existing proof works. If the pumping length is $10\\,000$ or less, then pumping the string $0^{10\\,000}1^{50\\,000}$ gives you a string that isn't in the language because it has too many zeroes.

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


# Question
Title: When problem A reduces to problem B, which problem is more complex?
When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?

# Answer
> 9 votes
When we reduce $A$ to $B$, we are saying "If I could solve $B$ in some model of computation, then I could solve $A$ in that model, too" (as long as the reduction is sufficiently simple that it can be performed within the relevant model of computation).

This means that $B$ is at least as hard as $A$. But $A$ could be easier – much easier. For example, let $A\in$ **P** and let $B$ be any **EXP**-complete problem. Because $B$ is **EXP**-complete, every problem in **EXP** reduces to $B$ so, in particular, $A$ reduces to $B$. But we know that $A$ is strictly easier than $B$ by the time hierarchy theorem.

# Answer
> 1 votes
When we reduce problem $A$ to problem $B$, we are claiming that $B$ is at least as complex as $A$.

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


# Question
Title: Pumping Lemma for $L=\{a^{2k} b^n b^k \mid k\ge0, n\ge0\}$
$L=\\{a^{2k}b^nb^k\mid k\geq0, n\geq0\\}$ over alphabet $\\{a,b\\}$

How do I prove that $L$ is not regular using Pumping Lemma? All the examples I've come across had same exponents all around, and I'm a bit confused how should I write this down.

Should I start with $w=\\{a^pb^pb^p\mid p\leq k, p\leq n\\}$ where $w$ is a subset of $L$, or how should this be tackled?

# Answer
> 1 votes
* Choose for example the word $x=a^{2k}b^{k}\in L$ ( with $|x|=3k\ge k$)
* Possible partitions of $x=uvw$ are $u=a^l,\\;v=a^s,\\;w=a^mb^{k}$ with $s\ge 1,\\; l+s\le k$ and $l+s+m=2k$
* Now lets look at $uv^2w=a^{2k+s}b^k$ which is clearly not in $L$. If $s$ is odd, than the number of $a$'s is odd and therefore $uv^2w\notin L$. If otherwise $s$ is even, then the number of $b$'s would have to be larger than $(2k+s)/2$, which it is not ($k\<(2k+s)/2)$. Therefore $uv^2w\notin L$ holds for each $s\ge 1$.

$\rightarrow$ $L$ is not regular.

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


# Question
Title: Can every recursively enumerable language be defined with regular expression?
Can every recursively enumerable language be defined with regular expression?

I came across this question, when studying for my test: Prove that for any finite language $L$, there is a Turing machine $M$ with $L(M) = L$ with time and space complexity $t(n) \leq n+1, s(n) \leq n+2$, respectively ($n$ is the length of the input word).

My proof goes as follows:

We can create a DFA from a regular expression defining the language. Then we read the input symbol by symbol and output YES, if we finished in a final state or NO otherwise.

Every DFA can be transformed into a TM where every transition of the DFA corresponds to one transition of the TM. It is obvious that we only need $n+1$ steps to read the input (+1 for the blank in the end) and $s+1$ cells.

However, I am not sure, if I can assume here, that there is a regular expression for every recursively enumerable language. And if not, would my proof be still valid? Can I create a DFA for arbitrary RE language?

# Answer
Of course you can't create a DFA for every RE language. The language $\\{0^n1^n\mid n\geq 0\\}$ is well known to not be regular and is obviously RE.

But you don't need that for this question. The question refers to finite languages, which are all regular. Also, given that finite languages are regular, they can be decided by a DFA, which is a Turing machine that uses zero storage space (so much less than the $O(n)$ allowed by the question) and which always moves the head forwards.
> 4 votes

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


# Question
Title: Is this problem decidable? (computation of $M_1$ longer than $M_2$ on every input)
Is this problem decidable?

Given two representations of Turing machines $R(M\_1), R(M\_2)$, is the length of the computation of $M\_1$ longer than the length of the computation of $M\_2$ on **every input**?

My guess is **not decidable**. I am not sure, however, how to justify it.

I tried this: Lets enumarate all possible words from $\\{0,1\\}^\*$ and run $M\_1$ and $M\_2$ simultaenously. If $M\_1$ accepts/rejects and $M\_2$ is still running, output NO. If $M\_2$ stops and $M\_1$ is still running, check next word. However, if neither $M\_1$, nor $M\_2$ do not halt on the word, I am stuck and cannot decide it (because I will get an instance of the halting problem for each combination of word and Turing machine).

Is this reasonable or is it a wrong assumption?

# Answer
Hint: Let $M\_2$ be a machine that on input $n$ runs for $n$ steps roughly, and only consider machines $M\_1$ that don't depend on their input. If you could solve your task then you could determine whether a given input-less machine ever halts.
> 1 votes

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


# Question
Title: Understanding the flaw in a proof attempt of the Communication Complexity of Equality
I'm new to communication theory and I've been wondering where the following simple argument fails:

**Equality Problem** We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob who gets an $n$-bit vector $Y$. We want one of them to output $1$ if and only if for all indices $i:$ $X\[i\] = Y\[i\]$.
Suppose that I choose the inputs $X$ and $Y$ uniformly at random from the set $\\{0,1\\}^n$. Initially, Alice knows nothing about Bob's input $Y$. Consider a protocol $P$ for equality. Alice and Bob run $P$ and assume that $P$ outputs $1$. By the correctness of $P$, Alice knows that for each index $i$, $Y\[i\] = X\[i\]$. Thus Alice has learned $|Y|=n$ bits . Doesn't this immediately imply the $\Omega(n)$ lower bound for $P$?

Note: Of course, I know that the above argument must be flawed since we can solve equality with $O(\log n)$ bits when allowing randomization. I'm just trying to understand *why* my proof attempt is flawed.

# Answer
> 1 votes
This vague argument can be made to work for deterministic communication complexity. In the randomized setting, protocols are allowed to err. Consider the standard protocol in which both players exchange a random hash of their inputs to some set of size $2^m$. They only learn $m$ bits of each other's input. When both hashes agree, they aren't completely sure that $X=Y$, and in particular no party has learned the other party's input.

---
Tags: algorithms, randomized-algorithms, information-theory, lower-bounds, communication-complexity
---


# Question
Title: High Level Explanation of the Pumping Lemma
I have a problem that I cannot figure out regarding using the pumping lemma to prove that a language is not regular. I don't understand how I go about proving through contradiction that the language is not regular.

When I read about the pumping lemma, all I am finding are complicated explanations involving $x$, $y$, $z$ and $m$ which seems difficult to understand.

I would appreciate if someone could provide a high level overview of the pumping lemma, and possible an example of proving a language is not regular with its use.

# Answer
> 2 votes
The context of the FSA pumping lemma is a very common one in computer science. The origin goes to the fact that we use finite definitions to represent infinite object, or collection of objects of unbounded size, such as infinite sets of strings.

In a discrete world, such as the syntax of mathematics, the only way you can go arbitrarily far in the confined space of a finite definition is by going repeatedly trough the same steps. That is why we use induction, loops and recursion.

## The kernel of the problem

To take the simplest example, the only way you can make an arbitrarily long walk on a finite directed graph is by going several time through the same node. And that implies that you have a loop, at least one.

Of course, if the way you measure your walk is by the number of encounters of a specific feature, a milestone, that may not appear everywhere, then an arbitrarily long walk implies that you have a loop with at least one such milestone.

Actually, you do not even have to consider arbitrarily long walks. It is enough to consider a walk that is strictly longer than the number of milestones, a walk of length $n+1$ if there are $n$ milestones. Then you necessarily encounter twice the same milestone (pigeon hole principle). Hence there is a loop with that milestone, and possibly others.

So, consider a finite directed graph with $n$ milestones. We choose a number $p \geq n+1$ (called the *pumping length*).

Any walk in that graph that encounters at least $p$ milestones has necessarily gone through a loop, at some point, when it encounters the $p^{th}$ milestone.

Let us call $u$ the part of the walk before entering the loop, $v$ the part of the walk inisde the loop, and $w$ the remaining end of the walk. We then know the following:

* The loop $v$ contains at least one milestone. We note $|v|$ the number of milestones it contains. Hence $|v|\geq 1$.
* The loop does not necessarily include the $p^{th}$ milestone. But may occur before it. Whatever the case may be, the total length of the beginning $u$ of the walk (of length $|u|$ milestones) and one run through the loop ($|v|$ milestones) must have occured when the $p^{th}$ milestone is passed. Hence $|u|+|v|\leq p$, i.e. $|uv|\leq p$.
* Since there is a loop $u$ that you have walked at least once, nothing prevents you from going around it as many times as you want, $i$ times for any integer $i$, before finishing the $w$ part of your walk. You could also be in a hurry and decide to skip the loop, finishing the $w$ part just after doing the beginning $u$ of the walk, which amounts to having $i=0$.

Using the usual concatenation notation, your walk can be $uv^iw$ for any integer $i\geq 0$.

Automata theory jargon is that you can pump the loop $v$ as many times as you want in your walk, and you can even pump it out once if you wish (when $i=0$).

This is the heart of the pumping lemma. It can then be translated in various forms, for different kinds of formalisms, and with variations to help prove theorems.

Note that most often, **you use the lemma to prove that no such $p$ can exist**. So do not worry too much about what its value may be. The way proofs work is by assuming there is such a number $p$ as required by the pumping lemma. Then you show that it leads to some contradiction, so that you have a problem or structure that cannot be pumped. And this proves that your problem or structure is not in some pumpable family. (see proof techniques)

For example, regular languages are in a pumpable family, with proper interpretation of the basic construction.

## Pumping regular languages.

In the case of regular languages, the graph is the FSA diagram. However, the milestones are painted with colors, which are the symbols of the input alphabet, and our walk fragment $u$, $v$, and $w$ are represented by sequences of symbols read on the milestones, one milestone for each symbol on the FSA diagram.

Actually we have proved more than the traditional pumping lemma for FSA. For example, we can decide that some symbols are not part of the milestones count. That still works, but does no more than applying an erasing substitution, which does preserve the regular character of a language. But we might possibly try other such games, possibly more subtle ... which I have not done yet ... I just wrote this.

# Answer
> 4 votes
By definition, a language is regular if, and only if, it is accepted by a deterministic finite automaton (DFA). So, given a language $L$, suppose it is accepted by some DFA $M$. $M$ has some number of states: let's call it $p$. Now, consider the operation of $M$ on a string $w\in L$ that has length greater than $p$.

If $M$ accepts $L$, then it must accept $w$. By the pigeonhole principle, there must be at least one state $q$ that $M$ visits twice. Write $w=xyz$, where $x$ is the sequence of characters that $M$ reads until it first reaches $q$, $y$ is the sequence of characters read between the first and second visits to $q$ and $z$ is the rest of $w$. Note that $y$ must be at least one character, since it occurs between the first and second visit to $q$, which are different positions in the input. Observe that:

* from the initial state, reading $x$ takes you to state $q$;
* from state $q$, reading $y$ takes you back to $q$;
* from state $q$, reading $z$ takes you to an accepting state.

The key point is that, from $q$, reading $y$ any number of times, including zero, will return you to state $q$ and you can then read $z$ to get to an accepting state. Therefore, the machine $M$ accepts any string of the form $xy^rz$ for $r\geq 0$. We have just proved the pumping lemma.

For examples of using the pumping lemma, see our reference question. In essence, you say, "If this language was regular, it would have to obey the pumping lemma. But if it did that, it would have to include all of these strings that it doesn't include. Therefore, it's not regular."

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


# Question
Title: Undecidability in the context of modern programming languages
Imagine a program, executed by an interpreter to be a Turing Machine. Consider this code:

```
x = read_input
print x

```

Does undecidability mean that there may possibly be an input to this program such that the program may never halt?

# Answer
Short answer: **No**.

Undecidability is a property of problems, not of programs. What is undecidable is however to check if some given program ever halts on any input. *This problem has the program as input.*

If you fix a program, then it *may* be decidable to check if the program halts for some input. *This problem has the program input as input.* In particular, for programs such as yours that *always* terminate, the termination problem is decidable, meaning there exists an algorithm for it: it just outputs "yes".

Note that the term "undecidability" only has a meaning in environments that allow arbitrary memory size and arbitrary input size. The Python language may fit to this definition, but the interpreter your are using certainly doesn't.
> 9 votes

# Answer
Undecidability tells us that, given an arbitrary program and some input, there is no general computational procedure which tells us whether that program halts on that input.

It says nothing about specific computational procedures which may be correct for specific (classes of) programs. That is, we can generate heuristics which correctly answer the question for some programs; the more complicated we're willing to make the heuristics, the more programs may be potentially covered. All that undecidability says is that no finite set of heuristics is going to correctly cover all cases.

To illustrate, we can start developing heuristics to decide whether a program $P$ halts on an input $x$. Let's narrow down our language first: we'll assume a procedural language, with no function calls, and the only control flow constructs are `while` and `if-else`. On the right machine, this system is Turing-equivalent.

> If the program doesn't contain a `while` loop, then it halts.
>
> If every basic block in the program contains a `return` statement, then it halts.

You can take this as far as you want to go, defining a sort of "halting semantics" for your programming language. The semantics will never be correct for all possible programs - if your language/machine is Turing-equivalent - but you can do pretty good. The above (correct) heuristics are enough to definitively answer the example in your question.
> 4 votes

---
Tags: undecidability
---


# Question
Title: Which method for ODE instead of Euler's?
I need a super-fast method for ordinary differential equations. Should I use the midpoint method? I need this for a reaction-diffusion system (Gray-Scott).

# Answer
> 2 votes
There are lots of methods. I have usually found a 4th order adaptive step size Runge Kutta method to work fairly well. A Leapfrog method might better preserve invariants over the long term. I'm afraid I don't know enough about reaction-diffusion systems to know how that might change my answer. You might look into our sister sites in scientific computing, computational sciences, etc. for more information. If you're not already familiar with the "numerical recipes" series, that could prove very useful, although it may not have anything exactly suited to your needs.

---
Tags: algorithms, numerical-analysis
---


title: how to prove a language is decidable

text:
# Question
Title: how to prove a language is decidable
Hopefully this is not a duplicate

How do I prove a Language L={a,b,c} is decidable or not

I read somewhere that if a turing machine accepts a language and halts on every input string then the language is decidable.

Having said that how do i design / prove that a turing machine accepts {a b c}

I am new to concepts of automata and compelexity so please don't kill me if this is too basic for a question

# Answer
> 6 votes
By definition, a language is decidable if there exists a Turing machine that accepts it, that is, halts on all inputs, and answers "Yes" on words in the language, "No" on words not in the language. Therefore one way of showing that a language is decidable is by describing a Turing machine that accepts it.

There are many offline and online resources on Turing machines. For example, here are some introductory slides on Turing machines: part 1, part 2.

---
Tags: decision-problem
---


# Question
Title: Lamport Timestamps: When to Update Counters
In the timepiece (excuse the pun) that is Time, Clocks and the Ordering of Events, Lamport describes the logical clock algorithm as the following:

1. Each process $Pi$ increments $Ci$ between any two successive events.
2. If event a is the sending of a message m by process $Pi$, then the message $m$ contains a timestamp $Tm = Ci(a)$.
3. Upon receiving a message $m$, process $Pi$ sets $Ci$ greater than or equal to its present value and greater than $Tm$.

However, the algorithm as it is described on Wikipedia (and other websites) is a little different:

1. A process increments its counter before each event in that process.
2. When a process sends a message, it includes its counter value with the message.
3. On receiving a message, the receiver process sets its counter to be greater than the maximum of its own value and the received value before it considers the message received.

This leaves me with the following questions:

1. Should be increment the counter before sending a message, as the sending of a message is itself an event. This incremented timestamp is the value that is sent with the message.
2. When a message is received by process $Pi$ Lamport states that $Pi$ logical clock should be set to $max(Tm + 1, Ci)$. However, the Wikipedia article says that this should be $max(Tm, Ci) + 1$. Is Wikipedia wrong?

# Answer
Considering that any local action (e.g. increasing a counter) done by a process *is* an event, the Wikipedia sentence

> "A process increments its counter **before** each event in that process."

does not make any sense to me. Let me try to answer your questions:

> 1. Should we increment the counter before sending a message, as the sending of a message is itself an event. This incremented timestamp is the value that is sent with the message.

Both actions (i.e. increasing the counter and sending the message) happen atomically in the same event. The same is true when a message is received: The receive event already includes the counter update.

> 2. When a message is received by process Pi Lamport states that Pi logical clock should be set to max(Tm+1,Ci). However, the Wikipedia article says that this should be max(Tm,Ci)+1. Is Wikipedia wrong?

Note that, according to Lamport's paper, the logical clocks must satisfy the following property:

> If $a$ happens before $b$ then $C(a) \< C(b)$.

In particular, this means that clock values (of events) at the same process must be strictly increasing. Therefore, the correct update rule is $\max(Tm,Ci)+1$, as otherwise two subsequent events at the same process might have the same value.
> 2 votes

---
Tags: distributed-systems, synchronization, clocks
---


# Question
Title: The meaning of $*$ in regular expressions
I'm designing a Turing machine that decides a language denoted by a regular expression. Let's say this expression is $a^\*bbc^\*$. Does this machine accept the string $bb$ since $a^\*$ and $c^\*$ can have zero instances or more?

# Answer
> 2 votes
Yes, the word $bb$ in the language generated by the regular expression $a^\*bbc^\*$, because, as you say, $a^\*$ and $c^\*$ generate also the empty word. So if you are building a Turing machine that accepts this language, it should also accept the string $bb$.

---
Tags: turing-machines, regular-expressions
---


title: Converting DFA to regular expression

text:
# Question
Title: Converting DFA to regular expression
I have the following DFA. (Yellow stated are accepting states.) I want to eliminate states step by step to find the regular expression of it.
In my steps, I think there is a bug because I do not know what to do with state 4.

If you know how to convert this DFA to regular expression please help me.

# Answer
> 2 votes
From state 4 you cannot reach an accepting state. That means that state 4 does not contribute to the language of the automaton. Therefore you can simply delete it and then apply the state elimination procedure to the rest of the automaton to find the equivalent regular expression.

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


# Question
Title: Why do we need "Bloom Filters" if we can use hash tables?
A Bloom filter is a probabilistic data structure designed to tell, rapidly and memory-efficiently, whether an element is in the set or no.

If we can use hash tables where we have O(1) in best time, O(n) in a very bad situations. Why do we need a new abstract data structure that look-up for an element with less certainty. What are the scenarios where HashTables fails and demands the use of bloom filters?

When should bloom filters be used over hashtables and vice-versa?

# Answer
The second paragraph of the Wikipedia article on Bloom filters says the following, with a citation to Bloom's original 1970 paper.

> Bloom proposed the technique for applications where the amount of source data would require an impracticably large hash area in memory if "conventional" error-free hashing techniques were applied. He gave the example of a hyphenation algorithm for a dictionary of 500,000 words, out of which 90% follow simple hyphenation rules, but the remaining 10% require expensive disk accesses to retrieve specific hyphenation patterns. With sufficient core memory, an error-free hash could be used to eliminate all unnecessary disk accesses; on the other hand, with limited core memory, Bloom's technique uses a smaller hash area but still eliminates most unnecessary accesses. For example, a hash area only 15% of the size needed by an ideal error-free hash still eliminates 85% of the disk accesses.

---

Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors. *Communications of the ACM* 13(7): 422–426, 1970. (DOI)
> 10 votes

---
Tags: data-structures, bloom-filters
---


title: What is the Big O of T(n)?

text:
# Question
Title: What is the Big O of T(n)?
I have a homework that I should find the formula and the order of $T(n)$ given by

$$T(1) = 1 \qquad\qquad T(n) = \frac{T(n-1)}{T(n-1) + 1}\\,. $$

I've established that $T(n) = \frac{1}{n}$ but now I am a little confused. Is $T(n) \in O(\frac{1}{n})$ the correct answer for the second part?

Based on definition of big-O we have that

$$O(g(n)) = \\{f(n) \mid \exists c, n\_0\>0\text{ s.t. } 0\leq f(n) \leq cg(n)\text{ for all } n\geq n\_0\\}\\,.$$

This holds for $f(n) = g(n) = \frac{1}{n}$ so, based on the definition, $O(\frac{1}{n})$ should be correct but, in the real world it's impossible that algorithm can be faster than $O(1)$.

# Answer
> 8 votes
Yes, all functions $f(n)$ satisfy $f(n) \in O(f(n))$. The definitions are meaningful even if $f(n)$ isn't the running time of any function. Indeed, this notation comes from number theory, where $f(n)$ is usually some error term. Even in computer science, sometimes big O notations is used while analyzing algorithms for something other than a running time or space requirements.

---
Tags: algorithm-analysis, asymptotics, recurrence-relation
---


title: Need help to derive the Complexity!

text:
# Question
Title: Need help to derive the Complexity!
Please help me regarding this one! What will be the communication and computation complexity of this code??

```
While (m>0) do
{
   While ((m mod 2)==0) do
       {
          m ← ⌊m/2⌋
         //parties communicate m times;
       }
m = m – 1;
}

```

This code been modified from the book "Fundamental of computer algorithm" by Sahni.So according to that, it seemed computational complexity is O(*logm*) as m decreases by a factor of at least 2. But can i say communication complexity is O(*logm*) as well?? Probably not; i'm really confused!!

# Answer
> 0 votes
If $m \> 0$ is even then the two parties communicate $m/2$ times at their first round of communication. If $m \> 1$ is odd then they communicate $(m-1)/2$ times at their first round of communication. In particular, the communication complexity is not $O(\log m)$, but at least $\Omega(m)$. In fact, it is also $O(m)$, but you'll have to figure out why yourself.

---
Tags: algorithms, complexity-theory, communication-complexity
---


title: Finding approximately collinear points

text:
# Question
Title: Finding approximately collinear points
my issue comes from image processing. The image below is for a better understanding of the problem. I have to detect three dots (shown in black, marked with red arrows). The other points I get from my image after processing it are shown in green. As you can see I get many more points from the image than just the black ones, due to other structures inside the picture. So I've got a set of points and I know that there are at least three of them that are on a curve which is approximately a line and the approximate distance between the points is also known. I need to find these three points from my set.

The algorithm should be able to detect whether there is such a structure in the picture or there isn't one.

# Answer
> 1 votes
A simple algorithm is to iterate over all ways to choose 3 of the points, and test whether those 3 satisfy your criteria (are approximately colinear, have the appropriate distances, etc.). There are ${n \choose 3}$ such triples, so the running time of this algorithm is $O(n^3)$.

It is possible to improve on that. Here is an algorithm whose running time is $O(n^2 \log n)$:

* For each point $p$:

+ Sort the points by their slope to $p$. In other words, for each point $q$, calculate the slope of the line connecting $p$ and $q$, and use this as the key to help you sort the points.
    + Look for two points $q\_1,q\_2$ such that the slope of the line connecting $p$ and $q\_1$ is approximately the negative of the slope of the line connecting $p$ and $q\_2$. You can check whether such a pair of points $q\_1,q\_2$ exist by a linear scan over the sorted list built in the previous step. For each such pair, test whether $q\_1,p,q\_2$ satisfy your criteria (are approximately colinear, have the appropriate distances, etc.); if they are, output them.

The running time is $O(n^2 \log n)$, since for each iteration of the outer loop you do $O(n \log n)$ work, and the outer loop does $n$ iterations.

The above algorithm sorts the list of points by their slope, to make it easier to find 3 points that are approximately colinear. You could also sort the list of points by their distance to $p$, to make it easier to find 3 points at the prescribed distances. It's hard to say a priori which one might work better, but you could certainly try them both.

---
Tags: algorithms, image-processing
---


title: Co NP problem correponding to SAT

text:
# Question
Title: Co NP problem correponding to SAT
I've been reading lately about SAT problem, NP and co-NP.

Many sources say that the SAT problem is co NP, though, I can't find a co-NP problem equivalent to SAT.

Does anyone have any idea about this ? (Or could lighten my misunderstandings)

# Answer
If SAT is in coNP then NP=coNP, which is believed to be false. However, coSAT, the language of unsatisfiable CNFs, is coNP-complete.
> 5 votes

---
Tags: satisfiability, co-np
---


# Question
Title: Order of storage of pointers for a linked list of length n
I have a linked list in which I have kept the elements in order (increasing/decreasing). I want to be able to perform a binary search on this linked list. For this I am keeping pointers to the middle element of list of length n, n/2, n/4 so on. I am not able to figure out what would be the order of storage in this case. Any ideas?

# Answer
> 1 votes
Let $T(n)$ be the number of middle-of-list pointers you need to store for a list of length $n$. For a list of length $n$, you need to store one pointer to the middle, plus however many middle-of-list pointers you need for the first half, plus however many you need for the second half. This gives $$T(n) = 1 + 2T(n/2)\\,,$$ and we can take $T(1) = 0$, since a list of length $1$ probably doesn't need a middle-of-list pointer.

We have a reference question on formally solving recurrences like this but, for a rough-and-ready approach, we see that $T(2)=1$, $T(4)=3$, $T(8)=7$ so it's pretty clear that $T(n)=O(n)$ and, more to the point, $T(n)$ is about equal to $n$.

Well, now we wonder if a linked list was really the right data structure to be using. First off, programming a linked list with middle-of-list pointers seems to be quite difficult. Appending an item to the list sounds like it'll be awkward because you have all those pointers to update. Actually, I'm not sure what the data structure would even look like. But, anyway, maintaining the middle-of-list pointers costs us time so we'd better hope get something back for our investment of time, such as a saving in space. Nope. Storing the linked list needs about $n$ "next" pointers and about $n$ middle of list pointers, for a total of about $2n$. But just storing your data in a binary tree would require $n$ nodes, each with a pointer to the left child and one to the right child, again giving a total of $2n$ pointers.

# Answer
> 0 votes
You have just described the order. First you include the middle of the list. Then the middles of the two halves. And so on. That's the same storage convention as a heap: the children of node number $x$ are $2x$ and $2x+1$, assuming the first element is $1$. Let's see what this means for $n = 7$. The middle of the list is element 4, in binary 100. The middle of the first half is 2, in binary 010, and of the second half 6, in binary 110. Finally we have 001,011,101,111. The order in binary is $$ 100,010,110,001,011,101,111. $$ See if you can figure out a pattern.

---
Tags: linked-lists, binary-search
---


# Question
Title: How to find a local minimum of a complete binary tree?
How to find a local minimum of a complete binary tree?

> Consider an $n$-node complete binary tree $T$, where $n = 2^d − 1$ for some $d$. Each node $v \in V(T)$ is labeled with a real number $x\_v$. You may assume that the real numbers labeling the nodes are all distinct. A node $v \in V(T)$ is a local minimum if the label $x\_v$ is less than the label $x\_w$ for all nodes $w$ that are joined to $v$ by an edge.
>
> You are given each a complete binary tree $T$, but the labeling is only specified in the following *implicitly* way: for each node $v$, you can determine the value $x\_v$ by *probing* the node $v$. Show how to find a local minimum of $T$ using only $O(\log n)$ *probes* to the nodes of $T$.

Attribution: this seems to be Problem 6 in Chapter 5 "Divide and Conquer" from the book "Algorithm Design" by Jon Kleinberg and Eva Tardos.

# Answer
> 7 votes
As the tree is finite and the labels are real numbers, we are assured that there is a least element in the set of labels (this question from math.SE has a proof of this simple property). In this case as all the labels are distinct, it is okay that we require the local minima to be strictly less than their neighbours. If they were, then we would have to relax this condition to "less or equal to", otherwise there may not be a solution. Nonetheless we know that there is at least one local minimum to find.

If the tree is rooted (i.e. we have a notion of a parent-child relation) we can solve the problem marginally cheaper. If the tree is unrooted, then asymptotically we can do as well, but we will likely perform more actual probes.

First we'll deal with the rooted case.

As the tree is a (complete) binary tree, each vertex has at most three neighbours, its parent and two siblings (with the root of course having no parent), so a vertex is a local minimum if its label is less than the labels of its two children and parent. Hence we can determine if a vertex is a local minimum or not with at most four probes (in fact as we will traverse the tree in an ordered fashion, we will need at most three in the rooted case).

To actually find a local minimum, we can traverse the tree, starting with the root as the current vertex, in the following fashion:

1. Probe the current vertex's label, and the labels of its two children.
2. If the current label is the smallest, halt and report that the current vertex is a local minimum.
3. Else set the current vertex to the child with the smallest label, and return to step 1.

As we start from the root, we never need to worry about the parent's label - the root has no parent, and if our current vertex has a parent, then we must have discounted it in the previous iteration. Note that in step 2 it's not strictly required that we choose the smallest label, any that is smaller than the current is sufficient1, picking the smallest just gives a definite choice (again because we have distinct labels).

As we select one vertex out of the two children, our traversal picks out a path from the root to (at furthest) a leaf, thus as we have a binary tree of depth $d \< \log n + 1 $ (as it's a complete binary tree with $n = 2^{d}-1$ vertices), we perform at most $3d \in O(\log n)$ probes.

In the unrooted case, we don't have such a convenient starting point, however we still have the tree structure (even if the algorithm doesn't know it). We can use the following algorithm:

1. Pick any vertex to be the initial current vertex.
2. Probe the label of the current vertex and all of its neighbours.
3. If the current vertex has the lowest label, halt and report it as a local minimum.
4. Else, select the neighbour with the lowest label as the new current vertex and return to step 2.

At each iteration we only perform at most 4 probes, so the question is how many iterations can there be? The key is to observe that we can never backtrack (we know that were we came from had a bigger label), so we must follow a simple path in the graph, but as the graph is actually a complete binary tree, the longest simple path has length $2d$. Thus even in the unrooted case we perform at most $8d \in O(\log n)$ probes.

For correctness we look at the second algorithm (the rooted case is clearly just a special case of the unrooted).

The fact that the algorithm can never backtrack also guarantees termination, as the graph is finite. Now we need only demonstrate that the vertex $v$ we terminate at is in fact a local minimum. Assume for contradiction that it is not, then it has some neighbour $u$ that has a label with a lower value. We have three cases: (1) $u$ is the previous vertex in the path which the algorithm has followed, in which case when the algorithm was at $u$, it would not have selected $v$ as the next vertex; (2) $u$ is appears in the path, but more than one iteration earlier, in this case the graph is not a tree; and (3) $u$ is not in the path the algorithm followed, but then the algorithm would select $u$ as the next vertex in step 4, and the algorithm would not have terminated at $v$. Thus $v$ must be a local minimum.

Another way to see this is to simply observe that the sequence of labels of the vertices selected by the algorithm is monotonically decreasing. From this both the termination and correctness follows immediately.

Footnote:

1. The property that allows this is that every subtree has a local minimum - again, every finite set which has a total ordering has a least element. Thus by induction, when we extend the subtree with a new root and a sibling-subtree, we have three cases: (1) the new root is smaller than both its children, so the algorithm would terminate the new root; (2) the new root is smaller than one child but not the other, then the algorithm will not choose the larger root and must take the smallest by definition; or (3) both children are smaller, but in this case, as noted, each subtree has at least one local minimum, so we may select either.

---
Tags: terminology, graphs, binary-trees
---


# Question
Title: How to identify statistically distinct features of different sets?
I have two non-overlapping sets of items, with feature counts for each. What standard algorithms can I use to extract the most statistically distinct features of each set?

For example:

* Items served at American restaurants (5 restaurants surveyed):
    + bread: 4
    + burgers: 2
    + cheese: 1
    + cronuts: 2
    + pasta: 2
* Items served at Italian restaurants (10 restaurants surveyed):
    + bread: 7
    + pasta: 10
    + cheese: 8

I want to be able to know that cronuts and burgers are distinctly associated with American restaurant menus, and cheese and pasta are distinctly associated with Italian restaurant menus.

Thanks!

# Answer
This looks like a standard machine learning problem. You could use any machine learning technique. You might start with Naive Bayes.

If you want to evaluate a single feature, you could use information gain or BIC.

For the combination of all features, you can use a machine learning algorithm. As I mentioned, I would suggest trying Naive Bayes first. If you need something more powerful, there are many other classifiers: random forests, SVM's, k-nearest neighbors. Read a textbook on machine learning to learn more about the subject.
> 1 votes

---
Tags: algorithms, machine-learning, classification
---


title: Strongly connected components in graph

text:
# Question
Title: Strongly connected components in graph
Statement:**SCC in G is same as Rev(G)**

Ex:Consider the following graph g

0-\>1

1-\>2

2-\>4

3-\>1

4-\>3

The strong components set would be S={0,1,2,3,4}

If I reverse the above graph (i.e)

1-\>0

1-\>3

2-\>1

3-\>4

4-\>2

Then the strong components set would be S'1={0} S'2={1,2,3,4}

Which shows that strong components in G is not same as strong components in Rev(g)

# Answer
In a strongly connected component of a graph, all nodes of the SCC must be reachable from all other nodes in the SCC. So, if $x$ and $y$ are nodes of the SCC, then there is a path from $x$ to $y$ and a path from $y$ to $x$. Clearly, if we reverse all edges in the graph, then there is still a path from $x$ to $y$ (the old path from $y$ to $x$) and still a path from $y$ to $x$ (the old path from $x$ to $y$).

Your mistake in determining the SCCs of the first graph $G$: there is no edge going into node $0$, thus $0$ is not reachable from any of the other nodes. Therefore the SCCs of $G$ are $\\{0\\}$ and $\\{1,2,3,4\\}$, which are also the SCCs of $\mathit{Rev}(G)$.
> 1 votes

---
Tags: algorithms, graphs
---


title: 2-way Graph Partitioning problem

text:
# Question
Title: 2-way Graph Partitioning problem
We have a graph $G=(V,E)$ and we need to divide this graph into two clusters $A$ and $B$. Some pairs of vertices $u$, $v$ should not be in the same cluster, and we define an edge $(u,v) \in E$. The total cost of a solution is the total number of edges with endpoints both in the *same* cluster. My goal is to find an algorithm that returns the optimal solution that *minimizes* this total cost. The solution does *not* have to be balanced in the sense that the clusters should be of the same size.

I was wondering what the general name for this problem is and what a proper algorithm is that can solve this efficiently. By a colleague I was pointed into the direction of using a (nice) *tree decomposition*.

# Answer
You're looking for a **maximum cut** in the graph – maximizing the number of edges between the partitions minimizes the number within them.

Unfortunately, Max Cut is **NP**-hard on general graphs and also hard to approximate. There's a polynomial-time algorithm on planar graphs, if that's of any use to you.
> 2 votes

---
Tags: algorithms, graphs, terminology, partition-problem
---


title: Acyclic Graph in NL

text:
# Question
Title: Acyclic Graph in NL
From the book *The Nature of Computation* by Moore and Mertens, exercise 8.9:

> Consider the problem ACYCLIC GRAPH of telling whether a directed graph is acyclic. Show that the problem is in NL, and then show that the problem is NL-complete.

I am mainly interested in the first part. It's quite easy to show that it's in coNL (just guess a walk, vertex by vertex, from a vertex $v$ that returns to $v$), and then we can use the Immerman-Szelepcsényi Theorem to prove that it's in NL.
But I was not able to construct a Turing machine directly, i.e. a machine that shows that the problem is in NL without the help of Immerman-Szelepcsényi or the construction from their proof. My question thus is:

How can I show *directly* that ACYCLIC GRAPH is in NL?

# Answer
It's easy to see that the problem is coNL-complete.

If you could find a direct proof that ACYCLIC GRAPH is in NL, then it would be a direct proof of NL=coNL. However, as far as I know, nobody knows about a proof of this fact that does not use the inductive counting technique. See https://cstheory.stackexchange.com/questions/2145/alternate-proofs-of-immerman-szelepcsenyi-theorem and Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$.

(By the way, I find it bit easier to think about the problem "CYCLIC GRAPH" as in "graph that has a cycle"; it's easy to show that's it's NL-complete.)
> 3 votes

---
Tags: complexity-theory, graphs, space-complexity
---


title: What problem does cache coloring solve?

text:
# Question
Title: What problem does cache coloring solve?
According to what I have read from two different sources, cache coloring is (was?) required in order to:

* **Counter the problem of aliasing:** Prevent two different virtual addresses with the same physical address from mapping to different cache sets. (According to a CS Stack Exchange Answer)
* **Exploit the spatial locality property of virtual memory**: by guaranteeing that two adjacent blocks of virtual memory (not necessarily adjacent in physical memory), do not map to the same cache index. (According to Wikipedia)

These seem to me to be fundamentally different definitions, and without comprehending the motivation for cache coloring, I can't seem to understand the mechanism for selecting the number of colors required. Are they really one and the same?

If the spatial locality of virtual memory is the primary motivation, is cache coloring really required for VIPT caches, where the index of the cache is derived from the virtual memory to begin with? Or is cache coloring simply used in VIPT caches to get around aliasing?

# Answer
> 3 votes
Both avoiding aliases and avoiding excessive cache conflicts are valid reasons for using page coloring. Requiring page coloring to avoid aliases is unpopular because it places a mandatory constraint on page allocation. In general, modern non-embedded processors do not require page coloring to avoid aliasing.

Avoiding aliasing issues in hardware increases hardware complexity, so earlier processors (and perhaps some more recent embedded processors) chose to place the burden on software. Hardware can avoid aliasing issues in a cache with more index+offset bits than bits in the page offset by (for example):

* checking alternate sets on a cache miss (as done by AMD's Athlon; when an alias was detected the block was moved to the current virtual index)
* including the virtual address bits used for indexing L1 in a (tag) inclusive L2 (on an L1 miss and L2 hit, if the virtual address bits match the corresponding bits for the request, no action is necessary; if the bits do not match, the appropriate set to probe is known \[whether the block is also in L1 could also be stored in the L2 tags to reduce coherence overhead, so some probes might be avoided\])
* using set prediction to guess the extra physical address bits used for indexing (a misprediction would be discovered after TLB access and corrected)
* using reverse translation (physical to virtual) on a cache miss to find possible aliases (I think a PA-RISC implementation used reverse translation for *coherence*)

Using page coloring to reduce conflicts (for caches with simple modulo a power of two indexing) is less unpopular because the page coloring is not required for correctness. If a particular color becomes scarce, a page can be mis-colored with only a possible reduction in performance. This rationale for page coloring also means that the number of bits colored is less constrained. The (less practical) ideal may be to match all physical index bits for the last level cache with the corresponding virtual address bits, but even coloring just four bits can substantially reduce conflict issues.

It might be worth noting that coloring for alias avoidance need not match virtual address bits with physical address bits. As long as all potential aliases share the same virtual address bits used for indexing, alias issues are avoided. However, matching physical and virtual address bits may be convenient (and provide predictable conflict in physically addressed levels of cache).

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


title: Model Checking: hardware vs software

text:
# Question
Title: Model Checking: hardware vs software
In short: What is the basic difference that allows model checking for hardware to be "easily" solvable, but makes it undecidable for software?

I guess it has to boil down to the difference between hardware being finite automata and software having the expressiveness of a Turing machine, which would basically mean that its the infinite amount of (randomly accessible, vs. that of a push-down automaton) memory that the Turing machine has available -- is this correct?

# Answer
The statespace explosion problem.

More specifically, software often uses unbounded loops, pointers into complex data structures on the heap, and dynamic allocation. Each of these can cause rapid statespace explosion: the number of states increases rapidly, or becomes infinite. Model checking has difficulty with that. These constructs tend to be more common in software than in hardware, explaining why model checking tends to be more effective on hardware than on software (as a general rule, though there are of course exceptions).
> 2 votes

---
Tags: undecidability, model-checking, software-verification
---


title: Comparing $2^{F_n}$ and $2^{\varphi^n}$

text:
# Question
Title: Comparing $2^{F_n}$ and $2^{\varphi^n}$
if we define $F\_n$ be the $n$th fibonacci number and $\varphi$ be golden number then can we say that

$2^{F\_n} \in \Theta(2^{\varphi^n})$

or in other word

$2^{\frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}} \in \Theta(2^{\varphi^n})$

It's simple to show that $F\_n \in \Theta(\varphi^n)$ but about above one I don't have any Idea

# Answer
> 2 votes
Hint: We have $F\_n = \[\varphi^n-(-\varphi)^{-n}\]/\sqrt{5} = \varphi^n/\sqrt{5} \pm o(1)$, since $|1/\varphi| \< 1$. Hence $$ 2^{F\_n} = 2^{\varphi^n/\sqrt{5}} 2^{\pm o(1)} = 2^{\varphi^n/\sqrt{5}} (1\pm o(1)). $$ In particular, $2^{F\_n} = \Theta(2^{\varphi^n/\sqrt{5}})$. I'll let you compare $2^{\varphi^n/\sqrt{5}}$ and $2^{\varphi^n}$ yourself.

---
Tags: asymptotics
---


title: Is CYK still relevant today?

text:
# Question
Title: Is CYK still relevant today?
I've come across the CYK algorithm and was wondering, as it's quite old, if it is still relevant today.

Is it or an extension of it still being used in compilers (for example), or have other algorithms proven to be better?

# Answer
> 9 votes
CYK is still relevant, afaik, as the simplest example of a family of general parsing algorithm based on dynamic programming, ranging over all parsing technique (that I know of) and many syntactic formalisms. There is a simpler general parsing algorithm (below), but where the dynamic programming (DP) aspect is no longer visible. as things are defined more globally.

What I mean by general parsing algorithm, is a parsing algorithm that can parse all memeber of a family of languages, according to their given grammar, and produce all the possible parse structures when the parsed string is ambiguous, combined in a condensed form called a (shared-)parse-forest. Though this is often considered only for context-free (CF) grammars, it does generalize to other formalisms.

Most known such algorithms are for CF grammars: such as CYK, Earley, GLR, GLL with diverse variants. They are also known as chart parsers, and extend beyond formal languages to some logical formalisms, often introduced by computational linguists via so-called feature structures. They can all be seen as extensions or refinement of CYK, though that is often a subjective assessment. They can also be seen as extensions or refinement of the more basic algorithm presented below.

My experience (but new research might prove me wrong) is that the DP structure of CYK is a proper route to understand, in a simple context, some of the issues raised by the various techniques for improving the performance of those parsers in the structured context of the DP calculation, or to introduce various features such as Viterbi selection of the best parses.

Some of the most basic issues, such as the grammatical forms to be used to keep a low time and space complexity (cubic), or how to represent parse-forests. can be more readily viewed and understood from the simplest algorithm, which is the old cross-product construction (Bar-Hillel, Perles and Shamir, 1961) between a CF grammar and a FSA, to produce the grammar of the CF intersection of their languages. This view is developed in a paper by (Lang 1995) along with extensions to other formal languages.

From a practical point of view, i.e. for use in actual parsers, some of the more recent general parsers may be better tool. But I believe that CYK remains an important and simple educational step, more so in my opinion than Earley's algorithm that is much more complex. Which of the other DP algorithm should be used for actual systems remains the object of some debate, as performance issues are somewhat subtle.

I discuss some aspects a bit more in depth in another answer.

---
Tags: context-free, compilers, dynamic-programming, parsers, syntax-trees
---


# Question
Title: Show that the string $( [ ) ]$ is not in a Dyck language
I think I understand why the string $( \[ ) \]$ is not in a Dyck language.

In my words,

D2\* is all the dyck words of 2 parentheses.

From the definiton of $D2\*$, every words must have exactly 2 pairs correctly nested pairs of parentheses.

All the words of the language are given by

$\sum = { (1, )1, (2, )2 } $

The alphabet consisting of 2 kinds of left and right parentheses.

The language is given by the following grammar :

1. Terminal set is $\sum$
2. Start variable is not in terminal set
3. $ S -\> \big( \epsilon | SS | (i S )i \big)$ for all i \> 1

But the form of that word is $(i (j )i )j$ which fails to match the definition.

But I'm having trouble writing a formal proof on that.

# Answer
> 3 votes
Consider producing a leftmost derivation of ( \[ ) \]. We can begin with $$ S\Rightarrow SS\stackrel{\*}{\Rightarrow}SS\dotsc S $$ and to get the ( on the left we must eventually use the production $S\rightarrow(S)$ on the leftmost $S$, giving $$ S\stackrel{\*}{\Rightarrow}(S)S\dotsc S $$ and then we'll have $$ S\stackrel{\*}{\Rightarrow}(SS\dotsc S)S\dotsc S $$ and to get the \[ as the second terminal on the left we must eventually use the production $S\rightarrow\[S\]$, giving $$ S\stackrel{\*}{\Rightarrow}(\[S\]SS\dotsc S)S\dotsc S\stackrel{\*}{\Rightarrow}(\[SS\dotsc S\]SS\dotsc S)S\dotsc S $$ and now we're stuck, since no production will give us the ) terminal we need on the left without introducing a ( first.

For a slightly different take, consider that $S$ can only derive strings in $D\_2$, so to derive ( \] ) \] we must use the production $S\rightarrow (S)$, where the $S$ in the right term of the production must also derive a string in $D\_2$, but that would imply $S$ derives \], which cannot be, since $\]\notin D\_2$.

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


# Question
Title: What algorithm is suitable for very small scale, time dependent optimization?
I have a **time-dependent** (dynamic) optimization problem: $$ f\_t : \[0;1\]^2 \mapsto \mathbb{R}^+; t \in \[1, \dots, n\] $$ $f\_t$ is to be maximized. That is for each $t$ I would like to find a relatively high value of $f\_t$. Mostly, $f\_t$ is a relatively simple, continuous, unimodal function. It changes with time, but not much and not predictably. I know only that the scale of the function goes down exponentially.

The problem is that at each time I can perform only a handful (5-10) of evaluations of $f\_t$.

I am absolutely new to dynamic optimization and therefore I am looking for some simple approach. Any suggestions or references to literature are welcome.

I have considered particle swarm optimization, but the papers on PSO I read are usually dealing with at least 10 dimensional problems, so PSO may be an overkill. Also I do not know if it is appropriate to use just 5-10 particles.

# Answer
> 2 votes
Many optimization procedures are based upon successive approximation: they start with a value of $x$, and try to successively refine $x$ to move it closer and closer to the optimum. For instance, hill climbing and gradient ascent both have this structure.

You can use this structure to solve your problem. Let $x\_t$ be the maximum for $f\_t$. Then you can use $x\_t$ as the starting point (the initial approximation) when looking for the maximum for $f\_{t+1}$. Now iterate, using the maximum for the previous time period as the starting point for hill climbing / gradient ascent / .... in the next time period. If the maximum for $f\_{t+1}$ is close to the maximum for $f\_t$, this might work reasonably well.

There are many different possible ways to instantiate this basic approach. Here are some possible examples of how this might look:

* With gradient ascent, you evaluate $f\_{t+1}$ three times at three points near $x\_t$: e.g., at $x\_t$, $x\_t+(\varepsilon,0)$, and $x\_t+(0,\varepsilon)$. You use the result to estimate the gradient around $x\_t$, and then move in the direction of the gradient.

As a possible optimization/variation, you might align the axes in the direction of the gradient for $f\_t$. For instance, if the gradient was maximum in the angle $\theta$ for $f\_t$, you might evaluate $f\_{t+1}$ at the three points $x\_t$, $x\_t+(\varepsilon \cos \theta, \varepsilon \sin \theta)$, $x\_t + (\varepsilon \cos (\theta+\pi/2), \varepsilon \sin (\theta+\pi/2))$, then use those values to estimate the gradient.
* As another possible optimization, you could follow this with a line search. Suppose $\delta$ is the direction that maximizes the gradient. Then you could evaluate $f\_{t+1}$ at $x\_t,x\_t+\delta,x\_t+2\delta,x\_t+3\delta,x\_t+4\delta,\dots$, stopping at the first one that stops providing any improvement. Or, you could evaluate $f\_{t+1}$ at $x\_t,x\_t+\delta,x\_t+2\delta,x\_t+4\delta,x\_t+8\delta,\dots$. You could even follow this with an iteration or two of binary search to find the best stopping point, though that might not be worthwhile.
* If you are trying hill-climbing, you will do something simple like this: pick a random point $x'$ in the neighborhood of $x\_t$, and if $f\_{t+1}(x') \> f\_{t+1}(x\_t)$, then move to $x'$. You can repeat this a few times.

Of course, you can combine these methods. There may be many other variations you could try. I would suggest that you read about methods for optimization, brainstorm other similar methods, and then try them all to see which work best.

Also, you might want to try a simulation: choose $f\_t$ that you believe to be representative and where you can evaluate them as many times as desired to find the true maximum and their shape, and then simulate each of these strategies to see how well they work. You might also want to visualize the shape of the $f\_t$ and what these strategies are doing (what points they are visiting), in case that helps you refine them or choose suitable constants that are appropriate for your particular application domain.

---
Tags: optimization, heuristics
---


title: Is ecological bin packing NP-hard?

text:
# Question
Title: Is ecological bin packing NP-hard?
The ACM Contest Problem 102 (HTML or PDF) can be paraphrased as:

> Given 3 bins each containing possibly different number of bottles of 3 colors, move the bottles so that there is one color per bin, minimizing the number of bottle movements.

Specifically, we wish to decide on an allocation of colors to bins so that moving from the initial position to the "sorted" position requires the least number of bottle moves. The bins are assumed to have infinite capacity.

For the problem as stated, one can brute-force check all $3! = 6$ permutations to see which has the fewest number of bottle movements. However, for $N \> 3$ colors of glass, $N!$ grows very large. Is there a way to solve this problem for general $N$ that runs in polynomial time?

# Answer
Yes, this can be solved in polynomial time, for arbitrary $N$. This is an instance of the assignment problem, for which polynomial-time algorithms are known.

You want to assign a color of glass to each bin, such that each bin gets exactly one color, and each color is assigned to exactly one bin. The cost of assigning bin $b$ to color $c$ is the number of bottle moves needed to move all bottles of color $c$ that aren't currently in bin $b$, into bin $b$. Therefore, this is an assignment problem.

(You can compute this cost function more efficiently as follows: the cost of assigning bin $b$ to color $c$ is the number of moves needed to move all bottles that aren't colour $c$ out of bin $b$. Thanks to @David Richerby for this insight.)

The assignment problem can be solved using standard methods, e.g., the Hungarian algorithm or algorithms for min cost max flow.
> 1 votes

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