Connected Graph: Select the minimum number of nodes such that the node and neighbor covers everything The problem is to select the minimum number of nodes from a graph such that, the selected nodes and their neighbors consists of all the nodes of the graph.

Any straight forward algorithm for this?
Repeatedly selecting the node with highest degree centrality doesn't work.

Thank you.

This depends on what you mean by "straight forward". There's a very straight forward brute force algorithm - it just doesn't have very good performance.

As to which problem this is, I would say it is Dominating Set. A vertex cover is also a dominating set, but not every dominating set is a vertex cover (i.e. a vertex cover might be significantly larger than a dominating set).

As for straight forward algorithms with good performance, you're not in a good spot.

It is NP-complete, so no polynomial-time algorithm unless $P = NP$.
It is $W[2]$-complete, so no $FPT$-algorithm unless $W[2] = FPT$.
It has no $n^{o(k)}$ algorithm unless the Exponential Time Hypothesis fails.
It is also $Log$-$APX$-complete, so no $o(\log n)$ approximation algorithm unless $P = NP$.

The best algorithm I know of at the moment is a $O(1.4969^{n})$ exact algorithm, but I don't think that would satisfy the "straight forward" criterion.

Even on restricted classes of graphs, you're unlikely to get good running times.

If you graphs happen to have very small treewidth, local treewidth, or are planar, then there are FPT algorithms, but again, they're not exactly "straight forward".

If you do want to solve Vertex Cover however, then it's still hard, but you have a few more possibilities:

Vertex Cover has a 2-approximation (find any maximal matching, and take all the vertices in the matching).
Vertex Cover is FPT, and has a number of kernelization algorithms of varying complexity (the more complex ones give significantly better running times). This paper contains details on a relatively simple one and this one the current best.
It is also amenable to a number of optimization approaches, and if you have access too something like CPLEX, then the ILP is easy to formulate, and relatively fast to solve.


Time complexity O(m+n) Vs O(n) Consider this algorithm iterating over 2 arrays (A and B)
size of A = n
size of B = m
Please note that m <= n
The algorithm is as follows
for every value in A:
    // code

for every value in B:
    // code

The time complexity of this algorithm is O(n+m)
But given that m is strictly lesser than or equal to n, can this be considered as O(n)?

Yes:
$n+m \le n+n=2n$ which is $O(n)$, and thus $O(n+m)=O(n)$

For clarity, this is true only under the assumption that $m\le n$. Without this assumption, $O(n)$ and $O(n+m)$ are two different things - so it would be important to write $O(n+m)$ instead of $O(n)$.


How does this reduction to prove undecidability account for epsilon? I have the following proof that the Empty String problem:
   ES = {M | M accepts $\epsilon$}
 is undecidable:

$f<M,w>$ = Construct a new machine $M_2$ such that:
$M_2$ = given input x erase x from the tape and run M on w:
if M accepts w $\longrightarrow$ accept
if M rejects w $\longrightarrow$ accept
if M loops on w $\longrightarrow$ loop

I see how the function only accepts when the halting problem accepts since it only accepts when M accepts/rejects (halts).  However I don't see how it only accepts when M accepts $\epsilon$ too.  If for example M rejects $\epsilon$ then $M_2$ would accept since M halted on w. Wouldn't this be a flaw in the reduction?  How does this reduction account for $\epsilon$?

Let $x = \langle M, w \rangle \in H$, where $H$ is the usual haltingproblem. Then $\langle M_2 \rangle$ halts on every input, especially on $\varepsilon$ and by construction accepts every input, especially $\varepsilon$. Hence, $f(x) = \langle M_2 \rangle \in ES$.

Now assume $x = \langle M, w \rangle \notin H$, i.e. $M$ loops on $w$. Then $M_2$ loops on every input, especially $\varepsilon$ and thus, never accepts it. $\langle M_2 \rangle \notin ES$.


Complete examples of program correctness proofs Does anyone have any complete example of a proof of program correctness? I'm talking about something that includes the usual predicate, base case, inductive hypothesis, and inductive step. But also important is the loop invariant, and termination. I'm just not sure what the proper format for something like this is.

The only things I've been able to find are powerpoint slides from random schools, but they are for teaching purposes, and all over the place. I'm looking for something from start to finish, easy to follow, and formatted nicely that it can be submitted academically.

I wish to understand what a program proof looks like when (if) it is used for real, rather than as a proof sketch for a toy example in the classroom.

You will find a collection of proof techniques illustrated with poofs of small programs in the following paper:

Inductive Methods for Proving Properties of Programs, Manna, Ness, Vuillemin, CACM 16-8, August 1973.

It is made available on the web by one of the authors. It is also the first paper I ever read on the subject, and I remember enjoying it.

But I would expect the literature, on and off the web, refereed papers, textbooks and other sources. to include a considerable number of such proofs, considering that today people are working on the proofs of real program (such as compilers), with the help of mechanized proof systems.

OF course, you are aware that there is no such thing as correctness in an absolute sense. Correctness is defined only with respect to some specification, i.e. to some predicate in a logic that can also express the meaning of programs
(or whatever part of it is relevant).

Of course, there are different ways of defining the semantics of a program. So one might expect to have proof techniques that vary accordingly.


Defining Grammar for Given Language I'm attempting to practice for an exam and I'm having some trouble on one of the practice problems. The problem asks to identify a variety of language as regular grammar, context-free grammar, context-sensitve grammar, or unrestricted grammar. It also asks that if the grammar is regular or context-free, to write out the exact grammar. I'm not having trouble with two out of the 4 pieces of language. For instance, the easiest one is as follows:

$\{a^n$ where $n\ge0$, $n\pmod 3 \not= 1\}$ can be described by the regular grammar $A \rightarrow aA \mid a$

However, the language I am struggling with is:

$$\{a^n b^m \text{ where } n>1, m\ge1, n>m\}$$

and

$$\{a^{2n} b^{3n}\text{ where }n\ge1\}$$

I believe that the first language is context-free because I know that the language $a^nb^n$ is context-free from prior examples and can be described by the grammar $A \rightarrow aAb \mid ab$, however, in this version, $b$ is taken to the $m$ power rather than the $n$ and the bounds for $m$ and $n$ are different, and I'm not sure how that affects the grammar that describes it. Frankly, I'm not sure where to start with the latter piece of language... I don't know how to determine what type of grammar describes it, let alone the grammar itself if it is context-free or regular.

Could anyone help, or at least point me in the right direction?

Both of your languages are context-free and not regular. The first one can be generated using the following grammar:
$$
S \to a S \mid a S b \mid aab
$$
The second one can be generated using the following grammar:
$$
S \to aaSbbb \mid aabbb
$$

You can show that these languages are not regular using the pumping lemma or using Myhill–Nerode theory. Let me briefly indicate how to do so using the pumping lemma.

For the first language, suppose it were regular. Let $p$ be the constant promised by the pumping lemma. Then the word $a^{p+1} b^p$ is in your language. According to the lemma, it can be written as $xyz$, where $|xy| \leq p$ consists solely of $a$'s, and $y \neq \epsilon$. But then $xy^0z$ is not in your language.

The second language is even simpler, and left to you.


The transition function of the union of regular languages I follow Michael Sipser's book, "Introduction to the Theory of Computation".
To be specific, I am trying to understand the proof about the union of regular languages. However, I have a problem grasping how exactly the transition function is defined.
The book says that for each $(r_1, r_2) \in Q$ and each $a \in\sum$, let
$\delta((r_1, r_2),a) = (\delta_1(r_1, a), \delta_2(r_2,a))$. The problem is that I cannot understand what happens if, for example, $\delta_2(r_2,a) = \emptyset$ and $\delta_1(r_1, a) = q_1$ and I get $\delta((r_1, r_2),a) = (q_1, \emptyset)$, which does not belong to the set of all pairs of states.

In the definition of a deterministic finite automaton, we require that the transition function $\delta$ is well defined on all of $Q\times\Sigma$, i.e. $\delta: Q\times \Sigma\rightarrow Q$. Sometimes we allow omitting transitions, and say that the automaton is "stuck" if it stumbles upon this transition, however in Sipser's book he defines the transition function as above (defined on all of $Q\times\Sigma$).

