# Question
Title: DFA/NFA/ε-NFA: subsetting each other or different sets?
I know that an ε-NFA (NFA with epsilon transitions) is not an NFA or a DFA and an NFA is not a DFA.

HOWEVER, say you have a complete DFA. Isn't that theoretically an NFA and an ε-NFA? Just because it doesn't have ε transitions, does it mean it is not ε-NFA? If a question asks you to turn a DFA into an ε-NFA, can't you just write the complete DFA as an answer? What properties make DFA different from ε-NFA and NFA?

The same question applies to NFA → ε-NFA, isn't NFA a more "primitive" version of ε-NFA? It's just NFA without the ε...

# Answer
> 4 votes
If I understand your question correctly, you are essentially talking about the syntactic difference between DFAs, NFAs and NFAs with $\epsilon$ transitions.

Well, in a way, every DFA is also an NFA, and every NFA is also an NFA with $\epsilon$ transitions (it just so happens that the former does not use these transitions). A caveat here is that if you really stick to the standard definitions, then in a DFA the "type" of the transition function returns a state, whereas in an NFA it returns a subset. This is just a technicality, of course, as you can define a DFA to be an NFA whose transition function only returns singletons.

I would look at things this way: An $\epsilon$-NFA would be the "standard". Then, define an NFA to be an $\epsilon$-NFA that does not use the $\epsilon$ transitions. Finally, define a DFA to be an NFA with a single initial state and a transition function that only returns singletons.

In the comments, you ask about the size of the different models, w.r.t a fixed language. This is an entirely different issue. As it turns out, $\epsilon$ transitions can always be removed, and no new states are introduced in the process, only new transitions. As for the translation to DFA - this may involve an exponential blowup in the state space.

# Answer
> 1 votes
Yes, every DFA is an NFA and every NFA is an $\epsilon$-NFA.

Every state in a DFA must have exactly one transition for every symbol in the alphabet. In an NFA, a state can have any number of transitions for each symbol, including zero. But "any number" includes one so anything that meets the definition of a DFA also meets the definition of an NFA. If you like, a DFA is an NFA that happens not to have any nondeterminism.

A state in an $\epsilon$-NFA may have any number of $\epsilon$-transitions to other states. But "any number" includes zero so an NFA (which has no $\epsilon$-transitions from any state) meets the definition of an $\epsilon$-NFA. If you like, an NFA is an $\epsilon$-NFA that happens not to have any $\epsilon$-transitions.

So, yes, if a question asks for an $\epsilon$-NFA, you're within your rights to give a DFA or an NFA: those are just special kinds of $\epsilon$-NFA. On the other hand, if the quesion explicitly asks for an $\epsilon$-NFA, there's probably an $\epsilon$-NFA that's simpler than whatever DFA or NFA you came up with. :-)

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


title: What kind of NP problem would this be

text:
# Question
Title: What kind of NP problem would this be
I have N by N symmetrical matrix with each side having the same items.

```
     A    B    C    D
A    0
B    4    0
C    8    3    0
D    3    1    8    0

```

In reality this would be much larger (100 x 100)

I am trying to find a subset of a fixed size in this matrix with the highest score. For example the selection ABC would be:

```
  AB = 4;
  AC = 8;
  BC = 3;
Total  15

```

It is kinda like traveling salesman problem, but with the final distance only determined by the final selection.

# Answer
You can reduce clique (or independent set) to your problem, so it is NP-hard. Just take the adjacency matrix as your matrix, use the same parameter $k$ (the size of the clique), and declare that there is a clique in the graph if the maximum score is $\binom{k}{2}$.
> 2 votes

# Answer
Is $k$ fixed or not? Fixed means that $k$ is the same for every input, whether it's $3\times 3$ or $1000000\times 1000000$. If $k$ is fixed, then there are fewer than $n^k$ possible subsets so you get a deterministic polynomial-time algorithm just by trying each subset in turn.

On the other hand, if $k$ varies, either by being a part of the input or by being a function of $n$, then the problem is (probably) NP-complete. If it's part of the input, Yuval has shown NP-completeness by reduction from clique. If it's some function $f(n)$ and $f$ can be computed efficiently enough, you get NP-completeness roughly like this, again by reduction from clique.

We want to know if an $m$-vertex graph $G$ has a clique of size at least $k$. First, find some $k'\geq k$ such that $f(n)=k'$ for some $n\geq m$. Then, add $k'-k$ vertices to $G$ and make each one adjacent to every vertex in the new graph $G'$ (including the new vertices). Finally, add isolated vertices to $G'$ to give a graph $G''$ with $n$ vertices in total. (You'll need to deal with the case where $G'$ already has more than $n$ vertices!)

Now, $G$ has a $k$-clique if, and only if, $G'$ has a $k'$-clique if, and only if, $G''$ has a $k$-clique. But $k'=f(n)$ and the adjacency matrix of $G''$ is $n\times n$, so we can use Yuval's answer to determine if $G''$ has a $k'$-clique.
> 1 votes

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


# Question
Title: Proving a PDA with CFG Transitions recognizes Context Free Languages
I'm working on a proof that deals with a modified PDA, which is identitical to a PDA, but with transitions: \begin{equation\*} a,b \to c \end{equation\*} where $a$ is a context free grammar, instead of just a symbol. The modified PDA then reads a prefix $w'$ of $w$, the suffix of the input stream, where $w' \in L(a)$.

I'm try to prove that the language recognized by this modified PDA is context free, but I'm really stuck. I have no idea how to even get started. If someone could point me in the right direction, I would really appreciate it.

# Answer
> 1 votes
Hint: Try replacing each such transition by an appropriate PDA.

---
Tags: formal-languages, automata
---


# Question
Title: Given an array of N integers, how can you find M elements to remove so that the array will end up in sorted order?
Here is my approach

First I compute the longest non decreasing sub-sequence in $N \log N$ time. Algorithm to do this (that only uses arrays and binary search) can be found here: http://en.wikipedia.org/wiki/Longest\_increasing\_subsequence#Efficient\_algorithms

Let's suppose the longest subsequence has $L$ elements. Then if $L \< N - M$, there isn't any way to solve the problem since there's no subsequence of length $N - M$ that's still sorted.

Otherwise, just remove the $N - L$ elements that aren't in the subsequence, and then remove more at random until exactly M total have been removed. In all this is an $N \log N$ algorithm.

I want to know, is there any more efficient algorithm (i.e. $O( N)$ ) to solve this problem ?

# Answer
You can adapt the algorithm described in Wikipedia so that it runs in time $O(N\log (N-M))$ if you're only interested in increasing sequences of length at most $N-M$. Judging by the existence of an $N\log N$ lower bound for the general case, $O(N\log(N-M))$ might be optimal. (Your problem is equivalent to the decision problem of whether there exists a non-decreasing subsequence of length $N-M$; this can be reduced to strictly increasing subsequences by adding appropriate $\epsilon$s.)
> 2 votes

---
Tags: algorithms, time-complexity, runtime-analysis, subsequences
---


# Question
Title: Verify correctness of quantifier elimination, using SAT
Let $x=(x\_1,\dots,x\_n)$ and $y=(y\_1,\dots,y\_n)$ be $n$-vectors of boolean variables. I have a boolean predicate $Q(x,y)$ on $x,y$. I give my friend Priscilla $Q(x,y)$. In response, she gives me $P(x)$, a boolean predicate on $x$, and she claims that

$$P(x) \equiv \exists y . Q(x,y),$$

or in other words, that

$$\forall x . \[P(x) \Leftrightarrow \exists y . Q(x,y)\].$$

I would like to verify her claim somehow. How can Priscilla help me verify this claim?

You can assume that both $P$ and $Q$ are represented as CNF formulas, and that they're not too large (polynomial size, or something).

In an ideal world, it'd be awesome if I could reduce the problem of verifying this claim to SAT: I have a SAT solver, and it'd be great if I can use the SAT solver to verify this claim. However, I'm pretty sure that it's not going to be possible to formulate the problem of verifying this claim directly as a SAT instance; testing the validity of a 2QBF formula is almost certainly harder than SAT. (The $\Leftarrow$ direction is easy to formulate as a SAT instance, but the $\Rightarrow$ direction is hard because it inherently involves two alternating quantifiers.)

But suppose Priscilla could give me some additional evidence to support her claim. Is there some additional evidence or witness Priscilla could give me, which would make it easy for me to verify her claim? In particular, is there some additional evidence or witness she could give me, which would make it easy for me to formulate the problem of verifying her claim as an instance of SAT (which I can then apply my SAT solver to)?

One unusual aspect of my setting is that I'm assuming (heuristically) that I have an oracle for SAT. If you like complexity theory, you can think about it this way: I am taking the role of a machine that can compute things in $P^{NP}$ (i.e., in $\Delta^P\_2$), and I'm looking to verify Priscilla's claim using an algorithm in $P^{NP}$. My thanks to mdx for this way of thinking about things.

---

My motivation/application: I'm looking to do formal verification of a system (e.g., symbolic model checking), and a key step in the reasoning involves quantifier elimination (i.e., starting from $Q$, obtain $P$). I'm hoping for some clean way to verify that the quantifier elimination was done correctly.

If there's no solution that works for all possible $P,Q$, feel free to suggest a solution that is "sound but not complete", i.e., a technique that for many $P,Q$ lets me verify the claimed equivalence. (Even if it fails to verify the claim on some $P,Q$ that do satisfy the claim, I can still try this as a heuristic, as long as it never inappropriately claims to have verified a false claim. On any given $P,Q$, it might work, or it might not; if it doesn't work, I'm no worse off than where I started.)

# Answer
Here are two techniques I've been able to identify:

* **Identify an explicit Skolem function.** Suppose Priscilla can identify an explicit function $f$ such that

$$\forall x . P(x) \Leftrightarrow Q(x,f(x))$$

holds. Then it follows that Priscilla's claim is correct.

This means that Priscilla can help us verify her claim by providing a function $f$ so that the above proposition holds. We can confirm that the above proposition holds by testing the following formula for satisfiability:

$$\neg (P(x) \Leftrightarrow Q(x,f(x))).$$

If this formula is not satisfiable, then Priscilla's claim has been verified.

