How to approach NFA design questions intuitively? I did see a lot of nice and informative questions, articles on inter-net and on StackOverflow itself, of-course. But I found all the questions or articles following a specific rule or a pattern to explain the topic. I mean, when a question was asked on NFA, DFA or Regular Expression, a solution was presented to the question abiding by the theorems / rules of these topics (Theory of Computation).

But what I feel is that, as most of the questions on DFA/NFA are of the type
"Design an NFA...." or "design a DFA..." , I feel that developing/Designing DFA/NFA must be an ART.

And where there is ART I feel there is an intuition. If these problems involve "DESIGNING" something ,then everyone must have their own way (of-course not going out-of-the-way of theorems or rules as such) of solving or attacking these problems. One should have developed a thinking process (over the years of practise) to solve these problems.

So I would like all the experts over this Site to share their knowledge (preferably in simple words) how they think over the problems (simple ones) of these topics.

I would like to elaborate the question with a simple example.

  Let F be the language of all strings over {0,1} that do not contain a pair of 1s that
  are separated by an odd number of symbols. Give the state diagram of a DFA with
  five states that recognizes F .

Or maybe this:

  Design an NFA to find a 4-state NFA for the complement of F.

These questions are from the Sipser's book and I have also found the solutions for them myself.

I just want to know , how one can develop an intuition for solving the problems?

There is one sentence in your question that is worth answering:

  I just want to know , how one can develop an intuition for solving the problems?

Same thing everybody does, be is musicians, crafts men or scientists: exercise. There is no shortcut.

You can certainly use the growing database of finite-automata questions we have here. There is little use in repeating techniques here as they more often than not depend on the concrete example.

For regular languages in particular, you can devise any formal representation of the language as long as the model is equivalent to regular languages. There typically are (computable) methods to transform such representations (e.g. regular expression) to finite automata.


Randomized algorithm for minimum cut Given a simple undirected connected graph $G$, I want to find a min-cut
of $G$ using a randomized algorithm.
My attempt was to select a random edge in $G$ and reduce that edge to a
single vertex.  And recursively do it until the number of vertices is at
most 2.
The number of edges present (in the resulting multi-graph) will be the
min-cut.  This is the standard algorithm I found at many places.
Will this lead to the exact number of min-cut and how can I extract the
vertices on each side of the cut?

Yes, that's exactly the correct algorithm, and what you have produced is Karger's algorithm.
Since the algorithm is randomized, you can run it several time over in the hope of getting a better solution.  There is no guarantee that you will get the optimum cut, but you can make the error probability as low as you want to.
Here is Thore Husfeldt's illustration of it (cc-by-sa-3.0), 10 repetitions of the contraction procedure in Karger’s algorithm for minimum cut on a 10-vertex graph.  The 5th repetition finds the minimum cut of size 3.


What is the time complexity for division by repeated subtraction? Given the following algorithm :

    input : a (integer), b (integer != 0)

    result = 0;
    while(a >= b)
    {
       a = a - b;
       result = result + 1;
    }

    return result;

How to find the number of instructions and the time complexity of this kind of algorithm since we don't know neither a nor b nor the number of iteration in advance ?

Your algorithm makes exactly $\lfloor\frac{a}{b}\rfloor$ iterations of while loop.

If we suppose that the size of the inputs is $n=max\{a,b\}$ then your algorithm will make at most $n$ iterations; when $a=n$ and $b=1$.

Therefore, with this notation, your algorithm (on a high level) runs in $O(n)$ time complexity.

If you want to analyze it deeper, including the complexity of addition and subtraction which are $\Theta(n)$ for $n$-digit numbers, things get more complicated because $n$ we defined above was not the number of digits (decimal representation) but a value (unary representation).
As it can be shown, the base in which we represent numbers is not relevant, so the overall analyzed algorithm, having in mind also the properties of big-O and big-Theta runs in $O(n^2)$ where $n$ is the number of digits (in any base).


Difference in Sorting 32- and 64-bit Integers In 2007, Barrack Obama was interviewed at Google.

The question was, "What is the best way to sort a million 32-bit integers?" Does the fact that the size range of the integer was specified elude to a different way to sort integers of different sizes (i.e., 64- or 32-bit)?

Yes.  For instance, sorting a million 5-bit integers is a lot easier: use counting sort.  And sorting a million long strings is a different question than sorting a million 32-bit integers.

In the case of this particular question, one crucial inference you can draw is that all million 32-bit integers would fit into RAM, so it would be appropriate to use an in-memory sorting algorithm (e.g., quicksort) rather than an external sorting algorithm.  If we didn't know the size of the items we were sorting, we wouldn't know whether they would fit in memory and thus wouldn't know whether it's more appropriate to use an in-memory sorting algorithm or an external sorting algorithm.


Why is Minimum $k$-cut NP hard when $k$ is specified as part of the input? As you know a set of edges whose removal leaves $k$ connected components is called a $k$-cut. The minimum  $k$-cut problem asks for a minimum weight $k$-cut.

For $k=2$ this problem is P.

Vazirani in his book says for any fixed $k$ when $3 \le k$ it is NP-hard and When $k$ is specified as part of the input this problem is also NP-hard.

I would like to know what difference does it make when $k$ is specified as part of the input? and why is it NP-hard in this case?

First, be careful what Vazirani actually says. On page 38, it is written that:

  "The minimum $k$-cut problem is polynomial time solvable for fixed $k$; however, it is NP-hard if $k$ is specified as part of the input."

(In particular, the claim you make about being NP-hard for any fixed $k \geq 3$ holds for a different problem, namely minimum weight multiway cut). Indeed, Wikipedia states this is the case as well: for any fixed $k$, you can solve the minimum $k$-cut problem in $O(n^{k^2})$ time. In other words, when $k$ is fixed, you have polynomially many ways of removing $k$ edges. So why does it matter if something is part of the input or fixed then?

When $k$ is fixed, it is not part of the input. The problem is this:

  (Minimum $k$-cut.) Input: A graph $G$. Question: Is there a $k$-cut?

So the problem is defined for every fixed value of $k$. We have minimum 2-cut, minimum 3-cut, minimum 4-cut, and so on. In contrast, the problem could be this:

  (Minimum cut.) Input: A graph $G$, an integer $k$. Question: Is there a $k$-cut?

Now, it is possible for $k$ to depend crucially on the size of the graph. This way a naive brute-force won't give you a polynomial time algorithm. Another example is given in this question of ours in the context of finding cliques.


How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime? This question is specifically related to

https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm

The $gcd(x,y)$ is solved in $O(T(n) log n)$, where $n$ is the number of bits of $x,y$, and $T(n)$ is the time to multiply two $n$ bit numbers, as described in

How is the Time Complexity of a Function Problem different than its corresponding Decision Problem?

so when it reads "if you're dealing with big integers, you must account for the fact that the modulus operations within each iteration don't have a constant cost. Roughly speaking, the total asymptotic runtime is going to be $n^2$ times a polylogarithmic factor. Something like n^2 lg(n) 2^O(log*n). "

Isn't this the same thing as stating "the fastest $gcd(x,y)$ is solved in n^2 lg(n) 2^O(log* n)"?  If so, then

How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?

If the $gcd(x,y)$ is solved in $O(T(n) log n)$, shouldn't this be true no matter how large $n$ is?

Based on your comments, I recommend go back to basics and first understand running time, bit-complexity, and the running time for multiplication well.  Focus on that before you try to tackle any of the topics in this post, or you're going to get confused.

Here is a suggested syllabus:

First, study big-O notation.  Understand what it means.  Work through the definitions.  This is well covered in standard algorithms textbooks, so work through that material patiently.  See also, e.g., How does one know which notation of time complexity analysis to use?, How to come up with the runtime of algorithms?.  Try to understand why your "shouldn't this be true no matter how large n is?" question is meaningless (hint: big-O notation relates two functions, not two numbers).
Understand bit complexity as a measure of running time for algorithms that work with large numbers.  See, e.g., Precise runtime of the algorithm to find number of digits in an integer,  Relationship between an integer N and the number of bits n required to represent the integer
Understanding the bit complexity of addition.  This will be a good test whether you understand bit complexity.  See, e.g., Time complexity of addition.
Understand the bit complexity of multiplication.  Understand why it is an open problem how fast we can multiply two integers.  See, e.g., Complexity of multiplication, https://en.wikipedia.org/wiki/Multiplication_algorithm,
Complexity of a recursive bignum multiplication algorithm, What is the fastest algorithm for multiplication of two n-digit numbers?.
Understand the bit complexity of division and modular reduction.  See, e.g., Complexity of Integer Division, Complexity of taking mod.

If there is any of these steps you are unclear on, ask a question about that specific aspect until you understand it well.  Then, go back and study the material on gcd's.  This background material will probably help you make it further through that material.

Remember that just because there is an algorithm to solve some problem in time $O(f(n))$, doesn't necessarily mean that that is the fastest algorithm to solve that problem.  It doesn't mean that is the fastest that the problem can be solved.  For instance, bubblesort can be used to sort numbers; it has a $O(n^2)$ running time.  That doesn't mean that $O(n^2)$ is the "fastest that numbers can be sorted".


Are $A$ and $B$ necessarily be decidable if $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable and $A$ & $B$ being exhaustive? I found the following question

  Suppose A and B are recursively enumerable languages such that $A∪B=Σ^∗$. Further, suppose $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable. Which of the following is true?
  A- It is possible that either A or B is decidable but not both
  B- None of them can be decidable
  C- Both of them are regular
  D- Both of them are decidable

My attempt: It is possible for $A$ & $B$ to be mutually exclusive and yet be exhaustive. Now this can happen even when one of them is not decidable. So $A$.

But answer given id $D$. Are my arguments flawed? If yes, how and where?

The source of the question is reputable test series, but still there are chances of it being wrong.

It is possible for $A$ & $B$ to be mutually exclusive and yet be exhaustive. Now this can happen even when one of them is not decidable. So option A.

The analysis above is correct except the last conclusion "So option A". We cannot exclude the possibility that $A$ and $B$ are both decidable. In fact, it happens in the current situation because of the extra condition, as shown in the latter part of this answer.

Hints, try using the following facts. If you do not know them, prove them first.

For any two languages $X$ and $Y$, if $X$ is exhaustive and $Y$ is decidable, then $X\cap Y$ is exhaustive. (Moreover, $X\setminus Y$ is exhaustive, too. We do not need this fact, though.)
For any language $X$, $X$ is decidable if (and only if) both $X$ and $\overline X$ are exhaustive.

Here is how we can find both $A$ and $B$ are decidable.

Since $A$ is exhaustive and $(A\cap \overline B)\cup(\overline A\cap B)$ is decidable, $A\cap ((A\cap \overline B)\cup(\overline A\cap B))=A\cap\overline B$ is exhaustive. Since $A\cup B=\Sigma^*$, $A\cap\overline B=\overline B$. Since $B$ and $\overline B$ are exhaustive, $B$ is decidable.