If you insist on allowing the the automaton to get stuck, then this results in a slight modification of the proof. Instead of looking at $Q_1\times Q_2$ (where $Q_i$ is the state set of the $i'th$ automaton), consider the state space
$\left(Q_1\cup\left\{\widehat{q_1}\right\}\right)\times\left(Q_1\cup\left\{\widehat{q_2}\right\}\right)$, where $\widehat{q_1},\widehat{q_2}$ are special states designed to deal with lack of transition. You can now complete the details yourself.


How to explain rehosting and retargeting with T-diagrams? I'm currently learning for an exam about compilers and found the following question:

  (3 p.) Bootstrapping: Explain the concepts of rehosting and retargeting. Use T-diagrams.

As far as I understand, rehosting means to compile a compiler for another platform (host), so it should look like this:

-------------
| a       b |     --------------
-----   -----     | a        b |
    | c |-------------    ------
    -----| c       x || x |
         -----   ----------
             | ? |
             -----

Is this correct? And what does retargeting mean?

Retargeting refers to having the compiler generate code for a different CPU or instruction set.
A different CPU would be X86 vs PowerPC.
A different instruction set would be ARM vs THUMB or x86 vs x86-64 (same CPU, but different mode).

Rehosting means running the code on a different machine than the code was compiled on.
The new machine usually has the same architecture.
Rehosting need not be trivial, because e.g. the filesystem may look different on the compiler system.

See: http://www.cs.southern.edu/halterman/Courses/Spring2009/425/Slides/ch11.pdf

  Retargetability
  Easily modified to generate code for a different target language

  Rehostability
  Easily modified to run on a different machine

Collectively the two terms are often combined in the term portability.
Code that is portable is not tied to an architecture (target) and not tied to the setup of a specific machine (host).

refering to your question
Rehosting does not mean compiling for another platform!
Retargeting is compiling for another platform.
Rehosting is moving your program to another computer (same platform) (and keeping your fingers crossed to see if it works)


Can a schedule with cyclic precedence graph still be serialisable? We know Every conflict serializable schedule is serializable, but not all serializable schedules conflict-serializable. (*) so it means there is at least one serializable schedule that not conflict serializable.

One way of Testing conflict serializability is using Directed graph as mentioned http://www.cburch.com/cs/340/reading/serial/index.html

So if a graph for a schedule has a cycle, this schedule is not conflic serializable. so by using (*) we can say maybe this schedule be a serializable . (i.e we cannot surely determine it's serilizabe or not, just we know it's not conflict serializable)

My inference is right? any idea?

So if a graph for a schedule has a cycle, this schedule is not conflic serializable. so by using (*) we can say maybe this schedule be a serializable

Yes. You cannot infer that a history is not serializable just because it is not conflict-serializable.

  so as a conclusion, it's contradict to Serializability Theorem that says that a history H is serializable iff SG(H) is acyclic.

No. You are talking about two different graphs and two different serializability criteria. And you are confusing them. See my explanation below.

The key point here is to tell serializability (SR, for short) from conflict-serializability (CSR, for short) and the polygraph (PG, for short) from serializability graph (SG, for short).

The definition for PG can be found in this paper. The results about SR and polygraph below are also in this paper.

The definition for SG and CSR can be found in this book chapter.

In the following, I list some key points on your questions.

SR $\supset$ CSR. In other words, if a history $h$ is CSR, it must be SR; however, the converse is not valid.
The Serializability Theorem is for CSR (although it is called Serializability Theorem):

A history $h$ is CSR $\iff$ SG(h) is acyclic.
For SR: a history $h$ is SR $\iff$ PG(h) is acyclic.
For a history $h$, SG(h) is more restrictive than PG(h) and leads to an efficient test for CSR. Specifically, we have the following complexity results:

Testing whether a history $h$ is CSR (or equivalently, whether SG(h) is acyclic) is polynomial.
Testing whether a history $h$ is SR (or equivalently, whether PG(h) is acyclic) is NP-complete.

Notice that the polygraph for a history for SR is quite different from the traditional graphs we learn in class. So don't assume that it is polynomial to test its acyclicity (actually it is not).


number of queries to recover the permutation Imagine this game. I pick a permutation $p$ of $1..n$ and give you an oracle. When the oracle is queried with any sequence of $n$ numbers $\in 1..n$, it masks each number by applying some unknown bijection $f$ and then permutes the masked values using $p$. Your goal is to repeatedly query the oracle to recover $p$ with as few queries as possible.

A $\theta(\log(n))$ solution is obvious. First query $1, 2, 3, 4, \ldots$ and $2, 1, 4, 3, \ldots$, the second query reversing each of the $\lfloor \frac{n}{2} \rfloor$ pairs. As swapping a pair in the input swaps the corresponding pair in the output, we identify the $\lfloor \frac{n}{2} \rfloor$ pairs that they map to, albeit with unknown correspondence. (If $n$ is odd, the $n$th item is the one remaining in place so $p(n)$ is known.) Then query $1, 1, 3, 3, \ldots$ to identify which item in each output pair corresponds to the first item of an input pair. With 3 queries we have reduced the problem to one of size $\lfloor \frac{n}{2} \rfloor$ by querying from now on with identical pairs of items; recurse. We use $3\log n \pm O(1)$ queries.

Can we do better? For example, is there a strategy using $\log n \pm O(1)$ queries?

Regarding lower bounds, if $q$ queries is optimal for $\frac{n}{2}$ we can run the strategy twice in parallel, side-by-side, in $q$ queries for $n$ but we still lack information about which $\frac{n}{2}$ of the input maps to the corresponding $\frac{n}{2}$ elements of the output, suggesting we need at least one additional query for $n$. This argument seems to imply $\Omega(\log(n))$ query complexity - can it be made rigorous?

Suppose that my input is some permutation $\sigma$. Applying $f$ is the same as multiplying by $f$ from the left (assuming that $\alpha\beta(i) = \alpha(\beta(i))$, and then applying $p$ is the same as multiplying by $p$ from the right. In other words, we have an oracle for the function $\sigma \mapsto f\sigma p$.

Given $f\sigma p$ and $f\tau p$, we can find $(f\sigma p)^{-1} (f \tau p) = p^{-1} (\sigma^{-1} \tau) p$. In particular, using two oracle calls we can find $p^{-1} (1\;2\;3\;\cdots\;n) p = (p^{-1}(1)\;p^{-1}(2)\;p^{-1}(3)\;\cdots\;p^{-1}(n))$. Using one more oracle call, we can also find $(p^{-1}(2)\;p^{-1}(1)\;p^{-1}(3)\;\cdots\;p^{-1}(n))$ (the only difference is the first two values). From these two long cycles we can locate $p^{-1}(1)$ and so recover $p^{-1}$ (and so $p$), as well as $f$ if we so wish. In total, we used three oracle calls.


Calculate the number of models of a KB Suppose we had a domain with two individuals, $x$ and $y$. Suppose we had two predicate symbols $p$ and $q$ and three constants $a$, $b$, and $c$. Suppose we had the knowledge base KB defined by:

  $p(X) \leftarrow q(X)$
  $q(a)$

  How many of these interpretations are models of KB?

So we know that in total there are 128 interpretations (Models and non-models).

Constants $a,b,c$ can have two different individuals $\{x,y\}$: $2^3 = 8$
There are two possible values $\{true,false\}$ each for: $\pi(p(x)), \pi(p(y))$: $2^2 = 4$
There are two possible values $\{true,false\}$ each for: $\pi(q(x)), \pi(q(y))$: $2^2 = 4$
$8 \cdot 4 \cdot 4 = 128$

But now we have to subtract all the interpretations that are not acceptable (no models) from 128. Supposedly the solution should be 24, but I cannot wrap my head around it.

Here's how to count the models:

There are two options for $a$. Denote the option not chosen by $\bar{a}$ (so if $a = x$ then $\bar{a} = y$, and if $a = y$ then $\bar{a} = x$).
There is one option for $p(a),q(a)$: both have to hold.
There are three options for $p(\bar{a}),q(\bar{a})$.
There are two options each for $b,c$.

In total, we get $2 \cdot 1 \cdot 3 \cdot 2 \cdot 2 = 24$.


Number of Final States Subset Construction for NFA to DFA "Suppose we use the subset construction to convert a $7$-state NFA $M = (Q,\Sigma, \delta, q_0, F)$ into a DFA $M' = (Q', \Sigma, \delta', q_0, F')$ for the same language. Then $M'$ will have $|Q'| = 128$ states. If $|F| = 2$, then $M'$ will have $|F'| = 96$ final states."

From the subset construction, I know there are $\mathcal{P}(Q)$ new states in the machine, which means there are $2^7 = 128$ new states in $M'$. I am not sure mathematically why there are $96$ final states.

Observations:

I see that if I have an initial NFA with $3$-states $\{1,2,3\}$ and a $|F| = \{1\}$, then $P(\{1,2,3\}) = \left\{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \right\}$. I can also note that there are now $4$ final states and can conjecture $|F| = 2^{n} - 2^{n-k} = 2^{3} - 2^{3-1} = 4$, where $k$ is the number of final states. I also notice that each particular state occurs $2^{n} - 2^{n-k}$ times in the construction.

However, if I let there be $2$ final states (say $\{1,2\}$) in the initial machine, the new machine will have $5$ final states, not $2^3 - 2^{3-2} = 6$. I can see this is because $\{1,2\}$ is a state that contains both elements, and is  being double counted.

I would prefer simple well-written intuitive answer rather than an overly mathematical one.

Think about which states in the new NFA don't contain a state that was in $F$. These are   $\emptyset$ and every combination of states from $\mathcal{Q}-F$, i.e. $\mathcal{P}(\mathcal{Q}-F)$.

In your 3-state example, the only elements of $\mathcal{P}(\{1,2,3\})$ that don't contain 1 or 2 are $\emptyset$ and $\{3\}$, which constitute $\mathcal{P}(\{3\})$, with cardinality 2, so we have $\mid F'\mid=8-2=6$.

For your 7-state example with $\mid F\mid=2$, the size of $\mathcal{P}(\mathcal{Q}-F)$ is 32, which means there are $\mid F'\mid=128-32=96$ states that also contain at least one state that was in $F$.

So your conjecture of $2^{\mid F\mid}-2^{\mid\mathcal{Q}-F\mid}$ is correct.


Linear equation solving with special sparse coefficient matrix Given a linear equation system of $n$ equations with unknowns $a_1,a_2,...,a_n\in [0,1]$, where the left hand side of each equation consists of not more than $k$ variables (so there are at least $n-k$ zero terms in each matrix row), what is the fastest way (in terms of time complexity) to solve such a system.

I know that simple equation-by-equation reduction will result in $\mathcal{O}(n^2)$ if I'm not mistaken. But is there a faster way of solving it (ideally linear in $n$, e.g. $\mathcal{O}(kn)$)? Because I'm new to the subject of computational linear algebra I have no idea wether or not this is possible.

EDIT: I should also say that either the coefficients in an equation are all the same and add up to zero (so they basically describe an arithmetic mean, for example $\frac{1}{2}a_1+\frac{1}{2}a_2-a_3=0$) OR the equation consists of a single variable and a value (e.g. $a_5=1$).

There are iterative methods in which each iteration takes time $O(nnz)$, where $nnz$ is the number of non-zero entries. See for example Chapter 4 of Saad's lecture notes. For the state-of-the-art, consult Section 5 of Lee and Sidford (2013). For special types of matrices, see Lee, Peng and Spielman (2016).


Why the name Recursively Enumerable and Recursive? Why did the sets of languages accepted/decided by a TM get the name Recursively Enumerable and Recursive, respectively?

A recursive set is synonymous with computable set.  In the beginning of computer science, the notion of computer had not been completely fleshed out, and there were various ideas on the matter.  These ran from Turing's machines, Church's Lambda calculus, and Kleene-Gödels recursive function theory.  The idea is a set is computable if its elements can be decided by a (terminating) algorithm.

Recursively enumerable sets are more general.  It turns out that not every subset of the natural numbers is decidable by an algorithm.  However, for some sets, we can give a procedure (possibly non-terminating) that will enumerate the elements of the set (enumerate is used because each number appears exactly once thus a bijection from the natural numbers to the set in question is defined).  This is equivalent to saying that the set is semi-decidable in more modern terms.


Algorithm to find maximum number of floors you can check with N eggs and D maximum drops Question:  You are given access to a multistory building.  You have N eggs and are allowed D maximum drops from their window.

Rules:  If a egg is dropped from window of floor F and it breaks, it will break for all floors > F.

If an egg is dropped from window of floor F and survives, it will survive for all floors < F.

What is the maximum number of floors you can check in the worst-case?

E.g:  With 1 egg and 5 drops, you can check at most 5 floors (1, 2, 3, 4, 5)

With 2 eggs and 5 drops, you can check at most 9 floors (2, 4, 6 ,8, 9)

EDIT: By "maximum floors you can check", I mean the highest floor for which you can guarantee that you know the outcome for all floors <= to it. For. e.g in N = 1, D = 5 case, there is no algorithm that guarantees you will know the outcome at every floor <= 6 in the worst case. This is because in the worst-case: drops from 6, 5, 4, 3, 2 break and you don't know what will happen at floor 1 since you have no more drops left.

My solution is as follows

findMaxFloors(N,D)
{
 nextFloor = 0

 while (D > 0)
 {
    nextFloor += MIN(N, D);
    D = D-1;
 }

 return nextFloor;
}

But the solution given on the forum is more complicated (using recursion)
maxFloors(N+1,D) = maxFloors(N, D-1) + 1 + maxFloors(N+1, D-1)

I would appreciate any suggestions on the conditions under which my solution won't work.

First we'll clarify the problem a bit. We have $n$ eggs, which we can drop from any floor we want. We also have the constraint that we are allowed a total of $d$ drops of these eggs (rather than $d$ drops per egg). Obviously, when we drop an egg and it breaks, we can't drop it again. Let $f(n,d)$ be the maximum number $M$ such that with $n$ eggs and $d$ drops, we can completely describe the behavior of our experiment for floors $1,\dotsc,M$.

In other words, with $M=5$ the possible outcomes are [YYYYY] (the eggs break when dropped from all 5 floors), [NYYYY] (the egg survives a drop from floor 1 but no higher floor), and [NNYYY], [NNNYY], [NNNNy], and [NNNNN]. Obviously, in all possible descriptions, all the N's must come before all the possible Y's

With that out of the way, let's tackle the recursion
$$
f(n,d)=f(n-1,d-1)+1+f(n,d-1)
$$
Our plan of attack is to drop the first egg from floor $x$, yet to be determined.
That egg either breaks or doesn't:

If it breaks, we know it will break when dropped from any higher floor as well, so we're left with $n-1$ eggs and $d-1$ more drops. In other words, we're looking at the lower floors and there will be $f(n-1,d-1)$ of them, namely floors $1, 2,\dotsc, f(n-1,d-1)$.
Since we've already settled the behavior at floor $x$, we need to have $x=f(n-1,d-1)+1$.
If it doesn't break, we know it won't break when dropped from a lower floor, so we still have $n$ eggs and $d-1$ drops remaining, which will mean that we can determine the behavior of the higher $f(n,d-1)$ floors. They will start at floor $x+1$ and will cover floors $x+1, \dotsc, x+f(n,d-1)=f(n-1,d-1)+1+f(n,d-1)$, exactly as the recursion stated.

For example, you correctly observed that $f(1,5)=5$ but your value for $f(2,5)$ was low. In fact, $f(2, d)=d(d+1)/2$, which is 15 in the case where $d=5$. Start with the first drop from floor 5, and you'll see that you can indeed determine the egg behavior at all of the first 15 floors.


Help me resolve my doubts about infinities, exemplified by an example of non DFA acceptable language I have always had a hard time making sense of infinities.

Example: the language $L = \{ \epsilon , 01, 0011, 000111, 00001111, ... \}$ is not DFA acceptable because a machine capable of accepting it would require an infinite amount of states.

I can draw a DFA with ellipses in the middle to represent it's expansion.  I can prove that:

For all strings x in L, using a machine M = mentioned DFA, under some finite expansion, I can accept all strings y in L, such that $|y| \leq |x|$ and such that M has $|x| + 2$ states and such that all strings in compliment(L) are not accepted by M.

All of those machines are finite.

The problem that prevents me from making the leap to claim that L is then DFA acceptable, is that I need to prove that there exists a largest string in L, but there is no largest string in L.

Anyways, I know this sounds stupid because knowing what is proven about convergence and divergence, I should be able to make mathematical sense of this.  The problem is that no matter how much I know about infinity, I still do not think that what is said about convergence and divergence seems logical.  I always have this feeling that something is wrong.

So I guess I just wonder how I can look at it so that it makes more sense.

In short, when a DFA needs a state for each character of a string in order to accept the string, and the language is an infinite set of strings whose enumeration could be represented as a sequence of strings increasing in length, how is it that a DFA needs an infinite amount of states to accept all of those strings, given each string is finite?

Look at your general procedure: given a language $L$ and integer $n$ build a DFA that properly recognizes any string $x \in L$ with $|x| \leq n$. Note that the language you selected is not special, any language can be represented by a sequences of DFAs with one for each $n$. To see this, just build a tree DFA with $|\Sigma|^{n + 1}$ states with a state for every possible string of length $\leq n$ marking the ones in $L$ as accept states and the ones not in $L$ as reject states and then minimizing. (If you want an even simpler example, then note than for any $L = \cup_{x \in L} \{x\}$ and every $\{x\}$ is recognized by a DFA with $|x| + 1$ states)

The whole point of DFAs is that it is a finite object that recognizes an infinite object. In fact, this is the whole point of computer science in general: Turing Machines are a different kind of finite object that recognizes (or encode) a different (larger) set of infinite objects. This means that for a language to be recognized, you need a single machine that works for all strings in that language.

What you have shown is that $L_n = L \cap \Sigma^{ \leq n}$ is recognized by a DFA, but these are just finite languages and every finite language is recognized by some DFA. However, regular languages are not closed under infinite union (in fact, very few things of interest to computer scientists are closed under arbitrary infinite unions), so the simple fact that $L = \cup_{n = 1}^{\infty} L_n$ does not imply anything about $L$.


Why is ww a linear indexed language while www is not? I am a little bit confused on one idea regarding indexed languages.

  $\{ww \mid w \in \{a,b,c\}^* \}$ is a linear indexed language, but

  $\{www \mid w \in \{a,b,c\}^* \}$ is not a linear indexed language.

What is the difference? As far as I know, indexed languages can be recognized by stack automatons, but I am a little confused on this.

In linear indexed languages, the intuition is that you cannot copy a big information in one step, you have to do it in aletter-by-letter way. This causes things like $ww^R$ much easier to do than $ww$. We can still do $ww$ because you can first "create" the word $w$ by pushing its letter onto the stack and writing them at the same time on the output. Then you can pop the letters to the right or to the left as you prefer, so you can always produce $ww$.
For $www$ it's not possible anymore, because after producing $w$ on the stack and writing in on the output, you need to duplicate the stack, which is not allowed. However you could produce $www^R$, by writing the letters on both sides when popping the stack.


How many decidable decision problems are there? Is there a "intuitive" way of understanding how many possible decidable problems there are, given some formal language to describe them?

There are a countable infinity of decidable problems. There must be at least a countable infinity, because all of the languages $\{a\}$, $\{aa\}$, $\{aaa\}$, ... are decidable. There cannot be more than a countable infinity, because there are only that many Turing machines (each Turing machine can be encoded as a finite string).

There can be no formal language that describes them all without also describing some undecidable problems. This is because the set of decidable languages is not recursively enumerable, but any formal language would give a way to enumerate them. At least, assuming it was decidable whether a string was in the formal language or not. And, if you can't even decide whether a string was in your formal language, it wouldn't be any better as a description than, "The set of all languages decided by Turing machines."


undecidability proof by using Turing Machines I have been reading some material about undecidability of a language, and I am not quite sure of one part. For what I see:

I start with a decider H, that has an input <M,w> where M is a Turing Machine and w is a string, so I have the following:

H(<M,w>)=accept if M accepts w
         rejects if M rejects w

all fine until this point. Now it says that I construct a new Turing Machine D, and this TM has H as a subroutine. If I make a graph I imagine something like this:

-------------      D that is a TM
|   -----   |
|   | H  |  |
|   |____|  |
|___________|

So it says that D calls H to determine what M would do if the input is M, it means something like:

H(M,<M>)

Now it says that it should do the opposite this decider H, it means that:

H(M,<M>)=reject if M accepts <M>
         accepts if M rejects <M>        ---------(1)

and this procedure can be generalized for D like:

D(<M>)=accept if M does not accept <M> ----------(2)
       reject if M accept <M>

I have two questions here, for not opening another thread, but in part (1) why the decider H makes the opposite? What would happen if it does not? I have read in a book that the argument is that sometimes a program can receive a program as an input, such as in a compiler, why it decides to do the opposite?

The interpretation of part (2) does it mean that the Turing Machine D, with input M, this input refers to the same Turing Machine that was put as an input for the decider H?

At the ends there is a contradiction, but I cannot get it, why in step (1) it is decided to do the opposite?

We have the language (commonly called $A_\text{TM}$):
$$
A_\text{TM}=\{(\langle M\rangle, w)\mid M\text{ is a TM and $M$ accepts $w$}\}
$$
and we want to show that this language is undecidable. We proceed by contradiction, assuming that there is a TM, $H$ that is a decider for $A_\text{TM}$. The action of $H$, when given a description $\langle M\rangle$ of a TM $M$ and a string $w$, is to accept if $M$, given $w$, accepts and to reject otherwise.

We use the purported decider $H$ to make another decider $D$ which takes as input a TM description $\langle M\rangle$ and sends that description to $H$, both as a machine description and as an input string (which answers your question (2): yes, we send $\langle M\rangle$ to $H$ as both inputs).

Now you've correctly interpreted the action of TM $D$:

  $D$, on input $\langle M\rangle$, accepts if and only if $M$, on input $\langle M\rangle$, rejects.

In other words, $D$ always correctly determines whether a TM doesn't accept its own description as an input.

Which brings us to your question (1): why design the decider $D$ in such a peculiar way? The answer is precisely so that we can reach a contradiction. Since $D$ uses $H$ as a subroutine, it's clear that $D$ is a valid TM as long as $H$ is also. But now consider what happens if we give $D$ its own description as input? The action of $D$ on its own description is now

  $D$, on input $\langle D\rangle$, accepts if and only if $D$, on input $\langle D\rangle$, rejects.

This contradictory behavior clearly is impossible, so our initial assumption, that there was a decider $H$, must be false. In other words, the language $A_\text{TM}$ must be undecidable.


Can we construct a Karp reduction from a Cook reduction between NP problems? We have had several questions about the relation of Cook and Karp reductions. It's clear that Cook reductions (polynomial-time Turing reductions) do not define the same notion of NP-completeness as Karp reductions (polynomial-time many-one reductions), which are usually used. In particular, Cook reductions can not separate NP from co-NP even if P $\neq$ NP. So we should not use Cook reductions in typical reduction proofs.

Now, students found a peer-reviewed work [1] that uses a Cook-reduction for showing that a problem is NP-hard. I did not give them full score for the reduction they took from there, but I wonder.

Since Cook reductions do define a similar notion of hardness as Karp reductions, I feel they should be able to separate P from NPC resp. co-NPC, assuming P $\neq$ NP. In particular, (something like) the following should be true:

$\qquad\displaystyle L_1 \in \mathrm{NP}, L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1 \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$.

The important nugget is that $L_1 \in \mathrm{NP}$ so above noted insensitivity is circumvented. We now "know" -- by definition of NPC -- that $L_2 \leq_{\mathrm{Karp}} L_1$.

As has been noted by Vor, it's not that easy (notation adapted):

  Suppose that $L_1 \in \mathrm{NPC}_{\mathrm{Cook}}$, then by definition, for all languages $L_2 \in \mathrm{NPC}_{\mathrm{Karp}} \subseteq \mathrm{NP}$ we have $L_2 \leq_{\mathrm{Cook}} L_1$; and if the above implication is true then $L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$ and thus $\mathrm{NPC}_{\mathrm{Karp}} = \mathrm{NPC}_{\mathrm{Cook}}$ which is still an open question.

There may be other differences between the two NPCs but co-NP.

Failing that, are there any known (non-trivial) criteria for when having a Cook-reduction implies Karp-NP-hardness, i.e. do we know predicates $P$ with

$\qquad\displaystyle L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1, P(L_1,L_2) \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$?

On the Complexity of Multiple Sequence Alignment by L. Wang and T. Jiang (1994)

its a generally open TCS problem subject to ongoing research whether & the exact conditions Cook & Karp reductions are equivalent and is apparently closely related to the open NP=?coNP question & other complexity class separations eg E=?NE (wrt sparse languages).

here are two research papers on the subject & further leads on tcs.se via similar question:

Are Cook and Karp Ever the Same? Beigel, Fortnow
Cook vs. Karp-Levin: Seperating Completeness Notions If NP Is Not Small (1995) Lutz, Mayordomo
many one reductions vs Turing reductions to define NPC, tcs.se


Check if there is only one simple path in graph between nodes x and y` Let's say we have given simple undirected graph $G$ having $N$ nodes and $M$ bidirectional edges. For given $x$ and $y$ we want to check if in the graph there is only one simple path between them.

What I was thinking for, is that we should find all the cycles in the graph and run bfs from $x$ to $y$, if the path doesn't move through the vertices that are in some cycle, there is only one path, and otherwise there are more.

Is there some other way to check this?

Raphael's suggestion to use 2-shortest path is correct but more complex than necessary.

Your approach is unfeasible, the number of cycles is factorial in the size of input.

Here's a sketch of a solution in time $O(|V|+|E|)$.

Find a path $p_1, \dots p_n$ from $x$ to $y$ in $O(|V|+|E|)$. If  no such path exists, answer $\textsf{NO}$. Otherwise, mark all the nodes in the path. That path is indeed unique if and only if no node in that path reaches a node that comes after it. Starting from the first node of the path $p_1$, pick a random edge going out from $p_1$ other than the one that connects it to $p_2$ and start a DFS from there. If you reach a marked node, answer $\textsf{NO}$, if you never reach a marked node, cut that branch from the graph and pick another random outgoing edge. Continue in a similar fashion until all outgoing edges are exhausted, then start again with the following node until you reach $p_n$.
If you finish the procedure without ever answering $\textsf{NO}$, answer $\textsf{YES}$. The entire procedure has the cost of a DFS, $O(|V|+|E|)$, therefore the overall time is $O(|V|+|E|)$.


How to generate a pushdown automata for accepting a language? I have an exercise in my book to come up with a pushdown automaton accepting a language.

The exercise is to come up with a state diagram for the PDA accepting the language of all odd-length strings over $\{a, b\}$ with middle symbol $a$.

Here's what I have so far...

I wasn't sure how many states I needed, but I was thinking 3. State $q_0$ for pushing symbols onto the stack until reaching the middle symbol, $q_1$ for after middle symbol is found, and state $q_2$ the accepting state. I think in $q_1$ I need to cancel out input symbols from the stack with the input. I don't know how to account for the string being odd length, also.

Is there a smart, systematic way to do this?

Designing an PDA (or a NFA, DFA, or any other automaton) is essentially programming (in a weird, extremely limited language). Just as there is no sure-fire way to write a program from some description, there isn't for automata either. The only way of becomming proficient is to practice. You'll find plenty examples here...

For some cases there is a way of translating a more human-readable description of the language into an automaton, like starting with a regular expression and getting an NFA, massage that one and you'll finally get the minimal DFA; or starting with a context free grammar and constructing a PDA. The results aren't always exactly pretty, but guaranteed to work.


Using Clique decision to solve Clique optimization How can you perform the clique decision algorithm fewer than $ O(n) $ times to solve clique optimization?

I'm not sure if my approach is right but this is my thought process: you would pick vertices in a graph and see if they form a clique, then keep picking more vertices until you have the max possible clique.

I'm not sure how it can be done less than $ O(n) $ times.

I can imagine an undirected graph such as:

where $ \{A, B, C\} $ and $ \{B, C, D\} $ would be cliques. The number of vertices is 4, and the number of vertices in the cliques is 3, which is $ n - 1 $. Would this count as being done in less than $ O(n) $ times, or is this the wrong approach to this problem?

You would use binary search.  Start with the lower bound being 3 and the upper bound $n$, where $n$ is the number of vertices.  Call your clique decision oracle with a $k$ value halfway between the two bounds.  If it answers "yes", move your lower bound to $k + 1$.  If it answers "no", move your upper bound down to $k - 1$.  Repeat until you have found the largest $k$ value the oracle answers "yes" to.  It should take $O(\log n)$ calls to the oracle.


3 Colorability reduction to SAT I'd like to reduce 3 colorability to SAT. I've stuffed up somewhere because I've shown it's equivalent to 2 SAT.

Given some graph $G = (V,E)$ and three colors, red, blue, green. For every vertex $i$, let the boolean variable $i_r$ tell you whether the $i$-th vertex is red (or more precisely, that the $i$-th vertex is red when $i_r = 1$). Similarly, define $i_b$ and $i_g$.

Suppose two vertices $i$ and $j$ were connected by an edge $e$. Consider the clause
        \begin{align}
   (\bar i_r \vee \bar j_r)
  \end{align}
        If we demand the clause is true, it means that the vertices cannot both be red at the same time. Now consider the bigger clause $\phi_e$
        \begin{align}
   (\bar i_r \vee \bar j_r)\wedge(\bar i_b \vee \bar j_b)\wedge(\bar i_g \vee \bar j_g)
  \end{align}
        which, if true, demands that the vertices $i$ and $j$ aren't both the same color. By itself, this clause is in 2-SAT.

For every edge $e \in E$, I now make a clause $\phi_e$ of the above form and put them all together using $\wedge$'s
          \begin{align}
              \phi = \wedge_{e \in E} \phi_e
           \end{align}
Thus, for the entire graph, I've come up with a 2SAT formula which is equivalent to 3 coloring.

This is obviously wrong, but I can't tell where I've screwed up.

With your modeling, setting $i$, $i_r$, $i_g$ and $i_b$ to false for all vertices yields a solution of the SAT problem and this is not a solution of the graph coloring problem.

You need to add clauses to say that each vertex is blue or green or red, namely
$(i_r\vee i_g\vee i_b)$.
Then it becomes a 3-SAT problem.

Note that if a vertex is assigned to more then one color, then we can take any of its colors and obtain a 3-coloring.


Is there a name for defining recursive functions as an infinite list of input/output pairs? Recursive functions are usually defined by directly calling a function inside its own body.

Nat = Z | S Nat
double Z = Z
double (S x) = S (S (double x)))

What if, instead of defining them this way, we just enumerated two recursive datatypes and zipped them?

To be more descriptive, mind the following functions/types:

enum Nat = [Z, S Z, S S Z, S S S Z ...]
elem (S S S Z) (enum Nat) = 3
[4,5,6] !! 1 = 5
zip [1,2,3] [4,5,6] = [(1,4), (2,5), (3,6)]
# a b = \x -> (zip (enum a) (enum b)) !! (elem x (enum a))

That is, enum enumerates elements of a recursive datatype, elem, !! and zip are just as defined by Haskel. Now, using #, there is an interesting way to define some recursive functions.

Even = Z | S (S Even)
double = Nat # Even

This makes double equivalent to:

double x = [(0,0),(1,2),(2,4),(3,6)...] !! x

In other words, instead of defining the function recursively, we just created an infinite list with the input/output pairs of that function, by zipping two recursive datatypes together. I never heard of this approach being used, so my question is: this there a name for this? Any relevant papers? What kinds of functions can be defined this way?

Well it's the "set-theoritic" perspective of a function where a function
from A onto B is really just the a subset of A x B where each a in A appears only once.

The problem is that some types are uncountable so enumerating them in this manner isn't possible; for some types a finite member may not be at a finite index.

Consider for example, how you would do this for Double.


DFA which visit a specific state at least once Given a DFA M that satisfies language A, how do I modify M such that a new language B consisting of all strings that are accepted by M and cause M to enter a specific state r at least once are satisfied by the modified DFA?

I try to remember whether state r is visited or not. But as I known, unlike turing machine, DFA does not have any memory.

You can add the "have seen $r$" information as follows.

Based on the old DFA $A = (Q, \Sigma, \delta, q_0,F)$ construct a new one $A' = (Q', \Sigma, \delta', q'_0,F')$. State set of $A'$ equals $Q'=Q\times \{0,1\}$, which adds a bit to the original states.

In each step you mave along just like the original automaton, except when entering state $r$ when we set the bit to $1$.

Initial state $(q_0,0)$: initial, not seen $r$. Final states $F' = F \times\{1\}$: final and seen $r$.


Absolute orientation alignment with vectors I have two trajectories of a moving object. Each trajectory is composed of poses at discrete time. Each pose is a translation vector and a rotation matrix.

Each trajectory defines the same path (with noise) but expressed in some arbitrary frame of reference. I need to find the relative transformation that aligns both trajectories.

This is the absolute orientation problem that can be solved with Horn's method for a collection of points in the 3D space. So, I can solve this by taking into account just the translation vectors of the poses. However, I'd like to include the rotations as well.

Does this new problem have a name? Is there any known technique to solve it?

A simple modification of Horn's approach can be made to incorporate local rotation information: rather than just matching the centers of the body (trajectory points), use several off-centered points on the body such as the endpoints of a tied reference frame (in a way, forming dipoles, quadrupoles, octupoles...). Then use Horn's method on this augmented point set.

By adjusting the remoteness of these points from the center, you can trade good translational fitting for good rotational fitting.

This aside, you can probably develop a method based on static equilibrium of two solids (formed by the whole trajectories), where elastic forces are developed between corresponding points as a function of distance and torques as a function of misalignment.

CAUTION: in case there is significant scaling difference, you will need to adjust the remoteness proportionally to the size of the whole trajectory, otherwise artificial discrepancies will arise because of rescaling.


Reachibility between first and last layer in grid graph in logspace I am trying to prove that there exists logspace deterministic Turing machine that check if exists path between first row and last row in grid graph. Grid graph is matrix of $0s$ and $1s$, the undirected edge exists between two $0s$  or $1s$ - one the left, right, up, down.   Path can contains only $0s$ or only $1s$.

For example in following graph there exists such path:

0 0 1 0
0 0 1 1
0 0 0 1
0 0 0 1

For following there is no such path

0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1

How to prove it ?

I can't post a comment, which would be more appropriate:

Reingold's result gives a logspace algorithm, but reachability on undirected grid graphs was show to be in $L$ by Blum and Kozen about 30 years prior:

M. Blum and D. Kozen. On the power of the compass (or,
why mazes are easier to search than graphs). In IEEE Symposium
on Foundations of Computer Science (FOCS), pages
132–142, 1978.


Maximize $\sum_{i\equiv r \pmod{m}} a_i$ over $m,r$ Given a circle with $n$ equal segments. On each segment there is an
integer. We want select segments at equal distance, maximizing the sum of integers on selected segments.

I have an algorithm with runtime $O(n^2)$ as follows:
First calculate maximum sum of segments at distance one. Second calculate maximum sum of segments at distance two, and so on. Return maximum of all above values.
According to the teacher, there is a solution with runtime $O(n\log n)$, but I cannot find it.

Denote the numbers by $a_0,\ldots,a_{n-1}$. We want to maximize, over all $m \mid n$ and $0 \leq r < m$, the sum of all $a_i$ such that $i \equiv r \pmod{m}$.
Let $p_1,\ldots,p_k$ be the prime divisors of $n$. Either $m = n$, or $m \mid (n/p_i)$. In the latter case, we can fold $a$ into an array $b^{(n/p_i)}$ of size $n/p_i$, and solve the problem there, recursively. If we use dynamic programming, then each $b^{(m)}$ will explored once, for each $m \mid n$.
What is the running time of this algorithm? The work done at $b^{(m)}$ takes time $O(m\rho(m))$, where $\rho(m) = O(\log m / \log\log m)$ is the number of distinct prime factors of $m$ (the upper bound on $\rho(m)$ follows from $n \geq \rho(m)!$). It follows that the total running time is proportional to
$$
\sum_{m \mid n} m\rho(m) \leq \frac{\log n}{\log\log n} \sum_{m \mid n} m = \frac{\log n}{\log\log n} \sigma(n) = O(n\log n),
$$
since the divisor sum function satisfies $\sigma(n) = O(n\log\log n)$.


How to convert a non-embedding context free grammar to regular grammar? Please note that I am aware the undecidability of the conversion of context-free grammar to regular grammar. But given the non-embedding property of the input context-free grammar, is there any algorithm to convert it to regular grammar, or DFA directly?

Check out this link.
This is a simpler version of a proof by Chomsky that NSE grammars represent regular languages. Fortunately, the proof technique illustrates how to construct a left-regular grammar from a given NSE grammar. Here's my explanation:

For each of the $\lvert V \rvert (\lvert V \rvert +1)/2$ pairs $(v_1, v_2)$ of elements of $V$, decide whether $v_1 \le v_2$ based on the definition given: $v_1 \le v_2$ if $v_2 *:= V^* v_1 V^*$.
Construct equivalence classes such that if $v_1 \le v_2$ and $v_2 \le v_1$, $v_1$ and $v_2$ are in the same equivalence class. This will be a partition of all elements of $V$ into one or more equivalence classes.
Now, for each pair $(VE_1, VE_2)$ of equivalence classes of $V$ as described above, determine whether $VE_1 \le VE_2$ by checking whether $v_1$ in $VE_1 \le v_2$ in $VE_2$.
Construct sets $UE$ corresponding to equivalence classes $VE$ such that if $VE_i \le VE_k$, $VE_i$ is a subset of $UE_k$. Each $UE_k$ must also contain the alphabet set $E$. You will have one $UE$ for each $VE$, and each $UE$ will contain variables in equivalence classes "less than" the corresponding $VE$, in addition to all the alphabet symbols.
Determine $P(v)$ for each variable $v$ as follows: $P(v)$ is the set of all productions in $P$ whose left-hand-sides belong to the equivalence class containing variable $v$.
For each variable $v$, construct a grammar as follows: $G(v) = (VE \cup UE, UE, P(v), v)$, where $VE$ is the equivalence class containing $v$ and the $UE$ is the one corresponding to the $VE$.
The authors have proven a lemma which claims that $G(v)$ is a linear grammar. From this, we can write regular expressions over $UE$ for each variable $v$. Note that for the $UE$ corresponding to the "smallest" $VE$, this regular expression will contain only symbols from the original alphabet $E$.
Iteratively substitute regular expressions containing only alphabet symbols into more complicated regular expressions obtained from step 7. Eventually, you will have a regular expression corresponding to the language generated from the original start symbol $S$, and this regular expression will contain only alphabet symbols from the original alphabet.
You now have a regular expression for the NSE grammar, and can obtain a minimal DFA using Kleene's theorem, the subset construction, and a DFA minimization algorithm.

If you would like an example, I can try to provide one later. Try to do a few yourself, read the paper (it's short), and we can talk about complexity later on.


Running time of median of 3 partioning I am hoping someone can break something down for me in a way I can digest.
I am trying to understand the running time for the median of three partitioning.

What is the goal of median of three partitioning? Is it to eliminate the possibility of selecting the largest / smallest element as the pivot, thus resulting in O(n^2) run time?
What would the run time be of a simple median of three partitioning function? Since there are only 3 possible comparisons, and the comparison operation runs in O(1) time, wouldn't it just be 3O(1) or negligible?

Any assistance would be greatly appreciated. Thus far, I have referenced CLRS and the following three pages for assistance:

Median of Medians Recurrence Relation for 3-grouping
Counting elements that are greater than the median of medians
http://www.cs.fsu.edu/~breno/COP-4530/slides/21-anim.pdf

You should not confuse median-of-median algorithm with median-of-3 trick.

The former is $O(n{\rm log}n)$ worst-case time.

Ans. to 1. The latter is still $O(n^2)$ worst-case time but faster in practice due to the low frequency of bad patterns seen in practice. This can be seen by the fact that randomized quicksort is $O(n{\rm log}n)$ expected time.

Ans. to 2. It is $O(n)$. The comparison work is $O(1)$ since there are only $3$ elements involving. After, determine the value of the median of three, you need to partition the array around this value. This takes $O(n)$ time.


How does the ID3 Algorithm differ from a generic Decision Tree learning algorithm Based on the notes of my Machine Learning lecturer, I am struggling to understand how the two algorithms differ? Both seem to select the most informative feature A (based on least entropy), then create subsets of the example set for each value of A. Then create a new branch on the tree by recursively calling ID3 on each subset.
Could someone please explain how they differ?

The ID3 algorithm is an algorithm for inferring a decision tree: given a training set, it tries to find a decision tree that tends to label a large fraction of the training set accurately.  See, e.g., https://en.wikipedia.org/wiki/ID3_algorithm.

There is no such thing as "the generic decision tree learning algorithm".  There is no such generic algorithm.

There are many algorithms for learning a decision tree.  ID3 is probably the most well-known algorithm for decision tree learning, and the simplest, but there are other algorithms.  Other algorithms include C4.5, CART, and others.


How to view Graph Reduction/Graph Representation for a Haskell program? I know that under the hood, for a Haskell program, the GHC compiler uses graph reduction for optimization. Is there any way to view this graphical representation of the program? I haven't been able to find an existing plugin that, given a Haskell program, produces its graphical representation. I am relatively new to Haskell.
Are there research tools available to study and manipulate such graphs?

Welcome to CS.SE!
I cannot present the underlying algorithms themselves, just the concepts they use.
The normal form (NF) of some expression is basically its result, like 42, Just 1, \ x -> 1 + x.
The weak head normal form (WHNF) is some expression which is one of three:

A lambda: \ x -> x + 5 * 6. The NF is \ x -> x + 30.
Data constructor: (3, 2 + 5). The NF is (3, 7). It could be partially applied: (,) (2 * 5). The NF is \ x -> (10, x).
Partially applied built-in function: (+) (2 * 8). The NF is \ x -> 16 + x.

As one can see, WHNF generalizes NF.
So, what have graphs got to do with this? Well, one can understand f e1 e2 ... en as a graph with a node f which is connected with n other nodes: e1, e2, ..., en. Evaluation is the reduction of the nodes1. To show why this is actually very cool I am going to use a picture which I stumbled upon on Wikipedia and HaskellWiki not so long ago:

So, what is going on in this picture? The idea is simple: when working with lists, we have a binary operation (:) and some initial value []. When we are folding, we have a binary operation f and some initial value z. The data structure does not change - only the nodes of our graph. To get the complete result (NF, that is), we reduce the graph.
(Please note that the initial 1 : 2 : 3 : 4 : 5 : [] could not have been reduced any further; in (pseudo-)haskell the lists are: data [a] = a : [a] | [].)

1Some technical details on evaluation (the basic tools to manipulate graphs, just as you have asked). The programmer might force the reduction. seq x y forces its first argument to the WHNF and returns the second (being basically flip const magically strict in the first argument). More formally:

...seq x y means that whenever y is evaluated to weak head normal form, x is also evaluated to weak head normal form.

If the programmer wants to do the same for the NF, they should take a look at Control.DeepSeq.deepseq.


Is Newton's Method to compute the zeros of a function an algorithm? Looking for Newton's method in Wikipedia, I read the following:

  In numerical analysis, Newton's method (also known as the
  Newton-Raphson method), named after Isaac Newton and Joseph Raphson,
  is a method for finding successively better approximations to the
  roots (or zeroes) of a real-valued function.

After describing briefly the method, the Wikipedia page adds:

  This algorithm is first in the class of Householder's methods,
  succeeded by Halley's method. The method can also be extended to
  complex functions and to systems of equations.

The emphasis on "algorithm" is mine.

I know Wikipedia is not always to be trusted, and I have been
wondering whether Newton's method as described in Wikipedia does
qualify as an algorithm, and what could be the reasons why it would
qualify or not qualify.

The same question applies to other similar methods, such as the whole
family of Householder's methods, also described in Wikipedia, but an
answer in the Newton-Raphson case is enough.

Note, as a last remark, that the same question could be applied to Euclid's method to compute GCD as described in Wikipedia, though I expect the answer would be: "yes, because ...".

Related questions:

What exactly is an algorithm?
Do Turing machines assume something infinite at some point?

It's pretty clearly an algorithm according to my definition in the linked question. I think your real question is "what is the problem, if any, for which this algorithm is correct?" The answer would be something like "given some stuff and a number of iterations, output a value satisfying some condition with an accuracy related to the iteration count."


Algorithm to calculate Polylogarithm In my code i want to solve the Fermi-Dirac-Integral numerically. This can be achieved with a Polylogarithm.

Actually I'm coding in C#, so my function to calculate this polylogarithm looks like that:

public double PolyLog(double s, double z)
{
    double sum = 0;
    for (int k = 0; k < 1e5; k++)
        sum += Math.Pow(z, k) / Math.Pow(k, s);
    return sum;
}

This actually does it's job pretty well for values |z| < 1.
However, I need to calculate the polylogarithm also for values that are bigger than 1.

Is there any code, that calculates polylogarithms for |z|>1?
Probably this would be done by any kind of analytic continuation.
Although, I'm using C#, I don't care about the language. I can easily translate any code to C#.

"Note on fast polylogarithm computation" by R. E. Crandall contains an explicit algorithm for computing the polylogarithm.


What is the time complexity of MergeSort without its penultimate merge? As in, with the two final sublists which are sorted arrays, let's say just for this example (yes it is no longer fully MergeSort but I am interested in the time complexity only), that we finish with a constant time operation involving the two sublists. MergeSort in worst case is $O(n\log(n))$, and not having the final merge would definitely lead to greater efficiency than this, but by how much? Again, I understand that MergeSort has not completed it's full run, I am only interested with its time complexity for my specified run only.

It will still take $O(n \log n)$.

There are four steps in mergesort.

Divide the list in half.
Mergesort the left half.
Mergesort the right half.
Merge the two together.

If I understand right, you're asking about removing the fourth step, in the final stage only (that is, not in any of the recursive calls).

In this case, you'll still have to do step 1 in $O(1)$, step 2 in $O(\frac{n}{2} \log \frac{n}{2})$, and step 3 in $O(\frac{n}{2} \log \frac{n}{2})$ (since steps 2 and 3 still call conventional mergesort, which is $O(n \log n)$).

So your total time complexity will be $O(1 + \frac{n}{2} \log \frac{n}{2} + \frac{n}{2} \log \frac{n}{2}) = O(n \log \frac{n}{2}) = O(n \log n)$.

The final merging only takes $O(n)$ time; it's the recursive part that's the real cost.


KMP Algorithm Example I'm studying KMP algorithm and I'm stuck on an example.

Suppose my text is "I am queen." and my pattern is "q".

The sp table will have only one value, q and it's sp index will be 0. Mismatch will occur at the very first index.

According to the formula: i - ( spi-1 + 1) ; the right shift will be 0.

And so the algorithm will get stuck and move nowhere.

What am I doing wrong?

The formula for shifting is i - spi + 1 if you start indexing from 0 and i - spi if you start indexing from 1.


Sort binary matrix by swapping columns to make subrectangle of ones with maximum size We have given binary matrix (matrix containing only 1 and 0) of size $n\cdot m$. We want to order the matrix such that the biggest rectangle containing only ones is with maximum size.

For example if the following matrix is given:

1000  0010
1101  0111
1101  0111
1101  0111

We should output 9 because the biggest rectangle we can get is with size 9. We are allowed to swap any columns infinite number of times and we are only requested to find the maximum size of the subrectangle.

Can we solve this problem faster that trying all possible permutations?

Yes, you can solve it faster than trying all possible permutations.

The biggest such rectangle must span consecutive rows.  So, for all $i,j$ with $i \le j$, check what is the biggest rectangle you can make that spans rows $i..j$.  You can do this check in $O(mn)$ time, by checking which columns have a 1 in all of those rows.  There are only $O(m^2)$ possible values of $i,j$.

So, the running time of this simple method is $O(m^3 n)$, which is faster than trying all permutations.  (Trying all permutations would take $\Omega(m \cdot n!)$ time, which is far slower -- it is exponential time, rather than polynomial time.)  I make no claim that this simple method is optimal -- rather, I merely claim that the answer to your question is "yes".


Known lower bounds on halting for finite machines? It's possible to determine whether a deterministic machine with finite memory will halt in O(n) time if the machine has n possible states. You simply run the machine until it halts or visits the same state twice, which is guaranteed to happen in no more than n steps.

Can any other algorithm do this in fewer steps? Is there a proof that no such algorithm can exist?

It seems that your machine runs without any further input once it is
started. Whatever input it has is encoded in its starting state. Since
your machine is deterministic, there is at most a single transition
from each state. So the state-transition graph of your automaton is a
directed graph composed of paths that either are isolated cycles or
are simply open linear path from an initial node/state to a final node
(corresponding to a halting state without transition). There may be
any (positive) number of such paths, possibly only one. Actually, only one of these paths is relevant, the one containing the initial state.

Depending on whether the initial state of your automaton is on a
cyclic path or on an open path, the automaton will run for ever or
halt at the end of the open path. The former is identified by checking
whether a state is visited twice. The latter is identified by the fact
that a halting state (without transition) is encountered.

In the question, you do not give any constraint or information on the way states and
transitions are defined, other than the following:

from a given state, there is a transition function that gives you
the next state;
you can know whether two states are the same or not.

So the only way you can map the graph structure to reason about it is
to follow the transition function from state to state, even when
knowing the total number of states $n$.

With $n$ states, you can have a graph $C_n$ composed of one cycle of
$n$ states. You can also have a graph $L_n$ composed of one open
linear path of $n$ states starting with the initial state and ending
with a halting state. The former is non-halting, while the latter is
halting.

Still assuming you know the number of states, and using only the gven
primitives, the only way to find a difference is to follow $n-1$
transition. Then you are either in a halting or a non-halting state.
The former tells you that computation halts, while the latter tells
you it does not halt.

You clearly will not do better when you do not know $n$ in
advance. Actually, you then need only one more transition to detect that
the computation is not halting.

So there is no way to decide whether your automaton halts in fewer
steps, unless you have other means for analyzing the state-transition
graph.

In other words, the only way you can have a faster algorithm is to
have some formalism that structures the state-transition graph with
properties that can be used to analyze it without having to follow the
transitions.


Integer Programming - packing wolves and sheep I'm new to linear/integer programming and I'm trying to solve a little problem I made up. I want to "pack" animals into a minimum number of bins where some of the animals cannot co-exist (wolves and sheep). Here is a picture of my little flow network that's guiding me.

Imagine that each animal node outputs 1 animal of that type.
The maximum each bin can hold is 2 animals
You don't want wolves together with sheep

I've figured out how to write constraints that would allow me to minimize the number of bins if there is no distinction in input type.

What I've tried so far is the following. I take two inputs and sum them. I also take the input type and compare them so that I get either a zero or 1. At the final node, multiple the 0 or 1 with the summation and you get either the sum or nothing.

My questions come into play here in the following:

Is there such a thing as a comparison operation that you can use in Integer Programming? I can subtract two types and if it's zero, they're the same, otherwise no. I'm not sure how one would represent this mathematically if one wanted to solve something like this in software.
My "solution" below won't work for just one sheep node since I can't compare sheep to anything to get the sheep through. Actually, if I were to do wolf and sheep first, and then wolf, this would return 0 as well. Would I have to duplicate my little tree snippet and run through all combinations of input nodes? Is there a more scalable way to do this?

Any suggestions are appreciated.

mj

I would approach it in the following way:

Suppose that I have the following sets:

$A$ - the set of all type of animals, i.e. $A = \{\text{wolf},\text{sheep}\}$
$B$ - the set of all possible bins. $B = \{B_1, \ldots, B_{n_B} \}$

Suppose I have the following parameters:

$c$ - a 1-dimensional matrix of the size of $A$, indicating the number of animals, per type that exist. Example: $c = \{2,3\}$ would mean that there are 2 wolfs and 3 sheeps.
$n_B$ - the number of bins available.

And suppose I have the following variable:

$M$ - is the integer matrix $A \times B$ that represents the number of animals per bin. Rows are animals, columns are bins. $M(\text{wolf},B_1) = 2$, for example, would mean that there are 2 wolfs in bin $B_1$.

So, for example, the following matrix:

$$
       M = \left[
 \begin{array}{ccc}
         2 & 1 & 0 \\
         0 & 0 & 1 \\
 \end{array}
\right]
$$

would indicate that there are 2 wolfs in $B_1$, 1 in $B_2$ and 1 sheep in $B_3$.

Your model would be:

$$
\begin{align}
& \text{Minimize}
& & U = \sum_{i = 1}^{n_B} 1 & \text{such that} \sum_A M_{ab_{i}} > 0 \\
& \text{subject to}
& & \sum_A M_{ab} \leq 2 & \forall b, \\
&&& \prod_A M_{ab} = 0 & \forall b, \\
&&& \sum_B M_{ab} = c_a & \forall a, \\
\end{align}$$

where $a$ is an element of $A$ and $b$ an element of $B$ and $b_i$ is the element of set $B$ at position $i$.

The OBJECTIVE FUNCTION U is the sum of all bins that are actually being used, and it is this sum that you want to minimize. There might be more elegant ways of defining that, but this is what I could think at the moment. Essentially you would count all bins that contain at least one animal - $\sum_A M_{ab_{i}} > 0$ represents that. In GAMS Programming language, I could represent this as what they call a dollar sign condition ($), check the language you are using to see how to impose this condition to the equation.

The FIRST CONSTRAINT indicates that there can be a maximum of 2 animals per bin - it translates to the following equations:

$$
\begin{align}
& M_{\text{wolf},B_1} + M_{\text{sheep},B_1} \leq 2 &\text{(rules for bin $B_1$)} \\
& M_{\text{wolf},B_2} + M_{\text{sheep},B_2} \leq 2 &\text{(rules for bin $B_2$)} \\
... \\
& M_{\text{wolf},B_{n_B}} + M_{\text{sheep},B_{n_B}} \leq 2 &\text{(rules for bin $B_{n_B}$)} \\
\end{align}$$

The SECOND CONSTRAINT limits the type of animals that can be put together - there can only be animals of one type in the bin, so that $M_{\text{wolf},B_1} \cdot M_{\text{sheep},B_1} = 0$, etc.

The THIRD CONSTRAINT limits the number of animals to be put in the bins to the number of animals available.


How to prove every context-free language over a unary alphabet is regular? How can I show that every context-free language over a unary alphabet is regular?

The following proof follows Pighizzini, Shallit and Wang, Unary Context-Free Grammars and Pushdown
Automata, Descriptional Complexity and Auxiliary
Space Lower Bounds.

Let $L$ be a unary context-free language. Assume for simplicity that $\epsilon \notin L$, and consider a grammar $G = \langle V,\{a\},P,S \rangle$ for $L$ in Chomsky normal form. Denote $h = |V|$.

In the sequel, whenever we say parse tree, we mean parse tree in $G$.

Let $\Pi$ be the collection of all triples $(U,i,j)$ such that $U$ is a parse tree rooted at some nonterminal $A$ which represents a derivation of the sentential form $a^i A a^j$, where $0 < i+j < 2^h$.

Let $(U,i,j) \in \Pi$, and let $A$ be the label of the root of $U$. Given a parse tree $S$ containing a node $v$ labeled $A$, we can "pump" $S$ by $U$ by replacing $v$ with a copy of $U$, attaching the children of $v$ to the leaf of $U$ labeled $A$.

Lemma. If $\ell > 2^{h-1}$ and $a^\ell \in L$ and $T$ is a parse tree for $a^\ell$, then there exists a triple $(U,i,j) \in \Pi$ and a parse tree $S$ for $a^{\ell-i-j}$ such that $T$ is obtained from $S$ by pumping by $U$.

Proof. Since $\ell > 2^{h-1}$, $T$ must have depth at least $h+1$ (recall that the last level corresponds to productions of the form $A \to a$), and so a path of length $h+1$ edges. This path contains $h+1$ nonterminals, one of which must repeat. Consider such a repetition within the last $h+1$ nonterminals of the path. The repetition corresponds to a triple $(U,i,j) \in \Pi$ (note $i+j < 2^h$ since we chose a repetition within the last $h+1$ nonterminals, and $i+j > 0$ since the grammar is in Chomsky normal form). By "pumping out" this derivation, we obtain the parse tree $S$ for $a^{\ell-i-j}$. $\quad\square$

Corollary. Every parse tree in $L$ can be obtained in the following way:

Start with a parse tree for some $a^\ell$, where $\ell \leq 2^{h-1}$.
Repeatedly pump by $U$ for some $(U,i,j) \in \Pi$.

Using this, we can construct an NFA for $L$:

Guess a parse tree for some $a^\ell$, where $\ell \leq 2^{h-1}$, and read the word $a^\ell$.
Set $X$ to be the set of nonterminals appearing in the parse tree.
Perform the following operation an arbitrary number of times:

Guess $(U,i,j) \in \Pi$ such that the label of the root of $U$ appears in $X$.
Read $a^{i+j}$.
Add all nonterminals in $U$ to $X$.

This shows that $L$ is regular.

Parikh's theorem can be proved in the same way.


Generating many graphs satisfying some properties Suppose I want to generate all graphs satisfying some properties (specifically 2-connected graphs on 30 vertices with degree sequence $(4, 4, 3, 3,3, \dotsc, 3)$). Unfortunately, there are an enormous number of such graphs. Probably the fastest way to find all of them would to use nauty, but it is too slow.

Is there a way to just generate many such graphs (i.e., not needing a complete list)?

There isn't an obvious way to get nauty to output just the first 10 million graphs, for instance. Maybe this isn't even possible, I don't know how nauty works.

There are methods for randomly sampling graphs with a given degree sequence. You could try sampling and post-selecting for 2-connectedness, since that test is essentially a DFS. See for example

Efficient and Exact Sampling of Simple Graphs with Given Arbitrary Degree Sequence


Cannot understand reductions from the halting problem and its complement When I was going through the reductions from $HP$ and $\overline{HP}$ in this handout, I do not understand how everywhere the following claim is made: $$⟨M,x⟩ \in \overline{HP} ⇒ \text{M does not halt on x} ⇒ M′ \text{ does not accept any strings} ⇒ L(M′)\text{ is finite} ⇒ M′ \in L_5.$$ Why does $M$ not halting on $x$ imply that $M'$ does not accept any string at all?
My understanding initially was that $M'$ is a non-deterministic Turing machine that simultaneously runs $M$ on all possible inputs, but that doesn't seem right. Can someone please take a few examples, $(L_3, L_4, L_5$ if possible) and explain how the reductions are performed?
Also, I do not understand what $\tau(⟨M,x⟩) = ⟨M'⟩$ means.
I do understand how reductions are done after reading a few pages from Sipser. I still don't understand how they're done in the linked handout though. If anyone can even comment on what book uses the same notation or the reduction procedure as the handout, it would be of a lot help!

The machine $M'$ ignores its input, and just simulates $M$ running on $x$. Hence:

If $M$ halts on $x$ then $M'$ halts on all inputs.
If $M$ doesn't halt on $x$ then $M'$ doesn't halt on any input.

The notation $\tau(\langle M,x \rangle) = M'$ is the definition of a reduction $\tau$ from $\overline{HP}$ to $L_5$. The input to the reduction is an instance of the halting problem, which is a pair consisting of a Turing machine $M$ and an output $x$, and the output is the Turing machine $M'$ described above.


A* 8-puzzle problem worst case memory usage We are testing the A* algorithm with Hamming and Manhattan on the 8-puzzle (and its natural generalization n-puzzle) problem.
We have to answer the following question but I can't figure out what it should be.

Our assignment is derived from this.

  How many board positions are in worst case in memory in function of board size N (where N is the side of a board of size NxN). Give a as low as possible upper bound. You can assume that a board configuration is never in the priority queue several times.

I was thinking about N^2! but that is impossible because not every board position can be reached.

Since the number of possible positions is quite low when N = 3 (9! / 2 = 181,400), you can do an exhaustive search to find the worst case. Check the result, and maybe it leads to some insight.


Problem of finding a very independent set of size at least $k$ is NP-Complete Given a simple graph $G$, A subset of vertices $V_G$ is called "very independent" if there is no edge between each pair of the vertices in $V_G$ and for each pair $v,v'$, there is no vertex which is connected to both $v$ and $v'$.

In other words, a very independent subset is an independent subset of vertices like $V_G$ such that there is no path of length $2$ or less than it, between each pair of vertices in $V_G$.

How can we prove that the problem of finding a "very independent set" of size at least $k$ in a given simple graph is NP-Complete?

Note: I was thinking of reducing it to the problem of finding an independent set of size $k$... But, Is that even NP-Complete?

Your notion is what is called distance-2 independent sets, also a particular case of rulling sets (see here Independent set where two vertices need to have distance >= c).

Your problem is NP-complete by an easy reduction to Independent Set (which is NP-complete, https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Maximum_independent_sets_and_maximum_cliques): for every vertex $u,v$ of $G$ such that there exists $w$ with $(u,w) \in E$ and $(v,w) \in E$, add the edge $(u,v)$.

This gives you a new graph $G'$ whose independent sets are the distance-2 independent sets of $G$.


Proof that $A_{DFA}$ is decidable in Sipser It seems like the proof that $A_{DFA}$ is decidable in Sipser (2nd ed.) assumes the computation will halt... and hence only really proves that $A_{DFA}$ is recognizable.
The language $A_{DFA}$ is defined by $A_{DFA} = \{\langle B, w \rangle \mid B \text{ is a } \mathsf{DFA} \text{ that accepts input string } w \}$.
Here is the passage (I've bolded the most relevant sentence):

First, let's examine the input $\langle B, w \rangle$. It is a representation of a $\mathsf{DFA}$ $B$ together with a string $w$. One reasonable representation of $B$ is simply a list of its five components, $Q$, $\Sigma$, $\delta$, $q_0$, and $F$. When $M$ receives its input, $M$ first determines whether it properly represents a $\mathsf{DFA}$ $B$ and a string $w$. If not, $M$ rejects.
Then $M$ carries out the simulation directly. It keeps track of $B$'s current state and $B$'s current position in the input $w$ by writing this information down on its tape. Initially, $B$'s current state is $q_0$ and $B$'s current input position is the leftmost symbol of $w$. The states and position are updated according to the specified transition function $\delta$. When $M$ finishes processing the last symbol of $w$, $M$ accepts the input if $B$ is in an accepting state; $M$ rejects the input if $B$ is in a nonaccepting state.

Am I missing something or is this proof bogus?
EDIT: Never mind, I think I see my problem. A Turing machine may move back and forth, never halting, but an automaton like $B$ given finite input $w$ finishes after $|w|$ steps, correct? So $M$ does halt. Feel free to post an answer explaining this yourself - I don't want anyone to miss out on a chance to answer by me deleting the question. If no one responds within a day, I'll post an answer myself.

The computation will always halt. If $M$ doesn't reject right away, then $B$ is an encoding of a DFA. DFA always halt on any finite input, so the simulation must halt too.


Does simultaneously finding max/min in array of coordinates by x and y increase comparisons? I have an unsorted array of (x,y) coordinates and need to find the min/max for both (x) and (y) separately so that I can build a bounding box using $O(\frac{3n}{2})$ comparisons.

If I use this method to find the min/max for the left/fight box boundaries, then use the same algorithm to find min/max of y for the top/bottom boundaries, does this double the amount of comparisons or can I still claim it’s $O(\frac{3n}{2})$?

does this double the amount of comparisons or can I still claim it’s $O(3n/2)$?

You misunderstand the big $O$ notation.

Even if you double or quadruple the amount of comparisons, you can still claim it is $O(3n/2)$. That is, the amount of comparisons as a function of $n$ is asymptotically not bigger than $3n/2$.  The very purpose of big $O$ notation is to hide a constant factor so that it becomes clearer what is the asymptotic picture. In fact, $O(3n/2)$ = $O(n)$. When I write "=", I mean equality. That is, the left hand side and the right hand side represent exactly the same set of functions.

Here is what you could say.

If I use this method to find the min/max for the left/right box boundaries and then use the same algorithm to find min/max of y for the top/bottom boundaries, I will use $2(\lceil 3n / 2\rceil - 2) \le 3n -3$ comparisons. That is, I will use $O(n)$ comparisons.


Why does the explanation of auxiliary carry flag differ from the article to article? These two images are from Google search.

  AUXILIARY CARRY FLAG: This flag is set to a 1 by the instruction just
  ending if a carry occurred from bit 3 to bit 4 of the A Register
  during the instruction’s execution

Explanation from Quora

  It indicates when a carry or borrow has been generated out of the
  least significant four bits of the accumulator register following the
  execution of an arithmetic instruction. It is primarily used in
  decimal (BCD) arithmetic instructions.

Explanation from Wikipedia

These two different definitions really confuses me.
As I experimented this on Keil using 8051, and it showed that AC is set when the carry occurs out of four low bits.
What is the precise definition?

The two definitions are exactly the same. Don't forget that in computer science, we often start counting things at zero rather than at one.


Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$ I want to find a near-optimal solution for a maximum weight independent set.
i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their weights is maximum (The weights are positive), under the constraint that every pair is not connected by an edge,
i.e $\forall\ v_i,v_j \in S:(v_i,v_j) \not\in E$.

A common problem instance would be a graph with around $2 \times 10^5$ nodes, up to around $5 \times 10^5$.
The degree of a node is bounded by ~$100$, and the number of edges will be around $10^6$.

Can anyone recommend a heuristic algorithm for finding a near-optimal solution? A runtime of hours or even days is acceptable.

I've been looking so far at articles about Tabu search and that is the current direction I am going towards.

Unfortunately, (weighted) maximum independent set is very hard to approximate. You might be able to do a bit better if you can analyze the graphs in your application (perhaps they are not truly arbitrary).

In any case, luckily your graphs are quite small (200 thousand vertices or so). A naive algorithm (say a greedy one) will run quite fast, but might be far from the optimum. Especially since several hours (or even days) of runtime is fine, I'd experiment with a genetic algorithm.

Being a rather central problem, there are studies into this as well. For a starter, one could look at [1]. In practice, I would expect one to be quite happy with such an approach.

[1] Hifi, Mhand. "A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems." Journal of the Operational Research Society 48.6 (1997): 612-622.


Trivial solution to the Continuous Knapsack problem I am a bit puzzled as to why the continuous knapsack problem is a non-trivial problem

https://en.m.wikipedia.org/wiki/Continuous_knapsack_problem

Using the terminology in the Wikipedia link above,

If the Knapsack had a capacity of $W$, couldn't we just pick $W/w_i$ of the material $i$ having the maximum value per unit weight $v_i$?

Briefly, the supply of each material is finite: there is only $w_i$ of material $i$. If $w_i < W$, then you cannot fill the knapsack just with material $i$.

In the continuous (or fractional) knapsack problem, we are given a bunch of materials $1,\ldots,n$. Material $i$ has weight $w_i$ and total value $v_i$. The goal is to pick $\alpha_1,\ldots,\alpha_n \in [0,1]$ such that $\sum_i \alpha_i w_i \leq W$ in a way which maximizes $\sum_i \alpha_i v_i$. Your suggestion of taking $\alpha_i = W/w_i$ (for the best material $i$) is only feasible and optimal if $W = w_i$. If $W > w_i$ then the choice isn't feasible – there is not enough of material $i$. If $W < w_i$, then the choice (probably) isn't optimal, since the knapsack will still have room left.


Find a Cook Reduction from $R_{Clique}$ to its determinist problem The question is to find Find a Cook Reduction from $R_{k-Clique}$ to its determinist problem.
Basically:
k-Clique: a group of $k$ nodes in the graph such there is an edge between every two nodes.
Suppose you are allowed to use an algorithm (B) that in $O(1)$, given as input a graph $G$ and a number $k$, returns whether the graph includes a $k-Clique$ or not.
Use B to define an algorithm (A), that in polynomial time, given as input a graph $G$ and a number $k$, returns a $k-Clique$ if it exists, and a symbol if it doesn't.
My idea:
My idea was to define something as follow:
1. While the size of the graph is greater than k
    2. Remove from the graph the node with the lowest deg
        1. check the new G with B, if yes, return it
        2. Else, continue

Something like that. I wasn't able to disprove it at least. But is it correct? How would I prove it?

Your algorithm doesn't return a $k$-clique. Simply consider a connected graph $G$ that is a proper supergraph of a $k$-clique, and an isolated vertex $x$. Your algorithm with input $G+x$ returns $G$.
You can solve your problem as follows:

While $\exists $ a vertex $v$ of $G$ such that $B(G-v)$ returns true:

Delete $v$ from $G$

Return $G$.

Let $G^* = (V^*, E^*)$ be the graph returned by the algorithm.
Since the algorithm preserves the invariant "G contains a $k$-clique", $G^*$ must also contain a $k$-clique. This means that we only need to prove that $G^*$ is not a supergraph of a $k$-clique.
Suppose towards a contradiction that there exists a proper subset $C$ of $V^*$ such that $|C|=k$ and the subgraph of $G^*$ induced by $C$ is a $k$-clique. Then, for any vertex in $v \in V^* \setminus C \neq \emptyset$,  $G-v$ also contains a $k$-clique. This shows that the algorithm cannot return $G^*$ and yields the sought contradiction.


Relation between best case and average case complexity I have two questions,

Does $T_\mathrm{best}(N) = O(f(N))$ imply that $T_\mathrm{avg}(N) = \Omega(f(N))$?
Does $T_\mathrm{avg}(N) = O(f(N))$ imply that $T_\mathrm{best}(N) = O(f(N))$?

Where,
\begin{align*}T_\mathrm{best}(N) &= \min \{T_1, \dots, T_N\}\\
T_\mathrm{avg}(N) &= \frac1N \sum_{1\leq i\leq n} T_i
\end{align*}
for some sequence $T_1, T_2, \dots$.

I think both are true but don’t know how to prove them.
Any ideas?

I think your definitions of $T_{\text{best}}$, $T_{\text{worst}}$, and $T_{\text{avg}}$ could use some clarification. I'll proceed assuming the correspond to best-, worst-, and average-case runtimes [1].

The first claim is false. The problem is that $f$ could dominate $T_{\text{best}}$ at an arbitrary rate. So we cannot make any claims about $f$'s status as an asymptotic lower bound of $T_{\text{avg}}$.

The second claim is true. Hint: prove $T_{\text{best}} = O(T_{\text{avg}})$, then use transitivity of $O$ to conclude the result.

[1] https://en.wikipedia.org/wiki/Best,_worst_and_average_case


What would "sum types with functions" look like in OOP? It's fair to summarize classes in OOP as "product types with functions." However, couldn't there be something like "sum types with functions"? How would inheritance work with them?

I'm trying to scout if anybody has considered this question before in language design.

The key to remember is that there's a sort of dualism between functional sum types, and OOP implementations of a superclass or interface:

Sum types require the variants for a type to  be specified up front, and for every operation, requires that we specify the operation for each variant. Adding a new operation is easy, adding a variant requires refactoring all functions.
OOP requires that we specify the operations for a type up front, and each implementation/subclass specifies its own implementation for each operation. Adding a new variant is easy, but adding a new operation requires refactoring in each subclass.

In each case, we have all possible pairs of variants and operations, but we differ on how we group them: all the implementations for variants in an operation together, or all the operations for a variant together.

  It's fair to summarize classes in OOP as "product types with functions."

At its most barebones version, maybe.  But this ignores any subtyping structure. Many versions of OOP are much richer, with interfaces being analogous to existential types.

As for the question of "what if we just did sum-types with functions", this would be pretty boring. You would specify a bunch of variants for your type, and then a bunch of operations your type, which would have to specify an implementation for each variant.

This is basically just a normal OOP type with a single member variable that's a sum-type, and a bunch of functions operating on that variable.


How to implement recursive solution with large number or parameterized possible next steps I was looking at a recursive solution for the robot on a grid problem which basically states that there is a robot on the top left corner on a grid and you are supposed to find a path to the bottom right of the grid and the robot can only move down or to the right.  Below is the recursive function for the solution

public static boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
        // If out of bounds or not available, return.
        if (col < 0 || row < 0 || !maze[row][col]) {
            return false;
        }

        boolean isAtOrigin = (row == 0) && (col == 0);

        // If there's a path from the start to my current location, add my location.
        if (isAtOrigin || getPath(maze, row, col - 1, path) || getPath(maze, row - 1, col, path)) {
            Point p = new Point(row, col);
            path.add(p);
            return true;
        }

        return false;
    }

I understand the solution, at every recursive call it checks if it is at the bottom right or if going down one step or going right one step takes it to the bottom right.

However I was thinking that this solution only works because there are only two possible next steps (down or right) that we are easily able to hardcode and connect with the || operator.  But what if there were N different next steps? In that case we would need to call the recursive getPath() function within a for loop from 1 to N.  But then how would we check if any of the 1 to N recursive calls return True? In this case it would not be possible to connect all of them with an || operator.  Would something like the following work?

public static boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
        // If out of bounds or not available, return.
        if (col < 0 || row < 0 || !maze[row][col]) {
            return false;
        }

        boolean isAtOrigin = (row == 0) && (col == 0);

        if(isAtOrigin){
            Point p = new Point(row, col);
            path.add(p);
            return true;
         }

         for(int i:N){
             if(getPath(maze,row,col-i,path)){
                Point p = new Point(row, col);
                path.add(p);
                return true;
             }
         }

        return false;
    }

Is this a valid solution for the change in the problem that I suggested? I think what is throwing me off here is that in the original solution all the recursive calls are made at the same time within the if statement, but here they are called sequentially in the for loop.  Is that still valid?

The way that that the short-circuit expression A || B is evaluated is as follows:

if A is True:
   return True
return B

In words:

Run $A$. If it returns True, return True. Otherwise, continue.
Run $B$, and return the result.

In particular, $A$ and $B$ are not run in parallel; they are run in sequence.

There is absolutely no problem generalizing this to a short-circuit OR of larger arity:

if A1 is True:
   return True
if A2 is True:
   return True
...
if An is True:
   return True
return False

We could also replace the last bit with simply return An, to make it match the previous pseudocode, but the form above is perhaps more easy to implement using a loop.


Counting letter frequency in array in O(1) with hash function I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p']
There are several ways to do this:

A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ space

Sorting the array first and serial counting the characters is a better solution with $O(n \log n)$ time and $O(n)$ space

But the optimal solution is... using hash tables with $O(1)$ access time. The thing is, I do not quite understand why the complexity is supposed to be $O(1)$ and not $O(n)$. After all, we still have to iterate over the array. For example
def fCount(A):

  frequencies = new hashTable()

  for character in A: // This is O(n) !!!
      frequencies(character) += 1

Yes, the access time is $O(1)$ but in order to create the hash table, you still need $O(n)$ time and space.
So why is this supposedly $O(1)$ time and $O(1)$ space?

The complexity is $O(n)$. What is $O(1)$ is the time it takes to access a cell in the hash table.
By the way, assuming that each character is a byte, you can just use a plain old array of length 256.


Why are there only 2^i configurations? In the proof of TQBF-complete, it says if the input size is i, then the TM for the input has at most 2^i numbers of configuration. Can someone explain why?
The proof is from: http://zoo.cs.yale.edu/classes/cs468/fall12/TQBF-complete.pdf

I don't know which proof you're referring to, but i'd expect it's because the input is assumed to be binary. I.E. a binary string of length 1 can have two values, 0 or 1. A binary string of length 2 can have 4 values, 00,01,10,11, and a binary string of length 3 can have 8 values, and so on.


Direct edges of undirected graph so that all indegrees are even Undirected graph is given which has M edges and N vertices we have to convert every edge from $u-v$ to $u\to v$ or $v\to u$ such that the total indegree of every vertex is even.

For example, consider a graph which has the edges 1-2, 1-3, 2-4, 3-4. We can direct it as 1→2, 1→3, 2←4, 3←4, so indegrees of 1,2,3,4 are respectively 0,2,2,0, which are all even.

Which method or algorithm is suited for least time complexity? M and N are between 1 and 100,000.

Orient all edges in an arbitrary fashion, and add a $0/1$ variable $x_{u,v}$ for each edge $(u,v)$, with the following meaning: $x_{u,v} = 0$ means that we use the orientation $u \to v$, and $x_{u,v} = 1$ means that we use the orientation $u \gets v$. The parity of the indegree of $u$ is equal to
$$
\sum_{(u,v) \in E} x_{u,v} + \sum_{(w,u) \in E} (1 + x_{w,u}) \pmod{2}.
$$
Let $p_u$ be the parity of the number of edges of the form $(w,u)$. Then we can formulate the task as follows:

  Assign $0/1$ values to the edges so that the sum of weights of edges adjacent to $u$ is $p_u$ (mod 2).

As an example, consider your sample graph, with edges
$$
(1,2), (1,3), (2,4), (3,4).
$$
We have $p_1 = 0$, $p_2 = 1$, $p_3 = 1$, $p_4 = 0$. We are looking for a solution (mod 2) of the following system:
$$
\begin{align*}
&x_{12} + x_{13} = 0 \\
&x_{12} + x_{24} = 1 \\
&x_{13} + x_{34} = 1 \\
&x_{24} + x_{34} = 0
\end{align*}
$$

One such solution is $x_{12} = x_{13} = 0$, $x_{24} = x_{34} = 1$. This is exactly the solution that you describe.

If you sum all equations, then all the edges cancel, and you get $\sum_u p_u = 0 \pmod{2}$. This gives a necessary condition for the existence of a solution. It turns out that this condition is also sufficient, assuming the graph is connected (otherwise, you need a similar condition for each connected component). A solution can be found using linear algebra modulo 2.

This is related to the so-called Tseitin contradictions in proof complexity, which correspond to assignments of the weights $p_u$ for which no solution exists.