What all can a valid approximation algorithm access? For example can an approximation algorithm call a subroutine which is solving a NP-Hard problem? (like say its trying to find the longest path in some graph as an intermediate step) Is that allowed?

Depends. Typically, with "approximation algorithms" people understand algorithms that run in polynomial time and return a possibly non-optimal solution (with a formal guarantee on the solution quality). In this definition, no, you can't spend exponential time solving an NP-hard problem.

On the other hand, nothing is forcing you to consider polynomial time algorithms that return non-optimal solutions. In fact, it is interesting to consider algorithms that take exponential time, and still return non-optimal solutions. See for instance [1, 2].

[1] Cygan, Marek, Lukasz Kowalik, Marcin Pilipczuk, and Mateusz Wykurz. "Exponential-time approximation of hard problems." arXiv preprint arXiv:0810.4934 (2008).

[2] Cygan, Marek, Łukasz Kowalik, and Mateusz Wykurz. "Exponential-time approximation of weighted set cover." Information Processing Letters 109, no. 16 (2009): 957-961.


Contraint with three variables into three binary constraints I'm having a hard time tackling the following problem (perhaps some key data is missing). We have a constraint:

$A+B= C$

One is supposed to represent this one constraint using three binary constraints. Is this even possible? No domain is given, but even if it was, I really don't see how this could be achieved...

Good question.  Your instinctive reaction is quite valid: if you stick with the variables $A,B,C$, there is no way to introduce some set of binary constraints that will be equivalent to $A+B=C$ (where each constraint is only allowed to mention two of $A,B,C$).

The trick is to introduce new variables, or change the set of variables.  If you do that, it can be done.  For instance, see the reference that hengxin suggests: http://ktiml.mff.cuni.cz/~bartak/constraints/binary.html.  However, it would be understandable if you feel that this is in some sense "cheating"... which might be why you didn't think of this approach.


The symbolic differentiation of univariate expressions I was reading "Doug McIlroy: McCarthy Presents Lisp" and the phrase "symbolic differentiation of univariate expressions" triggered a faint memory of a demonstration of differentiation done in haskell using higher order functions.  (I think my memory is of using the language to produce a function that is the differential of a function given.)

However I haven't been able to find any other reference to the above phrase in lisp or ML-based languages.

Does anyone have more information on this, and is "symbolic differentiation of univariate expressions" the same thing as the memory I described?

You might be looking for automatic differentiation, which is an entire field of research; many techniques are known.


$ \Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity My algorithms and data structures' book states that to create a dynamic array  the following procedure is followed:

  Let $d$ be the length of an array $ a $ and $n $ the number of elements stored in it. Each time an insertion operation is done, if there is enough space $(n+1<d)$, $n $grows by 1; otherwise if $n=d$, we allocate and array $b$ of size $2d$, $d$ is updated to$ 2d$ and all elements are copied to it, then we do $a=b$.
  Similarly, everey time a deletion operation is performed, $n$ decreases by 1, when $n=d/4$, we allocate and array of size $d/2$, $d$ is updated to $d/2$ and  we copy all elements of the array $a$ to the array $b$ an do $a=b$.

  The pseudocode of the functions doing the array doubling and halving is shown in the picture

then the following theorem is proved:

  The execution of N insertion or deletion operations in a dynamic array requires a time $O(n)$, beside d=$O(n)$

  proof:
  Let $d$ be the length of an array and n the number of elements stored in it
  After doubling the array's size there are $m=d+1$ elements in the new array of $ 2d $ positions. We need at least m-1 insertion requests for a new doubling and at least $m/2 $ deletion  requests for a halving.
  Similarly,after a halving, there are$ m=d/4$ elements in the new array of $ d/2 $ elements, for wich at least$ m+1$ insertion requests are needed for a new doubling and at least $m/2 $ deletion requests are needed for a new halving.

  In any case, the cost of $ O(m) $time   required for the resizing can be virtually distributed among the $ \Omega(m)$ operations that caused it(starting from the last resizing) . Finally, supposing the when the array is created there are $n=1$ and $d=1$, the number of elements of the array is always one fourth of its size, so $d=O(n)$

I am a beginner with this  $ \Omega(m)$ and  $ O(m)$ , I know the mathematical definitions and I've been reading a lot about it but I am not able to understand it well in context. I know big O should indicate an upper bound on the time complexity of an algorithm and big omega a lower bound.

I don't understand the last paragraph when they use these symbols, Why is the time cost O(m), why are they using $ \Omega(m)$ for the number of operations that caused the resizing (besides specifically what operations are they referring to?) and why do they write $d=O(n)$, what should I understand from it?
Any help will be greatly appreciated

Note: I got this from : Strutture di dati e algoritmi, progettazione, analisi e visualizzazione. Crescenzi, Gambosi, Grossi-2nd edition.

The definitions are (as used commonly in Computer Science, all functions positive):

$f(n) = O(g(n))$ if there is $c_1 > 0$ such that for some $N_1$ whenever $n \ge N_1$ it is $f(n) \le c_1 g(n)$

$f(n) = \Omega(g(n))$ if there is $c_2 > 0$ such that for some $N_2$ whenever $n \ge N_2$ it is $f(n) \ge c_2 g(n)$

$f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$

Note that the values of $N_i$ might be huge, and nothing is said about the values of $c_i$. This is a rather crude comparisons for very large $n$. Useful because they are (comparatively) easy to get, and we are mostly interested in our algorithm's performance for large inputs (small ones are dispatched with not too much work).

Informally, $f(n) = O(g(n))$ means $g$ is an upper bound to $f$, $f(n) = \Omega(g(n))$ means $g$ is a lower bound, $f(n) = \Theta(g(n))$ that they grow roughly at the same rate. Note that for example $n = O(n^3)$ and $n = \Omega(\ln n)$. The notation does not mean $g(n)$ is "best possible" in any sense. Often it is understood from the context that the bounds are tight, but you have to check the context/derivation.


Basic Theta-notation question Let $T$ be a function.

Is it true that if $\exists f\forall n,m> 0.\\ \frac m {f(n)} \leq T(n,m)\leq m$

Then $\exists g.T(n,m)=\Theta(m\cdot g(n))$?

In words: is such a case, is there a function $g$ dependent only on $n$ that satisfies the above?

It looks to me true, but I am really stuck and don't know how to prove it rigorously.

No. Consider, for instance,
$$T(n,m) = \begin{cases}
m, & \text{$m$ even} \\
\frac{m}{n}, & \text{$m$ odd}
\end{cases}$$
and notice $\frac{m}{f(n)} \le T(n, m) \le m$ holds for $f(n) = n$. Suppose $T(n,m) \in \Theta(m g(n))$ for some $g(n)$, that is, there are $c, c' > 0$ with $cmg(n) \le T(n,m) \le c'mg(n)$ for all but finitely many $m,n$. Since there are infinitely many odd $m$'s we get $g(n) \le \frac{1}{cn}$ for all but finitely many $n$. For even $m$ it then follows
$$m = T(n,m) \le c' m g(n) \le \frac{c'}{c} \frac{m}{n},$$
which can only hold for finitely many $n$.


$\epsilon$-transitions in NFAs I am reading "Introduction to the Theory of Computation" (2ed) by Michael Sipser. In Example 1.35, it says the NFA accepts $\epsilon$, which I understand, since the state can stay at $q_1$ upon input of $\epsilon$:

But in Example 1.38, it shows to be an empty set for $q_1$, $q_3$, and $q_4$:

I thought it should be $\delta(q_1, \epsilon)=\{q_1\}$ at least, for instance. I always assume there is an "implicit self-$\epsilon$-transition" at every state, but why it is $\emptyset$ now? I also noticed the lack of a "self-$\epsilon$-transition" in the proof of Theorem 1.45 (no staying at $q_0$ upon the input of $\epsilon$). Have I missed something important?

I think you're making a good point. It's just that since an $\epsilon$-transition from a state to itself must always be there in some sense (we can read nothing from the input stream and stay in the same state) it's more economical to make the convention that we don't consider such "transitions" to be transitions.


How does cycling happen in the simplex method? I'm reading Schrijver's Theory of Linear and Integer Programming, and I have a problem understanding cycling happens in the simplex method. The simplex is described as below:

Solving $\max\{cx\mid x \geq 0; Ax \leq b\}$ At each stage a set $C_k$ is maintained, which consists of $n$ linearly independent equalities from $Ax = b$, such that $x_k$ the current vertex is determined by $C_kx_k = b_C$.

$u$ is the unique vector $u_kA = c$ where $u$ is zero in the components corresponding to equalities outside $C_k$. if $u \geq 0$ then $x_k$ is optimal. Otherwise we choose an index $i^*$ where $u_{i^*} <0$, $y$ is the unique vector such that $C_ky$ is zero in all components except $i^*$. Then $\lambda$ is defined as $\min\{\frac {b_t - (Ax_k)_t}{(Ay)_t}, (Ay)_t > 0\}$, where $t^*$ is the index acquiring the minimum. Now $x_{k+1}$ is calculated from $x_k + \lambda y$ and $C_{k+1} = C_k + t^* \setminus i^* $. Also notice $cy = uAy = -u_{i^*} > 0$ so $cx_{k+1} > cx_k$.

So the book explains when choosing $i^*$ and $t^*$ and there are several options, there are different methods for breaking ties, some of which may cause cycling that is the algorithm wouldn't terminate. Here is what I don't understand: given there are finitely many vertices and $cx_{k+1} > cx_k$ how is it possible to visit the same vertex twice hence encountering cycling??

Later, when the average time of Simplex method is being analyzed due to Borgwardt, the book explains cycling can happen only if the LP problem is degenerate. And provides a condition for being non-degenerate there is no set of $n$ linearly dependent rows in the matrix $\begin{bmatrix}c\\A\end{bmatrix}$ and there is no set of $n+1$ linearly dependent rows in $\begin{bmatrix}A &b\end{bmatrix}$. can you please explain why is this?

Cycling happens in a different scenario: when $cx_{k+1} = cx_k$. This happens when the current solution is degenerate, that is, when the set $C_k$ is not unique.

For a worked out example, see Cycling in linear programming problems or The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling. There are many other resources which are available online.


Cutting equal sticks from different sticks You have $n$ sticks of arbitrary lengths, not necessarily integral.

By cutting some sticks (one cut cuts one stick, but we can cut as often as we want), you want to get $k<n$ sticks such that:

All these $k$ sticks have the same length;
All $k$ sticks are at least as long as all other sticks.

Note that we obtain $n + C$ sticks after performing $C$ cuts.

What algorithm would you use such that the number of necessary cuts is minimal? And what is that number?

As an example, take $k=2$ and any $n\geq 2$. The following algorithm can be used:

Order the sticks by descending order of length such that $L_1\geq L_2 \geq \ldots \geq L_n$.
If $L_1\geq 2 L_2$ then cut stick #1 to two equal pieces. There are now two sticks of length $L_1 / 2$, which are at least as long as the remaining sticks $2 \ldots n$.
Otherwise ($L_1 < 2 L_2$), cut stick #1 to two unequal pieces of sizes $L_2$ and $L_1-L_2$. There are now two sticks of length $L_2$, which is longer than $L_1-L_2$ and the other sticks $3 \ldots n$.