One caveat is that Priscilla needs to be able to identify a suitable function $f$. A further caveat is that we need $f$ to be concretely representable in some concise form, say, as a polynomial-sized boolean circuit. However, if those conditions are met, then this technique should work.
* **A hybrid argument.** Consider the special case of this problem, where we are quantifying over a one-bit variable (rather than a $n$-bit variable); it turns out the problem is easy to solve in this case. This suggests that we try to chain that technique $n$ times, each time removing one more bit of $y$. It turns out that this idea will sometimes work, but not always.

Let me explain how to verify Priscilla's claim in the case where $y=(y\_1)$ is a one-bit variable. Then $\exists y . Q(x,y)$ is equivalent to $Q(x,\text{False}) \lor Q(x,\text{True})$. The latter formula is at most twice as large as $Q$, so still polynomial sized. Now we can use our SAT solver to test whether $Q(x,\text{False}) \lor Q(x,\text{True})$ is equivalent to $P(x)$; the equivalence holds exactly if the following formula is not satisfiable:

$$\neg (P(x) \Leftrightarrow (Q(x,\text{False}) \lor Q(x,\text{True}))).$$

So, if we're quantifying over a single bit, this gives a way to verify that the quantifier elimination was done correctly.

To solve the original problem, apply this multiple times. Priscilla's job will be to give us $n+1$ boolean predicates $R\_0,R\_1,R\_2,\dots,R\_n$ such that

$$R\_i(x,(y\_{i+1},\dots,y\_n)) \equiv \exists y\_1,y\_2,\dots,y\_i . Q(x,y).$$

Our task will be to verify whether all of these boolean predicates were correctly generated. We can do this by testing whether $Q(x,y) \equiv R\_0(x,y)$, $P(x) \equiv R\_n(x)$,

$$R\_{i+1}(x,(y\_{i+2},\dots,y\_n)) \equiv \exists y\_{i+1} . R\_i(x,(y\_{i+1},\dots,y\_n)) \qquad \text{for $i=1,2,\dots,n-1$}.$$

Notice that the latter is an instance of quantifier elimination with a single bit, so we've already described how to test it was done correctly using a SAT solver. We can also test whether $Q \equiv R\_0$ and $P \equiv R$ using a SAT solver straightforwardly. So, we can check whether Priscilla generated $R\_0,\dots,R\_n$ correctly. If she did, then we've verified that $P$ was generated suitably.

One caveat is that Priscilla needs to be able to generate the $R\_i$'s. A bigger caveat is that the size of all the $R\_i$'s needs to be reasonable (say, polynomial-sized). If Priscilla generates the $R\_i$'s naively, their size might grow exponentially with $i$, which is no good. So, Priscilla will need a way to simplify at each stage; there needs to exist some sequence of $R\_0,\dots,R\_n$ that are all polynomial-sized, and Priscilla needs to be able to find such a sequence. That is by no means guaranteed. That said, if Priscilla can do this, then this technique should work.

I'm not fully satisfied with these techniques -- they are incomplete heuristics, and they might fail on some/many problem instances -- so I would still be interested to see other ways of approaching this problem.
> 3 votes

---
Tags: logic, satisfiability, first-order-logic, software-verification, model-checking
---


# Question
Title: Time Complexity of T(xn) + T((1 − x)n) + cn
What is the time complexity of the recurrence relation T(xn) + T((1 − x)n) + cn

# Answer
The Akra-Bazzi theorem shows that the solution is $\Theta(n\log n)$. Details left to you.
> 2 votes

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


title: Range query for sum of vectors

text:
# Question
Title: Range query for sum of vectors
We have two sets of vectors of positive numbers, $X$ and $Y$ where for $x\in X$ we write $x=(x\_1,x\_2,\ldots,x\_k)$ and similarly for $y\in Y$ we write $y=(y\_1,y\_2,\ldots,y\_k$).

We are given two vectors $l=(l\_1,l\_2,\ldots,l\_k)$, and $u=(u\_1,u\_2,\ldots,u\_k)$ such that $l\_i\le u\_i$ for all $i$.

We want to find all pairs $(x,y)$, $x\in X$, and $y\in Y$ such that $l\_i\le x\_i+y\_i\le u\_i$

Handwaving a bit, we can do this in a divide and conquer sort of way, separating each set into pieces that are larger and smaller than $l\_i/2$ and throwing away the pairs where both are in the smaller half. This gives a recurrence $$T(m,n) = T(m,n/2) + T(m/2, n/2) + c(m+n)$$ where $m=|X|$ and $n=|Y|$. For equal size sets, this gives $T(n,n) = O(n^{1.7})$, which is better than quadratic, but less than I would hope for.

A similar question could be asked for three or more sets.

# Answer
One approach would be to solve this using orthogonal range trees. Orthogonal range trees allow range queries in $k$ dimensions.

Store the $n$ values of $Y$ in an orthogonal range tree. The space complexity is $O(n (\lg n)^{k-1})$.

Next, for each $x=(x\_1,\dots,x\_k) \in X$, we're going to search for a matching $y \in Y$. Notice that for $y$ to match this particular $x$, we must have $l\_i - x\_i \le y\_i \le u\_i - x\_i$ for each $i$. This means that $y$ must fall into the $k$-dimensional box $\[l\_1-x\_1,u\_1-x\_1\] \times \cdots \times \[l\_k-x\_k,u\_k-x\_k\]$. So, we want to know if there is any element of $Y$ that falls within this box. That's a $k$-dimension range query, which an orthogonal range tree can handle.

The time complexity is $O((\lg n)^k)$ for each range query. We do $m$ range queries, so the total running time of this algorithm is $O(n (\lg n)^{k-1} + m (\lg n)^k)$. Of course, there is a symmetry between $X$ and $Y$, so you can swap $m,n$ if that reduces the running time.

It is possible to reduce the asymptotic running time slightly further by using more sophisticated data structures and algorithms, but I don't know if they will actually help in practice.

Bottom line: A slightly pessimistic bound is that the running time is $O((n+m) (\lg n)^k)$ (but the preceding discussion shows you how to get a slightly tighter bound). If $k$ is small enough this might be better than the $O(nmk)$ running time of the naive ("quadratic") algorithm.

---

Independently: Here is a heuristic that might help you in practice (even though it might not offer any guarantees in worst-case complexity).