Symmetrically, $A$ is decidable.


Is there a DFA that accepts no string, but has at least one final state? Is there a DFA that accepts no string, but has at least one final state?

I think it would be possible to make a DFA that accepts no string only by creating no final states or by making sure that the final states are not accessible. But how can a state not be accessible if a DFA has all of its transitions defined?

Consider a 2-state DFA over the alphabet $\{a\}$ (single character alphabet) that accepts only the empty string:

In this DFA, state 0 is the start state, and also the only accepting state. Now, if state 1 were the start state (but state 0 still the only accepting state), what strings would this machine accept?


$L$ is a context free language so prefix$(L)$ is also context free language In case $L$ is context free language. $L_1 \setminus L_2 = \{x\in \Sigma ^* : \exists y\in L_2$ s.t $xy\in L_1 \}$ when $L_2$ is regular, is a context free language, thus using $L_1 = L$ ,$L_2 = \Sigma ^*$ one conclude that prefix$(L)$ is context free. However I wish to build a grammar for prefix$(L)$. My attempt so far was as follow: $L$ has a Chomsky's normal form grammar, $(N,T,S,P)$ so I defined the grammar $(N\cup N' , T, S, P\cup P')$ when $N' = \{A' : A\in A\}$ ,$P' = P\cup \{A\rightarrow BC' : A\rightarrow BC \in P \} \cup \{A' \rightarrow t : t\in T, A\rightarrow t \in P\} \cup \{A' \rightarrow \varepsilon\} $ my idea was that the non-tagged terms will be fully producted as in the usual grammar and the tagged terms might product a terminal or an $\varepsilon$. Yet I didn't succeed to prove it's a correct grammar for prefix$(L)$.

Let $G$ be a Chomsky's normal form grammar for $L$. So $G = (N,T,S,P)$ when $P\subseteq\{A\rightarrow BC , A\rightarrow a  : A,B,C \in N , a\in T \}$. We will defined $G'$ as follows: $G'= (N\cup N'\cup \bar{S} ,T,\bar{S},P')$ when:

$N' = \{A' : A\in N\} $
$P' = P\cup\{\bar{S} \rightarrow  S' | \varepsilon \} \cup \{A'\rightarrow BC'|B' : A\rightarrow BC \in P\} \cup \{A'\rightarrow a|\varepsilon : A \rightarrow a \in P\}$