In both cases, a single cut is sufficient.

I tried to generalize this to larger $k$, but there seem to be a lot of cases to consider. Can you find an elegant solution?

The first core observation to solving this problem is that the feasibility of a cutting length $l$,

$\qquad\displaystyle \operatorname{Feasible}(l) = \biggl[\, \sum_{i=1}^n \Bigl\lfloor\frac{L_i}{l} \Bigr\rfloor \geq k \,\biggr]$,

is piecewise-constant, left-continuous and non-increasing in $l$. Since the number of necessary cuts behaves similarly, finding the optimal length is just

$\qquad\displaystyle l^{\star} = \max \{ l \mid \operatorname{Feasible}(l) \}$.

Furthermore, as the other answers have proposed, all jump discontinuities have the form $L_i/j$. This leaves us with a discrete, one-dimensional search problem amenable to binary search (after sorting a finite set of candidates).

Note furthermore that we only need to consider the $L_i$ that are shorter than the $k$-largest one, since that one is always feasible.

Then, different bounds on $j$ lead to algorithms of different efficiency.

$1 \leq j \leq k$ results in a search space of quadratic size (in $k$),
$1 \leq j \leq \lceil k/i \rceil$ in a linearithmic one (assuming the $L_i$ are sorted by decreasing size), and
slightly more involved bounds in a linear one.

Using this, we can solve the proposed problem in time $\Theta(n + k \log k)$ and space $\Theta(n + k)$.

One further observation is that the sum in $\mathrm{Feasible}$ grows in $l$ by $1$ for each candidate $L_i/j$ "passed", counting duplicates. Using this, we can use rank selection instead of binar search and obtain an algorithm that runs in time and space $\Theta(n)$, which is optimal.

Find the details in our article Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts (by Reitzig and Wild, 2015).


For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X For a given set of coordinates (lat/lng) I need a path which will visit each coordinate only once. The path needs to be selected to minimize the number of times the haversine distance between two subsequent points along the path is greater than X (ex: 200 miles).
The practical application:
I have airports on a map. I have a string of LED lights which are connected by a fixed distance of wire between them. I want the optimal path between all the airports where I minimize the number of times I need to splice additional wire into the string.
Suggestions on the approach? Maybe some type of genetic algorithm implementation?

Create a graph from the airport coordinates where edges have the haversine distance as weights.  Since the graph is a metric graph, you can apply Christofides algorithm.  This algorithm is a $\frac 3 2$-appoximation, which means that it gives a solution which is not worse than 50% longer than the optimal.
However, since you want to also minimize the number of long edges, you can remove all edges that are longer than you would like, but you now have a non-metric graph (it does no longer satisfy the triangle inequality).
One related problem is the Bottleneck traveling salesman problem, in which you want to find a Hamiltonian path that minimizes the longest edge.  Since your original graph is a metric graph, you can apply the 2-approximation to get an algorithm in which the longest edge is not more than twice possible.

Since you seem to be set on using genetic algorithm, you can consider using both of these algorithms for seeding the initial pool for the GA.  Run both algorithms many times to get many different solutions (introduce some randomness), and you might have a very good starting pool.


How can Kolmogorov complexity help me practically with measuring entropy? A comment was made to me saying the following in relation to Kolmogorov complexity:-

You're not the first to think non-computability = impractical or even useless. But it can be useful. In particular to random, "non-algorithmic" data.

I now have a physical   box on my bench that outputs perfectly random bytes with the following distribution:-

I'm trying to estimate the entropy rate of this box, and the problem is that these bytes are highly correlated. Very highly. I can't stress that enough. They are not independent nor identically distributed and arrive in blocks of 20,000ish bytes but that length varies randomly too.
How can Mr. Kolmogorov be useful to me with measuring this "non-algorithmic" data?

How to practically measure entropy of a file? has not yielded a practical answer so far.

How can Kolmogorov complexity be useful to you in measuring the complexity of this data?  It can't.  The Kolmogorov complexity of a sequence of bytes is not computable.

Don't read too much into that comment.  I'd take it as hinting that the idea of Kolmogorov complexity might be a relevant or interesting concept to know about, not necessarily that you can directly compute that value in a particular real-life situation.  Anyway, just because someone wrote something doesn't mean it's true.  If you're not sure what they meant by it, or you are wondering what justification they had for saying that, you might need to ask them.

I notice that Yuval Filmus's answer to the question you linked to provided a similar summary of Kolmogorov complexity, so I'm a bit confused about what is unclear here.


How to prove that the probability that a random graph has a stable set of size $2\lceil \log n\rceil$ is sub-constant? Given a random graph on $n$ vertices where each edge is included with probability $1/2$. Lets call it $G=(n,1/2)$. How can we show that the probability that this graph has a stable set of size at least $2\lceil \log n\rceil$ is sub-constant?

The probability that a specific set of size $k$ is a stable set is $2^{-\binom{k}{2}}$. Hence the probability that some set of size $k \leq n/2$ is stable is at most
$$
\binom{n}{k} 2^{-\binom{k}{2}} \leq 2\left(\frac{en}{k}\right)^k 2^{-k^2/2}.
$$
When $k = c\log n$ (logarithm to the base 2), this upper bound is
$$
2\left(\frac{en}{C\log n}\right)^{C\log n} 2^{-C^2\log^2 n/2}=
\frac{2^{(C-C^2/2)\log^2n}}{\Omega(\log n)^{\Omega(\log n)}} = o(2^{(C-C^2/2)\log^2n}).
$$
For $C \geq 2$, this is $o(1)$.


What are the definitions for "hard problem" and "easy problem"? Take for example the following sentence:

  Computing a hash for a message is "easy"; retrieving the message from the hash is "hard".

Intuitively, I can perfectly understand what's written there. But, in mathematical terms, when is a problem considered hard and when is it considered easy?

I know that easy/hard should not be confused with "efficient", and I know that efficiency has to do with polynomial time complexity. Does it mean that hardness has nothing to do with asymptotic time complexity?

They're not technical terms, so they don't have precise definitions. A problem is "hard" if it requires (or we think it requires) "large" computational resources to solve, and "easy" if it doesn't. "Large" depends on context but, in most contexts, a problem that can be solved in polynomial time is considered "easy".


A binomial random number generating algorithm that works when $Np$ is very small I need to generate binomial random numbers:

  A binomial random number is the number of heads in $N$ tosses of a coin with probability $p$ of a heads on any single toss. If you generate $N$ uniform random numbers on the interval $(0,1)$ and count the number less than $p$, then the count is a binomial random number with parameters $N$ and $p$.

In my case, my $N$ could range from $10^3$ to $10^{10}$ and my $p$ is around $10^{-7}$.  Often my $Np$ is around $10^{-3}$.

There is a trivial implementation to generate such binomial random number through loops:

getBinomial(int N, double p):
  x = 0
  repeat N times:
    if getUniformRandom() < p: # getUniformRandom() returns a real number in (0,1)
      x = x+1
  return x