Pick some value $k'$ such that $k'\< k$. Now randomly select a subset of $k'$ of the $k$ dimensions, and project everything to those $k'$ dimensions (so we temporarily ignore all of the other $k-k'$ coordinates). That reduces the problem from a $k$-dimensional problem to a $k'$-dimensional problem. In lower dimensions, the problem becomes easier, so you can solve the $k'$-dimensional problem to find all pairs $x\in X, y \in Y$ such that $x+y$ is correct in those particular $k'$ dimensions. Then, you can test each such pair to see whether $x+y$ is correct in all $k$ dimensions. The total running time will be the running time to solve the $k'$-dimensional problem, plus the running time to examine all pairs that survive the first phase. You can then try to choose $k'$ to balance these two contributions to the total running time.

I suspect that if you experiment with this sort of idea, then in practice this might significantly improve performance (at least if you start with a large value of $k$).
> 1 votes

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


title: Algorithms to play randomized game

text:
# Question
Title: Algorithms to play randomized game
I'm interested in building an AI algorithm to play a board game. This is a sequential two-player game, where they alternate taking turns, so minimax or alpha-beta algorithms sound natural.

However, the twist here is that the game is randomized. There is a deck of cards that is shuffled randomly; each turn involves drawing the next card from the deck, then making a move.

What algorithms are appropriate for selecting a move, in a game with randomness?

I understand that one approach is to think of this as a three-player game: in addition to the two players, there is a third player (the dealer) who makes a random move. For instance, if the two players are Minnie and Maxwell, we might alternate moves in the following order: Dealer (chooses a random card for Minnie), Minnie (selects a move), Dealer (chooses a random card for Maxwell), Maxwell (selects a move), and so on. I think I've read that alpha-beta search can be adapted to this setting. However, this doesn't sound too promising to me. There are perhaps 52 possible outcomes of the moves by Dealer, so the tree will be very bushy (with a large branching factor), causing exponential blowup. Also, this sort of modified alpha-beta search feels a bit inefficient to me. Each move likely affects a player's score by only a little bit at a time, so we'd expect that the effects of the randomness to average out over many moves, and there is no need to explore all combinations of possible random outcomes. To put it another way: the game is more about positional elements and random luck than about tactical/combinatorial elements.

Is there a better algorithm framework for randomized games, that takes into account the stochastic element? (Bonus points if you can suggest something that takes advantage of the fact the strength of a position changes only slowly over many moves.)

# Answer
> 3 votes
From your explanation I assume that the game is not episodic, but sequential: each move outcome is dependent on the previous moves.

The Minimax algorithm modification you explained is called Expectimax and is generally a standard approach for such problems as far as I know. In order to avoid the big branching factor you can try some variation of the Monte Carlo algorithm. This way you will be able to explore deeper the game tree and still take into consideration the randomness.

---
Tags: algorithms, artificial-intelligence, board-games, computer-games
---


# Question
Title: Theoretical foundations of robust and distributed services
I have the notion of a social network which is robust against malicious attacks from the outside. My vision is a system that is structurally built up as a distributed network of equal servers that operate on the same data and offer the identical services. Users should all interact on the same network, independent of the respective server they communicate with. The idea is to prevent (at least theoretically) every opportunity to bring the whole system down and to achieve a total failure of the whole service. Obviously the design of such a system is not trivial because of proper synchronization mechanisms. On the other hand there is the challenge to convey the participants to the appropriate servers. Hope you got my idea roughly.

The thing is that I only have a vague notion how such a system can function, and furthermore have seemingly successful passed over the relevant lectures about distributed systems in my cs studies. I'm therefore a little bit in a lack of an overview of relevant literature, scientific papers describing theoretical models and also real world examples.

Can anyone help me out with references, links and helpful explanations?

# Answer
You might be interested in these papers:
> 5 votes

# Answer
To me, what you are looking for is the "replicated state machine" approach, which is a general method for implementing a fault-tolerant service by replicating servers and coordinating client interactions with server replicas.

You can first check the wiki: State machine replication and the survey paper Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial.

For further reading, you may need to learn distributed consensus algorithm, especially the Paxos algorithm (for example, Paxos Made Simple).
> 0 votes

---
Tags: distributed-systems
---


title: Division by a constant

text:
# Question
Title: Division by a constant
After skimming Multiplication by a Constant is Sublinear (PDF), (slides (PDF), slides with notes (PDF)) I was wondering if this could be extended to division by a constant in sublinear time?

Additionally, what about division with a constant numerator, ie. "division of a constant"?

# Answer
Division by a constant can always be recast as multiplication by a constant followed by a shift. The relevant papers are:

Robert Alverson, "Integer Division Using Reciprocals," *IEEE Int'l Symp Comp Arithmetic*, (ISCA-10):186-190, 1991.

Torbjörn Granlund and Peter L. Montgomery, "Division by Invariant Integers using Multiplication," *ACM Conf on Prog Lang Dsgn and Impl*, (PLDI-1994):61-72.

Daniel J. Magenheimer, Liz Peters, Karl W. Peters, and Dan Zuras, "Integer Multiplication and Division on the HP Precision Architecture," *IEEE T. Comp.*, 37(8):980-990, August 1988.
> 8 votes

---
Tags: algorithms, reference-request, integers
---


# Question
Title: Notation for average case complexity of an algorithm
I'm just wondering what the correct notation is when referring to an average case complexity of an algorithm that was calculated by doing empirical analysis.

For example, I have tested my algorithm and fitted the results to the curve $f(n)=2.65\times 10^{-15}\cdot(2.17^{n})$ and in my report right now I'm saying something like:

> *the average case complexity was found to be $\approx 2.65\times 10^{-15}\cdot(2.17^{n})$*,

but I would rather say something like

> *the average case complexity is $\in \Theta(2.17^{n})$*.

But I'm not sure if this is technically correct because the result hasn't been theoretically proven, only empirically tested and fitted to the curve.

# Answer
The notation $\Theta(f(n))$ isn't reserved for worst-case complexity, it's asymptotic notation applicable to functions in general. So you can state that the average case complexity is $\Theta(2.17^n)$, and it means exactly what you think it does. (Regardless of whether this has been proved or not.)
> 2 votes

---
Tags: asymptotics, notation
---


# Question
Title: $P$-complete problems and Logspace reductions
It is known that HORN-3SAT is complete for $P$ under Logspace many-one reductions ($\<\_L^m$).

This implies that $\bar{A} \<\_L^m A$ for any $P$-complete problem $A$, where $\bar{A}$ means the complement of $A$. This immediately follows from that fact that $P$ is closed under complement and the $P$-hardness of $A$.

My question is to find such Logspace many-one reduction $\bar{A} \<\_L^m A$ for any $P$-complete problem $A$ (such as HORN-3SAT). The reduction must show the mapping between short certificates of $A$ and $\bar{A}$.

EDIT: As David stated in his comment on the case of HORN-3SAT problem, we know that Logspace function exists but it seems that it is hard to find explicitly.

# Answer
The circuit value problem: input is a Boolean formula and a truth assignment to its variables; accept if, and only if, the input is well-formed and the formula evaluates to true under the given assignment. The complement is to accept iff the input is malformed or the formula is false.

The reduction is to check that the input is well-formed. If so, output the negation of the formula, with the same truth assignment; if not, output either $X; X=\mathrm{t}$ or $X; X=\mathrm{f}$, depending on which way you're going.
> 5 votes

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


# Question
Title: Would it be possible that the intersection of two non-context-free languages is context-free?
Assume two languages $L\_1$ and $L\_2$, both of which are non-context-free.

Let $L = L\_1 \cap L\_2$. Could $L$ be context-free?

# Answer
> 6 votes
The intersection could be empty.

---
Tags: context-free
---


# Question
Title: How to show that a non-empty $L$ is recognizable iff there exists a total computable function whose range equals $L$
This almost makes sense to me, but I feel like I'm missing something.

I know that for a decidable language, there must exist some total computable function $f$ that can take in any $x \in \sum^{\*}$ and tell us whether or not $x$ is accepted (while my textbook is unclear, I would infer from this that decidable languages and computable functions are equivalent?)

So I can see that $L$ is decidable if and only if some computable function can determine if $x \in L$ or not, which implies the existence of a function $f(x)$ that outputs $x$ if $x \in L$, and nothing otherwise (this makes sense in my head at least...correct me if I'm wrong). How would I use what's given to show that this is true for any recognizable $L$ though? Computable functions have finite steps have to halt, from my understanding, so how that they be used to check if $x$ belongs to a recognizable but undecidable language?

# Answer
Hints:

1. If $L$ is recognized by some Turing machine $T$, then consider a Turing machine that on input $(x,n)$, runs $T$ on $x$ for $n$ steps and outputs $x$ if $T$ halts within $n$ steps.
2. If $L$ is enumerated by some Turing machine $T$, then given $x$, accept it if it appears in the list generated by $T$.
> 2 votes

---
Tags: formal-languages
---


# Question
Title: If A is reducible to its complement, is the converse true as well?
I was reading a proof that said that if $A \le\_{m} \bar{A}$, then it can be inferred that $\bar{A} \le\_{m} A$ as well. Is this a logical conclusion, and if so, why? I didn't think this followed with languages A and B, but if B is A's complement, can one make such a statement?

# Answer
> 6 votes
In general whenever $A\le\_m B$ via computable function $f$, we automatically have $\bar{A}\le\_m \bar{B}$ via the same $f$. The reason is that $x\in A\iff f(x) \in B$ implies that $x \in \bar{A} \iff f(x) \in \bar{B}$.

# Answer
> 1 votes
Yes, you can even use the same reduction. Recall that $A \leq\_{m} B$ if we can take in instance $I\_{A}$ of $A$ and produce an instance $I\_{B}$ of $B$ such that $I\_{A}$ is a Yes-instance of $A$ *if and only if* $I\_{B}$ is a Yes-instance of $B$ (or equivalently $I\_{A} \in A \Leftrightarrow I\_{B} \in B$ if you prefer).

The key thing to note when we take the two languages to be $A$ and $\bar{A}$ is that the Yes-instances of $A$ are precisely the No-instances of $\bar{A}$ and vice versa.

So if we have this reduction $A \leq\_{m} \bar{A}$, then any Yes-instance of $A$ gets mapped to a Yes-instance of $\bar{A}$ *which is also No-instance of $A$*. Say then we take a Yes-instance of $\bar{A}$ - *this is a No-instance of $A$* \- the reduction maps it to a No-instance of $\bar{A}$ - *which is a Yes-instance of $A$*.

Thus the reduction maps all the Yes-instances of $\bar{A}$ to Yes-instances of $A$ (because they're also No-to-No for $A$-to-$\bar{A}$). If that's clear, then it should be obvious that the No-instances are taken care of in the same way.

To write it as language membership, we have a reduction $f$ that gives $I \in A \leftrightarrow f(I) \in \bar{A}$ which is the same as $I \notin A \leftrightarrow f(I) \notin \bar{A}$. Then as $X \in A \leftrightarrow X \notin \bar{A}$ (equiv. $X \in \bar{A} \leftrightarrow X \notin A$), we get $I\in\bar{A} \leftrightarrow f(I) \in A$.

---
Tags: formal-languages
---


# Question
Title: Finding number of numbers dividing n^m exactly p times
Suppose I am given a number $n$ (less than $10^8$) and $m$ (less than $10^7$) and $p$ (less than $10^4$), I have to write a program to find number of numbers that divide $n^m$ exactly $p$ times.

Mathematically, I have to find number of distinct $x$ such that $$ n^m \equiv 0 \mod x^p \qquad\text{and}\qquad n^m \ne 0 \mod x^{p+1} $$

(From UVa Online Judge)

What approach could be better than brute force?

# Answer
Start by factoring $n$ (you can use a table of all primes of size at most $1e4$). Now you can write $n^m = \prod\_i p\_i^{c\_i}$. Now come up with a criterion for $x = \prod p\_i^{a\_i}$ to divide $n^m$ exactly $p$ times, and use this criterion to answer your question.
> 2 votes

---
Tags: algorithms, number-theory, arithmetic, mathematical-programming
---


# Question
Title: Shortest path that passes through specific node(s)
I am trying to find an efficient solution to my problem. Let's assume that I have positive weighted graph `G` containing 100 nodes(each node is numbered) and it is an acyclic graph. So there cannot be any edge like 2,2 or 2,1. I have got a list of nodes let's say 10 from graph `G`. Let's say each of these nodes are also in an array. I am looking for a way to find the shortest path's total weight from node 1 to 100 that passes through at least some particular(let's say 5) of those nodes from that list.

To simplify it, consider graph with 6 nodes, 0...5, now node 1 and 4 are marked as points where we could specify to pass. Let's say existing paths are 0-1-2-5, 0-3-4-5, and 1-4. Now let's say all edges are weighted as 5 except 3 to 4 is weighted as 1. If we run a shortest path algorithm this would basically find the path 0-3-4-5 as it is weighted 11. However if we run an algorithm specifying minimum amount of specified points and try the amount 2. Then the algorithm should be running on 0-1-4-5 which is weighted as 15.

I have written this way

```
    shortestPath(destinationNode, minAmount)

        if(destinationNode == srcNode && minAmount < 1)
            return 0

        else if(destinationNode == srcNode && minAmount > 1)
            return INFINITY

        int destNo = destinationNode get number
        int cost = INFINITY
        for (int i = 0; i < destNo; i++)
            if (d[i][destNo] != null)
                int minimumAmountCount = minAmount;
                for (int j = 0; j < marked.length(); j++)
                    if (marked[j] == i)
                        minimumAmountCount = minimumAmountCount - 1;

                cost = MIN(cost, shortestPath(Node(i), minimumAmountCount);

        return cost;

```

Basically we call this algorithm by using the our destination node and minimum amount of nodes from that list. Firstly we want to make sure that this is a recursive function and it should have a stopping point, which would be when passed destination is equal to source node(which is essentially node #0). The second case we need to check is whether we visited enough amount, so if it is less than 1(0 or negative number) then we visited enough points and return 0 as distance from node #0 to node #0 would be 0. If we did not visit enough amount then we return infinity so that algorithm would consider other paths.

So in order for the returning part to work, we have to define the destination node's number(if we consider that we have 100 nodes it would be node #99 at the initial start) and initialise cost as infinity.

Then we run a for loop that starts from 0(essentially node #0) till our current node number, this is because there are no backwards edges on the graph. By using node number we check from the matrix whether there is an existing weight for those nodes. If it exist then we initialise a variable for our current minimum amount and then run a loop and check if source to the current destination is in the list of marked nodes. If it is marked then we simply decrement the minimum amount.

For the final step we run the function again by changing destination as the current source and with the current minimum amount.

But it seems very expensive, considering the fact that the worst case complexity of nested loop takes O(|Node|^2) and total recurrence would take O(|Node|^2 * |Edges|). So is there any other efficient solution for this problem?

# Answer
Compute the shortest path between all pairs of the twelve special nodes (nodes 1, 100, and all ten of your particular nodes), and use these as edge lengths in a new graph consisting only of these twelve nodes. Now, you have a graph containing twelve nodes, and you want to find the shortest path from 1 to 100 that uses at least five other nodes. Now, you can use your algorithm (which I think is just dynamic programming) on this graph, which is much smaller. The solution on the new graph will give a solution for the original graph, which you can find by replacing the edges in the solution in the new graph with the shortest paths you computed in the first step.

For your example, we will have 4 nodes in the new graph. The edge lengths in the new graph are: 0-1:5, 0-4:6, 0-5:11, 1-4:5, 1-5:10, 4-5:5. These correspond to the shortest paths between nodes $i$ and $j$ in the original graph. The shortest path including one node from the list is 0-4-5, which has length 11. Now, replacing each edge in this path with the path computed in the first step gives the path 0-3-4-5 in the original graph.
> 2 votes

# Answer
If all you have is 100 nodes, and your arcs are given or easy to compute: don't worry about it.

If not: your graph is probably very sparse (many more pairs of nodes with arcs than without arcs). So use linked lists or some other data structure that allows you to iterate over just arcs, not having to skip non-arcs. The names of such data structures are language dependent; various types of Java or C# Lists or Dictionaries quality, as do e.g. hashes in Perl or associative arrays in PHP.

I'd use them to build a mapping from nodes to forward arcs (i.e. pairs of cost and destination node), and another from nodes to backward arcs.

I'd allocate two more to hold the node-to-node distances from each node to each intermediate node, and from each intermediate node to each node, and compute them using the standard algorithm (Floyd's, also known as Dijkstra's, or, erroneously, Warshall's).

I'd allocate one more to hold the final node-to-node distances, and compute them as $$d(x,y) = min\_{z \in I}(d(x,z) + d(z,y))$$ for the intermediate nodes $I$.
> 0 votes

---
Tags: graphs, shortest-path, weighted-graphs
---


# Question
Title: How to prove the structured program theorem?
Wikipedia:

> The structured program theorem \[...\] states that \[...\] any algorithm can be expressed using only three control structures. They are
>
> * Executing one subprogram, and then another subprogram (sequence)
> * Executing one of two subprograms according to the value of a boolean expression (selection)
> * Executing a subprogram until a boolean expression is true (iteration)

This theorem is developed in the following papers:

* C. Böhm, "On a family of Turing machines and the related programming language", ICC Bull., 3, 185–194, July 1964.
* C. Böhm, G. Jacopini, "Flow diagrams, Turing Machines and Languages with only Two Formation Rules", Comm. of the ACM, 9(5): 366–371,1966.

Unfortunately, the first one is practically unavailable, and the second one, in addition to being a bit cryptic (at least for me), refers to the first, so I have problems to understand the proof. Can anyone help me? Is there a modern paper or book which presents the proof? Thanks.

---

**UPDATE**

To be exact, I would like to understand the *second part of the CACM paper* (section 3). The authors write in section 1 the following:

> In the second part of the paper (by C. Böhm), some results of a previous paper are reported \[8\] and the results of the first part of this paper are then used to prove that every Turing machine is reducible into, or in a determined sense is equivalent to, a program written in a language which admits as formation rules only composition and iteration.

Here \[8\] refers to the unavailable ICC Bulletin paper. It is easy to see that the above quote from Wikipedia refers to this second part of the CACM paper (the Turing machine serves as a precise definition of algorithms; "composition" means sequence; an iteration can replace a selection).

# Answer
> 14 votes
The Böhm-Jacopini theorem essentially says that a program based on 'goto' is functionality equivalent to one consisting of 'while' and 'if'.

Sketch of proof based on the following lecture notes:

Say you have a program that consists of a sequence of statements $S\_i$; prefix each statement with a label $S\_i^{\prime} \gets L\_i: S\_i$ and update existing goto statements to point to the right locations. Declare a location variable, $l \gets 1$, and wrap the prefixed statements in a while loop that will continue until the last statement is reached, $\textbf{while} (l \neq M) \ \textbf{do} \ S^{\prime}$.

Apply the following rewrite rules to $S^{\prime}$:

* Goto rule: Replace $L\_i \ \textbf{goto} \ L\_j$ with $\textbf{if} \ (l = i) \ \textbf{then} \ l \gets j$
* If-goto rule: Replace $L\_i : \textbf{if} \ \text{(cond)} \ \textbf{then} \ \textbf{goto} \ L\_j$ with $\textbf{if} \ (l = i \land \text{(cond)}) \ \textbf{then} \ l \gets j \ \textbf{else} \ l \gets l + 1$
* Otherwise rule: Replace $L\_i : S\_i$ with $\textbf{if} \ l = i \ \textbf{then} \ S\_i, \quad l \gets l + 1$

The resulting program is then free of goto statements showing the correspondence between the two paradigms.

A more formal proof is provided in your second reference.

**Update**

After studying the paper in greater detail, this is my interpretation:

Based on the definitions in CACM, let $\mathcal{B}^{\prime} = \mathcal{D}(\alpha, \lbrace \lambda, R \rbrace)$ be the class of Turing machines represented by the language $\mathcal{P}^{\prime}$ that covers flow diagrams. Let $\mathcal{B}^{\prime \prime} = \mathcal{E}(\alpha, \lbrace \lambda, R \rbrace)$ be the class of Turing machines represented by the language $\mathcal{P}^{\prime \prime}$ that covers the transformation covered above.

According to CACM, the author wants to prove that if a Turing machine exists in the family of Turing machines described by $M \in \mathcal{B}^{\prime}$, then there exists a corresponding Turing machine in the family of Turing machines described by $M^{\*} \in \mathcal{B}^{\prime \prime}$.

Sketch of the author's proof: He does this by drawing from the derived relationship $M \in \mathcal{B}^{\prime}$ and $M \in \mathcal{E}(\cdots)$ (definition (5)) and then sets up the relationship $M^{\*} \in \mathcal{E}^{\*}(\cdots)$. For each component of $\mathcal{E}(\cdots)$ he draws a one-to-one mapping with those of $\mathcal{E}^\*(\cdots)$. Thus by establishing the bridge between $M$ and $M^{\*}$ through $\mathcal{E}(\cdots)$ the author proves $M \in \mathcal{B}^{\prime} \implies M^{\*} \in \mathcal{B}^{\prime\prime}$.

---
Tags: computability, programming-languages, computation-models
---


title: Recurrence Equation Question

text:
# Question
Title: Recurrence Equation Question
I have some difficulty trying to tell which equation to use when I'm given an explanation on how an algorithm operates. Especially divide and conquer.

Normally I see these kind of equations:

```
C(n) = aC(n/a) + b where a and b are constants

```

Other times I don't see the a in front of C(n/a) as an answer. That really confuses me.

Can you tell me when I will need to use which?

Thanks!

# Answer
We can't tell you when you need to use which, since it depends on the algorithm. If the algorithm makes $a$ recursive calls to subproblems of size $n/a$, then you will see the $a$ in front. If it makes only one recursive call, then you won't see it. You need to understand what the algorithm is doing. That said, you will tend to see the $a$ in front when you are applying some operation that updates the entire list, and not see it in front when you're trying to focus on some specific element. There could also be other values other than $1,a$ in front.
> 2 votes

# Answer
To use any formula, you need to think about what it means. You can't just blindly apply formulas.

$C(n) = aC(n/b) + c$ (and, yes, I've changed the constants) means that the cost of running the algorithm on an input of size $n$ is $a$ times the cost of running it on an input of size $n/b$, plus some constant overhead $c$. A typical case of that would be an algorithm that chops its input into $b$ equally sized parts and makes recursive calls on $a$ of those parts. Normally, you'd have $a=b$ (e.g., split the input into three and recurse on each part), which is why the formula you quoted has just two constants. But you could imagine some sort of average-case analysis where you split into some number of parts and, on average, only need to look at half of them.
> 3 votes

---
Tags: algorithms, recurrence-relation
---


# Question
Title: why does ${a^nb^n}$ fit the pumping lemma for context-free languages?
I am writing somthing about Ppumping Lemma. I know that the language $L = \\{ a^nb^n| n ≥ 0 \\}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma (for context-free languages) ?

if we pick the string $s = a^pb^p, |s| \> p , |vxy| \< p \land |vy| \> 0$.

it seems it will be out of the language when we pump it (pump up or down) or there is something I'm missing.

Any explanation would help.

Edit: I am applying pumping lemma to a^nb^n and it fails to stay in the language for all cases. So, why is it Context free?

# Answer
This language satisfies the conditions of the pumping lemma. (By the way, your question title is wrong: you are not asking why it is context-free; you are asking why it satisfies the conditions of the lemma, which it does.)

Take the string $s=a^mb^m$ and assume $m\>0$. Don’t use $p$ or $n$; otherwise it is confusing, because those letters are used in the lemma. Now let $v=a$, $y=b$, $x=\epsilon$ (the empty string), $u=a^{m-1}$, and $z=b^{m-1}$.

You can definitely pump it as much as you want. In other words, you take a string such as $aaaaabbbbb$, then you pick the two middle letters: $aaaa\mathbf{ab}bbbb$. Then you pump them: $aaaa\mathbf{aaabbb}bbbb$ — still in the language.
> 3 votes

---
Tags: context-free, pumping-lemma
---


# Question
Title: A* to find the longest path in a directed cyclic graph
I have written an A\* algorithm to find the shortest path through a directed cyclic graph. I am trying to modify it to find the longest path through the same graph.

My attempt was to write it so that all I change is \[1\] the weights per edge (making them negative instead of positive) and \[2\] the heuristic function.

I seem to be having trouble getting it to do this. It is pretty good at finding the longest path sometimes, but it is not guaranteed.

It seems that the problem lies with \[2\] the heuristic -- for shortest path an L2 norm is a good optimistic way to get it to head towards the goal, but for longest path I want the heuristic to point it at paths that are further from the goal to continue to increase total length.

If I set the heuristic to return 0 so that it's a Dijkstra's search, it's less predictable as there's no incentive to search from nodes further away (using \[1\] negative weights per edge).

I think if I keep the weights positive and try to maximize the score instead of minimize it may work, but I was attempting to do this without changing the algorithm, only the edge weights and the heurstic.

I have found similar posts on stackExchange but they don't answer my specific questions:

Q1) Can this be done with A\*

Q2) Is setting the weights negative the right thing to do

Q3) Is the only way to do this is to set the heuristic to zero and keep the weights positive and try to maximize the score instead of minimize it?

# Answer
First of all, bear in mind that the Longest Path Problem (LPP) is a NP-complete problem whereas finding the Shortest Path Problem (SPP) is a problem known to be in P. The proof for the NP-completeness of LPP is trivial and consists of a reduction from the Hamiltonian Circuit (HC) problem which is already known to be NP-complete.

In other words, if you could find *a simple way* (in the sense of the modifications taking only polynomial time) to modify A\* to solve the LPP problem you would actually make a nice discovery! :)

This is not to say that A\* can not be used, but it should be expected to take longer. I recently co-authored a paper about the "Target Value Search Problem" with other two people. This problem is stated as follows:

Given a graph $G(V,E)$ and a natural number $T$ find the path between the vertices $s, t\in V$ whose cost (or length in case of unary costs) is as close as possible to the given target value $T$.

Obviously, if $T=+\infty$ then you are seeking the longest path between any arbitrary pair of vertices, $s, t$. If, in addition, $s=t$ then you are looking for the longest path that joins both vertices. You can verify in $O(1)$ whether the length equals the number of vertices. If so, you found a Hamiltonian path.

Regarding your questions:

* Q1: *Can this be done with $A^\*$?* Certainly yes (indeed, we modified A\* to get T\*, our implementation of the Target Value Search problem that can be used to solve this variant) but you should not expect for it to be as fast as when solving SPP. As a matter of fact, we provided a simple modification of A$^\*$ that can be used to solve the LPP as well (and it is certainly complete but terribly inefficient)
* Q2: *Is setting the weights negative the right thing to do?* Well, the real problem is that you need a heuristic function that returns an upper bound on the path to the goal $t$ instead of a lower bound (as when solving the SPP) and these sort of heuristics seem particularly hard to derive (how would you do it? there is no concept such as "*relaxation*" here, maybe you should constraint the problem further to derive a heuristic)
* Q3: *Is the only way to do this is to set the heuristic to zero and keep the weights positive and try to maximize the score instead of minimize it?* Well, you can do it but that is just a brute-force approach. Note that this approach forces you to consider all paths. Even if you find a path which seems to be too large you are still forced to expand other nodes in OPEN until you CLOSE them all. In the absence of a heuristic that is all you can do. This is, indeed, what our variant of A\* for the Target Value Search problem does if $T=+\infty$ ---however $T^\*$ is more efficient even to solve LPP.

Hope this helps,
> 5 votes

---
Tags: graphs, shortest-path, weighted-graphs
---


# Question
Title: Balancing subproblems in resilience testing
You’re doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with $n$ rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung. It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung $n/4$ or $3n/4$ depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer.

If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single jar—at the moment it breaks, you have the correct answer—but you may have to drop it $n$ times (rather than $\log n$ as in the binary search solution).

So here is the trade-off: it seems you can perform fewer drops if you’re willing to break more jars. To understand better how this trade- off works at a quantitative level, let’s consider how to run this experiment given a fixed “budget” of $k \ge 1$ jars. In other words, you have to determine the correct answer—the highest safe rung—and can use at most $k$ jars in doing so.

Suppose you are given a budget of $k = 2$ jars. Describe a strategy for finding the highest safe rung that requires you to drop a jar at most $f (n)$ times, for some function $f (n)$ that grows slower than linearly. (In other words, it should be the case that $\lim\_{n\to\infty} f (n)/n = 0$.)

Anyone any insights how to solve this problem?

I know that the answer is $h = \sqrt n$. I know that it solves the problem. But I want to know how you got that answer, there must be a general way to do it?

# Answer
> 2 votes
Drop the first jar at the $\sqrt{n}$th rung, $2\sqrt{n}$th rung, and so on until it breaks at the $m\sqrt{n}$th rung. (This takes at most $\sqrt{n}$ steps). Then drop the second jar at every rung between the $(m-1)\sqrt{n}$th rung and the $m\sqrt{n}$th rung until you find the precise breakpoint.

# Answer
> -1 votes
for k equal to 2 first drop the jar from the second rung if it breaks the safe rung is 1st rung else then drop it from 5th rung if it breaks then the safe rung lies below it and come one rung down and drop another jar if it breaks again then the safe rung is the below one else this is the safe rung you can repeat this process again and again till u find the safe rung with the help of this stratergy at the expense of k equal to 2 rungs we will find the maximum safe rung with higher efficiency

---
Tags: algorithms, binary-trees, decision-problem, divide-and-conquer
---


# Question
Title: How can you bound the error of an approximation without knowing the optimal solution?
I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length it is supposed to be?

# Answer
> 8 votes
In general when you want to bound the approximation ratio of an algorithm you look for an easy lower bound on the optimal value. The most straightforward is often the LP relaxation of a (suitably chosen) ILP formulation of the problem. Sometimes other things are used, for TSP for example you can also use the weight of a MST (the optimal tour minus one edge is a tree, so it can't weigh less than the MST).

For particular instances you can of course still use the thing you use in your proofs, i.e. you can solve the LP and compare your heuristic solution to the LP value. If you have more CPU time on your hands you can also start a branch-and-bound process to solve the ILP. Even if you don't solve the ILP completely, you get better lower bounds from LP duality.

---
Tags: complexity-theory, approximation
---


# Question
Title: Context Free Grammar for $\{0^n1^n \mid n \geq 0\}^*$
> Give a context free grammar for the following language over $\Sigma = \\{0,1\\}$:
> $ L = L\_1^\* $ where $ L\_1 = \\{0^n1^n : n \geq 0\\}$.

Not really sure where to start with this one. Any help is appreciated

# Answer
Hints:

1. Start with a context-free grammar for $L\_1$.
2. Modify it to a context-free grammar for $L = L\_1^\*$. There is a simple transformation which works for *any* context-free language $L\_1$ and *any* context-free grammar generating it.
> 5 votes

# Answer
As others have pointed out, the first step is to get $L\_1$. After that, constructing $L$ is straightforward. You've already given a correct grammar for $L\_1$: $S \rightarrow 01 \mid 0S1 \mid \epsilon$. Of course, you could simplify this grammar a bit: $S \rightarrow \epsilon \mid 0S1$. However, the grammar you give is perfectly fine.

Now, $L\_1^\*$ means any number of strings from $L\_1$ concatenated together. From the grammar we already have, the nonterminal symbol $S$ can derive all strings in $L\_1$. So, we need a grammar capable of generating $S^\* = \epsilon$, $S$, $SS$, ..., $S^n$, ... Try to show that the grammar $S' \rightarrow \epsilon \mid SS'$ works.

Once you show (a) that your grammar works, and (b) the grammar in the second paragraph generates $S^\*$, you should be able to put these grammars together to form a single grammar with two nonterminal symbols ($S$ and $S'$) which generates $L$.
> 2 votes

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


# Question
Title: Borrowing bioinformatic methods in other fields
Have the bioinformatic methods like sequence analysis, genome annotation, comparative genomics (and many others), been applied to solve problems outside the field of bioinformatics?

# Answer
Of course! The perfect example is Gusfield book. Many of string algorithms came from bioinformatics. For example, sequence analysis algorithms are used in text editors.

PS: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Dan Gusfield
> 5 votes

---
Tags: bioinformatics
---


title: Shannon's entropy for an image

text:
# Question
Title: Shannon's entropy for an image
Shannon's entropy \[plog(1/p)\] for an image is a probabilistic method for comparing two pixels or a group of pixels.Suppose an image with a matrix of 3x3 has pixel intensity values

```
1 1 2
2 3 3
4 4 5

```

and another image with 3x3 matrix has group of pixels having intensity values

```
5 5 6
6 7 7
8 8 9

```

Then shannon's entropy for the images would be the same.So in this case the entropy values would point out that the images are same though in actual they are different.So image matching using this technique doesn't help.On basis of supervised classification where I classify an image based on trained databases of shannon's entropy ,we use the concept of entropy to find similarity between two images.Is there any method or research paper where this entropy can be used or modified for image matching for the above case..?

# Answer
> 5 votes
Shannon's entropy works as a hashing or fingerprinting function here; they are not injective which means we have to be careful not to interpret too much into relations of values.

If $H(I\_1) \neq H(I\_2)$, then images $I\_1$ and $I\_2$ are certainly not the same.

If $H(I\_1) = H(I\_2)$ (or even $H(I\_1) \approx H(I\_2)$), however, we know nothing. The images might be similar, but the values can also be close because of non-injectivity.

We would like to have some smoothness, that is that two images are more different if $|H(I\_1) - H(I\_2)|$ is larger. Whether this is the case is certainly a quality criterion of such fingerprinting functions. Given your example, it does not seem as if entropy was a good fingerprint in this sense.

It would be confusing if any kind of entropy would be. Any rectangle of one color holds no information (entropy zero), yet two rectangles of different colors are as different as two images get.

# Answer
> 2 votes
I think this an awesome idea. But you won't be able to use it for image matching anymore than you can hope that one image of "white noise" will match another. But it's a great idea for finding similar *categories* of images.

# Answer
> 2 votes
One related approach would be to compute a histogram of the pixel intensities for each of the two images, then compare those two histograms. More typically, we'd compute a histogram of some measure of color (e.g., the hue), instead of pixel intensities. This is a crude measure that can sometimes nonetheless be helpful: e.g., for distinguishing a picture of one room from a picture of another (e.g., if their walls are painted different colors, or they have a different distribution of colors).

There are many ways to compare two histograms. You can think of each histogram as a distribution for some random variable, and then compare the two distributions using of a number of methods. For instance, you could compare them using KL-divergence. Another approach is to use any standard distance measure on vector spaces, e.g., the ${\cal L}\_2$ measure (sum of squared differences). You'll often want to bin the values first, before computing the histogram.

See also

---
Tags: pattern-recognition, image-processing, entropy, computer-vision
---


# Question
Title: SVM optimization objective: why are we maximizing $\frac{1}{\|w\|}$?
I'm learning about Support Vector Machines(SVM). I understood that their objective is to maximize the margin between the decision line and the closest point to it. For simplicity, let's assume we have a linear SVM and linearly separable data X. We would like to find the maximum distance D and vector W, such that

$\dfrac{W^T \cdot X\_i+W\_0}{\\|W\\|}\geq D$ for all $X\_i$ in the first class

$\dfrac{W^T \cdot X\_i+W\_0}{\\|W\\|}\leq-D$ for all $X\_i$ in the second class.

Why is the problem equivalent to maximizing $\frac{1}{\\|W\\|}$, given the following constraints are satisfied:

$W^T\cdot X\_i+W\_0\geq1$ for all $X\_i$ in the first class

$W^T\cdot X\_i+W\_0\leq-1$ for all $X\_i$ in the second class.

I'm more interested in a formal proof than in the intuition.

# Answer
Let's slightly rewrite the condition you give: the quantity $$ \frac{W^T \cdot X\_i + W\_0}{\\|W\\|} \mp D $$ is non-negative for $X\_i$ in the first class (with $-D$), non-positive for $X\_i$ in the second class (with $+D$). Now suppose $\lambda \> 0$. Then the quantity $$ \frac{(\lambda W)^T \cdot X\_i + (\lambda W\_0)}{\\|\lambda W\\|} \mp \lambda D $$ satisfies the same properties as before; in fact the two sets of inequalities are equivalent. Therefore we can assume without loss of generality that $\\|W\\| = 1$ (choose $\lambda = 1/\\|W\\|$), and so the quantity in question becomes $$ W^T \cdot X\_i + W\_0 \mp D, $$ where we are promised that $\\|W\\| = 1$. Now divide everything by $D$ to get another quantity satisfying the same properties: $$ (D^{-1}W)^T \cdot X\_i + (D^{-1}W\_0) \mp 1. $$ Maximizing $D$ is the same as minimizing $D^{-1} = \\| D^{-1} W \\|$, which is the same as maximizing $1/\\|D^{-1} W \\|$. Now imagine that instead of $W,W\_0$, you were optimizing over $W'=D^{-1}W,W'\_0=D^{-1}W\_0$; for each choice of $W',W'\_0$ you can recover $D = 1/\\|W'\\|$ and so $W,W\_0$, which shows that both problems are equivalent. In these terms, you want the following quantity to satisfy the required properties: $$ W'^T \cdot X\_i + W'\_0 \mp 1. $$ Under these conditions, you want to maximize $1/\\|W'\\|$.
> 7 votes

---
Tags: machine-learning
---


# Question
Title: How to prove that context sensitive languages are closed under intersection and complement?
This is a question from the exam of our "Automata and Formal Languages" course. There is a question where asked to prove or disprove that any "relative complement" operation between two context sensitive languages will also produce a context sensitive language.

From the context sensitive closure properties Wikipedia, and princeton.edu. I know that those languages are closed under intersection and complement.

I have spent too much time on finding the formal prove of those statements. Where / How can I find the proofs? Or how to prove them by myself? Can anyone point me to a reference ? Can any one post here the proofs ?

# Answer
The first closure property, closure under intersection, is a DIY proof if you choose the right model for the context-sensitive languages. By defining them with the help of linear-bounded automata you can run two of these automata successively to test (nondeterministically) for acceptance of the intersection.

Second, closure under complement, is hard! It used to be a famous open problem until solved independently by Immerman and Szelepcsényi. It is quite a surprising proof, how to prove complement for a nondeterministic automaton. The technique is called *inductive counting* and works for larger families of complexity classes: NSPACE($s(n)$)=co-NSPACE($s(n)$), where context-sensitive equals linear nondeterministic space.
> 11 votes

---
Tags: formal-languages, closure-properties, context-sensitive
---


# Question
Title: Distinguish Decision Procedure vs SMT solver vs Theorem prover vs Constraint solver
Those terminologies confuse me. As I understand

* SAT solver: decide the satisfiability of propositional logic (using DPLL or Local Search).
* Decision procedure is a procedure to decide the satisfiability of a certain decidable first-order theory.
* SMT solver is a SAT solver + decision procedure.
* Theorem prover indicates something like Dynamic Logic, e.g. the KeY tool
* Constraint solver: I don't know.

But I see people calling Z3 a theorem prover. So I don't know how to dishtinguish those terms. And what is the most general term for all of them? Thank you.

# Answer
> SMT solver is a SAT solver + decision procedure

A SAT solver is a solver for a decision problem: the SAT problem is a decision problem. Additionally, this decision problem is "self-reducible":

> The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment
>
> — (wikipedia)

This means that SAT solvers can also give the satisfying assignment, in addition to deciding the problem.

**TL;DR SMT solvers solve a generalization of the SAT problem, depending on the types/constraints allowed in the theory. Furthermore, they also allow encoding of higher level type-relationships than the SAT encodings allow.**

A SAT solver usually deals with many single boolean variables, that are related only through the clauses/constraints of the CNF. A QF\_BV (quantifier-free bitvector) theory SMT solver is basically a SAT solver + more information about the relationships. For example, a QF\_BV SMT solver is reducible to SAT1. So why use a QF\_BF SMT solver? The the major advantage is that in SAT, an integer is represented by different variables, that at first glance might appear unrelated. A SAT solver would spend much time relearning simple relationships, like $(A = B) \wedge (B = C) \implies (A = C)$ **on an integer level**, while the SMT solver knows that the individual bits are related this way from the outset, because the QF\_BV SMT language is on an integer level (fixed bit-width). Thus a QF\_BV SMT solver can reason on the integer level, in addition to the bit level.

1. See Beaver SMT solver which can even output the equivalent SAT problem that would need to be solved.

While the QF\_BV SMT solver has this advantage over a SAT solver, I don't think this is a complexity advantage: they both essentially equivalent and take exponential time to solve their worst-case problems. But practically, a QF\_BV SMT solver might be much quicker due to this extra knowledge. See my answer to Limits of SMT solvers, for an example of something considered "hard" that (current) QF\_BV SMT solvers and SAT solvers would both choke on.

There are also SMT solvers that try to solve even tougher problems than Boolean Satisfiability (for example allowing types and constraints on reals, or allowing quantifiers); obviously these are theoretically at least as slow as a SAT solver. These SMT solvers are a solving a generalization of the SAT problem; instead of using binary variables, each "theory" allows relationships/constraints over different domains, such as reals, or quantified (for-all) constraints.

> Theorem prover

A *automated theorem prover* is a solver that given some sort of proof system, some assumptions, and a goal to prove, will "fill in the gaps" between the assumptions and the goal. It will also have some sort of verifier to check proofs (which runs quickly). A theorem prover can rely on a SAT solver to fill in the blanks; in fact, if $P=NP$ and there is a practical algorithm to solve NP-complete problems, one can potentially prove almost all useful provable things (in reasonable time):

> But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. According to Stephen Cook, \[19\]
>
> > ...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.
>
> — (wikipedia)
>
> \[19\]: Cook, Stephen (April 2000). The P versus NP Problem. Clay Mathematics Institute (PDF).

The reason this would work is because "formal proofs can easily be recognized in polynomial time" via the verifier, and $P=NP$ would imply that that problems that can be verified in polynomial time can be answered in polynomial time as well.

But for now, automated theorem mostly provers use heuristics or exponential time algorithms (but are still helpful).

> Constraint solver

These are usually reformulations of the SAT/SMT solvers into other languages. If you've ever use any SAT/SMT solvers to solve a problem, you can really get to love the non-deterministic ability of the solvers. That is, instead of telling the computer *how* to do something, you tell it *what you want*, ie. what properties you want the output to have, and a SAT/SMT solver will in a non-deterministic "fill it in", without bothering you with the implementation details. This sort of programming paradigm is very appealing, and is called *constraint programming*, and to run, it must use a constraint solver (which might use a SAT/SMT solver in the backend, depending on the types and constraints it allows you to use).

> But I see people calling Z3 a theorem prover. So I don't know how to dishtinguish those terms.

AFAIK, Z3 is a suite of many tools, including a SMT solver, several theorem proving/model checking languages, and more.

> And what is the most general term for all of them?

I think the generalization of the satisfiability problem is Satisfiability Modulo Theories, and so "SMT solver" would be the most general of all of these. However, not all actual SMT solver implementations solve all the theories, so this doesn't mean that all SMT solvers are equally general.
> 22 votes

---
Tags: algorithms, terminology, reference-request, decision-problem
---


# Question
Title: Distribution algorithm according to weighted parameters (with a min-max constraint)
I'm trying to solve the following problem related to distribution-

I have a list L of items (I1, I2,....In) sorted in order of importance, I1 being the most important. Each item has multiple tags assigned to it and the combination of these tags can be different on each item, so I1 may have tags T1 and T2, I2 can have tags t2, t3 and t4, and I3 can have tag T1, and so on.

Now, I have to make batches from this list L, with a distribution of items (according to the tags) subject to the following constraints-

Each batch has a fixed size B Each tag has a range of items in the batch distribution, ranging from a minimum to maximum. So, B should contain minimum x1 items with tag t1, x2 items with tag t2, and maximum y1 items of t1, y2 items of t2 and so on. We start picking items from the top of L and keep filling the batch until we reach the final distribution that satisfies the constraints. If, say, L has 300 items, and we have to make a batch size of 50, we can go until any number of items in the list and pick the items to make the desired distribution. Remember that if an item is picked from the list, count of all the tags assigned to it goes up by 1. I was thinking of a solution where in first, I make lists of items corresponding to each specific tag. I pick the minimum desired items for a particular tag from its list. So, I'd pick x1 items with tag t1 from the list of items with tags t1, irrespective of whether the items contain any other tag. This way I'd ensure that the 'minimum' criteria of all the tags are satisfied. But for the max part, each tag will most definitely go overboard. How do I recursively keep replacing items from the batch with the remaining items in L to make the final desired distribution?

Any other solution would be great. Or any existing algorithm that can get me in the right direction to approach this problem.

I know the question is a bit too wordy, and probably a bit confusing, but I'v tried to explain it as well as I can, and of course, the problem might be a lot interesting I suppose.

# Answer
Let me repeat my understanding of the problem (as I understand it), then sketch a candidate solution approach. If I've misunderstood the problem, you might need to revise the question to clarify.

The problem: You have $n$ items, and want to divide them into $n/B$ batches of $B$ items. Presumably, $n$ is a multiple of $B$. Each item has some set of tags (a subset of $\mathcal{T}$, where $\mathcal{T}$ denotes the set of all possible tags). For each batch, we're given a function $f:\mathcal{T}\to \mathbb{N}$; we want to ensure that, for each candidate tag $t \in \mathcal{T}$, there are at least $f(t)$ items in the batch with tag $t$. The question is to identify a valid division into batches, if one exists.

One candidate solution: we can formulate this as an integer linear programming problem. Let $x\_{i,j}$ denote a 0/1-valued variable that is $1$ if item $i$ is placed into batch $j$, and 0 otherwise. Now we can write down some constraints on the $x$'s that correspond to the problem description. We get

$$0 \le x\_{i,j} \le 1$$

$$\sum\_j x\_{i,j} = 1$$

$$\sum\_i x\_{i,j} = B$$

$$\sum\_{i \in S\_t} x\_{i,j} \ge f(t)$$

for all $i,j,t$. Here $S\_t$ denotes the set of items with tag $t$. You can now use an off-the-shelf integer linear programming solver to search for a solution to this problem.

If I didn't understand your problem quite right, I hope you see the basic idea of my solution and hopefully you'll be able to come up with the appropriate tweaks to address any misunderstandings I might have had about what problem you were looking to solve.
> 0 votes

---
Tags: algorithms, distributed-systems
---


# Question
Title: Non context free language that is pumpable?
For my homework assignment, I have to come up with a non-cfl that is pumpable. I came up with the following: $$ C = \\{a^n b^n c^n d^m \mid n \ge 1 \text{ and } m \ge 1 \\} $$

I'm not sure whether this works. For the pumping lemma, let $p$ being the pumping length. If I generate a string with $p$ $a$'s, $b$'s, and $c$'s, and only one $d$, my only choice for $vxy$ would be $d$. Pumping this down to $v^0xy^0$ gives $a^p b^p c^p$, thus escaping the language. However, if I let $m$ be greater than or equal to zero, if I choose a string with no $d$'s, then I am forced to put either $a$'s, $b$'s or $c$'s in my $vxy$ string.

# Answer
> 0 votes
As you say "thus escaping the language" which means your example language is *not* pumpable: for $m=1$ we cannot pump $d$ and stay in the language. Instead consider $D= C \cup \\{a,b,c\\}^\*$. Now we can pump $d$ whenever it is present, and we can pump any string that does not contain $d$.

---
Tags: context-free, pumping-lemma
---


title: Kripke automaton and observations

text:
# Question
Title: Kripke automaton and observations
This is a question concerning Kripke automaton. My answers seem a little short and I was wondering if I was missing something? Transition table of a Kripke automaton:

A -\> red light is on

B and D -\> blue light is on

C -\> both light are on

1) Is the test 001blue satisfied by any state?

```
Attempt: No

```

2) Is the test 001red satisfied by every state?

```
Attempt: Yes but I dont know how to show it.

```

3) Which test could tell difference btw A and C?

```
Attempt: test = 100both; C satisfies test, A doesnt

```

4) Can any test distinguish B and C?