Observation - let $A \in N$ we define $L(A) = \{w\in T^* : A\Rightarrow^{*}_G w \}$, So, in $G'$ , $A'\Rightarrow^{*}_{G'} w\in prefix(L(A))$.

proof, by induction over production steps:

$A'\rightarrow^1w\in T^* \Rightarrow w \in \{a,\varepsilon\}$ due to $P'$ definition. So in $G$ ,$A\rightarrow a$ thus $\{a,\varepsilon\} \in prefix(L(A))$.
assumption - $\forall A'\in N'$, $A'\Rightarrow^{k <n}w\in prefix(L(A)) $
$A'\Rightarrow^n w\in T^*$, so $A'\rightarrow^1 \gamma\Rightarrow^{n-1} w$, thus $\gamma \in \{BC' , B'\}$: In case $\gamma = B'$ then $B'\Rightarrow^{n-1} w\in prefix(L(B))$ and $A'\rightarrow B' \Rightarrow A\rightarrow BC \in P$ then $prefix(L(B)) \subseteq prefix(L(A))$. If $\gamma = BC'$, $B$ products $w_1 \in prefix(L(A))$ because $A\rightarrow BC \in P$, and $BC \Rightarrow^* w_1w_2\in L$ when $B \Rightarrow^* w_1 , C\Rightarrow^*w_2$, and $C'$ products $w_{2}' \in prefix(L(B))$ from the assumption. Thus $A' \Rightarrow w_1w_2'$ which is a prefix of $w_1w_2 \in L(A)$.

$L(G') \subseteq  prefix(L)$:

$\bar{S} \rightarrow^1 \varepsilon$ , $\varepsilon \in prefix(L)$.
$\bar{S} \Rightarrow ^n w\in T^* \setminus \{\varepsilon\}$ , so $\bar{S}\rightarrow S'\Rightarrow ^{n-1}w$ now, using the first observation we made $S' \Rightarrow^* w\in prefix(S) = prefix(L)$.

So $\bar{S} \Rightarrow^* w\in T^*$ means $w\in prefix(L)$.

$prefix(L) \subseteq L(G')$:

Observation : in case $A\Rightarrow^* w\in T^*$, then $A' \Rightarrow^* w' \in prefix(w)$ for all $w'\in prefix(w)$.

proof by induction over $w$'s length:

$A\rightarrow a$ $\Rightarrow$ $A' \rightarrow a$ and $A'\rightarrow \varepsilon$, due to $P'$ definition, when $prefix(a) = \{a,\varepsilon\}$.
$A\Rightarrow^* w, |w|=n$, so $A\rightarrow BC \Rightarrow^* w_1w_2 =w$ when $B \Rightarrow^* w_1 ,C \Rightarrow^* w_2$ (from $P$'s definition in chomsky's form). For $w'\in prefix(w)$:

in case $w' \in prefix(w_1)$, then $B'\Rightarrow^* w'$ from the induction assumption ($|w'|<n$, and the assumption stands for every $A'\in N'$ ). So $A'\rightarrow B' \Rightarrow^* w'$ as wanted.
in case $w' = w_1w_2'$ when $w_2'\in prefix(w_2)$ the same arguments holds for $c' \Rightarrow^* w_2'$, thus $A'\rightarrow BC' \Rightarrow^*w_1w_2'$.

For $w \in prefix(L)$:

in case $w = \varepsilon $ , $\bar{S} \rightarrow \varepsilon$.
otherwise $\exists z\in T^*$ such that $wz \in L$, so $S\Rightarrow_G^{*} wz$ and by the observation we made $S'\Rightarrow^* w'\in prefix(wz)$ for all $w'\in prefix(wz)$ and particularly $w$ it self. So $\bar{S} \rightarrow S'\Rightarrow ^* w$. Thus $w\in L(G)$


NP-completeness of a problem with pretty fast algorithm Supposing if a problem with $n$ non-deterministic bits is in $O(2^{\alpha n})$ time at every $\alpha\in(0,1)$ then is there evidence that problem can or cannot be $\mathsf{NP}$-complete?

Yes, such problems can be NP-complete.

Consider classical NP-complete graph problems like clique.

Clique has an $O(2^n)$ time algorithm, where $n$ is the number of vertices. However the input for clique is the adjacency matrix of the graph, which has $n^2$ bits. Therefore when the size of input is measured in bits, clique has an $O(2^\sqrt{n})$ time algorithm, which is $O(2^{\alpha n})$ for any positive $\alpha$.


Complexity of matrix inverse via Gaussian elimination I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$.
If it is known that the complexity of Gaussian elimination is $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then is it true that the complexity of finding $A^{-1}$ should be about twice same, since we are effectively doing two sets of Gaussian eliminations in parallel plus some row interchanges and multiplications?

Please correct me if I'm wrong.

No, it's not true.  You can use Gaussian elimination to invert a matrix in $O(n^3)$ time, but there are other algorithms that are even faster.  The complexity of a problem is the running time of the fastest algorithm for that problem.  Therefore, it is not correct that the complexity of matrix inversion is $\Theta(n^3)$.

See https://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency, https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm, https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra, https://scicomp.stackexchange.com/q/22105/4274, Complexity class of Matrix Inversion.


Why is the lower bound of element uniqueness in $\Omega(n\log n)$? I wish to discuss the element uniqueness problem. First let's define the problem:

Definition from wikipedia:

  In computational complexity theory, the element distinctness problem
  or element uniqueness problem is the problem of determining whether
  all the elements of a list are distinct.

i am aware that this question has been asked before, however, I am confused about what lower bound actually means.

Let's say we are given an arbitrary array of integers. We could simply use hashing to check for element uniqueness. Hashing works in amortized $O(1)$ time. Hence, shouldn't the lower bound of element uniqueness be $\Omega(n)$?

Am I understanding lower bound wrongly? Does lower bound mean an asymptotic lower bound for general cases (i.e. we could have arrays of strings as well) or does it apply to all cases?

We assume the comparison model in the lower bound of the element uniqueness problem. That is, the key operations are to compare elements. In particular, hashing is not allowed.


Why BFS is source vertex specific? Take a graph $G=(V,E)$ .

As we know both DFS and BFS are graph search algorithms .

But why the algorithm for BFS is designed in such a way that it does not cares about the vertices that are not connected to the source vertex  $s$  but DFS takes care about all vertices in $V$.

I mean if $G$ has $l$ connected components and a vertex $s$ is in one of the connected component among $l$ , then if $s$ is the source vertex for BFS , then BFS performs only traversal on the only one connected component (which contains $s$).

If $G$ is input for BFS , it constructs one BFS tree (for component which contains $s$).

But in case of DFS , it constructs a DFS forest with $l$   DFS trees.

Why no BFS forest and it is restricted to a specifc component (containing $s$)?  Any reason involved ?

For Bfs algorithm page # 595 and for Dfs algorithm page # 604 from here

Both BFS and DFS are algorithms for exploring a single connected component, and there are also several others. All such algorithms can be extended to explore all connected components in a graph.


Can Quantum Computing solve Problems not even a Turing Machine can solve? In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "became the first machine ever to perform non-trivial computations that no Turing machine could perform".

My question: Do we really know that quantum computing is powerful enough to solve problems that not even Turing machines can solve? (Or is this just a personal belief of David Deutsch?)

While it is true that the computation of a quantum Turing machine is vastly different from that of a classical one, nevertheless quantum Turing machines can be simulated on a classical Turing machine, albeit with exponential slowdown. In particular, everything that can be computed on a quantum Turing machine can also be computed on a classical Turing machine.

The main advantage of quantum Turing machines is that they appear to solve some problems much faster than classical Turing machines. As Sasho comments, at the moment we can't quite prove this, yet this advantage is believed to hold by most researchers.

For more, check out this talk by Ashley Montanaro.


Describing explicitly the MyHill-Nerode classes created by a language I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt:

For the language
$$L=\{\omega \in \{a,b\}^* \colon \omega \text{ contains at most 1 } 'a' \}$$
The classes are
$$M_1=\{\omega \in b^*\}$$
$$M_2=\{\omega \in b^*ab^*\}$$
$$M_3=\{\omega \in b^*ab^*a(a\cup b)^*\}$$

Now, the way I understand it I need to prove 2 things:

For each $u,v\in M_i (1\le i\le 3)$ and for each $x\in \Sigma^*$
$$ux\in L \iff vx\in L$$
There exists $u\in M_i,v\in M_j(1\le i \neq j \le 3)$ and $x\in \Sigma^*$ such that
$$ux\in L,vx\notin L$$

Am I right about how I described the classes, and about how to prove it?

Your classes are correct, and one can also describe them in words: words containing no $a$, words containing a single $a$, words containing at least two $a$s. When described in this fashion, it is clear that the every word belongs to exactly one class.

However, there is no reason to use the Myhill–Nerode criterion to prove that a language is regular. Instead, you can use its vast generalization and give a DFA or NFA for the language. In the other direction, there is no need to describe all classes, only infinitely many; this already shows the language is not regular.


The range of significance in Type Theory What exactly does "Types as ranges of significance of propositional functions. In modern
terminology, types are domains of predicates" mean?

Update:
I found in this paper (Pag 14 or 234) by Russell, where he defines what is ranges of significance, not exactly including types else propositions.

  A function is said to be significant for the argument $x$ if it has a value for this argument. Thus we may say shortly $\phi x$ is significant,
  meaning the function $\phi$ has a value for the argument $x$. The range of significance of a function consists of all the arguments for which the
  function is true, together with all the arguments for which it is
  false.

Comes from Russell, and it's actually about the domain, not the codomain, if I understand ol' Bertie correctly. A propositional function like "x>3" only has significance if we limit the possible values of x to numbers.  Today we would call that the domain, but his choice of words is defensible: the range of significance of a propositional fn  is the set of values that make it meaningful - i.e. true or false - as opposed to meaningless nonsense, like "Pegasus>3".  The range of significance of a numeric fn is the set of values for which it yields a value, rather than crashing, so to speak.

The relation to types is fairly obvious: the range of significance of a fn $f: A\rightarrow B$ is just the "values" of type $A$ to which $f$ can be meaningfully applied.  The concept and term "type" is just a more commodious way of expressing the same basic concept.  Google "propositional function range of significance" and you'll get links to his original paper and lots more.


Is regex golf NP-Complete? As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), "regex golf" (which might better be called the regular expression separation problem) is the puzzle of defining the shortest possible regular expression that accepts every word in set A and no word in set B.  Norvig's post includes an algorithm for generating a reasonably short candidate, and he notes that his approach involves solving an NP-complete Set Cover problem, but he's also careful to point out that his approach doesn't consider every possible regular expression, and of course his isn't necessarily the only algorithm, so his solutions aren't guaranteed to be optimal, and it's also possible that some other assuredly polynomial-time algorithm could find equivalent or better solutions.

For concreteness' sake and to avoid having to solve the optimization question, I think the most natural formulation of Regular Expression Separation would be:

  Given two (finite) sets $A$ and $B$ of strings over some alphabet $\Sigma$, is there a regular expression of length $\leq k$ that accepts every string in $A$ and rejects every string in $B$?

Is anything known about the complexity of this particular separation problem?  (Note that since I've specified $A$ and $B$ as finite sets of strings, the natural notion of size for the problem is the total lengths of all strings in $A$ and $B$; this swamps any contribution from $k$). It seems highly likely to me that it is NP-complete (and in fact, I would expect the reduction to be to some sort of cover problem) but a few searches haven't turned up anything particularly useful.

Assuming the TCS-variant of regex, the problem is indeed NP-complete.

We assume that our regexes contain

letters from $\Sigma$, matching themselves,
$+$, denoting union,
$\cdot$, denoting concatenation,
$*$, denoting Kleene-Star,
$\lambda$, matching the empty string

and nothing else. Length of a regex is defined as the number of characters from $\Sigma$. As in the comic strip, we consider a regex to match a word, if it matches a substring of the word. (Changing any of these assumptions should only influence the complexity of the construction below, but not the general result.)

That it is in NP is straightforward, as explained in the comments (verify a candidate-RE by translating it into an NFA and running that on all words from $A$ and $B$).

In order to show NP-hardness, we reduce Set cover:

  Given a universe $U$ and a collection $C$ of subsets of $U$, is there a set $C' \subseteq C$ of size $\leq k$ so that $\bigcup_{S \in C'} S = U$?

We translate an input for Set cover into one for regex golf as follows:

$\Sigma$ contains one character for each subset in $C$ and one additional character (denoted $x$ in the following).
$A$ contains one word for each element $e$ of $U$. The word consists of exactly the characters representing subsets in $C$ that contain $e$ (in arbitrary order).
$B$ contains the single word $x$.
$k$ is simply carried over.

This reduction is obviously in P and equivalence is also quite simple to see:

If $c_1, \ldots, c_k$ is a solution for the set cover instance, the regex $c_1 + \cdots + c_k$ is a solution to regex golf.
A regex matching the empty subword would match $x$. Thus, any regex solving the golf problem has to contain at least one letter from each of the words in $A$. Hence, if the golf instance is solvable, there is a set of at most $k$ letters from $\Sigma$ so that each word in $A$ is covered by this set of letters. By construction, the corresponding set of subsets from $C$ is a solution to the set cover instance.


(Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets? The following question is taken from Leetcode entitled 'Combination Sum'

  Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

  The same repeated number may be chosen from candidates unlimited number of times.

  Note:

  All numbers (including target) will be positive integers.
  The solution set must not contain duplicate combinations.

  Example 1:

  Input: candidates = [2,3,6,7], target = 7,
  A solution set is:
  [
   [7],
   [2,2,3]
  ]

  Example 2:

  Input: candidates = [2,3,5], target = 8,
  A solution set is:
  [
   [2,2,2,2],
   [2,3,3],
   [3,5]
  ]

To solve this problem, I applied dynamic programming, particularly bottom up 2D tabulation approach. The method is quite similar to 0/1 knapsack problem, that is, whether we want to use an element in candidates or not.

The following is my code:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not len(candidates):
            return 0
        dp = [ [1] + [0]*target for _ in range(len(candidates) + 1)]
        for row in range(1, len(candidates) + 1):
            for col in range(1, target+1):
                dp[row][col] += dp[row - 1][col]
                if col - candidates[row-1] >= 0:
                    dp[row][col] += dp[row][col - candidates[row-1]]
        print(dp[-1][-1])

However, my codes above do not give solution set. Instead, it gives the number of elements in solution set.

I attempted to generate solution set from my codes above but to no avail. Can anyone help me?

Suppose that the candidates are $x_1,\ldots,x_n$ and the target is $T$. I'm assuming all candidates are positive. If $T < 0$ then there are no solutions. If $T = 0$ then the only solution is the empty solution. Otherwise, there are two kinds of solutions:

$x_1$ together with a solution for $T - x_1$ using all candidates.
A solution for $T$ using the candidates $x_2,\ldots,x_n$.

Using this, you can easily write a recursive procedure that generates all solutions.


Turing machines with a finite number of states In a class on Turing machines, the lecturer said that the language for a machine with 100 states is both recognizable and decidable.

How can we infer this just from the number of states in the machine?

You misunderstood your lecturer's claim. Their claim was that the language of descriptions of Turing machines with 100 states is decidable. The language accepted by each such machine need not be.

In other words, given a string, you can decide whether it describes a Turing machine having 100 states. That's the extent of the claim.


What is an example of a decidable language? I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?

No.

As an example of a language that is decidable but does not have a context-free grammar is the language over the decimal digits that only contains the prime numbers.


Is $n^{1/\log \log n} = O(1)$? Is $n^{1/\log \log n} = O(1)$ ?

Suppose that $n^{1/\log \log n} = c$ where $c$ is constant.

Taking logs of both sides,

$$\frac{1}{\log \log n}\log n = \log c.$$

I am not able to spot an error. Please help

The function $n^{1/\log \log n}$ tends to infinity, since
$$
n^{1/\log\log n} = e^{\log n/\log\log n},
$$
and $\log n/\log \log n \longrightarrow \infty$.


Why are not programs already in binary code? First of all, please forgive me if this question shows ignorance on my behalf. What I'm asking is not why we don't program in languages written in binary code, I know the answer for that. What I would like to ask instead is: considering all information we input into a computer is registered as binary code, and all data is stored in binary code, are not common programming languages already binary code, and what we see as instructions or variables just a translation? If that is so, why are assemblers or compilers necessary?

The short answer to your question is "for productivity and portability".

Let me expand on this. The very first generation of computers were indeed programmed directly in binary, either by entering each binary instruction using physical switches on the computer itself or by some simple bulk loading mechanism such a reading and loading instructions from a paper tape. This was first generation programming (although at the time it was just called "programming").

Programmers soon realised that it would be simpler and quicker to write programs use mnemonics instead of binary instruction codes. So instead of having to remember or look up the binary code for "load the next byte into register A", they could use the mnemonic "LDA". Translating mnemonics into binary instructions required a program called an assembler. Once someone had invested the time and effort into writing an assembler on a particular computer, programs could be written in mnemonics or "assembly language". This was much quicker than working out all the binary codes for yourself, and it also made it much easier to debug and update programs. This was second generation programming.

As more and more programs were written on different machines, programmers realised that the underlying concepts of programming were similar, regardless of which type of computer the program was being written for. Programmers would be even more productive if they could use a language that implemented concepts like variables, loops, case statements and sub-routines. It would also be convenient to be able to write complex instructions like "print the following string of characters to the screen" or "multiply A+1 by B+2, divide the result by C and store the final result in a variable called D" in one line of code instead of multiple assembly language instructions. So programmers invented higher-level languages such as FORTRAN and BASIC (and eventually C and Java) and wrote compilers and interpreters which would translate code written in a higher level language into assembly language instructions or directly into binary instructions. Not only did this make programmers even more productive, but also by creating compilers for different types of computer, the same FORTRAN program could be translated and run on different computers. So programs became portable and programmers did not have to learn lots of different different assembly languages. This was third generation programming.

Mainstream development in programming languages and computer architectures have continued in this direction, with more and more layers of abstraction between the languages that programmers write in and the machine code instructions that a CPU executes directly. Programming languages have become more specialised, with languages specifically designed for implementing user interfaces; processing data in large databases; creating management information reports; running simulations; processing graphics; developing video games etc. Developments in computer architecture design have concentrated on running a relatively small, simple and general set of machine code instructions more rapidly. Increasing CPU speeds and falling memory costs mean that it is more cost effective to translate each line of high level language into hundreds of machine code instructions than it would be to develop more complex CPUs that could execute higher level language code more directly.


Relationship between Coloring a graph and its complement Let $G = (V, E)$ be a graph and $G^*$ its edge complement (that is, $G^* = (V, E^*)$, where an edge $\{u, v\} \in E^* \Leftrightarrow \{u, v\} \not \in E$).

What is the relationship between a coloring in $G$ and a coloring in $G^*$ ?

I was expecting something like

"If $G$ accepts a $k$-coloring, than $G^*$ accepts a $(n - k)$-coloring"

but I can't prove that.

(Of course, I am dealing with proper coloring)

Sorry, this is false:

For example, take $G$ as a size-$10$ independent set. It has a $1$-coloring, or even a $3$-coloring... its complement is a clique, which admits neither a $9$- nor $7$-coloring.


How do you detect if an algorithm is running at O(nlogn)? Given only input and output(e.g. runtime), how do you know if an algorithm is running at O(nlogn) time complexity?

For example, how does LeetCode detect my code is running at O(nlogn)？
https://leetcode.com/problems/sort-list/description/

  Sort a linked list in O(n log n) time using constant space complexity.

Here's what I think:

I assume the complexity formula looks like  $ f(x) = a\cdot x \cdot\log_{b} x\ $

Then for input $x_2 = 2x_1$, $ \frac{f(x_2)}{f(x_1)} = 2\cdot\log_{x_1}x_2
$

So I take inputs like $2,4,8,16...$, get each runtime let's say $i_1,i_2,i_3,i_4... $. Then check if runtime ratio $\frac{i_2}{i_1}, \frac{i_3}{i_2} ,\frac{i_4}{i_3} \approx \log_{2}4, \log_{4}8,\log_{8}16...$.

If it is, then I would "guess" it's running at O(nlogn).

Can I make a good "guess" based on the "characteristic" I described above?

I would like to apologize for sloppy notation in advance.

Recall that $\log_2 10^{10} < 34$, so that for any practical purposes, $O(n \log n)$ will be bounded by $34 \cdot O(n)$, which of course is $O(n)$ (again for all practical purposes).

That means that if language A is 34 times faster than language B, then an $O(n)$ algorithm in B is indistinguishable from an $O(n \log n)$ algorithm in language A.

In practice, it's not possible without a theoretical analysis of the algorithm.

However, it's often simpler to distinguish an $O(n \log n)$ algorithm from an $O(n^2)$ algorithm (in the same language, at least), although we do have problems distinguishing an $O(n \log n)$ algorithm in Python from an efficient $O(n^2)$ in C/C++ in programming contests.


Can the runtime of functions with no loops change with the number of calls? How can we perform time complexity analysis on a function that has no loops?

int somefunction(int param) {
  if (something)
    do this;
  else
    do this;
}

Would the time complexity of this function change depending on how many times the function is called within a program? I currently believe that the time complexity is O(n), because it is dependent on the amount of times that we call it.

Depends on what something and do this are. In particular, do we have to assume global (or object) state?

Consider this:

int switch(int param) {
  if ( !set.contains(param) )
    set.add(param);
  else
    set.remove(param);
}

Now the runtime clearly depends on the implementation of set and the number of entries it has when switch is called. Calling switch $n$ times starting with an empty set and using pairwise distinct parameters, you might get $\omega(n)$ runtime in total, hence not all calls run in time $O(1)$.

On the other hand, if somefunction does not access state outside of its scope -- assuming that the function itself does not have persistent state -- the runtime can only depend on param. That does not mean runtime is in $O(1)$ -- something and do this may still do non-constant things. Call methods, recurse, etc.

Note that depending on the cost model you use, even adding two numbers has non-constant cost.


Shortest distance between a point in A and a point in B Given two sets $A$ and $B$ each containing $n$ disjoint points
  in the plane, compute the shortest distance between a point in $A$ and a point in $B$, i.e., $\min \space \{\mbox{ } \text{dist}(p, q) \mbox{ } | \mbox{ } p \in A \land q \in B \space \} $.

I am not sure if I am right, but this problem very similar to problems that can be solved by linear programming in computational geometry. However, the reduction to LP is not straightforward. Also my problem looks related to finding the thinnest stip between two sets of points which obviously can be solved by LP in $O(n)$ in 2-dimensional space.

I have a solution which may seem a bit convoluted, but should be more efficient than the naive $\mathcal O(n^2)$ brute-force search:

let $v$ be the axis between the centres of mass of $A$ and $B$.
Sort the points in $A$ and $B$ along this axis in descending and ascending order respectively, resulting in the sequences $a_0$, $a_1$, ... , $a_n$ and $b_0$, $b_1$, ... , $b_n$.

The rest is in pseudo-code to make it clearer:

d = infinity.
for j from 1 to n
    if (b_1 - a_j) along v > d then break endif
    for k from 1 to n
        if (b_k - a_j) along v > d then
            break
        else
            d = min( d , ||b_k - a_j|| )
        endif
    enddo
enddo

That is, by pre-sorting the points along $v$, you can filter out pairs that will never be within $d$ of each other since $b_k-a_j$ along $v$ will always be $\le \|b_k-a_j\|$.

In the worse case this is still $\mathcal O(n^2)$, but if $A$ and $B$ are well separated, it should be much faster than that, but not better than $\mathcal O(n\log n)$, which is required for the sorting.

Update

This solution is by no means pulled out of a hat. It's a special case of what I use in particle simulations to find all the interacting pairs of particles with spatial binning. My own work explaining the more general problem is here.

As for the suggestion to use a modified line-sweep algorithm, although intuitively simple, I'm not convinced that this is in $\mathcal O(n\log n)$ when disjoint sets are considered. The same goes for Rabin's randomized algorithm.

There doesn't seem to be much literature dealing with the closest pair problem in disjoint sets, but I've found this, which makes no claim to being under $\mathcal O(n^2)$, and this, which doesn't seem to make any claims about anything.

The algorithm above can be seen as a variant of the plane sweep suggested in the first paper (Shan, Zhang and Salzberg), yet instead of using the $x$-axis and no sorting, the axis between the sets is used and the sets are traversed in descending/ascending order.


Why complement of most negative number in octal does not turn out to be itself I know the range of the $n$ digit numbers in $r$'s complement system is given as

  $r^{n-1}-1$ to 0 to $-r^{n-1}$.

So for 3 bit 2's complement, its:

  $(2^2-1)$ to $0$ to $-(2^2)$
  that is
  $3$ to $0$ to $-4$
  that is
  $(011)_{\text{2's comp}}$ to $(0)_{\text{2's comp}}$ to $(100)_{\text{2's comp}}$

And for 3 digit 8's complement, its

  $(8^2-1)$ to $0$ to $-(8^2)$
  that is
  $63$ to $0$ to $-64$
  that is
  $(077)_{\text{8's comp}}$ to $(0)_{\text{8's comp}}$ to $(700)_{\text{8's comp}}$

Now I came to know that

  the $r$'s complement of the smallest / most $-$ve number in the range will be the same number.

For example, taking 2's complement of most $-$ve / smallest number possible with 3 bit 2's complement system, $(100)_{\text{2's comp}}$ is itself:

1 0 0
0 1 1 (1's complement)
1 0 0 (add 1 to get 2's complement)

But taking 8's complement of most $-$ve / smallest number possible with 3 digit 8's complement system, $(700)_{\text{8's comp}}$ does not seem to be itself:

7 0 0
0 7 7 (7's complement)
1 0 0 (add 1 to get 8's complement)

So 8's complement of 700 does not seem to be 700 itself but is in fact 100. So what I am missing? Or I am doing it all wrong?

First of all, if you are considering the $n$th digit of the number as being a sign digit, you can think of it as being either 0 or 1, no matter the value of $r$. In other words, it is always a bit (a  binary digit), and that's how you would represent it in hardware, should that be the case.

  $[1]73_{\text{8's comp}} = -5$

  $[1]73_{\text{8's comp}} + [0]06_{\text{8's comp}} = [0]01_{\text{8's comp}}$

The complement of a negative number represented in $r$'s complement will obviously produce the positive version of that same number. The most negative number doesn't have a positive of the same magnitude that fits into the given number of digits (a weakness of this form of representation).

The number is still there, though, only unsigned:

  $[1]00_{\text{8's comp}} = -64_{10}$

  $100_8 = 64_{10}$


Does the following algorithm has amortized constant time per element? Consider the following streaming ``algorithms'':

When an element $x$ arrives, flip a fair coin until it shows ``heads''.
Fix a random hash function $h:U\to\{0,1\}^\infty$ (i.e., it maps elements into infinite bit strings). When an element $x$ arrives, do $LZ(h(x))$ operations, where $LZ$ is the number of leading zeros in $h(x)$. Notice that for any element $x$, the distribution of time spent is same as in (1).

Clearly, both algorithms spend in expectation $O(1)$ time per element, and their worst case is unbounded.

The key difference is that algorithm (1) makes the coin flips independently for each arrival, and (2) fixes a distribution such that every time $x$ arrives, it spends the same amount of time.

(1) should clearly be called amortized constant time.
(2), however, might spend more than constant time if the input consists of many appearances of an element $x$ for which $LZ(h(x))$ is large.

  Would you consider (2) to have an ``amortized'' constant time?

If not, is there anything more accurate than saying that it has "expected constant time per element"?

While these ``algorithms'' are clearly useless, there exist algorithms with a runtime similar to (2) (e.g., see here).

I wouldn't use the word amortized in this context, since there is no change of state between different operations (this is unlike classic examples for amortized analysis such as dynamic arrays). In that case amortized and worst case analysis will agree.

The first case is a randomized algorithm, so you can talk about the expected or worst case complexity (where in the former, the expectation is over the inner randomness of the algorithm). The worst case complexity is unbounded, while the expected number of operations is indeed constant.

In the second case, you have a fixed function $h$ which you use for all inputs, so again there isn't actually a change of state and thus there is no sense in talking about a recurring bad input. Note that the algorithm is not randomized (it does not toss coins after seeing the input), so the question you're looking for now is what is the average case complexity of your algorithm, where the expectation is over the choice of $x$ (relative to some distribution over $U$), and the random choice of  $h$. For a completely random $h$, you will get the same answer as in the first case.


Find the minimal tank capacity to be able to travel from any city to any other There are $n$ cities in the country. The car can go from any city $u$ to city $v$, On this road it spends $w_{u,v} > 0$ fuel. At the same $w_{u,v}$ can differ from $w_{v, u}$. The task is to find the minimal tank capacity to be able to travel from any city to any other (possibly with refuels) in $O(n^2\log n)$.

We first sort all edges according to their costs from small to large. Say the sorted edges are $e_1,e_2,\ldots,e_{n(n-1)}$, and the corresponding costs are $w_1\le w_2\le\cdots\le w_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e_1,\ldots,e_i$. Now $w_i$ is the minimal tank capacity we want.

Sorting costs $O(n^2\log n)$ time. To find the minimal $i$, we can use the bisection method. We first test whether the graph is strongly connected with the edges $e_1,\ldots,e_{n(n-1)/2}$. If yes, we then test the connectivity with the edges $e_1,\ldots,e_{\lceil n(n-1)/4\rceil}$, otherwise we test the connectivity with the edges $e_1,\ldots,e_{\lceil3n(n-1)/4\rceil}$, and so on. The running time to find the minimal $i$ is also $O(n^2\log n)$. So the total running time of this algorithm is $O(n^2\log n)$.


Are there minimum criteria for a programming language being Turing complete? Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete?

From what I can tell from wikipedia, the language needs to support recursion, or, seemingly, must be able to run without halting. Is this all there is to it?

I always though that $\mu$-recursive functions nailed it. Here is what defines the whole set of computable functions; it is the smallest set of functions containing resp. closed against:

The constant $0$ function
The successor function
Selecting parameters
Function composition
Primitive Recursion
The $\mu$-operator (look for the smallest $x$ such that...)

Check above link for details; you see that it makes for a very compact programming language. It is also horrible to program in -- no free lunch. If you drop any of those, you will lose full power, so it is a minimal set of axioms.

You can translate those quite literally into basic syntactical elements for WHILE programs, namely

The constant 0
Incrementation _ + 1
Variable access x
Program/statement concatenation _; _
Countdown loops for ( x to 0 ) do _ end
While loops while ( x != 0 ) do _ end


Please check my Huffman tree My professor gave an example of Huffman tree.

Given inputs

a 80
b 10
c 20
d 50
e 100
f 35
g 60

… then the tree will be:

But when i tried to solve it at home, I get this answer:

Which is correct, and why?

The average codeword length of your professor's code is $2.577$.

The average codeword length of your code is $2.662$.

Huffman's algorithm produces a code minimizing the average codeword length.

You draw the conclusions.


What mathematics can be interesting for these CS areas? For my CS degree I have had most of the "standard" mathematical background:

Calculus: differential, integral, complex numbers
Algebra: pretty much the concepts up until fields.
Number Theory: XGCD and related stuff, mostly for crypto.
Linear Algebra: up until eigenvectors/eigenvalues
Statistics: probabilities, testing
Logic: propositional, predicate, modal, hybrid.

My main interests in the CS area are security, cryptography and artificial intelligence.
I was wondering if there are any suggestions for mathematical topics that could be interesting for these areas, particularly for AI as it is not my main field of study at the moment.

For the field of A.I. and machine learning, I would recommend you to explore and learn more about these topics:

Statistics
Probability
Stochastic processes
Bayesian Data Analysis
Convex Optimization
Graph Theory

With your math background, you could easily pick any good machine learning book and learn the required math that you don't have as you go. Kevin Murphy's new book, Machine Learning: A Probabilistic Perspective, covers most of these topics and it serves as a good introductory textbook to machine learning.

I personally learned a lot from Dephne Koller's book, Probabilistic Graphical Models. It also covers most of the previously mentioned topics, but, as the book's name suggests, it focuses on graphical models.

Although both of these books have enough math to keep you busy for a while, you might find "The Elements of Statistical Learning", by Hastie et al. more useful if you want to focus more on the mathematical part of the machine learning.


If $L = \{ a^{2^n} \mid n \ge 0 \} $ is not regular, then why there is a DFA thats accepts its language? Let $L = \{ a^{2^n} \mid n \ge 0 \}$, which is a non-regular language (no proof here). Let $M = (\Sigma,Q,\delta,z_0,F)$ be a DFA with $\Sigma = \{a\}$, $Q = \{z_0\}$, $\delta(z_0, a) = z_0$ and $F = \{z_0\}$. Then the DFA should accept $L$ and $L$ is therefore regular. Why is my approach wrong?

The definition of an automaton accepting a language is that it must

accept every string that is in the language;
reject every string that is not in the language.

Your automaton does 1. but not 2. – it accepts all strings of $a$s, but it's supposed to reject all the strings whose length is not a power of two.


Reduction from NP-complete problem to unknown complexity problem and vice-versa Suppose I have two problems: $B$, which is NP-complete, and $A$, of unknown complexity.

Question:

If I show that $B \le A$ I can state that $A$ is also NP-complete because the two required conditions are satisfied: (i) $A$ is in NP; (ii) I reduced a NP-complete problem to $A$.
If I show that $A \le B$ I can say that $B$ is at least hard as $A$, so $A$ is at least NP-complete, but can be harder.

Are these statements correct?

I shall assume "$\le$" indicates a poly-time, many-one (i.e., Karp) reduction. This seems to be the case since you are referring to NP-completeness.

  If I show that $B \le A$ I can state that A is also NP-complete because the two required conditions are satisfied: (i) A is in NP (ii) i reduced a NP -complete problem to A.

If $B \le A$, that is, $B$ is reducible to $A$, then $A$ is necessarily $\mathbf{NP}$-hard, that is, any problem in $C \in \mathbf{NP}$ is reducible to $A$ (i.e., $C \le A$). This is because any problem $C \in \mathbf{NP}$ is reducible to $B$ (due to the $\mathbf{NP}$-completeness of $B$) and we have $C \le B \le A$; using the transitivity of (this form of) reduction we obtain $C \le A$. However, this does not at all imply that $A \in \mathbf{NP}$—otherwise, any $\mathbf{NP}$-hard problem would be $\mathbf{NP}$-complete! To prove $A$ is $\mathbf{NP}$-complete, thus, you would also have to prove $A \in \mathbf{NP}$ separately.

  If I show that $A \le B$ I can say that $B$ is at least hard as $A$, so $A$ is at least NP-complete, but can be harder.

$A \le B$ means $A$ is reducible to $B$, which can be reformulated as $B$ being at least as hard as $A$, as you have stated. In no way does this imply that $A$ is $\mathbf{NP}$-complete. Granted, it could be the case, but, for all we know, $A$ could be in $\mathbf{P}$, a regular language, or even trivial (i.e., $\Sigma^\ast$ or $\varnothing$).


What is the motivation behind " Descriptive Complexity "? Time and Space are two commons parameters (and also natural parameters) to measure the complexity of the problem. I am not able to understand the motivation behind defining " Descriptive Complexity". I search on the internet and find out that it is the complexity of expressing some property of the input. Take the example of the sorting problem. Time and Space seems to be a natural choice. I am unable to come up with an example or a problem which immediately implies the importance of defining the  " Descriptive Complexity ".

Question :  What is the motivation behind " Descriptive Complexity "?

If you're interested in logic, "what problems can you express in this logic?" is a completely natural question.

If you're interested in computational complexity, descriptive complexity gives another tool that you might be able to use to prove things. For example, the fact that existential second-order logic exactly corresponds to NP means that, if you can prove either (a) no logic corresponds exactly to P or (b) there is a logic that corresponds exactly to P but it has different expressive power to existential second-order, then you've proven that P$\,\neq\,$NP. And it's turned out that trying to prove it via logic has been exactly as fruitful as every other approach!


Relabel to front, what does topological sort according to admissible network mean? In the CLRS book it says that "relabel to front" algorithm, which solves the maximum-flow problem, maintains a list of topologically sorted vertices in the admissible network and that vertices with zero excess flow are moved to the front of the list.

I do not fully understand what is the meaning of it. I would imagine that the vertices are sorted according to the number of admissible edges incident on it. But then how would moving vertices with no excess flow to front affects the sorting order in this case. Also how come the list is already sorted when it is initialized with random order of vertices?

Edit:

Just realized that topological sorting of vertices in the admissible network means that for every admissible edge (u,v) in the admissible network the vertex u appears before v in the list.

This does not answer the last two parts of my question though, how is that the list is already sorted when initialized and how does moving zero-excess-flow vertices to front affect the order. Thanks.

By definition an "admissible edge" $(u,v)$ is an edge that has a residual capacity $c_f(u,v) > 0$ and the height of the vertex it enters is greater than the vertex it leaves by exactly one $h.u = h.v + 1$.

1- When the list is initialized, there exist no admissible-edges in the admissible-network because the height difference between all pairs of vertices in the network is either $|V|$ or $0$; only the source vertex has a height of $|V|$ while all other vertices has a height of $0$. Therefore, no matter which order of vertices we use, the list will be topologically sorted.

2- After relabeling a vertex $u$, there is at least on edge leaving $u$, but there are no edges entering it (according to lemma 26.28 in CLRS book p.750). Therefore, there can exist no other vertex $v$ such that $(v,u)$ is an edge and $v$ precedes $u$ in the topological order. So moving $u$ to the front of the list keeps it topologically sorted.


Questions about class of problems that can be solved with unlimited computational power, but access to only logarithmically many bits of the input? Consider the class $\text{DLOGTIME}^{\text{ALL}}$: the class of problems that can be solved by a machine with unlimited computational power but only access to logarithmically many bits of the input.  Which bits of the input it accesses can depend on the values of bits it has already seen, and it has random access to the input.  For conciseness, let's call this language $\text{X}$.

Does this class have a name?  What is known about it?

Here is what I know so far:

It includes problems that are very undecideable – it includes padded versions of every language whatsoever!
$\text{E}^\text{X} = \text{ALL}$ by a padding argument.
$\text{X}$ does not contain the problem $\text{PARITY}$ (are the number of 1 bits in the input even?).  As such, $\text{X}$ does not contain the regular languages.

Questions:

Is $\text{X}$ contained in $\text{P}/\text{poly}$?
Is $\text{X}$ contained in any other well-known complexity class?
What else is known about $\text{X}$?

It is contained in $P/Poly$

Let $M$ be a logarithmic time superoracle machine which decides some language $L$ in your class. We can define it by adding a special tape in which we can specify our desired language by writing some real number. Upon querying the oracle it will determine the membership of the given string to the specified language.

With polynomial length advice, you could provide the choice tree that determines what bits are read from a length $n$ input (if the first bit is x then go read y...). The questions to the oracles are determined by the bits read, and I can ask only a logarithmic number of questions (would work for polynomial too).

In the advice i could also hardcode a table which links any possible logarithmic input to the answers from the desired oracles. Given such advice and some input $x$, read the required bits using the choice tree, and simulate the special machine with the oracle answers given in the advice.


Converting English into Logic I'm learning about Logic; I've devised a few sentences to convert into logic to test myself and see if i've grasped the topic. It would be of great help if you could tell me if i'm doing it right!

Every student who likes chocolate is smart:

(Every student) (who likes chocolate) (is smart)

∀x ∈D, [Like (Student (x), chocolate) → Smart(x)]

There exists a barber that shaves all men who do not shave themselves.

(There exists a barber) (that shaves all men) (if and only if they do not shave themselves)

∃x ∈D, [Shaves (x, ∀y) → Shave (y, y)]

Thank you

These are both wrong, as they don't obey the syntactic rules of first-order logic. The rules are:

if $P$ is an $n$-ary predicate and $x_1, \dots, x_n$ are variables, then $P(x_1, \dots, x_n)$ is a formula;
if $\varphi$ and $\psi$ are formulas, then $\neg \varphi$, $\varphi\wedge\psi$ and $\varphi\vee\psi$ are formulas;
if $\varphi$ is a formula and $x$ is a variable, then $\exists x\,\varphi$ and $\forall x\,\varphi$ are formulas;
nothing else is a formula.

(If you like, you can say that $\varphi\rightarrow\psi$ and $\varphi \leftrightarrow \psi$ are formulas, or you can say that they're just abbreviations for $\neg\varphi\vee\psi$ and $(\neg\varphi\vee\psi)\wedge(\varphi\vee\neg\psi)$, respectively.)

There's often more than one way of translating any English-language statement into a first-order sentence.  Decide what your domain is going to be and the rest will follow.

Every student who likes chocolate is smart.
Here, you have several choices of domain, such as the following.

Domain is the set of all students: $\forall x\,\big(\mathrm{LikesChoc}(x)\rightarrow\mathrm{Smart}(x)\big)$. Since everything in the domain is a student, the variable $x$ can only be a student so you don't need a predicate to say that.
Domain is, say, the set of all people: $\forall x\,\big(\big(\mathrm{Student}(x) \wedge \mathrm{LikesChoc}(x)\big)\rightarrow \mathrm{Smart}(x)\big)$. The domain now includes things that aren't students, so we need to enforce that with a predicate. A professor who likes chocolate isn't necessarily smart.
Domain is, say, the set of all people and all foods. $$\forall x\,\big(\big(\mathrm{Student}(x) \wedge \exists y\,\big(\mathrm{Chocolate}(y) \wedge \mathrm{Likes}(x,y)\big)\big)\rightarrow \mathrm{Smart}(x)\big).$$ That is, for every entity $x$, if $x$ is a student and there is a thing $y$ that is chocolate and is liked by the student $x$, then $x$ is smart. I've assumed that "likes chocolate" means "likes at least one thing that is chocolate"; you could interpret it to mean "likes all things that are chocolate", and you can probably figure out how to change the formula to reflect that.

There exists a barber who shaves all men if, and only if, they do not shave themselves. I'll let you have another go at this. Try taking the domain to be the set of men, with a unary predicate that says who's a barber and a binary predicate (as you have), that says who shaves whom.


For proof automation in Coq, when is it appropriate to use canonical structures or Equations instead of Ltac? There are a few possible approaches to proof automation in modern Coq.

Writing proof scripts with Ltac. This is the approach described in http://adam.chlipala.net/cpdt/, which the author uses to great effect in projects like http://adam.chlipala.net/papers/BedrockPOPL15/. It can significantly reduce the amount of proof code required, but requires a good handle on the quirks of Ltac and does not seem straightforward to debug.
Canonical-structures-based automation. This is the approach described in https://people.mpi-sws.org/~beta/lessadhoc/, and used in Mathcomp. It involves taking advantage of Coq's type inference mechanism to automatically execute logic programs that search for certain kinds of proof terms. It's described in that paper as less ad-hoc than the Ltac-heavy approach, but not necessarily faster, and can be more verbose due to needing to use the canonical structures mechanism for something it wasn't directly designed for.
Dependent types/Equations. The Equations plugin (https://www.irif.fr/~sozeau//research/publications/drafts/Equations_Reloaded.pdf) seems to faciliate in Coq the same convenience when working with dependently typed programs as a language like Agda or Idris. With this approach the elaborator acts as a form of automation, and the amount of proof code is reduced by having algorithms create, manipulate and pass around proof terms directly.

There are also some modern developments that complement these.

Ltac2. This is meant as a replacement for Ltac, with fewer quirks and potentially better performance, as described in https://popl19.sigplan.org/details/CoqPL-2019/8/Ltac2-Tactical-Warfare. The paper states that "Ltac2 is still in an active development phase, but the foundations of the language have been settled. More than anything, it is in need of users in order to polish the rough edges". If it is meant to be a superior replacement to Ltac, then should it be considered instead of Ltac for new projects, since it's already ready for user testing?
Metacoq. This provides metaprogramming features that allow the development of higher level tools, as described on https://www.irif.fr/~sozeau/research/publications/drafts/The_MetaCoq_Project.pdf, and presumably simplify the use of proof by reflection, a technique used in both canonical-structures-based an Ltac-heavy approaches.

My question is, if I'm starting a new project, what criteria should I use to determine which approach or combination thereof to adopt? As a concrete example, imagine I want to verify the easy-to-verify parts of a program that connects to a server over the internet, downloads some data, processes the data somehow, then serves the processed data over TCP. By easy-to-verify I mean not verifying the TCP/HTTP stack, or proving from scratch the correctness of well-known algorithms used in the data processing. When I consider how I'd structure this it seems like the structure would be quite different depending on which of the above approaches I used, and I lack the experience to make a judgement regarding which would produce the best result in terms of maximising the output of verified code per unit of development time. What factors should necessitate the use of canonical structures or Equations instead of just plain Ltac?

Choosing how to structure your development based on what proof automation you're using seems backwards.  First you decide what functions and definitions you want to prove theorems about, then you decide what theorems you want to prove, and then finally you decide how to prove them.  Unless you are doing interesting abstract math, it is not until the third step that you should even consider what the proof automaton will look like.

There's an intermediate step, which is deciding how dependently typed to make your code.  Unless you know what you're doing, the first rule of thumb is that you should never combine your proofs and your programs; the proofs must depend on the programs, but the programs must not depend on the proofs.  (The second rule of thumb is that if you do convince proofs and programs, you must never separate them after they are combined, or must never recombine them after they are separated.  This case comes up when formalizing abstract math.)

After you have decided what theorems to prove, now you must decide how to prove them.  This is best done on a whiteboard, or with paper, or talking with colleagues.  There are a couple different kinds of proofs you might be writing:

are you doing very finicky dependent type hackery?  Use Equations or build the proof term yourself.  (This is not entirely fair to equations, but I think it occupies the unfortunate middle ground of being most useful when you have dependent types that are painful enough that you don't want to deal with them manually, but not so painful that it's hopeless to avoid manual labor)
are you writing a well-defined decision procedure?  Use canonical structures if you want something fast, lightweight, easy to do proofs about, but exceedingly hard to debug.  Use MetaCoq if you want something powerful and general.  Use your own custom reflective automation if the generality of MetaCoq makes proving things too painful (I'm not actually sure how much MetaCoq gives you out of the box; it's plausible that proving things in it is quite easy.)
are you performing long complicated chains of reasoning that don't generalize?  Then write your proof by hand (perhaps using ssreflect).  But also reconsider your decisions about what theorems to prove, and maybe include more lemmas.
are you proving things by taking a bag of tricks and throwing them at your problem again and again until it's solved.  You probably want Ltac2 (or Ltac, if you're not ready to use a language still requiring a great deal of polish, and would prefer instead to use a stable language which is overflowing with quirks).  If you have good tactic hygiene, Ltac is not too painful to debug (and Ltac2 is much better).  The rule of thumb when writing tactics is that every tactic should either do one precisely specified thing (these are tactics like destruct, induction, revert, generalize, rewrite, etc), or should be nothing more than "keep repeatedly trying whichever tactics in this bag of tricks work" (tactics like auto, autorewrite, now, easy, done, trivial, etc).  If you have tactics in the middle-ground, that try to apply this bag of tricks then that bag of tricks then this chain of reasoning and then this third bag of tricks, then you will be in for a rough time.


Binary Search Tree: Replace $k$ min elements with their average Given a valid binary search tree whose keys are unique real numbers, and a set of $k$ pointers to the $k$ minimum elements in the tree, will the BST property be maintained if I replace all $k$ elements with the average of the $k$ elements?

The BST property as given in Corman:

  Let $x$ be a node in a binary search tree. If $y$ is a node in the
  left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the
  right subtree of $x$, then $y.key \geq x.key$.

I've tried this with a few test cases for $k=3$ and a few different trees, and it seems to hold, but I'm not sure if it actually does and how I could prove it.

The following is either a proof, or an argument that runs in circles.

Given a binary search tree the ordered sequence of keys can be retrieved using the symmetric inorder traversal. Conversely any ordered sequence of keys can be stored in a binary tree with the BST property only if the keys are mapped precisely in inorder. (Proof: the root has a unique value as all keys the the left must be smaller, to the right must be larger. Use recusion for the subtrees).

Now take a BST tree and retrieve its keys in order. Take any consecutive segment of the keys and replace these keys by any value between the first and last of the segment. The result is again an ordered sequence of keys and remapping to the original tree will give again a BST.

Taking the minimum $k$ values and replacing with the mean is a special case.


Create a schedule from overlapping events Let me first sketch my situation. I have a list of events with time slots, and I need to generate a schedule from these. We can assume that I have already validated and ordered the events from lowest to highest priority, so I will have a list like:

Starts  Ends   Event
---------------------------------
   0     12    Background
   2     3     Event A
   4     7     Event B
   6     9     Event C
   6     10    Event D

and I want to generate from this the following schedule

Starts  Ends   Event
---------------------------------
   0     3     Background
   2     3     Event A
   3     4     Background
   4     6     Event B
   6     10    Event D
   10    12    Background

Of course there is the naive O(n²) algorithm

schedule: []

for each currentEvent in events:

   piecesToAdd = [currentEvent]
   for each eventSoFar in schedule:
     determine the overlap
     modify eventSoFar and piecesToAdd to remove overlap

   append piecesToAdd to schedule

but I was wondering if there is a more efficient way.

If all the time slots are integers, I thought I could just fill a big array at the start with

Starts  Ends   Event
---------------------------------
   0     1     Background *
   1     2     Background *
   2     3     Background *
   3     4     Background
   ...

but in general I do not want to (and probably cannot) assume that this will be the case. Still, if non-integer time slots are the exception rather than the rule, it may be better to start out like this and split the predefined slots only when needed. But then I need a postprocessing step to consolidate all consecutive slots with the same event, i.e. collapse the lines marked * in the example above into a single "Background: starts 0, ends 3" entry.

It looks like this will be scripted in PHP so any language-specific tricks are welcome, but I am mainly curious about the most efficient way to program this in general.

One idea would be to construct an additional list of so-called 'changes'. So for your data it would look like this:

Time   Change
0      Background Start
12     Background End
2      Event A Start
3      Event A End
4      Event B Start
...

Then sort by 'Time' O(n log n)

Time   Change
0      Background Start
2      Event A Start
3      Event A End
4      Event B Start
6      Event C Start
...

Construct an empty balanced binary search tree T. Loop over the changes in order, when a change is an 'event start' add that event to T, when the change is an 'event end' remove it from T. At each change determine the highest priority event and do that until the next change (If it is not different than your last event, in which case just keep doing it).

Each of the tree operations is log n, and are done n times so this is all O(n log n). Most languages have some sort of balanced tree that could be used. You could encode the event changes as integers which represent the priority, positive meaning add this event, negative meaning remove this event. This works with non-integer times.


The most appropriate way to implement a heap is with an array rather than a linked list, why is this? The most appropriate way to implement a heap is with an array rather than a linked list, why is this?

I don't completely comprehend why this is? is it because it is easier to traverse?

It doesn't make any sense at all to implement a heap as a linked list. (The most common kinds of) heaps are inherently binary trees. You can store a heap in an array because it's easy to compute the array index of a node's children: the children of the node at index K live at indices 2K+1 and 2K+2 if indices start at 0 (or at indices 2K and 2K+1 if indices start at 1). It's massively more efficient to find the Kth element of an array than the Kth element of a linked list.
Advantages of storing a heap as an array rather than a pointer-based binary tree include the following.

Lower memory usage (no need to store three pointers for every element of the heap).
Easier memory management (just one object allocated, rather than N).
Better locality of reference (the items in the heap are relatively close together in memory rather than scattered wherever the allocator put them).


Lower bound on running time for solving 3-SAT if P = NP Is there a lower bound on the running time for solving 3-SAT if P = NP.  For instance, is it known that 3-SAT can't be solved in linear time?  What about quadratic?

These are some of the best time and space bounds known. In this area the research has gone to the direction of giving bounds in both time and space. My understanding is that superlinear time bounds without a space constraint are not known.

Time-Space Lower Bounds for Satisﬁability Lance Fortnow, Richard Lipton, Dieter van Melkebeek

  We establish the ﬁrst polynomial time-space lower bounds for satisﬁability on general models of computation. We show that for any constant $c$ less than the golden ratio there exists a positive constant $d$ such that no deterministic random-access Turing machine can solve satisﬁability in time $n^c$ and space $n^d$, where $d$ approaches 1 when $c$ does.


What is the purpose of Bayesian networks? I have seen a lot of explanations of what Bayesian networks are, but I simply cannot wrap my head around their use in code. So here is my three part question.

Am I right in my definition of Bayes nets? Bayesian networks are a way to (visually) portray how variables/events are linked and how they will affect each other. Probabilities can be added to each node to give you a greater sense of what will happen. In conjunction with an acting AI, Bayes nets are used to predict the AI's actions and inform what it should be doing, i.e. giving minimax a better prediction.
Can you give a pseudo code representation of a Bayes net?
Let's get a little more specific. I have a creature simulator, the creature has a home where he sleeps and, there are patches of grass where he eats. There are other creatures out there that he wants to avoid because they will fight him. So his action -> reaction set is:

{hungry->find food -> eat food
tiered -> go to shelter -> sleep
in danger -> avoid other creature
under attack -> run to shelter}

I am trying to express this as an mdp so that it will learn what actions are best when; and what are the best spots (most prosperous & least dangerous) on the map.

How, if at all, am I supposed to use a Bayes net? If the situation requires probabilities feel free to add your own, pseudo code also appreciated.

I am trying to state a possible bayes net:
What the creature wants to know is what to do next. So the root node is 'ACTION'. Possible actions are (let's say field 1 = home): [move to field 1, move to field 2, ... move to field n, sleep, eat] or [go north, go south, go east, go west, eat, sleep]. 'ACTION' depends on the creature's 'STATE', that can be [afraid(by another creature), under attack, hungry, tired]. 'STATE' depends on 'ANOTHER CREATURE' and 'FOOD AVAILABLE'. The latter two nodes can be [yes,no] and both depend on the current 'FIELD', [field 1, ..., field n].

'FIELD' -> 'ANOTHER CREATURE'

'FIELD' -> 'FOOD AVAILABLE'

'ANOTHER CRATURE' -> 'STATE'

'FOOD AVAILABLE' -> 'STATE'

'FIELD' -> 'ACTION'

'STATE' -> 'ACTION'

Each node has a table containing the probabilities p(value|value of dependency1, value dependency2,...). For example the 'ACTION' table holds the probabilities for each combination of p(action to take | value of 'STATE', value of 'FIELD').

I think suitable methods to estimate the model's probabilities are Q-learning or SARSA-learning.


Splitting the array in the median-of-median solution for $k$th smallest element problem Regarding the median of medians solution to the $k$th smallest element in an array, why does the algorithm split the array into subarrays of length $n/5$, where $n$ is the length of the initial array? Why not $n/7$ or $n/3$? Why 5??

Along with the explanation given on wikipedia, I'll try to give more visual examples. The main point is that subarrays of length $ \frac{n}{3}$ make it a non-linear algorithm.

We can actually check out the 3 scenarios you discuss. I'm going to be referring to area diagrams similar to the one depicted on wikipedia. These area diagrams are a useful abstraction to see how large of a subproblem we might have to recurse on in the worst case. The area diagrams will look something like this:

Where $M$ is median of medians, $(< M)$ and $(> M)$ represent the area (amount of values in the array) that are potentially less than $M$ and greater than $M$ respectively, in the worst/best case. Note that in the area diagrams I present I say the area is roughly (~) some value. This is because it may be off by one or two and I am largely ignoring these small constants because they will be insignificant to the analysis. If you are bothered by this, you can assume $n$ is of a useful form such that the values are exact.

For $\frac{n}{3}$ size subarrays we will end up with an area diagram like this:

It is clear that in the worst case we will have to recurse on roughly $\frac{4 n}{6}$ elements in the array. This will give us a recurrence relation:
  $$\begin{align}
T(n) & = T\left(\frac{n}{3}\right) + T\left(\frac{4n}{6}\right) + cn\\
& = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + cn
\end{align}$$
  This actually turns out to be on the order of $O(n \log n)$. I won't go through an explicit proof of this recurrence because I'm sure it's been done before. If you wish to prove it to yourself, you can use a similar approach to this, or use the recursion tree method, or use the Akra-Bazzi method. So this subarray size won't work because we now have non-linear time complexity.

For $\frac{n}{5}$ size subarrays we will end up with an area diagram like this:

We similarly get a worst-case recurrence of the following:

$$T(n) = T\left(\frac{n}{5}\right) + T\left(\frac{7n}{10}\right) + cn$$

This is linear $O(n)$! You can use this method directly to prove it is linear.

For $\frac{n}{7}$ size subarrays we will end up with an area diagram like this:

We similarly get a worst-case recurrence of the following:

$$T(n) = T\left(\frac{n}{7}\right) + T\left(\frac{10n}{14}\right) + cn$$

This is also linear! Again, you can use the method I described above to prove this.

So in conclusion

Diving the subarrays into length $\frac{n}{3}$ will not be good because it is non-linear! Diving the subarrays into length $\frac{n}{5}$ or $\frac{n}{7}$ will be very good because it is linear! You can actually go on to use $\frac{n}{9}, \frac{n}{11}, \ldots$ and still get linear time!


Is there any difference between the terms userland and userspace? Sometimes I read about the term userland and sometimes userspace.

From Wikipedia, it is said that userland is referring userspace:
https://en.wikipedia.org/wiki/Userland

Is there any difference between the terms userland and userspace?

Taken from yourdictionary.com

  Userland: (computing, informal) A conceptual space outside the kernel in which a user's applications can run without the risk of damage to the operating system.

  Userspace: (computing) The area of memory used for a user's applications, etc., as opposed to that reserved for the operating system


Uncertainty whether $\{a^i b^j c^k \mid i+j \le k\}$ is context-free or not I'm having trouble with this particular language: $$\{a^i b^j c^k \mid i+j \le k\}$$

If it's not context-free, I don't know how to correctly apply the Pumping Lemma for CFLs; if it is context-free, I don't know how to create a context-free grammar that generates this language.

Which one applies? Can you help me out?

Hint. $k = i + j + ?$, so the language is $a^ib^jc^?c^jc^i$.


largest subset of pairwise intersecting intervals Given a set of intervals on the real line, compute the largest subset of pairwise
intersecting intervals (an interval in the subset must intersect with every other interval
in the subset). Design a greedy algorithm that computes an optimal solution.

First, suppose the intervals $[l_1,r_1],\ldots,[l_n,r_n]$ are pairwise intersecting, then we have $l_i\le r_j$ for any $i,j$, which means for any $i$,  $l_i\le\max_k l_k\le r_k$, i.e. all these intervals contain the point $\max_k l_k$.

The observation above leads to the algorithm mentioned in jaxa 9831's answer:

  First, sort the intervals according to their left endpoints. Then at each left endpoint, check how many intervals cross that point. Finally, report the optimal one.

To efficiently find the point that maximum intervals cross, we can use an algorithm mentioned in GeeksforGeeks. Roughly speaking, we first sort all endpoints, and maintain a counter initialized with 0. We then travel these endpoints from left to right. Each time we come across a left endpoint, we increase the counter by 1, while each time we come across a right endpoint, we decrease the counter by 1. The maximum value of the counter represents the maximum number of pairwise intersecting intervals.


Space and time complexy of operations on 32-bit array vs. binary array Assume an array a of length $n$. I am wondering how to characterize the difference between time- and space complexity of 32-bit arrays of length $n$ and bit-arrays of length $n$.

Normally, you'd just state the array uses $O(n)$ space and algorithms run in $O(n)$, $O(n^2)$ and so on. But isn't there some difference between the two arrays?

I have read something about the word-size but I can't figure out how this fits into the picture..

PS.
In an actual implementation (e.g Python). There is no difference between the space used by:

a1 = [1, 402, 303]
a2 = [1,0,1]

Right?

If you ignore the word size then both arrays use $\Theta(n)$ space. Remember that $32n = \Theta(n)$.

If your word has a (non-constant) length of $w$ bits and all the integers in a1 fit in a constant number of words (with no additional assumptions on their values), then a1 still uses $\Theta(n)$ words, while you can represent a2 using $\Theta(\lceil \frac{n}{w} \rceil)$ words (by packing groups of $w$ bits of a2 into a single word).

A common choice of $w$ in the word-RAM model is $w=\Theta(\log n)$.

In your Python example there is no difference between a1 and a2 since both lists are storing integers (using a fixed number of bytes that depends on the implementation and architecture, and assuming that the stored integers fit within the maximum integer representable using these bytes. Handling arbitrary precision integers is another story).
However there might be ad-hoc types specifically designed to handle indexed collection of bits (e.g., bitsets).

Also, the language/implementation might optimize the array representation when it knows that it will store bits. This is the case, for example, of std::vector<bool> in C++, which can possibly reduce the space usage by some constant factor by packing bits into integers (as described above). For a fixed words size (e.g., 32 or 64 bits), this does not change the asymptotic space complexity.


What is the difference between Data Hazard and Dependencies in Pipelining In my GATE Exam I have given with the following question  statements and

R5 ← R0 + R1
R6 ← R2 * R5
R5 ← R3 - R6
R6 ← R5/R4
X  ← R6

the question was to calculate number of Output, True and Anti Dependencies in the instructions.
I calculated and it turns out to be
RAW (True Dependency)

I1 - I2 (R5)
I2 - I3 (R6)
I3 - I4 (R5)
I4 - I5 (R6)

WAR  (Anti-Dependency)

I2 - I3 (R5)
I3 - I4 (R6)

WAW (Output Dependency)

I1 - I3 (R5)
I2 - I4 (R6)

Now my friend argued

Had the question been to calculate the number of possible data hazards the answer would have been different because Dependencies and hazards are not same

When we calculate possible hazards we should reorder the instructions and find the dependencies. Dependencies and hazards are closely related but not same. He has also gave me a pdf which implies that a dependency may not be a hazard. A dependency is a "possible hazard" considering all cases which involve reordering of instructions etc. But the solution of GATE question is involving those dependencies only which are causing hazards only not potential or possible hazard.
I go through them but was not able to finalize proper relationship between hazard and dependencies.
Can someone please explain how Dependencies, Possible Hazards and Potential Hazards  relate to each other in a way more easily understood? (Explanation using the above instruction set  is preferred)

I think a dependency is something you see by looking at the code and trying to figure out possible WAW, WAR, RAW hazards that could happen. Actual hazards instead are a property of the pipeline which means that a dependency you found earlier may or may not generate an hazard depending on the actual code execution in the processor.
In your example there's an output dependency between the instructions I2 - I4, but if we assume that the pipeline does not stall for any reason between the two and that the execution time for each instr. is the same, I2 wll be completed before I4 thus not generating any hazard.
To make the answer more clear, with the information you give about the excercise it's impossible to know the number of hazards because we don't know the architecture on which that code is executed nor the state of the pipeline.
I found your question searching for an answer so I'm not completely sure. Since you asked some months ago maybe you already found the correct answer. If so could you share it please ?


Smallest Circuit for Square of Sparse Symmetric Matrix I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input will be sparse by the output will be nearly a density of 1. A normal sparse multiplication algorithm would take O(n^2) time which is clearly optimal, but the circuit depth for any sparse representation I can think of is at least O(n^3). (The act of "accessing a given location in memory" is not efficient in circuits.)

Using a fast matrix multiplication method like Coppersmith Winograd would bring me to O(n^~2.4). I know I can use the symmetry to reduce by a constant factor, but I figure not more than that. I'm hoping that the fact that it's squaring (and not multiplying two different matrices) can reduce the exponent, but I don't know how -- I know that it can cut my work down a bit because the first iteration of C-W will have some identical results. I can't find any way to use the sparsity at all.

Numerical precision isn't an issue for me; the input is a 0-1 matrix.

In terms of practical purposes, I particularly care about n~3000, but am generally curious about asymptotically good answers too. (Just saying this to explain that very huge constant factors are a big negative for me.) Any references very much appreciated!

If it's really depth that you care about, I think you should be able to do it with a circuit of depth $O(\log^2 n)$ using sorting networks.  I'll assume we want to compute the product $AB$, and that $A$ is represented as an array of rows, where each row is a sorted list of non-zero entries; and $B$ is an array of columns, where each column is a sorted list of non-zero entries.  Then the $ik$ cell of the product $AB$ (namely, $(AB)_{ik}$) can be computed as follows: copy the entire row $A_{i\cdot}$; copy the entire column $B_{\cdot k}$; concatenate these two lists; sort them based on their indices, using a sorting network, to bring together entries with a common index; at each position where both matrices have an entry, multiply those entries; and sum up those products.  You can build a sorting network with depth $O(\log^2 n)$, and the multiply-and-sum step can be done with depth $O(\log n)$ using an addition tree.


Why has Windows used NTFS for 20+ years, while many different systems have trendend in the linux community over the same time? I'm a first year MS:CS student, and my data structures class has inspired me to research file systems and their implementations.  I recall using ext2, then ReiserFS, then ext3, then ext4, and now btrfs seems like the new thing.  I understand (more or less) what changed from each of these, and their relative improvements, but what I don't understand is how NTFS has stayed relevant during roughly the same period of time (looks like the last major version of NTFS shipped with Windows XP).
Was NTFS simply that well spec'd and designed from the beginning, or has Windows been working around some NTFS deficiencies in the interest of not having to rewrite some core parts of Windows from scratch?  If that is the case, why are linux distros much more flexible in changing FS (user can even select a different FS at install time).

NTFS is pretty good. From the start it had journaling (unlike ext2), size limits large enough that they would never be an issue (unlike ext2/3), and a flexible design that allowed arbitrary attributes to be defined and attached to files.

Developing filesystems for Windows is difficult. The necessary headers and documentation were for years not included in the Windows driver development kit; instead you had to, I think, sign an NDA and pay thousands of dollars for the IFS kit and support. The number of features you'd have to implement to be able to replace NTFS is large. Filesystem design is a black art under the best of circumstances. And Microsoft probably wouldn't want to support a filesystem designed by a third party in the default Windows install no matter how good it was.

Your list of popular Linux filesystems isn't all that long. ext2-4 are all pretty similar to each other, and btrfs is similar to ReFS.


Minimum cost node cut I am interested in solving the following problem:

  Given an undirected graph whose vertices are weighted, find a subset of vertices of minimal weight whose removal disconnects the graph.

Is there any known algorithm solving this problem?

Here is an attempt at a solution (in python), using network flow:

deg_G = nx.degree(G)
max_weight = max([deg for i,deg in deg_G])+1

st_Weighted_Complement_G = nx.DiGraph()
r = np.arange(len(Complement_G.nodes))

nodes = ['s','t']
edges = []
for i in r:
    nIn = (str(i)+'in')
    nOut = (str(i)+'out')
    nodes.extend([nIn,nOut])
    edges.extend([(nIn,nOut,{'capacity':deg_G[i],'weight':deg_G[i]}),('s',nIn,{'capacity':math.inf,'weight':0}),
                  (nOut,'t',{'capacity':math.inf,'weight':0})])

for edge in Complement_G.edges:
    print(edge[0],edge[1])
    edges.extend([((str(edge[0]))+'out',(str(edge[1]))+'in',{'capacity':max_weight,'weight':0}),
                  ((str(edge[1]))+'out',(str(edge[0]))+'in',{'capacity':max_weight,'weight':0})])

print(edges)
st_Weighted_Complement_G.add_nodes_from(nodes)
st_Weighted_Complement_G.add_weighted_edges_from(edges)

mincostFlow = nx.max_flow_min_cost(st_Weighted_Complement_G, 's', 't',capacity='capacity',weight='weight')
print(mincostFlow)

Your problem is a slightly more general version of computing the vertex-connectivity of a graph. If all weights are equal, then it is equivalent to the vertex-connectivity problem.

The problem can be solved in polynomial time with network flow, yes; but you'll need to invoke a network flow subroutine several times; just one invocation won't be enough.

The simplest approach is the following. Consider all pairs $s$, $t$ of nodes in the graph. For each such pair, we are going to compute the minimum cost, call it $c_{st}$, of separating that pair, that is, the weight of a minimum vertex-weighted $s$-$t$ cut. Then the set you look for will be the set achieving the minimum cost $c_{st}$ over all pairs $s$, $t$.

For a given pair $s$, $t$, the minimum weight cut can be computed with network flow by first replacing every edge $\{u,v\}$ with a directed pair of edges $(u,v)$, $(v,u)$. Then you need to expand your graph by splitting every vertex $v$ into a pair $(v^-, v^+)$. An arc $(u,v)$ is replaced by an arc $(u^+, v^-)$ and an arc $(v,u)$ is replaced by an arc $(v^+, u^-)$. Moreover you add arcs $(v^-, v^+)$ with capacity equal to the weight of $v$; all other arcs have unbound capacity ($\infty$). This complication is necessary to properly model the vertex removal costs. After creating this new instance, you just call the network flow subroutine with source $s^+$ and sink $t^-$. The amount of flow shipped from the source in the solution will tell you $c_{st}$. (To find the set of vertices disconnecting $s$ from $t$, look for all vertices $v$ such that $v^-$ is reachable from $s^+$ in the residual flow network while $v^+$ is not.)

All in all, you need to call the network flow subroutine $n(n-1)/2 = O(n^2)$ times. In fact, there is also a less intuitive but somewhat faster algorithm that allows you to call the network flow subroutine $m$ times instead of $n^2$, where $m$ is the number of edges. This could be much better if the graph if sparse. See the reference below for more details about this faster version.

You can also substantially reduce the time complexity if you know for sure some vertex $s$ that is not going to be one of the nodes that will be removed from the graph. Then you can just try all other nodes $t$ and follow the same strategy as above, only this time you will need to invoke $n-1$ times the network flow subroutine, because $s$ is fixed.

Reference: A. Schrijver, Combinatorial Optimization, Section 15.2. Springer, 2004.


Asymmetric Transition Probability Matrix with uniform stationary distribution I am solving a discrete  Markov chain problem. For this I need a Markov chain whose stationary distribution is uniform(or near to uniform distribution) and transition probability matrix is asymmetric.

[ Markov chains like Metropolis hasting has uniform stationary distribution but transition probability matrix is symmetric ]

Take the matrix $A$ such that for every $i$, we have:

$A_{i,i} =0.5$
$A_{i,i+1}=0.5$ (for $i=n$, set $A_{n,0}=0.5$)

Then it is not symmetric, but has a uniform stationary distribution.


Analysing a small recursive algorithm I need to calculate the complexity of func5, depending on variables $n, m$.

func4 is a function whose complexity is $\Theta(n+m)$

void func5(int a[], int n, int m, int b[])
{
    if (n==0) { return; }
    *b = func4(a,n,m);
    func5(a+1,n-1,m,b+1);
}

I get an expression which looks like:

$$C_1*n + C_2*(nm+n^2) - C_2(1+2+3+..n)$$

$C_1$ is the operations done in each iteration of func5,
$C_2$ is the operations done in each call to func4,
and the substraction comes since func4 is receiving each time a smaller $n$ by one.

The answer says that complexity is $\Theta(n*m+n^2)$ but I don't understand how to find the constants leading to Big-Theta notation.

Thanks.

Since $1+2+\cdots+n = \frac{n(n+1)}{2}$, your expression is equal to
$$
C_1 n + C_2 (nm+n^2) - C_2 \frac{n^2+n}{2} = C_2(nm+n^2/2) + (C_1-C_2/2)n.
$$
This shows that for constant $m$ and large enough $n$, your expression is at least $(1/2-\epsilon)C_2(nm+n^2)$ (for any $\epsilon > 0$ and, if $C_1 \geq C_2/2$, even for $\epsilon = 0$), and at most $(1+\epsilon)C_2(nm+n^2)$ (for any $\epsilon > 0$ and, if $C_1 \leq C_2/2$, even for $\epsilon = 0$).