This naïve implementation is very slow, $O(N)$. I tried the Acceptance Rejection/Inversion method [1] implemented in the Colt (http://acs.lbl.gov/software/colt/) lib. It is very fast, but the distribution of its generated number only agrees with the naïve implementation when $Np$ is not very small. In my case when $Np = 10^{-3}$, the naïve implementation can still generate the number 1 after many runs, but the Acceptance Rejection/Inversion method can never generate the number 1 (always returns 0).

Does anyone know what is the problem here? Or can you suggest a better binomial random number generating algorithm that can solve my case?

[1] V. Kachitvichyanukul, B.W. Schmeiser (1988): Binomial random variate generation, Communications of the ACM 31, 216-222.

If $Np$ is small then the distribution is very close to Poisson, which is easier to generate, especially when the expectation is small.

In your specific case, most of the time the result is zero, and the probability that this happens can be calculated exactly. This optimization will probably result in a speed-up of $10^3$.


How to determine if given “complex” time complexity is $O(n^2)$? If a given time complexity, such as these:

$(n + \log n) * \sqrt{n+\log n}$
$n * (200 + \log^2 n)$
$(7+n^3)\log(n^5)$

is not determinable by just looking at it whether is it in class $O(n^2)$ or not, how do I decide? If a time complexity is given, and in it there are more types of expressions (exponential, logarithmic, polinomial, ... ) how do I decide which one determines the $O(n^2)$ or $O(n\log n)$ or ... complexity?

Sometimes, you can replace them by $n$. For example, in $F_1(n) = (n+\log(n))\times \sqrt{n+\log n}$, replace $\log(n)$ by $n$. So, $F_1(n) \leqslant 2n \sqrt{2n}$ and it means $F_1(n) = O(n\sqrt{n})$. Also, in multiplication or summation, you can ignore constants (not all the time in power functions). Hence, $F_2(n) = n \times (200 + \log^2(n)) = \Theta(n
\log^2(n))$. Or in $F_3(n) = (7 + n^3) \log(n^5) = 5 \times (7 + n^3) \log(n) = \Theta(n^3 \log(n))$ (as $\log(n^c) = c \log(n)$).


What is the formal name for an "entry" in an ontology? I am trying to wrap my head around ontologies and their related counterparts (RDF, OWL, etc.).

My understanding is that an ontology, at the end of the day, really boils down to some database storing objects/entries, where each entry has a set of known attributes as well as relationships to other entries.

If that's true, I'd imagine ontologies lend themselves as perfect candidates for NOSQL graph DBs.

Either way, after all my initial reading, I still haven't found what the formal/official name is for a single "entry" in an ontology. Any ideas? Ditto for what the official names of their attributes and other relationships are. Thanks in advance!

My understanding is that an ontology, at the end of the day, really boils down to some database storing objects/entries, where each entry has a set of known attributes as well as relationships to other entries.

The more common understanding is that one can emulate1 any ontology as a theory in single sorted first order predicate logic. Because such a theory can be seen as an ontology itself, it "really boils down to ... database(s)" if and only if predicate logic boils down to databases. And indeed, there is a close connection, but it won't help you to understand ontologies.

  What is the formal name for an “entry” in an ontology?

Even in your database analogy, you are missing the fact that you also have to specify the database scheme itself in the ontology language. There are different components of an ontology, namely individuals, types/classes, attributes, interrelationships/relations, function terms, restrictions, rules, axioms, and events1. Your "entry" seems to be intended to describe the attributes of an individual, and the relations between individuals. This task is done by the rules, but note that rules are more powerful than this.

1If the ontology contains events, then it is unclear how to emulate it in predicate logic.

Just like vzn, I now have the urge to clean up some of the confusion from the question, independent of whether it will earn me downvotes or not. (People might argue that such explanations based on mathematical logic require too much background knowledge, are too unrelated to ontology, and only lead to confusion. They may be right...) Even if there are practical reasons to prefer RDF or OWL as ontology languages over predicate logic, the simple structure of the later makes it a good tool for explaining some essential components of an ontology language.

A theory in single sorted first order predicate logic consists of axioms and a signature describing the non-logical symbols, i.e. the constants, functions, and predicates (and their arity). The axioms are well formed logical sentences over the given signature (with equality). Let's take set theory as an example. The signature just consists of $S_{rel}=\{\in\}$ and $\operatorname{ar}(\in)=2$, i.e. "$\in$" is a binary predicate. The axioms are logical sentences like $\forall A \, \forall B \, ( \forall X \, (X \in A \iff X \in B) \Rightarrow A = B)$ (Axiom of extensionality).

As an ontology, such a set theory has (at least) the following components:

a single type/class (sets),
a single interrelationship/relation (set $A$ is an element of set $B$ written as $A\in B$),
and a set of axioms/rules

Further attributes and relations can be defined based on these, for example

$\operatorname{singleton}(A) \iff \exists S \, (S \in A) \land \forall X \, \forall Y \, ((X \in A \land Y \in A)\ \Rightarrow\ X=Y)$
$A\subset B\ \iff\ \forall X \, (X \in A\ \Rightarrow X \in B)$

In single sorted first order predicate logic, you could use such attributes (as well as attributes that are part of the signature) to emulate further types/classes. One can also define constants (like the empty set $\{\}$) and functions (like union $\cup$) based on these. So individuals can be emulated as constants and function terms as functions.


deterministic finite automaton for "does contain substring $w$" is of linear size A (non-deterministic) finite state automaton for "all strings that contain substring $w$" is very simple. Just make the path for $w$ and add looped transitions for all letters at the first initial state and the last final state.

When asked to make a deterministic automaton in general we might expect that the automaton can be of exponential size (see the warning of Yuval in the case where $w=101$: Write a regex to match string that does NOT contain a certain pattern).

However, Knuth-Morris-Pratt tells us that a pattern match automaton for $w$ is of linear size, and can be constructed in linear time. That means that the deterministic automaton for "contains substring $w$" is of linear size too (failure links can be replaced by transitions, on for each mismatching letter).
Luke has used KMP to provide an automaton for the example "not ABCDABD" in his answer Automaton for substring matching.

My question is the following: will the standard determinization of a "substring $w$" automaton always lead to a linear sized automaton? Here I mean the practical version of the construction, where unreachable states are not constructed (so not the full $2^Q$ subset construction). Is the answer direct from the construction, or do we need KMP?

A little observation. In the construction there might be many states that contain the original final state. As they all will accept and also all transitions for ever will lead to accepting states (once we have seen $w$) these states can be grouped into one single state. I do not know whether that is a necessary trick to avoid exponential explosion, see https://cs.stackexchange.com/a/11842/4287

Consider the following NFA: the states are $q_0,\ldots,q_{|w|}$, there are transitions $q_{i-1} \to q_i$ on $w_i$, there are self-loops on $q_0,q_{|w|}$ (for all alphabet symbols), the initial state is $q_0$, and the unique final state is $q_{|w|}$.

Assuming $w \neq \epsilon$, the determinization generates $2|w|$ states:

For each location $0 \leq i < |w|$, a state consisting of $q_0$, $q_i$, and $q_j$ for $j < i$ such that $w_1\ldots w_j$ is a suffix of $w_1\ldots w_i$.
Same as before, with $q_{|w|}$ added.

When $w = \epsilon$, the NFA is already deterministic, and contains only one state.


Determine wether a set of sets contains a partition of a given set Consider the following problem :

  Given a set of sets of integers, $\Sigma = \{S_i, i \in I\}$, and a set G, determine wether $\Sigma$ contains a partition of G, i.e. a set $J \subseteq I$ such that $G = \bigsqcup_{j\in J} S_j$.

This problem is (if i'm not mistaken) in NP.

I'm trying to determine wether this problem is in P (Or maybe NP-complete).

Do you know if this problem is treated anywhere in the litterature (Algorithm or NP Completeness) ?
Do you know any problems that are close to this one ?

I have tried to design a polynomial algorithm for the problem, but nothing working so far.

Without loss of any really interesting aspect, we can assume that $S_i\subseteq G$ for all $i\in I$. Otherwise, we can we can remove each $S_i$ which is not a subset of $G$. This reduction step takes $O(ng)$ times, where $n=\sum_{i\in I}|S_i|$ and $g=|G|$.

Now that $S_i\subseteq G$, this problem is the exact cover problem, which is one of Karp's 21 NP-complete problems. You can find all sort of information about it at its Wikipedia entry.

I have played briefly a game called Pentomino, which is an exact cover problem.


Complement of language $\{ x \in \{a,b,c,d\}^* : \exists$ prefix $y$ of $x$ such that $||y|_a - |y|_b|\leq 10 \}$ Is the complement of the following language a regular language?
$$L = \{ x \in \{a,b,c,d\}^* : \exists \text{ prefix }y\text{ of }x\text{ such that }||y|_a - |y|_b|\leq 10 \}$$

My first thought is that it is not a regular language because finite automata can't store the number of $a$ in $x$ and the number of $b$ in $x$, but I guess I do not understand what is the meaning of the prefix here. Could someone help me?

First of all, a language is regular iff its complement is regular. Therefore it suffices to determine whether $L$ itself is regular.

Indeed, since $\epsilon$ is a prefix of every word, and $\epsilon$ satisfies $||\epsilon|_a-|\epsilon|_b| \leq 10$, we see that $L = \Sigma^*$, and in particular $L$ is regular.

Matters become more interesting if we replace the condition $||y|_a-|y|_b| \leq 10$ by its complement $||y|_a-|y|_b| > 10$. In this case the language $L$ is still regular, but the argument is a bit more complicated. Let us show that the following language is regular:
$$
L' = \{ x \in \{a,b,c,d\}^* : \text{some prefix $y$ of $x$ satisfies $||y|_a-|y|_b| > 10$}\}.
$$
(Its complement is the language of all words, all of whose prefixes satisfy $||y|_a-|y|_b| \leq 10$.)

We construct a DFA with 22 states $\{q_{-10},\ldots,q_{+10},q_f\}$. The initial state is $q_0$, and the unique final state is $q_f$. The transition function is given by the following table:
$$
\begin{array}{c|cccc}
q & \delta(q,a) & \delta(q,b) & \delta(q,c) & \delta(q,d) \\\hline
q_{-10} & q_{-9} & q_f & q_{-10} & q_{-10} \\
q_{-9} & q_{-8} & q_{-10} & q_{-9} & q_{-9} \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
q_9 & q_{10} & q_8 & q_9 & q_9 \\
q_{10} & q_f & q_9 & q_{10} & q_{10} \\
q_f & q_f & q_f & q_f & q_f
\end{array}
$$
If the current prefix satisfies $||y|_a-|y|_b| > 10$, the DFA moves to state $q_f$ and stays there. Otherwise, the DFA is in state $q_i$, where $i = |y|_a - |y|_b$.


Cryptosystems whose hardness depends on solving the halting problem? There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes.
This post Gives a list of some famous cryptosystems whose underlying problem is NP-Hard problem.
While I don't expect this to have much practical merit it really does beg what I think is an interesting theoretical question. Can we construct cryptosystems whose underlying problem is undecidable, such as the halting problem or automated theorem proving or the group word problem?
The way such a scheme might behave is that you declare some arbitrary conjecture/instance of other general undecidable problem as a public key, and people can use this conjecture to encrypt their messages, and only the person having the proof of the conjecture could decrypt, vice versa.
Someone Else thought of this too: http://www.cs.utsa.edu/~wagner/PKC/pkc.pdf
Some rebuttals on the practicality of such systems: https://crypto.stackexchange.com/questions/81114/updated-utilizing-a-non-computable-function-to-create-a-one-way-function/81115#81115

For any reasonable public key cryptosystem that I can think of, no, this is not possible. You cannot base a practical public key cryptosystem on any complexity class larger than EXPTIME.
If the private key is linear in the size of the public key (i.e. if the public key is $b$ bits in size, then the private key is no larger than $\alpha b + \beta$ bits for some constants), then you can test all possible private keys (in exponential time) and see which one decrypts a message.


Is $AlwaysHalt$ recursively enumerable? I was doing some complexity theory exercices and I came over this one:

$AlwaysHalt = \{R(M) | M$ halts with all $x \in \{0,1\}^*\}$

Is $AlwaysHalt$ recursively enumerable?

I would say YES and construct the following TM that accepts this language:

Enumerate all $x \in \{0,1\}^*$ starting with length 1 and then increasing the length in every iteration and try the current $x$ with our TM $M$. We only care about those machines $M$ that halt with all words (we do not care if we do not halt, it would only mean that $R(M)$ is not in our language) so each $x$ will halt  eventually. There is only countably many words $x \in \{0,1\}$ so we can do that.

However, I am not sure if this is a correct proof? Can I enumerate all words from and infinite (but countable) language to  show that a TM behaves in some way on every single one of them?

Consider the language $ALL_{TM}$ (sometimes also called $L_{\Sigma^*}$)
$$ALL_{TM}=\{\langle M \rangle: M \text{ is a TM and } L(M)=\Sigma^*\}$$

It is well known that $ALL_{TM}$ is not RE (nor co-RE). See, e.g., this question (and search for other related questions on this site).

From this fact, it is easy to see that AlwaysHalt cannot be RE: a reduction
$$ALL_{TM} \le AlwaysHalt$$ is rather trivial.


Knapsack-type problem where the objective function is a ratio I have a problem where I have a number of proposed initiatives each with a cost and payoff. I need to select a subset of these initiatives in order to maximize the ROI for the selected set as a whole while staying within a total cost constraint. Specifically, the problem is:

Maximize [sum(v_i*x_i)/sum(c_i*x_i)]
Subject to sum(c_i*x_i) <= C and x in {0,1}
Where v_i = payoff from initiative i, c_i = cost of initiative i, and x_i = 0/1 decision to select investment i or not

I understand that if the objective function in such a problem is just a sum then it is a 0/1 knapsack problem. If the function is a ratio as in this case, is there a specific name for this kind of a problem, or a recommended algorithm for solving it?

I can't refer you to literature on this subject, but I did come up with a strategy to solve it.

Do the regular dynamic programming approach to solve simply maximizing $\sum v_ix_i$. In that approach you end up with an array $m[i, c]$ which is the maximum value you can reach with cost less than or equal to $c$ using items up to $i$.

Then simply do a $O(C)$ loop to find the best possible $\frac{m[n, c]}c$ for each $c$ where $n$ is the number of items.


What's the advantage of two pointers linked list implementation of Queue versus one pointer circular list Princeton Algorithms course shows the implementation of Queue using linked list and two pointers - head and tail. I've implemented the same functionality as a circular linked list using only one pointer tail. I'm wondering what's the advantage of two pointers versus one in a circular list. It takes more space as I understand so why did they choose this implementation?

If you're not using a circular list, then you must have a pointer to head and tail to achieve $O(1)$ enqueue and dequeue. Furthermore, if it is not a circular list and not a doubly-linked list, then without a pointer to head, we can't enqueue!

Some picture might help a little too.

Single Linked List with only tail pointer:

There's no way to get back to the head to enqueue! We would have to remedy this with a pointer to the head.
Doubly Linked List with only tail pointer:

We can get back to the head, but at an $O(n)$ cost, we might as well just add another pointer to head for convenience.
Single Circular Linked List with only tail pointer:

We can get back to the head in $O(1)$! This is a good shortcut. In circular linked lists this node can sometimes implemented as a Sentinel Node which does not contain any information but works as a separator between the head and tail of the queue.

In terms of additional space, adding tail or head or both is almost negligible. The nodes will be taking up memory no matter what, it's just whether or not you use a variable to reference them. Using a circular linked list kind of acts like a head pointer if you think about it. tail.next would be a synonym for head, so it's not really saving space, nor is it really costing much space.


Which part of the computer allocates memory in RAM? When we declare a variable there will be a random part of memory will be allocated in RAM. Which component will allocate the memory? Is the processor or any other specific hardware doing the allocation?

It is a combination of the standard C library (usually) and the operating system. No hardware is involved. Check out this answer on stackoverflow for more details.


n-bit 2's Complement Conversion I'm learning 2's complement conversion for positional number systems. For the most part I have only seen 2's complement for represented in 8-bits. I had a discussion with a friend who explained that for values that exceed 8-bits (>255) you would need to go to the next largest word size i.e. 16-bit followed by 32 and 64... That is all well and good, however I don't fully understand if or why I can't do 2's complement for something like a 5-bit, 21-bit, etc system.

For example, if I were to represent 0000 0001 1100 0111 as a 13-bit value I would take off some 0's xxx0 0001 1100 0111, perform some arithmetic to find the complement, xxx1 1110 0011 0001 therefore the 13-bit 2's complement of (0 0001 1100 0111) is (1 1110 0011 0001 0001)? Please let me know if I am missing something...

You can do this for 13 bits, or 15 bits etc, etc.. there is nothing stopping you.

The reason you jump to the next word size is because of the computers hardware. If a register has 8 bits and you are only using 6 bits, the register STILL has 8 bits.

You can design a system with 13 bit word size, and it will still work the same.


How to draw a clearly arranged DFA of a language with modulo rules? I know how to draw a DFA, but I have problems with this specific one:

${L = \{ w \in \{a,b,c\}^* \mid \ |w|_a \equiv |w|_b - 2|w|_c \mod \ 5 \} }$

This language is regular and there has to exist a DFA (It would be great if someone could leave a comment WHY a language like this one is regular). Finally, I got a solution, but I'm not really satisfied with my solution. How can I present the DFA in a more clearly way? (is it possible to draw a "Planar graph" of it?)

Here is the minimal DFA. It keeps track of $|w|_a-|w|_b+2|w|_c\bmod 5$.


Any algorithm better that O(N*logN) for a problem of finding student with largest average score in a list of N scores of the form StudentID, score Question:  Suppose you are a given a csv with N lines of the form StudentID, score.  Multiple lines can have same student-ID.  Find the student with maximum average score

I can't think of any way to make it faster than O(N*logN).

Maintain a hash-table that keeps track of STudentID = Key and Value being an object with sum of scores and number of scores seen with that studentID --> O(N)
Create an array with values in hash table, maybe convert each entry into average while doing so
Sort it worst-case N(logN), all entries belong to same student

Is there any way to do it faster?

You are on a good path, but seem to be confused for no reason. After step 2 you have created an array with average scores. This is a worst case O(N) size array. What is the complexity of finding the highest average score now? Do you need to sort the array?


Byte addressable vs Word addressable I am trying to understand the difference between byte addressing and word addressing.

  A 4-way set-associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB.

No of sets in the cache $= (16 * 1024) / (4 * 8 * 4) = 2^7$

If word addressing is used :

Block offset $= 3 \ bits$

Since PAS is $4 \ GB$, total no of addresses = $2^{32} / 2^2 = 2^{30}$

So, total address bits $= 30\ bits$

Address structure :

Tag bits : $20 \ bits$
Set bits : $7 \ bits$
Block offset bits : $3 \ bits$

Now, suppose the CPU wants to access the 3rd byte of a particular word.

The cache controller will use the $7 \ bits$ set-field to index into a set and then comparing the higher $20\ bits$ tag-field with all of the $4$ blocks in the set. If a match is found, then cache hit occurs and the lower $3 \ bits$ block offset to put one of the word out of the $8$ words in one of the general purpose register. The CPU then extracts the 3rd byte from the word and perform the operation.
If tags are unmatched, then cache miss occurs, a memory read signal is sent and due to spatial locality of reference, a block containing the word is transferred into the cache.

If the CPU is byte addressable:

Total address bits $=32$

Address Structure :
Tag bits : $20 \ bits$
Set bits : $7 \ bits$
Block offset bits : $5 \ bits$

If the CPU wants to access 3rd byte of a word:

Same as in Step 1 of word addressable, but the CPU now can directly address the 3rd byte of the word, using the lower $2 \ bits$ byte offset. However, I'm confused how that would happen. Since, the CPU register size has a width of 1 word, similar to the word addressing, one word out of the 8 words in the block will be transferred to the register. But how would the "byte extracting" step be easier here? And why do we call it byte addressing if still we are actually addressing a word?
Same as in Step 2 of word-addressing. Block of data will be transferred from the memory to the cache in case of cache miss.

Also, this answer says that physical memory is always byte addressable. Now, what is the difference between the addressablity of the memory and addressablity of the CPU architecture?

Word addressing means that, the number of lines in the address bus in the processor is lesser than the number of bits in the word itself.

Lets say we have a 4 byte word. (32 bit address space)

If this machine is byte addressable, then the address bus of the CPU will have 32 lines, which enables it to access each byte in memory.

If this machine is word addressable, then the address bus of the CPU will have 30 lines ($32 - log_{2}4 =30$), which enables it to access memory ONLY in words/chunks of 4 bytes and that too from addresses which are a multiple of the wordsize.

Now if you ask the CPU to fetch a byte from a particular address, it will first drop the 2 least significant bits(by drop i mean overwrite them with 0's) of the address, fetch a word from the resulting address and return a byte using the 2 least significant bits as an offset within the fetched word.

This causes memory access time to increase, since the CPU has to spend more time modifying the address and processing the fetched word. But it also helps reduce hardware cost since the complexity of the circuits is reduced due to the reduction in address bus lines.

However, this overhead never arises in a byte addressable machine, hence 'byte extracting' is easier.


Importance of the empty string In the sense of a string distinct from a null reference string, what is the importance of an empty string in CS (and specially in formal languages)?

Why do you need a separate concept, that of 'empty string', which even has it's own Greek letter (ε)?

Couldn't just an EOL character replace it?

There is a mathematical meaning for the empty string. Indeed the concatenation product of words is an associative operation. But this operation also has a neutral element, namely the empty word. For this reason, the empty word is also frequently denoted by $1$, which allows one to write, for each word $u$,
$$
1 \cdot u = u = u \cdot 1
$$

Of course, if the alphabet is $\{0, 1\}$, it is not a good idea to denote the empty word by $1$ and this is probably the reason why the notation $\varepsilon$ (or sometimes $\lambda$) was introduced. But as Yuval Filmus pointed out, the empty word is a word of length $0$, that is, it contains no letter.

It is certainly disturbing to denote the empty word by $1$ (or by a greek letter $\varepsilon$ or $\lambda$), but you have to take it as a conventional notation, in the same way you denote the empty set by $\emptyset$.


How to distinguish empty cells from cells outside of the input cells? Setup

I need to develop a Turing Machine that accepts a string m that has the same number of a's and b's.
My alphabet is {a,b}, and we use a diamond in class to represent an empty space.

Problem

The part I'm having trouble with is returning to the beginning of the string.

So far

At first I was planning on taking a character(a) marking it with a diamond, moving right until the other character(b) is found, marking that with a diamond, then moving left until the other's other character(a) is found, and repeating the process.
The parenthesis are for example, it could have been b,a,b just as well.

Then at the end if there is an outlier I will know the number of a's and b's was not similar.

But then I developed an example language
ab... and realized that this process will never end in this case, so instead I need a way of determining when I have reached the beginning of the string.

So now my question...

Is it possible to determine when I have reached the beginning of the string without introducing another letter into the alphabet, or another special character like the diamond?

The common definition of the Turing machine is that when you go left when you're at the furthest left point on the tape, is to stay on that spot. So if you want to determine where it began, mark it off, as you said, with a diamond or similar.


Searching through all program of a stack-based language with little memory I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output.

Given a program fragment, I can determine if it is terminated, and, if not, how many operands it requires.  Currently, my search strategy is:

 If program is terminated --> test it
 else --> add all programs with one additional operand to the queue

However, the queue ends up using too much space.  Instead, I'd rather keep the queue small, and find a way to produce all valid programs efficiently (more efficiently than just trying all program text).  What is a good strategy to generate all valid programs for a simple stack language?

UPDATE The language is guaranteed to halt (and is of course not Turing complete).

UPDATE: The approach I am working on is as follows:

Observe that, for certain program fragments, nothing that can be appended to them will make them valid
Define an ordering over each token that may appear in a program.
Define a "mayBeAppendedToToMakeAValidProgram" over a incomplete program.
For n = 0 to infinity:
Start with a program of n tokens; set each token to the first
Increment token-0 until mayBeAppendedToToMakeAValidProgram(token-0)
Increment token-1 until mayBeAppendedToToMakeAValidProgram(token-0 + token-1)
Etc. until the last token
Increment the last token until the program is valid; test that program
On to the next one

I can give you a answer about the principles.

Find a computable bijection between your programs and the natural numbers. In essence, you would construct an admissible numbering. Then, you can just iterate over the naturals, compute the program corresponding to each number and perform your checks. You do not need to store any programs but the one under consideration.

The challenge is, of course, to find this bijection; it will depend on your language. If that helps you can relax injectivity; it is not necessary but duplicates will have performance impacts, obviously.

One concrete idea is: represent your language by a context-free grammar. Enumerate left-derivations along rule precedences, going from one program to the next using backtracking. It may even be possible to encode the derivation process in numbers, yielding a mapping as mentioned above.


Generating function of non-regular language Let's say $\sum_{n \ge 1} a_{n}x^n$ is generating function for regular language $L$. $a_{n}$ is number of words with length $n$.

Find an example of generating function which isn't correspond for any regular language.

My attempt : I use the fact for any regular language there is exists $n_{0}$ $\lambda_{i}$ and $p_{i}$ : $a_{n} = \sum_{i} \lambda_{i}^{n} p_{i}$ and as example get language with $a_{n} = C_{n}$ , where $C_{n}$ is Catalan number. My teacher said that's not obvious and told me to get easier example. But I don't know useful criteria to find an example with contradiction about regularity. Any ideas?

If we apply a substitution that maps all letters of the alphabet to the same letter, we obtain a unary language. This shows that if $L$ is regular, then the set $\{n : L \cap \Sigma^n \neq \emptyset\}$ is eventually periodic. This shows that $\sum_{n=0}^\infty x^{n^2}$ corresponds to no regular language, for example.


Cryptography: Play Fair cipher In our university, we were taught that since all 26 letters cant be placed together in a $5*5$ square matrix we must put $i/j$ together like this represented in the below diagram. Here our key is $monarchy$, now what would have happened if the key contained $j$ in itself? say if the key would have been $jargon$ then how do we accommodate the one extra letter which should have been left?

When using the convention that i and j are in the same square then they are for all intents and purposes regarded as the exact same letter, both in the key and in the plaintext. In the ciphertext, whenever it is required to write 'i/j' you can choose which one to write, while introducing no ambiguity for the decoder (in order to make the ciphertext 'look more random' it is probably best to flip a coin).

In particular, the Playfair tableau with key 'jargon' is the same as the tableau with key 'iargon': both have 'i/j' in the upper left-hand corner. HOWEVER, if you use an online solver tool it may be (the first site I checked had this implem bug) that j is not parsed, and the tableau is built as if the key were 'argon'; this is a (common?) implem bug though.

Note also that there other conventions than placing i and j in the same square.


Why are there so many programming languages? I'm pretty fluent in C/C++, and can make my way around the various scripting languages (awk/sed/perl). I've started using python a lot more because it combines some of the nifty aspects of C++ with the scripting capabilities of awk/sed/perl.

But why are there so many different programming languages ? I'm guessing all these languages can do the same things, so why not just stick to one language and use that for programming computers ? In particular, is there any reason I should know a functional language as a computer programmer ?

Some related reading:

Why new programming languages succeed -- or fail ?
is there still research to be done in programming languages?

Programming languages evolve and are improved with time (innovation).

People take ideas from different languages and combine them into new languages. Some features are improved (inheritance mechanisms, type systems), some are added (garbage collection, exception handling), some are removed (goto statements, low-level pointer manipulations).

Programmers start using a language in a particular way that is not supported by any language constructs. Language designers identify such usage patterns and introduce new abstractions/language constructs to support such usage patterns. There were no procedures in assembly language. No classes in C. No exception handling in (early) C++. No safe way of loading new modules in early languages (easy in Java). No built-in threads (easy-peasy in Java).

Researchers think about alternative ways of expressing computations. This led to Lisp and the functional language branch of the language tree, Prolog and the logic programming branch, Erlang and other actor-based programming models, among others.

Over time, language designers/researchers come to better understand all of these constructs, and how they interact, and design languages to include many of the popular constructs, all designed to work seamlessly together. This results in wonderful languages such as Scala, which has objects and classes (expressed using traits instead of single or multiple inheritance), functional programming features, algebraic data types integrated nicely with the class system and pattern matching, and actor-based concurrency.

Researchers who believe in static type systems strive to improve their expressiveness, allowing things such as typed generic classes in Java (and all of the wonderful things in Haskell), so that a programmer gets more guarantees before running a program that things are not going to go wrong. Static type systems often impose a large burden on the programmer (typing in the types), so research has gone into alleviating that burden. Languages such as Haskell and ML allow the programmer to omit all of the type annotations (unless they are doing something tricky). Scala allows the programmer to omit the types within the body of methods, to simplify the programmer's job. The compiler infers all the missing types and informs the programmer of possible errors.

Finally, some languages are designed to support particular domains. Examples include SQL, R, Makefiles, the Graphviz input language, Mathmatica, LaTeX. Integrating what these languages' functionalities into general purpose languages (directly) would be quite cumbersome. These languages are based on abstractions specific to their particular domain.

Without evolution in programming language design, we'd all still be using assembly language or C++.

As for knowing a functional programming language: functional languages allow you to express computations differently, often more concisely than using other programming languages. Consider about the difference between C++ and Python and multiply it by 4. More seriously, as already mentioned in another answer, functional programming gives you a different way of thinking about problems. This applies to all other paradigms; some a better suited to some problems, and some are not. This is why multi-paradigm languages are becoming more popular: you can use constructs from a different paradigm if you need to, without changing language, and, more challengingly, you can mix paradigms within one piece of software.


Relation between problems and algorithms From Wikipedia

  a computational problem is understood to be a task that is in principle amenable to being solved by a computer (i.e. the problem can
  be stated by a set of mathematical instructions). Informally, a
  computational problem consists of problem instances and solutions to
  these problem instances. For example, primality testing is the problem
  of determining whether a given number is prime or not. The instances
  of this problem are natural numbers, and the solution to an instance
  is yes or no based on whether the number is prime or not.

  ... A key distinction between analysis of algorithms and computational
  complexity theory is that the former is devoted to analyzing the
  amount of resources needed by a particular algorithm to solve a
  problem, whereas the latter asks a more general question about all
  possible algorithms that could be used to solve the same problem.

So a problem can be solved by multiple algorithms.

I was wondering if an algorithm can solve different problems, or can only solve one problem? Note that I distinguish a problem and its instances as in the quote.

I think the question is more philosophical than scientific, and indeed, as @raphael mentioned, the problem is in the definition of a "Problem".

Algorithm, in the simplest way, is a function (a mapping).
It gets an input (instance) $in \in I$ and gives an output $out \in O$.
For any instance $in$ there is only a single output $out=\mathsf{ALG}(in)$.
Therefore, the algorithm solves only a single problem — that is, it defines only a single mapping from $I$ to $O$.

True, if you have two problems (mappings), $P_1 : I_1 \to O_1$ and $P_2: I_2 \to O_2$ we can construct a "single" algorithm that solves "both". It gets as an input the pair $(in,type)$. If $type=1$ it returns $P_1(in)$ and otherwise it returns $P_2(in)$.

But again, this fancy algorithm can be seen as solving a single problem from the domain $(I_1\cup I_2) \times \{1,2\}$ into $O_1 \cup O_2$.


An algorithm for effecient resource redistribution For those who think visually, say I've got 5 warehouses with a current stock level of # of fish, and a target level for each.  How do I achieve the new target levels in as few truck shipments as possible?

Or given an array A{250, 150, 45, 205, 350}, how can it be transformed to {200, 200, 150, 320, 130} in as few transfers as possible?  Moving 50 from A[0] to A[1] would be an efficient first move.
I'm sure I could muddle through this and come up with something, but I'm also sure this problem has already been solved by people smarter than me.  And it's important to me that it be correct and as efficient as possible.  This is a little outside my normal work, and I'm not sure how to search for something like this (I couldn't find anything).
Thanks much!

Update:
An initial thought ... find the warehouse with the biggest deficit, then find the one with the biggest (or closest matching?) surplus, do the shipment, then repeat.  Seems like that would work, but I'm not sure if there's a more elegant or efficient solution.  I'll add an answer once I've got the code working.

There is no polynomial-time algorithm unless $\mathsf{P}=\mathsf{NP}$. Here is a proof.
Let $d_1, d_2, \cdots, d_n$ be the change for each warehouse to reach its target level. For the example in the question, they are $200-250=-50$, $\ 200-150=50$, $\ 150-45-150=105$, $\ 320-205=115$, $\ 350-130=-220$. We assume that sum of all $d_i$'s is 0; otherwise, it is not possible.

Proposition: The target levels can be reached in less than $n-1$ steps if and only if there exist some $d_i$'s but not all of them whose sum is $0$.
Proof.

"$\Leftarrow$". Suppose, WLOG, $d_1+d_2+\cdots+d_k=0$ for some $1\le k\lt n$. Suppose $k\ge2$. Then we can find $d_i\le0\le d_j$ for some $1\le i,j\le k$. We can transfer $\min(-d_i, d_j)$ fish from warehouse $i$ to warehouse $j$. Then either warehouse $i$ or warehouse $j$ reaches its target level. Now we can apply math induction.

"$\Rightarrow$". Suppose the target levels can be reached in some $k$ steps, $k\lt n-1$. At most $k+1$ warehouses are involved in those $k$ steps. The sum of changes for those warehouses must be 0. Note that $k+1<n$.  $\checkmark$.

Let us consider the following warehouse-distribution problem, which is an easier version of the original warehouse-distribution problem.

Given $n$ warehouses with some fish and their target levels of fish,
can we use less than $n-1$ transfers to reach their target levels?

Let us recall, as explained in the Wikipedia article subset sum problem, it is $\mathsf{NP}$-hard to decide, given a multiset of integers, whether there is a non-empty subset whose sum is zero.
Given a multiset of integers $f_1, f_2, \cdots, f_n$, we can construct the following instance of warehouse-distribution problem. Let $f=\sum_{i=1}^n|f_i|$. Let $n+1$ warehouses have $g_1, g_2, \cdots, g_{n+1}$ fish respectively, where $g_1=f+f_1$, $g_2=f+f_2$, $\cdots$, $g_n=f+f_n$ and $g_{n+1}=nf-\sum_{i=1}^nf_i$. The target for each warehouse is $f$ fish. We can verify easily, thanks to the proposition above, that we can use less than $n$ transfers to reach all target levels if and only if there is a non-empty sub-multiset of all $f_i$'s whose sum is zero. Hence, the warehouse-distribution problem is at least as hard as the subset sum problem.

Since a polynomial-time algorithm is unlikely, let me give an algorithm of time-complexity about $O(n2^n)$.

Compute the changes, $d_1, d_2, \cdots, d_n$.

For each subset $S$ of $\{1,2,\cdots, n\}$, compute $\sigma(S)=\Sigma_{i\in S}d_i$. When $\sigma(S)=0$ and $S$ is non-empty,  $S$ will be called a zero-set.

For each subset $S$, let $p(S)$ be the biggest number of disjoint subsets of $S$ that are zero-sets. $p(\emptyset)=0$. For non-empty $S$, use the following recurrence relation to compute $p(S)$. A proof of the recurrence relation is given later.
$$p(S) = \begin{cases}
      \max_{a\in S} p(S\setminus\{a\}) & \text{if }S\text{ is not a
 zero-set} \\
      1 + \max_{a\in S} p(S\setminus\{a\}) & \text{if }S\text{ is a
 zero-set} \\
\end{cases}$$
where $S\setminus\{a\}$ means $S$ without $a$.

The answer is $n-p(\{1,2,\cdots,n\})$.

First, for any subset $S$, we have
$$\max_{a\in S} p(S\setminus\{a\})\le p(S)\le 1 + \max_{a\in S} p(S\setminus\{a\}).$$
Suppose $S'$ is a subset of $S$. Since any disjoint subsets of $S'$ can be considered as disjoint subsets of $S$, we have $p(S')\le p(S)$. In particular, for any number $a\in S$, we have $p(S\setminus\{a\})\le P(S)$.
Suppose $S_1, S_2, \cdots, S_{p(S)}$ be some disjoint subsets of $S$ that are zero-sets. Let $a\in S_1$. Then $S_2, S_3, \cdots, S_{p(S)}$ are also disjoint subsets of $S\setminus\{a\}$, i.e., $P(S)=1+(P(S)-1)\le 1+ p(S\setminus\{a\})$. $\quad\checkmark$.
Now, Let me explain the recurrence relation in the step 3 above.
There are two cases.

$S$ is not a zero-set.
Suppose $S_1, S_2, \cdots, S_{P(S)}$ are disjoint subsets of $S$ that are zero-sets. If the union of all these subsets is $S$, then $S$ must a zero-set as well, which is not true. So there is a number $a\in S$ that is not in any of $S_1, S_2, \cdots, S_{P(S)}$. That means all of $S_1, S_2, \cdots, S_{P(S)}$ are subsets of $S\setminus\{a\}$. That is, $P(S) \le P(S\setminus\{a\})$. So, $p(S) = \max_{a\in S} p(S\setminus\{a\}).$

$S$ is a zero-set.
Let $a\in S$. Suppose we have disjoint subsets $S_1, S_2, \cdots, S_d$ of $S\setminus\{a\}$ that are zero-sets. Let $S_{d+1}$ be all the numbers in $S$ but not in any of those subsets. $S_{d+1}$ contains $a$. $S_{d+1}$ is also a zero-set since $\sigma(S_{d+1})=\sigma(S)-\sigma(S_1)-\sigma(S_2)-\cdots-\sigma(S_d)=0$. Since $S_1, S_2, \cdots, S_{d+1}$ are disjoint subsets of $S$ that are zero-sets, $p(S) \ge 1 + d$. That means, $p(S)\ge 1 + \max_{a\in S} p(S\setminus\{a\}).$ So, $p(S) = 1 + \max_{a\in S} p(S\setminus\{a\}).$  $\quad\checkmark$.


References on comparison between quantum computers and Turing machines I was told that quantum computers are not computationally more powerful than Turing machines.
Could someone kindly help in giving some literature references explaining that fact?

What is actually the case is that anything a quantum computer can compute, a Turing machine can also compute. (This is without commenting at all on how long it takes the Turing machine to compute the function compared to a quantum computer.)

This is actually not difficult to see, provided you understand quantum computation. For a quantum circuit over a typical gate set, for example, the outcome is governed by a probability distribution, which is determined by the coefficients of a unitary matrix. That unitary matrix is just a matrix product of those of the gates, and can be computed — if you're patient enough — by a classical computer. So for sheer computability (as opposed to efficiency), there is no advantage to using quantum computers.

The whole challenge arising from quantum mechanics is to determine whether such coefficients can be computed efficiently, which is a more demanding problem than whether they can be computed at all.


What is the maximum number of classes resulting from partitioning by DFA as function of number of states? I was wondering whether it is possible (and if so, then how) to tell what is the maximum number of equivalence classes generated by a DFA as per Myhill-Nerode theorem (assuming it has no redundant transitions) as a function of number of accepting and rejecting states and cardinality of its alphabet.

My guess is that it should be something like $\log(n) \cdot |{\Sigma}|$, where $n$ is the number of states, since one could see this as tree of derivations created by something like left-regular grammar equivalent to the same automata, and classes would be the leafs of this tree.  But this is just a guess.

I'm not sure what you mean by classes, but if you mean Myhill–Nerode equivalence classes, then the classical construction shows that the (unique) minimal DFA has as many states as equivalence classes.


The reverse DFA is not working as expected Assume a regular language contains all the strings that are ended with "01". We can draw the following DFA for it:

And I reversed the DFA according to this answer (designing a DFA and the reverse of it)

I expected this DFA to accept all strings that start with "10" but it is not. What is my mistake in drawing the reverse DFA?

Answering my own question based on the comment by Hendrik Jan:

The reverse DFA is correct. It is just that it is not deterministic. It's an NFA, so we should follow all the paths possible. And if we do so, it will accept all the strings starting with "10".

Example: assume we want to test this string: "10001". and assume that states are named 1, 2, and 3 from the right. By following this path, the NFA accepts the input string: "1,2,2,2,3,3"


Why do some search trees store all the elements in leaves, while others don't? Why do some search trees store all elements in the leaves, while other search trees don't?
One difference that makes is whether a successful search may end up in an internal node.

For m-ary search trees, the former case will need more leaves and more heights than the latter. Is this the benefit of not storing all the elements in the leaves?

Is storing all the elements in the leaves only for looking consistent? Does it have some benefits?
Someone said that

  Contrary to what you said, in the three examples you gave, the internal nodes also contain values.

  In a B+ tree for example, all values are located in the leaves, the internal nodes only contains keys

  "This is interesting only when the data is separated in a key and some other value (as in a database). This allows more keys to go in the internal nodes, limiting the tree depth. When the nodes are on a slow medium, this limits the time needed to go to the data." But I don't quite understand that, because

when we choose to store records in the internal nodes, we don't need to store the actual records in the internal nodes, but can always store with each key a pointer to the actual records, so that we can save space to store more keys. So I don't understand why he said that "This allows more keys to go in the internal nodes".
as mentioned above, I guess storing elements in the leaves rather than also in internal nodes will make the search trees higher, so I don't understand why he said that storing all the elements in the leaves can "limit the tree depth".

For B-trees and 2-3 trees, why do some references define them so that all the elements are stored in the leaves, while other references don't? Note that 2-3 trees are special B-trees, according to Aho's book.

I just found that

the definitions of 2-3 trees and B trees in Aho's Data Structures and    Algorithms store all the elements in the leaves, so that a
successful    search always end up in a leaf

But the examples of 2-3 trees and B trees in Wikipedia and also    in wikipedia and in Sedgewick's Algorithms (also
see the    first picture below) and in CLRS (see the second picture
below) store    only some elements in the leaves, so that a
successful search may end    up in an internal node.

For binary search trees, why all the references define them so that not all elements are stored in the leaves?

I haven't seen any reference that define binary search trees with all elements defined in the leaves, or am I missing it?

Can Huffman trees be viewed as binary search trees where all the elements are defined in the leaves?
Is balancing the only or most important aspect where 2-3 trees improves over binary search trees?

From the above questions, I mentioned that some references define 2-3 trees  so that all the elements are stored in the leaves, while others don't, and within my readings, binary search trees are always defined so that not all the elements are stored in the leaves. Is whether search trees store all elements in the leaves  an important aspect to distinguish between 2-3 trees and binary search trees, as important as the balancing aspect?

Thanks.

The point is that often data is bulky and moreover of variable size (i.e., a full student record) while the keys needed to locate the data (name, enrollment number) is small and fixed size. Different requirements, keep them separate.


AVL Tree or HashTable for storing relatively big data? I have been looking to implement a data structure for my project. I came across AVL tree and Hash Table. As I am a beginner so I'm in dilemma what data structure I use for large data. The main operation will be mostly searching through the database efficiently.

AVL Tree seems to be very good option to store around 120000 entries(object) of data and keep the search time to O(logn), however I stumble upon a perfect hashing concept. It states it expected the search time is constant O(1), if collision occur then it would use secondary hash function that will still have access time of O(1) if I'm not mistaken.

perfect hashing function according to Introduction to Algorithm by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stien is :-
h(k) = ((3k + 42) mod 101) mod size(number of enteries)

Data that I'm storing is from text file, converting each line into an object. All those objects will be inserted all at once in data structure. After that main operation I have to use is search through the data structure.

Bus -> street1 -street2- street3- destination, this line would be converted into an object. So search would be like return the route bus1 took to reach destination5.

Any suggestions which one would be more reliable and efficient for time and space complexity?

For search dominant operation, supported insert, delete, find only there are huge benefits in using the Hash Table.

the memory footprint is low, only colliding entries require pointer, one per entry while AVL requires two pointers per entry.
access time is expected $\mathcal O(1)$, say in the worst case 5, which gives one hash calculation and 5 equality tests while AVL has 25 full comparissons for 120000 entries in the worst case.
rehashing could be avoided with maximal capacity known in advance, otherwise it would be rare operation.

What would opt for AVL?

traversal queries, looking for ranges etc.
access to sorted data.
inexact queries, looking for nearest neighbour (at the cost of additional pointers).

By the way the perfect hash table is commonly refered to as having no collisions, which requires static setting, rehashing. What you refer to is probably dynamic perfect hashing, a two-tier scheme with guaranteed deterministic constant lookup.

If you have all data (or substantial amount) it is beneficial to sort data and create balanced tree to avoid inserting nodes one by one. (Something like DSW algorithm would help).
In that case the hash table may be constructed without collisions at all for initial data, leaving space for future elements and work really fast.

For the search part, none of the structures would help. If I understood correctly, your data is a graph, so both presented structures will help with indexing only and the Hash Table is the winner.

Sidenote:
To store compactly textual data something like Trie or Directed Acyclic Word Graph would be better. The edited part about search would require a graph, path finding algorithm and auxiliary indexing data structure, in your case probably Hash Table or DAWG used as map.


Complexity of a Turing Machine when changing its alphabet to binary I found in 'Computational Complexity: A Modern approach' Book the following statement that i dont quite understand its proof:

  For every f : {0, 1}∗ → {0, 1} and time-constructible T : N → N, if f is computable in time T(n) by a TM M using alphabet A, then it is computable in time 4log|A|T(n)by a TM M ̃ using the alphabet {0,1,Blank,◃}.

The proof is on the link :

First Part of proof

Second Part

So basically if we have a running time of T(n) on a certain alphabet A and we wanna switch to binary.. we gonna have to multiply it by log(|A|) (log of base 2, the number of bits to represent an element from A) because every step will be multiplied by the number of bits used to represent the element.

But in the proof, starting from the second paragraph, i dont really understand what they say and how they end up with the '4' in '4log|A|T(n)'.

The first part the proof reads "To simulate one step of $M$, the machine $M^{\sim}$ will: (1) ... (2)... (3)... (4) and (5) ....". Can you see the factor of 4?

You have a good understanding regarding the factor $\log|A|$.  Let us take a close look at the steps in each stage of $M^{\sim}$ above. There are $\log|A|$ steps in stage (1) and in stage (5). However, there is only one step in stage (2) or stage (3) or stage (4). So there are less than $2\log|A|$ steps in stage (2), (3) and (4) combined, assuming $\log|A|\gt1$. If $\log|A|=1$, we can just let $M^\sim$ be $M$ and we are done. So there are less than $\log|A|+\log|A|+2\log|A|=4\log|A|$ steps of $M^\sim$ for one step of $M$.

The second part of the proof is justifying that the stage (2), (3) or (4)  can be done in one step of machine $M^{\sim}$. It explains the power of larger registers. It points out that we can use more states in $M^\sim$ to identify the possibly much more situations ("states" could have been a better word had we not reserved that word for Turing machine) of the machine. Take your time. You will understand.


In which O-class does my Θ-result belong? In a multiple-choice test, I'm asked to solve the recurrence $T(n)=2T(n/2)+n/2$.
I've done this using the master theorem: $f(n)=n/2$, $a=2$, $b=2$, so we're in the second case and $T(n)=\Theta(n\log n)$.

But the possible answers are $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$ and $O(n^2/\log n)$ and more than one may be correct. What do I do now?

You've solved the recurrence more precisely than the test-setter was expecting you to.  You know that $T(n)=\Theta(n\log n)$, which means that $T(n) = O(n\log n)$ and $T(n) = \Omega(n\log n)$, and that gives you the answer.

(By the way, I didn't check that you solved the recurrence correctly, but you can do that yourself. Answer checking is off-topic here, and you didn't ask for it, so I focused on the rest of your question.)


How to prove the language of contractible strings is context-free but not regular? How to prove this language is context-free but not regular? I can't figure out it.

A string is contractible if there is a sequence of contractions which result in the empty string, where a contraction is the removal of a sequence of length 2 or more consecutive identical symbols. When a contraction is applied it must contract a maximal length sequence of
consecutive identical symbols.
For example, $abaaababb$ is contractible as witnessed by the following sequence of contractions,
$$ab\underline{aaa}babb \rightarrow abba\underline{bb}\rightarrow a\underline{bb}a \rightarrow \underline{aa}\rightarrow \epsilon$$
Let $L$ be the language of contractible strings over the alphabet ${a, b}$. Prove that $L$ is a context-free language and that $L$ is not a regular language.

For $i \ge 0$ consider the word $x_i = (ab)^i$.
For $0 \le i < j$, $(ba)^i$  is a distinguishing extension for $x_i$ and $x_j$. Indeed $x_i(ba)^i \in L$ but $x_j(ba)^i \not\in L$. By the Myhill–Nerode theorem $L$ is not regular.
Given a non-empty word $w \in L$,
$w$ can be written as $\alpha_1 \alpha_2 \dots ... \alpha_k$ where (i) each $\alpha_i$ is a non-empty contractible string that starts and ends with the same symbol, and (ii) the first symbol of $\alpha_{i+1}$ differs from the last symbol of $\alpha_i$.
Each $\alpha_i$ starting with some symbol $x$ can be written, in turn, as
$x \beta_1 x \beta_2  \dots \beta_h x$, where $h \ge 1$, all $x$ are exactly the characters removed in a single contraction step, and all $\beta_i$ are (possibly empty) substrings that are contracted before contracting $x$. It follows that each non-empty $\beta_i$ must start and end with the unique symbol in $\{a,b\} \setminus \{x\}$.
Consider hen the following context-free grammar $G$, in which $A$ (resp $B$):
generates a contractible string starting and ending with $a$ (resp. $b$):$$
S \to \varepsilon \mid S' \mid S''\\
S' \to A \mid AB \mid ABS' \\
S'' \to B \mid BA \mid BAS'' \\
A \to aa \mid aBa \mid aA \mid aBA \\
B \to bb \mid bAb \mid bB \mid bAB
$$
The above observations imply that $L(G) \supseteq L$, while
a parse tree for $w$ (according to $G$) provides a sequence of contraction for $w$, showing that $L(G) \subseteq L$.


how many boolean functions exist that satisfy the condition How many boolean functions exist that satisfy the following condition?
$$\neg f(x_1,x_2,x_3,....,x_n) = f(\neg x_1, \neg x_2,...,\neg x_n)$$

If we did not have this constraint, there would initially be $2^{2^n}$ possible boolean functions on $n$ boolean variables. We have $2^n$ unique inputs that we can either map to a 1 or 0 for any of them.

Now for this problem, we need to map a subset of those $2^n$ inputs because the rest will be implicitly mapped. For instance if we map $f(x_1, \neg x_2, \neg x_3) = 0$, this will implicitly map $f(\neg x_1, x_2, x_3) = 1$. This means only a subset of the $2^n$ inputs can be uniquely mapped, the rest will be implicitly mapped as described. For this, we need to determine how many pairs of inputs exist such that we have: $$(\{\ell_1, \ell_2, \ldots \ell_n\}, \{\neg \ell_1, \neg \ell_2, \ldots, \neg \ell_n\})$$ where $\ell_i$ is a literal (positive or negative) containing variable $x_i$. Intuitively, we should know that each pair contains 2 sets of $n$ variables so there should be $2^n / 2 = 2^{n-1}$ pairs possible. Another way to think about it would be to hold one variable constant positive, let's say $x_1$. We then define a new function: $$f_{x_1}(x_2, x_3, \ldots, x_n) = \ldots$$
In this function we "hold" $x_1$ to be positive so that we're only ever setting one of the sets in these pairs that we have described, thus we only have $2^{2^{n-1}}$ possible functions $f_{x_1}$. With this, we can now define $f$ pretty easily:

$$f(x_1, \ell_2, \ell_3, \ldots \ell_n) = f_{x_1}(\ell_1, \ell_2, \ldots, \ell_n)$$

$$f(\neg x_1, \neg \ell_2, \neg \ell_3, \ldots \neg \ell_n) = \neg f_{x_1}(\ell_1, \ell_2, \ldots, \ell_n)$$

We basically use $x_1$ to say "we're looking at the positive instance of this input" vs "we're looking at the negative instance of this input". Then this configuration of $f_{x_1}$ will ensure they are opposite. Consider the following example on 3 variables:

$$\begin{array}{|c|c|c|c|}
\hline x_1 & x_2 & x_3 & f_{x_1}(x_2, x_3) & f_{x_1}(\neg x_2, \neg x_3) & f(x_1, x_2, x_3) \\
\hline 0 & 0 & 0 & 1 & 0 & 1\\
\hline 0 & 0 & 1 & 1 & 1 & 0\\
\hline 0 & 1 & 0 & 1 & 1 & 0\\
\hline 0 & 1 & 1 & 0 & 1 & 0\\
\hline 1 & 0 & 0 & 1 & 0 & 1\\
\hline 1 & 0 & 1 & 1 & 1 & 1\\
\hline 1 & 1 & 0 & 1 & 1 & 1\\
\hline 1 & 1 & 1 & 0 & 1 & 0\\
\hline
\end{array}$$

With this we can see $f_{x_1}$ is clearly a function over $n-1$ variables and thus there are $2^{2^{n-1}}$ possible functions that satisfy this.


Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one What is the complexity of this problem

EULERIAN ARC REVERSAL
Input: a directed graph $G(V,A)$ and an integer $k$
Output: YES if $k$ arc reversals are enough to transform $G$ into an Eulerian graph, otherwise NO

Given an arc $(u,v)\in A$, an act of reversing it will result in the opposite arc $(v,u)$ while the original arc $(u,v)$ will disappear as well.

There are related meta-results on node and edge deletions by Yannakakis. So, I wonder what we can do if the actions are changed from deletion to reversals.
If instead of using Eulerian property, we use Hamiltonian property then we immediately get an NP-complete problem by setting $k=0$.

This problem can be solved in polynomial time.

For such a graph $G=(V,A)$, turn it into a new weighted undirected graph $G'$ as follows, where we denote respectively by $d^{\mathrm{in}}(v)$ and $d^{\mathrm{out}}(v)$ the in-degree and out-degree of $v$.

For every $v$, we have that $d^{\mathrm{in}}(v)- d^{\mathrm{out}}(v)$ is even. Otherwise, the graph cannot be changed to an Eulerian graph.

For each edge $(u,v)\in A$, construct two vertices $u_{\rightarrow v}, v_{u\rightarrow}$ and an edge with weight $1$ between them.
For each vertex $v\in V$, add an edge with weight $1+\epsilon$ (where $\epsilon$ is a small positive number that depends on the size of the graph) between $v_{u_1\rightarrow}$ and $v_{\rightarrow u_2}$ for all $u_1,u_2\in V$ such that $(u_1,v),(v,u_2)\in A$.
For each vertex $v\in V$, construct $\left|d^{\mathrm{in}}(v)- d^{\mathrm{out}}(v) \right|/2$ vertices $v_1,v_2,\ldots$. If $d^{\mathrm{in}}(v)\ge d^{\mathrm{out}}(v)$, add an edge with weight $1$ between $v_i$ and $v_{u\rightarrow}$ for all $i$ and $u\in V$ such that $(u,v)\in A$. Otherwise, add an edge with weight $1$ between $v_i$ and $v_{\rightarrow u}$ for all $i$ and $u\in V$ such that $(v,u)\in A$.

Recall that a directed graph is Eulerian iff each vertex has equal in-degree and out-degree, assuming the underlying undirected graph is connected. Now we can see finding a minimum number of edges to reverse in $G$ is equivalent to finding a maximum weight matching in $G'$, by reversing all edges $(u,v)$ such that $u_{\rightarrow v}$ is matched with $v_{u\rightarrow }$ in the maximum matching.


Is the Wall-Follower Algorithm in P? Is the wall-follower algorithm a poly-time algorithm (for Perfect Mazes)?

In particular, are there poly time algorithms for solving the Perfect Maze problems?

A perfect maze has the following properties:

no inaccessible areas and is simply connected.
no closed loops
one and only one path from any point to any other point.
the maze has exactly one solution.

Yes, there is a polynomial-time algorithm for solving perfect mazes: depth-first search solves them, and runs in polynomial time.  Actually, depth-first search is more general, as it can handle loops and other structures, too.

Breadth-first search also works, and will give you the fastest way out of the maze, but is only implementable on a computer given the full description of the maze.  In contrast, depth-first search can be implemented by a human with a piece of chalk and a ball of string -- the piece of chalk allows you to mark rooms as visited, and the ball of string lets you simulate the stack.


Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$ The recurrence form of bubble sort is $T(n)=T(n-1)+ n- 1$

How can I prove by induction that this is $\Omega(n^2)$?

I'm stuck with $T(n+1) \geq cn^2 + n = n(cn+1)$

Assuming $T(1)=1$, you can show by induction that $T(n) = \frac{n(n-1)}{2} + 1$.

The base case is trivial since $T(1) = 1 = \frac{1 \cdot 0}{2} + 1$.

As for the inductive step, suppose that the claim holds up to $T(n)$.
$\begin{align*}
T(n+1) &= T(n) + (n+1) - 1 =\frac{n(n-1)}{2} + 1 + n  \\
 &= \frac{n^2 -n +2n}{2} + 1 = \frac{n^2 + n}{2} + 1 = \frac{n(n+1)}{2} + 1 \\
&= \frac{(n+1)((n+1) - 1)}{2} + 1.
\end{align*}
$


Hardness of ambiguity/non-ambiguity for context-free grammars A grammar is ambiguous if at least one of the words in the
language it defines can be parsed in more than one way. A simple example of an ambiguous grammar
$$
   E \rightarrow E+E \ |\ E*E \ |\ 0 \ |\ 1 \ |\ ...
$$
because the string 1+2*3 can be parsed as (1+2)*3 and 1+(2*3).  For
context free grammars (CFGs) ambiguity is not decidable [1, 2]. This implies that non-ambiguity is also not decidable. Moreover, at least one of ambiguity and
non-ambiguity cannot even be recursively enumerable, for otherwise
ambiguity of a given CFG $G$ could be decided by running the
enumeration of ambiguity and non-ambiguity together and seeing which
one contains $G$ (and one of them must).

So which problem is harder in this sense? Ambiguity or non-ambiguity?

D. G. Cantor, On The Ambiguity Problem of Backus Systems.
R. W. Floyd, On ambiguity in phrase structure languages.

Ambiguous grammars can be enumerated, since each ambiguous grammar has a proof of ambiguity, namely a word with two different parses.


Capacity of a discrete memoryless channel For an integer $I$, the input-output relationship of a discrete memoryless channel is given by:

$Y = X + Z$ (mod $I$, i.e. sum indicates a modular addition)

where $I ≥ 2$,
and

• $X$ is an integer chosen from the alphabet $A_x = \{1,\dots,2I\}$,

• $Z$ is noise which is a uniform Bernoulli random variable. This means that $A_z = \{0,1\}$, and

$$\Pr\{Z = 0\} = \Pr\{Z = 1\} = 0.5.$$

How can we calculate the capacity of this channel?

This answer assumes that $Y = X + Z \bmod 2I$, which seems more reasonable than the current $Y = X + Z \bmod I$, which would mean that $X$ is effectively chosen from an alphabet of size $I$ rather than $2I$.

The capacity is $\log I$.

For the upper bound,
$$
I(X;Y) = H(Y) - H(Y|X) = H(Y) - H(Z) = H(Y) - 1 \leq \log(2I) - 1 = \log I.
$$

For the lower bound, if $X$ is chosen uniformly among the $I$ values $1,3,\ldots,2I-1$ then you can recover $X$ from $Y$ (without any error!), and so $I(X;Y) = H(X) = \log I$.


Show that a language belongs to the polynomial hierarchy I think the following exercise is to "warm up", but nevertheless it's quite difficult for me:

  Let $k \in \mathbb{N}$ and let $L \in \Sigma_k$. Show that also $L^{*} \in \Sigma_k$.

The following details from my lecture notes seem to be useful:

Notation. Let $n \in \mathbb{N}$.

We write $\exists_n y. \varphi(y)$ for $\exists y \in \Sigma^{*}.|y| \le n \wedge \varphi(y)$.

We write $\forall_n y. \varphi(y)$ for $\forall y \in \Sigma^{*}.|y| \le n \Rightarrow \varphi(y)$.

Theorem.

$L \in \Sigma^P_i \Leftrightarrow$ there is a language $A \in P$ and a polynomial $p$ so that: $x \in L \Leftrightarrow \exists_{p(|x|)}y_1 \forall_{p(|x|)}y_2 \exists_{p(|x|)}y_3 .../\forall_{p(|x|)}y_i (x,y_1,y_2,...,y_i) \in A$

Unfortunately I don't see the solution of the "puzzle". Can somebody please help me a little bit (despite the fact that it's weekend)?

Let me assume your are familiar with the oracle-version of the polynomial hierarchy. Thus, if $L\in \Sigma_k$, then there exists a (non-deterministic polytime) Turing machine $M$ with oracle $\Sigma_{k-1}$.

To show that $L^*$ is also in $\Sigma_k$ we explain how one could build a new non-deterministic polytime Turing machine $M^*$ with oracle $\Sigma_{k-1}$ that accepts $L^*$. The key idea is, that we use the (simulation) of $M$ as a sub-module for $M^*$.

The machine $M^*$ works as follows. It guesses a partition of the input $w$ into some words $u_1u_2\cdots u_k$. Then it runs the simulation for $M$ for every $u_i$. If the simulation verifies that all $u_i\in L$ then $M^*$ accepts, otherwise it rejects. Clearly $M^*$ accepts $L^*$ and uses only the oracle $\Sigma_{k-1}$. What is left to check is if $M^*$ runs in polytime. The running time of $M^*$ is dominated by
$$t_M(|u_1|)+t_M(|u_2|)+\cdots+ t_M(|u_k|)\le t_M(n)+t_M(n)+\cdots+ t_M(n)\le n \cdot t_M(n),$$
for $n=|w|$. Since $t_M(n)$ is a polynomial, we have that $n\cdot  t_M(n)$ is a polynomial as well.


Flipping all incoming/outgoing edges from a vertex in a DAG I'm working on a problem where I have a directed acyclic graph and I need to repeatedly flip all incoming (or outgoing, or both incoming and outgoing) edges from a single vertex. I think that resulting graph is still a DAG. Am I correct?

This doesn't hold if we flip both outgoing and incoming edges as shown by @Yuval Filmus.

Here is my try of a proof by contradiction for only flipping outgoing of incoming edges (sorry if it's too informal):

After flipping all incoming(outgoing) edges from vertex v in a DAG G, we get another graph that is not a DAG (it has a cycle).
Since we only changed the direction of the vertices incident to v, the only way we loose the acyclic property is if there is a new cycle going through vertex v.
Since we flipped directions of all incoming(outgoing) edges from vertex v, all edges incident to vertex v are now outgoing(incoming), so it is not possible for any cycle to go through vertex v, which contradicts 2.


What is a reducible flow graph? What is a reducible flow graph?   sorry if this is a stupid question but I'm having trouble finding an answer.
Also multiple equivalent definitions and some motivation would be nice too.

This blog post summarises the situation well my opinion, but let me go through some of your concerns:

Reducible is NOT equivalent to acyclic: consider a path $x\rightarrow y\rightarrow z\rightarrow w$ with a loop from $z$ to $y$. Then there is an SCC $\{y,z\}$ so it is not acyclic. But it is reducible because the SCC $\{y,z\}$ has a single entry point y. Notice how this corresponds to a program with a while/for loop. On the other hand, if you consider a path $x\rightarrow y\rightarrow z\rightarrow w$ with again a loop $z\rightarrow y$ but also a forward jump $x\rightarrow z$. Not this is not reducible anymore because the SCC $\{y,z\}$ has two entry points: $y$ can be entered from $x$, but $z$ can also be entered from $x$. This intuitively corresponds to a program like that:

x: if <some condition> goto z
y: do { <instruction>
z: }while(<cond condition}
w: end

Notice how there is no way to jump to $z$ without a goto, this is the point of reducibility and it corresponds to well-structured code without goto.

Concerning the back edges, if you take the counter-example for above, notice that there are two different ways to explore this tree in a DFS:

from $x$, explore $z$ then $y$ and $w$: in this case the edge $z\rightarrow y$ is part of the spanning tree built by the DFS. But $z$ does not dominate $y$ because the path $x\rightarrow y$ does not go through $z$.
from $x$, explore $y$ then $z$ then $w$: in this case the edge $y\rightarrow z$ is part of the spanning tree built by the DFS. But $y$ does not dominate $z$ because the path $x\rightarrow z$ does not go through $y$.

Maybe the source of your confusion is that domination is related to the initial vertex $x$, and not to the DFS. Recall that a vertex $y$ dominates a vertex $z$ if every path from the initial vertex to $z$ goes through $y$.


Multiple paths for a accepting string in NFA? If a string(w) is accepted by an NFA, then corresponding to w,
can there be multiple paths each starting from the start state and ending at an accepting state?

Yes, there can be many paths from the starting state to the ending state. It is not too difficult to cook up many trivial examples of when this happens, for instance

Clearly accepts the string $ab$ but it can go through either $s1$ or $s2$.

However, in DFA's this will never happen because at each state there is only a single possible transition for each character, and those fixed transitions uniquely determine the path.


negative weight cycle detection using dijkstra's algorithm Can we store a struct in place of vertex.
struct {
int v, update_count;
}

run dijkstra's algorithm and whenever a node is updated we will increase update_count value. If update_count value is greater than V(no of nodes) we will know that there is negative weight cycle. Is this a viable solution.

No. In a graph with $n$ nodes, Dijkstra's algorithm never updates a node more than $n-1$ times, so your test will never change anything. More fundamentally, negative-weight edges or cycles don't cause Dijkstra to get into infinite loops; they just make it give wrong answers in some cases.

This answer on Stack Overflow gives more detail.


What is the relationship between two definitions of Turing-computability of a partial function? When one wants to know that whether a partial function $f \colon \Sigma^{*} \supsetneq \mathrm{dom}(f) \rightarrow \Sigma^{*}$ is Turing-computable, there are two methods that I think they are both useful.

We can define a total function $\bar{f}$ such that
$$ \bar{f}(x) = \left\{
\begin{aligned}
&f(x),&x \in \mathrm{dom}(f) \\
&\bot,&x \not\in \mathrm{dom}(f) \\
\end{aligned}
\right.$$
Thus, $f$ is Turing-computable if $\bar{f}$ is Turing-computable by a TM using $\bar{\Sigma} = \Sigma \cup \{ \bot \}$.
(Some answers use this definition. see [1] and [2])
Let $M$ be a TM, and We say $f$ is Turing-computable by $M$ if
$$M(x) = \left\{
\begin{aligned}
&f(x),&& x \in \mathrm{dom}(f) \\
&\bot,&&x \not\in \mathrm{dom}(f) \\
\end{aligned}
\right.$$
where $M(x) = \bot$ means that $M$ never halts on $x$. (This definition is introduced in my books.)

These two definitions are not equivalent, since $M$ can computes some functions whose domain is Turing-recognizable instead of Turing-decidable in sense of definition 2.

I want know that is the definition 2 more powerful? In another word, if $f$ is Turing-computable in sense of definition 1, can we prove that it is also Turing-computable in sense of definition 2?

Definition 1 is incorrect. It does not define the notion of partial computable function correctly. Definition 2 is correct.

Proposition: A partial function $f$ is computable according to your definition 1 if, and only if, it is a partial computable function whose domain $\mathrm{dom}(f)$ is a computably decidable set.

Proof.
Suppose $f$ is computable according to definition 1. Then for every $n \in \mathbb{N}$, we have $n \in \mathrm{dom}(f)$ if, and only if, $\bar{f}(n) \neq \bot$. So we can decide whether $n \in \mathrm{dom}(f)$.

Conversely, suppose $f$ is a partial computable function whose domain $\mathrm{dom}(f)$ is decidable. Then $\bar{f}$ is computable because we can compute it like this: given input $n$, if $n \in \mathrm{dom}(f)$ then output $\bot$, otherwise output $f(n)$. $\Box$


Do "compiler" and "assembler" correspond to frontend and backend phases of a compiler? In Compilers: Principles, Techniques, and Tools (2nd Edition) 2nd Edition
by Alfred V. Aho (Author), Monica S. Lam (Author), Ravi Sethi (Author), Jeffrey D. Ullman (Author) , Figure 1.5 gives a language processing system, and Figure 1.6 shows the phases of a compiler. In Figure 1.6, if I am correct, a compiler has a front end (the first four phasesin Figure 1.6) and a backend (the last three phases "machine independent code optimizer", "code generator" and "machine dependent code optimizer" in Figure 1.6).

Literally by the names, the "compiler" in Figure 1.5 should correspond to the all 7 phases of a compiler in Figure 1.6.

But when I try to understand the individual phases of a compiler in Figure 1.6, I found that the book says:

  In App endix A, we put the techniques in this chapter together to build a
  compiler front end in Java. The front end translates statements into assembly-
  level instructions.

I was wondering:

Does the "backend" of the compiler in Figure 1.6 correspond to the "assembler" in Figure 1.5, and does the "frontend" of a compiler in Figure 1.6 correspond to the "compiler" in Figure 1.5?

Is the "intermediate repesentation" in Figure 1.6 the "assembly program" in Figure 1.5?

I guess the answers are all yes, but Yuval's reply mentions that an assembler does its job in only one way, while the books seems to say that each of the three steps in the backend can be done in more than one ways.

For Figure 1.5 in the book, let's take GCC as an example. In the following figure  from https://medium.com/@andrewlindburg/gcc-main-c-explained-1287d91b12a7, what phases does the compiler perform, and what does the assembler perform? Does "compiler CC1" perform the first four phases in Figure 1.6, and does the "assembler AS" perform the "assembler" in Figure 1.5 and to the backend (i.e. the last three phases) in Figure 1.6 in the book above?

Thanks.

Some compilers translate source code to assembler code in one or more phases, then use an assembler which will produce bit patterns of the instructions needed, and store them in a file that the linker understands.

Many compilers don’t do this. Producing code in assembler (human readable) form takes time. Parsing the human readable form, which is the first thing the assembler has to do, takes time again. Substantial time, actually. By generating the output directly that the linker needs, substantial time can be saved.

So usually there is no assembler involved.

And please note that (1) all these charts are just examples of how you could. The UCSD Pascal compiler had one single phase for compiling. And (2) gcc is more than a compiler. There is no iron rule how a compiler has to be organized. It's just a program, and the developers of that program figure out a good way to make the software work.

PS. Do “compiler” and “assembler” in Figure 1.5 and in the GCC figure respectively correspond to frontend and backend phases of a compiler in Figure 1.6? Absolutely not. The whole Figure 1.6 is just a more detailed view of the "Compiler" box in Figure 1.5.