```
Attempt: Yes, test = 10001blue; B satisfies test, C doesnt

```

5)Show that no test can tell the difference btw B and D.

```
Attempt: Their observations are different.

```

# Answer
Your answers seem correct. As for 2: one way is to simply check, a quicker way is to observe that all states go to A upon reading 1, so the sequence 001 ends in A, and A satisfies "red".

3 can be solved by the test "blue" (without any moves) and 4 can be solved with the test "red".

As for 5: in order to show that no test can differentiate B and D, observe that for the letter 1, both go to A, for the letter 0 both go to C, and both have the same light (blue). Thus, you can say that the "language" of both state is equal.
> 1 votes

---
Tags: automata
---


# Question
Title: What does "prompt collection" mean in the context of memory management?
I often see people assert that reference counting techniques such as `shared_ptr` in C++ provide prompt collection (e.g. here and here) but I am not sure what exactly is meant by this. Some people tell me that they mean "collects at the earliest possible point" but I think that is not true of scope-based reference counting because it defers collection to the end of scope even if a variable is dead. Therefore, I'm wondering if other people have a different interpretation that may be correct.

Do computer scientists use the term "prompt" in this context and, if so, what do they mean by it?

More concretely, I once studied the behaviour of various OCaml and F# programs and found that they often collect values before they fall out of scope and, therefore, more "promptly" than scope-based reference counting. For example, the following function runs in bounded memory:

```
let rec loop tmp i =
  if i<=0 then tmp else
    loop (Array.copy (loop (Array.copy tmp) (i-1))) (i-100)

```

Even though the argument `tmp` is in scope for the entire body of the function it is collected before even the first recursive call to `loop`.

**EDIT** Here is a simpler F# example with a single recursive call and some post-processing to ensure that the call is not in tail position so it cannot be eliminated:

```
let rec loop tmp i =
  if i<=0 then tmp else
    let tmp = loop (Array.copy tmp) (i-1)
    tmp.[0] <- tmp.[0] + 1
    tmp

```

Between the copying of the array and the call to `loop` the argument `tmp` dies and, indeed, I find that it is garbage collected so this program requires only O(1) space.

Here is the equivalent reference counted C++:

```
shared_ptr<vector<double> > loop(shared_ptr<vector<double> > tmp, int i) {
    if (i<=0) {
        return tmp;
    } else {
        shared_ptr<vector<double> > tmp1(new vector<double>(*tmp));
        shared_ptr<vector<double> > tmp2 = loop(tmp1, i-1);
        ++(*tmp2)[0];
        return tmp2;
    }
}

```

Although `tmp` dies between the creation of `tmp1` and the call to `loop`, scope-based reference counting keeps it allocated until the end of scope. So `n` recursive calls require O(n) space.

# Answer
> Do computer scientists use the term "prompt" in this context and, if so, what do they mean by it?

What is meant by prompt, is that it is guaranteed to be deleted *and* more importantly, **destructed**, when it goes out of scope. The main point of this, is to take advantage of the mainly-C++-ish paradigm of Resource Acquisition Is Initialization.

Look at the following program in pythonish:

```
def procedure():
  f = open('path')

  ... #use f

def main():
  procedure()
  #f *might* still be alive here, which means it is hogging a file resource

```

So, languages like python therefore must supply some manual cleanup methods. One is supposed to call `f.close()` before leaving `procedure()`. However, this can be error prone, because of early-return (you must remember to close at every return, and remember this when changing code later; it is very cumbersome) and exception safety (what if somewhere before returning, something throws an exception?, then your `f.close();return` isn't called at all).

The C++ solution to this is very elegant; when things go out of scope, they are guaranteed to call a destructor. The destructor of a resource object will/should clean up the resource. So you have the following code in C++:

```
void procedure(){
  std::ofstream f("path");
  ... //do stuff with f
  // we *can* call f.close(), but we don't have to, because f::~() (the destructor) will clean it up, and it is guaranteed to be called when going out of scope.
}

```

The python solution to this is to use the `finally` exception block like so:

```
def procedure():
  f = open('path')
  try:
    ... #use f
  finally:
    f.close()
def main():
  procedure()

```

Alternatively, there is some syntax sugar for some special resource classes (you can add this to any custom class as well) that accomplishes the same thing:

```
def procedure():
  with open('path') as f:
    ... #use f
  #f.close() is called once out of "scope" of the with; it is essentially the same as the finally block.
def main():
  procedure()

```

So it is simply two different paradigms; C++'s concept of the "on-the-stack" objects allows self-cleanup, python and most other languages require manual cleanup, but enjoy garbage collection.

Now, the issue is, *pointers* don't have destructors; they are essentially POD (plain old data). Therefore, if you want to keep an object around longer, you would allocate it on the heap, and save a pointer to it, but you must manually call the destructor (via `delete ptr;`), but only when you "know" you are done with it. In many situations, it is hard to know when you are done with a pointer, for example, if it is used in many places ("shared ownership"); therefore a reference counter such as `shared_ptr` can be used, and the underlying objected that is pointed to will be destructed (the destructor will be called) "promptly" when it goes out of scope, ie. when the last user gets rid of the pointer.

> More concretely, I once studied the behaviour of various OCaml and F# programs and found that they often collect values before they fall out of scope and, therefore, more "promptly" than scope-based reference counting.

This is probably not *guaranteed* though. A garbage collector can decide to clean things up whenever it wants to, they usually don't take resources other than memory into consideration, and AFAIK, never provide any such guarantees. C++, and the finally blocks provide *guarantees* of resource cleanup.
> 2 votes

# Answer
I have never heard the term "prompt" used in a technical sense with regard to memory management or reference counting. "No longer than the lifetime of the last pointer to the object" would be accurate (and that is *not* true of OCaml or F#).

I don't really understand your example, (why is `tmp` getting garbage collected before the second call to `array.copy tmp`?) but I think you may be confusing C++'s "automatic (stack allocated) variables have a destructor that is called when the variable goes out of scope," with "reference counted." In C++ you mainly use reference counted pointers when you don't know the scope of the dynamically allocated object (and so, in cases where there may be another pointer to the memory, which means that it is not dead yet.)

Your example is not demonstrating a problem with reference counting so much as it is demonstrating that C++ doesn't have tail recursion elimination in the language definition (or in most compilers), so you can't use recursion to do looping. The similarly double nested loop in C++ would, I think, look something like this:

```
void
loop(vector<foo> tmp, int i)
{
top_label:
   if (i > 0) {
     do {
       auto mem = System.GC.GetTotalMemory(false) // whatever this means
       if (mem > maxMem) maxMem = mem;            // and what is maxMem?
       tmp = tmp;     // call the assignment operator (which does nothing in this case.)
       i--;           // mem goes out of scope on every loop iteration
     } while (i > 0);
     tmp = tmp;
     i = 0;
     goto top_label;
  }
}

```

There's no reference counting, but there are automatic stack-allocated variables. Whereas in OCaml you really do make a copy, and then delete the original (because the compiler is doing tail recursion elimination) in C++ you call the assignment operator, which by convention is required to test for equality of the source and destination and do nothing.
> 0 votes

---
Tags: memory-management
---


# Question
Title: What do I need to know about algorithms?
Drawing from Are algorithms (and efficiency in general) getting less important?, I get that algorithms are more important than ever, but I need to know anything about them other than their complexities?

I would expect to use algorithms out of a library of some sort that has been written by people that are much much more knowledgeable than me, and have been thoroughly tested (most of the STL comes to mind here, but also boost, and probably every other library that someone would care to name).

Thus, unless I am a library maintainer/implementer of some sort, do I need to know anything about these algorithms?

# Answer
> 4 votes
If you do anything a bit complicated, you will almost certainly have to design your own algorithms. STL/boost are nice, amazing really, but it is useful to know how things work behinds the scenes and be able to reproduce it. This will help you tackle problems that the STL/boost, generic enough as they are, cannot handle; or problems that are entirely different from the ones the STL/boost can help with. Many times, algorithms and data structures that I've designed were built *on top of* STL/boost.

> Thus, unless I am a library maintainer/implementer of some sort, do I need to know anything about these algorithms.

Chances are, if you make any interesting programs, you are going to find it useful to design some algorithms and data structures. Sometimes, the most effective optimizations cannot beat a simple change in methodology or representation.

Unless the algorithm you require/design is useful to a wider audience, it can sometimes be difficult to package it as a useful library. Perhaps you will find that something you made *can* be useful, and *will* publish it (github is chock full of these projects). Therefore, I think that if you program long enough, you will *become* a "library maintainer/implementer of some sort", even if you are the only one using it, for lack of publicity.

**Bottom line:** I don't think libraries like STL and Boost are making knowing algorithms less important at all; rather they are making more advanced algorithms within reach. While libraries such as these can sometimes make knowledge of their algorithms unnecessary for small programs, in practice it can important to know if you intend to design anything complex.

# Answer
> 1 votes
Algorithms are step-by-step problem-solving procedures that are suited for computer implementations. So I don't see how you can become a serious programmer without knowing algorithms.

The standard algorithms and data-structures implemented in standard library are primitive building-blocks, and won't help in designing methods for solving problems. Just like you can't write a novel from taking words or phrases from dictionary. I also consider writing programs a creative process! But surely having the building blocks will help you implement your algorithms faster.

Please also see my other answer: https://cs.stackexchange.com/a/16033/204

---
Tags: algorithms, efficiency
---


# Question
Title: How to analyze/test a binary search algorithm?
I was asked to "Compute the average runtime for a binary search, ordered array, and the key is in the array." I'm not quite sure how to approach this problem. Isn't the runtime of binary search O(log n)? And the average would be something like n + n/2 + n/4... etc?

I'm then asked to "Implement a program performing an empirical test of the binary search (using a fixed number of random arrays for each n), then do a ratio test justifying your analytical answer." How would I go about doing this? Could I perform a basic binary search algorithm on a number of random arrays, counting the basic operations, and compare that to my original analysis from the first question?

I appreciate any help/guidance here.

# Answer
First, of all, the *worst-case* running time of binary search is $\Theta(\log n)$. What you are looking for is the *average* running time of binary search under some reasonable random model, for example the element to be looked for is chosen uniformly at random from the (distinct) elements in the array.

Second, the average running time can't be $n + n/2 + n/4 + \cdots$, since the average running time is *lower* than the worst-case running time. I'm not sure what exactly you're counting here. The average running time is the average number of operations taken by your algorithm, on a random input. In contrast, the worst-case running time is the maximal number of operations taken by your algorithm on *any* input.

Perhaps the following example will make things clear. Consider the following task: given an array of size $2n$ containing $n$ zeros and $n$ ones, find the index of a zero. The worst-case running time of any algorithm is $\Omega(n)$. In contrast, consider the algorithm which scans the array from left to right, and returns the first zero index. Its worst-case running time is $\Theta(n)$. Under the assumptions that the input array is chosen randomly among all legal arrays, the average running time is $\Theta(1)$ (why?). You can modify the algorithm to one which probes locations randomly, and then the worst-case *expected* running time is $\Theta(1)$. (If you don't understand the last remark, wait until you learn about randomized algorithms.)

Finally, you're required to empirically demonstrate the claimed average running time $\Theta(f(n))$. The idea is that for large $n$, the average running time will be $\approx C f(n)$ for some constant $C$ whose units are *seconds*. In other words, $C$ is the constant "hidden" inside the big O notation. Suppose you calculate for several values of $n$ an average $T(n)$ over several runs of the algorithms. Then you expect $T(n)/f(n)$ to be roughly constant, and that would demonstrate your claim concerning the average running time.
> 3 votes

---
Tags: algorithm-analysis, runtime-analysis, binary-search
---


title: Pentary Search Recurrence Relation

text:
# Question
Title: Pentary Search Recurrence Relation
I have done an assignment question which asks me to find the average case of pentary search. The one I came up with is:

```
C(n) = C(n/5) + 14/5

```

However, I got it wrong and the professor didn't really explain why.

Can you help me?

Thanks!

Edit:

Pentary search is dividing the array into 5 parts and look for a specific key.

In perspective:

1|2|3|4|4

These are the number of comparisons made by the computer from pentary search.

Adding all possible comparisons I get 14 over 5 slots. This is why I have 14/5

# Answer
> 1 votes
There is at least one thing that could be wrong with your recurrence, depending on how exactly the algorithm is stated: you are overlooking the case that the element could be found before recursion.

---
Tags: recurrence-relation, average-case
---


# Question
Title: Is $\{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \}$ context free if $L_1$ and $L_2$ are?
In class, it was alluded to that a language: \begin{equation\*} \\{s\_0 w s\_1 : s\_0s\_1\in L\_1, w\in L\_2 \\} \end{equation\*} would be context free, if $L\_1$ and $L\_2$ are context free.

Intuitively, that doesn't make sense to me. I tried doing my own research and attempted a proof using the pumping lemma, but didn't get anywhere. Maybe I misunderstood? If that is correct, how could I prove it (or convince myself).

# Answer
Class is right.

The pumping Lemma is not very helpful in this setting. It is usually used to show a given language non-context-free.

As for your language, first try to understand the special case, where $L\_s = \\{A\\}$ for a special symbol $A$, that is try to prove that the language $\\{ s\_1As\_2 \mid s\_1s\_2\in L\_1 \\}$ is context-free whenever $L\_1$ is context-free.

In the comments below, Yuval gives a hint how to perform the construction with a PDA, for the general case. Start an automaton for $L\_1$. At any nondeterministic moment (once during the computation) interrupt the $L\_1$ computation and push a new bottom-of-stack symbol. Then use that as a marker to simulate a PDA for $L\_2$ which stops when we accept by empty stack. Remove the marker, and happily resume the computation on the second part of $L\_1$.

A simple construction using CF grammars is given by Yuval in his answer.
> 4 votes

# Answer
Hint: Consider (for simplicity) a grammar for $L\_1$ in Chomsky normal form. For each original non-terminal $A$, add another non-terminal $A'$; the starting symbol is the marked version $S'$ of the original starting symbol $S$. For each production $A \to BC$, add the additional productions $A' \to B'C$ and $A' \to BC'$. For each production $A \to a$, add the addition productions $A' \to S\_{L\_2} a$ and $A' \to a S\_{L\_2}$, where $S\_{L\_2}$ is the starting symbol of $L\_2$.
> 4 votes

---
Tags: formal-languages, context-free, closure-properties
---


title: Find equidistant triplets in a tree

text:
# Question
Title: Find equidistant triplets in a tree
Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between two nodes).

It's pretty easy to do it in $O(n^3)$ time. Is it possible to do it faster?
I think that on-line algorithm and pre-processing should help.

# Answer
Consider such a triplet $(a,b,c)$, and root $T$ at $a$. Let $e$ be the lowest common ancestor of $b$ and $c$. If $e = a$ then $d(b,c) = 2d(a,c)$, and we conclude that $a=b=c$. If $e \neq a$, then if we now root $T$ at $e$ then $e$ is the lowest common ancestor of $a,b,c$ (pairwise). That means that $a,b,c$ belong to different branches below $e$.

This gives rise to the following algorithm. First, there are $n$ triplets of the form $(a,a,a)$, which you may or may not want to count. Second, each triplet $(a,b,c)$ comes with its unique vertex $e$. So we enumerate over the vertices $e$, root $T$ at $e$, and for each child $f$ of $e$, count the number of vertices at any given depth; this takes time $O(n)$. Now for each depth $D$, we are given a list $a\_1,\ldots,a\_k$ corresponding to the number of vertices at depth $D$ for the children of $e$. We want to compute $$ \sum\_{i\<j\<k} a\_i a\_j a\_k = \frac{1}{6} \left(\sum\_i a\_i\right)^3 - \frac{1}{2} \left(\sum\_i a\_i^2\right) \left(\sum\_i a\_i\right) + \frac{1}{3} \sum\_i a\_i^3.$$ This phase can also be accomplished in $O(n)$ (going over all possible depths), with some care (you need to sort the children according to depth, but that can be done in linear time since the depths are integers from $0$ to $n-1$; other details left to you). Therefore the entire algorithm is $O(n^2)$.

My guess is that you can find the number of triplets in $\tilde{O}(n)$.
> 4 votes

---
Tags: algorithms, graphs, dynamic-programming, trees
---


# Question
Title: How are the web based compilers designed?
Is it possible to design a compiler that can safely compile and run untrusted code?

As a practical example, I want to know how the online compilers are designed/programmed?(Like the one on codepad.org) Are they similar to our traditional day-to-day compiler. How they are hosted on servers?

# Answer
This question is asked on stackoverflow:

> How do sites like codepad.org and ideone.com sandbox your program

A short summary from the answers:

---

A more theoretical answer would be that it is possible to restrict all calls out of the program, (syscalls, function calls etc.), in a manner similar to how native client works, if you have control of the compiler (and even moreso, if you control the CPU and OS). For time and memory consumption, you can simply have have cut-offs that would kill the compilation process/running program. This should only leave you vulnerable to bugs in the compiler, runtime libs, and the OS/hardware level; which a VM can mostly eliminate the danger of.
> 1 votes

# Answer
How is the compiler built? The same way standard non-web compilers are built. Really, the web interface is just a interface to the compiler -- there's nothing fundamentally different about compiling a program submitted via the web vs submitted from the filesystem.

What *would* be fundamentally different would be if the service allowed you to compile *and run* the program on the server. Running untrusted code on the server poses some challenges (how do we do it securely?). If that's what you wanted to know about, Realz Slaw's answer should provide some more details about that aspect. But in your question you only asked about compiling, and there's nothing different about compiling.
> 0 votes

---
Tags: compilers
---