In Asyptotic notation if g(n) < f(n) is it possible to have f(n)<=c*g(n)

Everything depends on the type of relation you want to define between f and g.

In O and Ω you just have to find one c>0 and one N for which the corresponding inequality between f and g holds and the relation shall be established.

In o and ω you have to show that for every c>0 you can find some N such that the corresponding inequality shall hold for all n > N.

Perhaps this can help you understand it better.


Finding a method to classify pixels according to how drastic their intensity change

One approach to distinguish between (1) vs (2)-or-(3) is to use a statistical hypothesis test.  A statistical hypothesis test can tell you whether the amount of change is too large to be explained by random chance.  One reasonable approach might be to use linear regression: try to model intensity as a linear function of time $y = at+b$, and then use a statistical hypothesis test to see whether the coefficient $a$ is positive (i.e., $a>0$ and the null hypothesis $a=0$ can be rejected at a 99% significance level).

Once you've identified all the type-(1) pixels, it's not clear how to distinguish between (2) vs (3), because you haven't given us a precise definition of what counts as drastic vs slow.  One reasonable approach would be to again use linear regression, and then use a threshold $\alpha$: if it's not a type-(1) pixel and $0<a\le \alpha$, then classify it as type (2), else if if it's not a type-(1) pixel and $a \ge \alpha$, then classify it as type (3).  You'd have to set the threshold $\alpha$ in some way that's appropriate for your application.  You could of course consider variations on this, e.g., where the linear regression only considers observations from the last 10 seconds of time (or whatever), or weights more recent observations more highly, etc.


Is a matching $M$ maximum iff the graph doesn't have an augmenting path wrt $M$?

An augmenting path must alternate between gold and black, starting and ending with black edges. In this way, if you replace the gold edges with the black edges, you obtain a larger matching. This argument shows that a matching can only be maximum if there is no augmenting path, and Berge's theorem states the inverse direction: if a matching has no augmenting path then it is maximum.


Why is it not a good idea to branch a thread outside of a parallel region while other threads are still executing?

OS functions are called to create and join a thread.
The main thread waits for all created thread to return (join).  When a thread jump out in middle, the main thread will wait infinitely. In the example you have given one of the spawned thread jumps to a location in main thread. It will proceed and the program will eventually end. Any thread can exit/close the program. It may be the case that other spawned threads are in different stages of their execution and since parent (main) thread has exited, they will terminate inflight as well.
A lot of resources allocated to the abruptly terminated threads by OS, will waste. A properly terminated thread releases all the resources allocated to it properly, improperly terminated threads won't.


Create Shortest Path tree for every node after Floyd Warshall in O(nm)

Compute all pair to pair distances $D[u,v]$ for $u,v \in V$ using Floyd-Warshall.
For each vertex $s \in V$ construct a graph $H_s$ as follows:

For each edge $e = (u,v)$ check whether $D[s,u] + D[u,v] = D[s,v]$. If the answer is yes the (directed) edge $(u,v)$ belongs to at least one SPT from $s$, and you add $e$ to $H_s$.

This requires time $O(n \cdot m)$ and each graph $H_s$ is encoding all SPTs from $s$. To get a single SPT from $T_s$ each $s$ compute any spanning arborescence of $H_s$ rooted in $s$. This can be done, e.g., via a BFS.


How does the index of a disk work in finding the desired address?

The index specifies the cylinder, head, and sector where the data resides.  The hard drive then moves the arm/head so it is positioned over that block and reads the data stored in that block as the disk rotates under the arm.  The hard drive then sends that data back to the processor.   Read http://pages.cs.wisc.edu/~remzi/OSTEP/file-disks.pdf for more of an overview how hard drives work.


Understanding x64 and x86 OS with 64bit cpu

You should notice there are two directories for your program files. For the directory with the suffix x86 it contains the programs which are based on 32-bit addresses. Any program which is made to produce 32-bit addresses is compatible with 64-bit architecture but not vice-versa. The OS installs the programs based on 32-bit addresses in the x86 directory.


I assumed that you have calculated the probability of successful transmit (which is about 1e-4 or something)

$$
P[trials =  3] = P[Fail] ^3 * P[Succ]
$$
$$
Average = E[X] = 1/P[Succ]
$$

Please revise or study (if you haven't) the geometric distribution


Language to Construct Finite State Transducer

Yes, such a specification would work. Basically a FST is a finite state automaton, with different labels on the edges. We can go from FST to regex by a standard algorithm. The same method works with transducers, only the labels are now pairs of strings. The concatenation of labels is done component-wise: $(a,x)(b,y) = (ab,xy)$.

There are several types of FST. To obtain a general one both input and output component are strings, not just letters. It is not difficult to see that alternatively one might require that both input and output are either a letter or the empty string.

All said, I personally prefer as a "language" the finite state graphs: they are easy to "program".


NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution

Short answer: if you can solve the decision (yes/no) problem, calling that tells you if it has no solution; if there is a solution, pick a variable and set it to true, see if the result can be satisfied; if not, it has to be false. This way, with one call to the oracle per variable you get a "solution" (set of values of the variables making the expression true, it here are any). Thus the cost of the search problem isn't "too much more" (multiply by the size of the input --number of variables-- is polynomial).


Is my algorithm to find the median of 2 sorted arrays O(log(m + n))?

Judging from your description and your code, you are basically doing a merge of the two array but stop at the median. This means that your main loop (body) is executed $(m + n) / 2 \in O(m + n)$ times, which is linear in $m + n$. You could also figure that one out experimentally by trying your algorithm on a range of different inputs and plotting the time taken against $m + n$, I guess.
If you want to find a solution which takes $O(\log (m + n))$ time you could try working backwards: A binary search over a (sorted) array of length $n$ takes $O(\log(n))$ time.


Parameter sharing / weight constraints in Neural Networks

I'll list two approaches, either of which should work.

Projected gradient descent

One general approach would be to use projected gradient descent, which provides a way to accommodate these kinds of constraints.  For specific kinds of constraints there may be a better way.

Let's recall how we train neural networks.  We have an objective function $\Psi$ that computes the total loss, as a function of the weights $w$.  Training a neural network amounts to solving the optimization problem "minimize $\Psi(w)$".  This is typically done using (stochastic) gradient descent to find the weights $w$ that minimize $\Psi(w)$.  In each iteration, you take a single gradient step to update $w$ (backpropagation is just a way to help you compute the gradient $\nabla \Psi(w)$, to help you take this step).

Now you want to add some constraints on $w$.  Let $\mathcal{R}$ denote the region (linear subspace) of $w$'s that satisfy all your constraints.  Now we want to solve the optimization problem "minimize $\Psi(w)$ subject to $w \in \mathcal{R}$".  One standard way to solve such an optimization problem is to use projected gradient descent: in each iteration, you take a single gradient step to update $w$, then project $w$ to the nearest point in $\mathcal{R}$; and repeat.  So this amounts to doing the standard backprop training procedure for a neural network, but after each weight update, projecting the weights to the nearest valid value that satisfies all the constraints.  You can read more about projected gradient descent in standard resources. In your situation, it is easy to project onto a linear subspace; this is a simple matter of linear algebra.  So projected gradient descent should be straightforward to apply.  It also shouldn't be too hard to add the projection step, in a framework like Tensorflow.  This also has the nice benefit of generalizing beyond linear constraints.

Reparameterization

The other plausible approach would be a reparameterization trick.  If you have $m$ weights, your region $\mathcal{R}$ has the form $\{w : Aw=c\}$, where $A$ is a $m \times n$ matrix and $c$ a constant $m$-vector.  This can be reparametrized into the form $\{Bv\}$ where $B$ is a $n\times n-m$ matrix and $v$ ranges over all possible $n-m$-vectors.  In other words, we can find a matrix $B$ such that every valid weight value $w$ can be expressed as $w=Bv$ for some $v$.  (I think you can compute $B$ as the pseudoinverse of $A$.)  Then, instead of solving the optimization problem "minimize $\Psi(w)$ subject to $w \in \mathcal{R}$", you can solve the optimization problem "minimize $\Psi(Bv)$", where now there are no constraints on $v$.  This in turn can be done using gradient descent.

Once you've found the matrix $B$, you'll probably find the latter approach very easy to implement in frameworks like Tensorflow; you just let $v$ be the variables you are trying to solve for, compute $w$ from $v$ using $w=Bv$, and then the neural network uses these derived weights $w$, and you can ask Tensorflow to minimize the loss as usual.


Prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values

Let's try to define those terms in math language:

Denote $x$ as the input, and $f(x)$ is the solution to the problem with input $x$.
Ill-condition problem: $x'=x + \delta \Rightarrow f(x') \gg f(x) + \delta$
Stable algorithm $F(x) \simeq f(x')$ (stable algorithm give you result close to result of a nearby input)

So apply stable algorithm on ill-condition problem we get: $F(x) \simeq f(x') \gg f(x) + \delta$

Which says the best you can get can't be smaller than error in the input.

I think you can also prove by contradiction, saying if the stable algorithm can do that, then the changes in input will make only small change in the output which makes the problem well-condition.


Proving a certain hypothesis class on a given distribution is not learnable

Since each $x$ is uniformly chosen, the probability of having a certain value at the $i$'th spot is independent of the probability of finding some other certain value in the $j$'th spot. You showed this already, but notice it means that you dont need the inclusion-exclusion principle, and instead the probability will just be the probability of the complement, which is $1-\frac{1}{2^{km}}$. You can now easily choose $k$ such that this probability would be bigger than $\delta$


Why are Oracle call instances bounded in the definition of FPT Turing reductions?

As Pål GD mentions, the requirement that $l(y)\leq g(k(x))$ is necessary to obtain reductions with the proper result. In particular, the property 'If $X$ is FPT, and there is an FPT-reduction from $Y$ to $X$ then $Y$ is FPT'.

An example to see why this requirement is necessary is to consider reductions between $k$-Clique and $k$-Vertex cover. Recall that we can construct polynomial time reductions both ways between Clique and Vertex cover (without the parameters), using the fact that if $X\subseteq V$ is a maximum clique in the graph $G$, then $V\setminus X$ is a minimum vertex cover in the complement of $G$.

However, this doesn't give a FPT reduction from $k$-clique to vertex cover: If we try to solve $k$-clique by finding a vertex cover in the complement of $G$, we need to find one of size $k'=|V|-k$. As $k$-vertex cover is FPT, applying the reduction and solving $k$-vertex cover can be done in $O(f(k')\cdot|G|^{O(1)})= O(f(|V|-k)\cdot|G^{O(1)}|)$. So, we don't get an FPT algorithm for $k$-clique from this 'reduction', as the 'non-polynomial' part of the running time depends on $|V|$! In fact, we shouldn't expect $k$-clique to have an FPT reduction to $k$-vertex cover, as $k$-vertex cover is FPT, but $k$-clique is $W[1]$-hard.

Additionally, I agree with Pål GD that the definition of parameterized Turing reductions you give is a bit difficult to read. I've looked at Flum & Grohe's book and their presentation of this definition is in fact a lot clearer than than one you provide (from a different book/edition?):

  Definition 2.8. Let $(Q,\kappa)$ and $(Q' ,\kappa' )$ be parameterized problems over the alphabets $Σ$ and $Σ'$, respectively. An fpt Turing reduction from $(Q,\kappa)$ to $(Q' ,\kappa' )$ is an algorithm $\mathbb{A}$ with an oracle to $Q'$ such that:

  $\mathbb{A}$ decides $(Q,\kappa)$.
  $\mathbb{A}$ is an fpt-algorithm, that is, there is a computable function $f : \mathbb{N} \rightarrow \mathbb{N}$
  and a polynomial $p(X)$ such that the running time of $\mathbb{A}$ on input $x \in \Sigma^*$ is bounded by $f(\kappa(x))\cdot p(|x|)$.
  There is a computable function $g : \mathbb{N} \rightarrow \mathbb{N}$ such that for all oracle queries
  “$y \in Q'$?” posed by $\mathbb{A}$ on input $x$ we have $κ'(y) \leq g(κ(x))$.


How does CNN deal with rotation invariant pictures?

With a standard CNN, features are not rotation invariant, and the are not rotation equivariant.  They are translation equivariant, but not rotation equivariant.
If you would like the model to be rotation invariance, then there are fancy methods to provide that, and simple methods.
The fancy method is to use a rotation-equivariant neural network.  There are many research papers on this subject.  See, e.g., Deep Rotation Equivariant Network by Li et al., Learning Steerable Filters for Rotation Equivariant CNNs by Weiler et al., and many others.
The simple method is to use data augmentation.  During training time, randomly rotate the input image before feeding it to the neural network.  You might need to train the neural network for more epochs.
Data augmentation is a lot easier to implement, and my impression is that it gives results that are close to what can be achieved with the fancy methods.  Therefore, I suggest you try data augmentation first.


What are the k-collections described in ch. 8 of "An Introduction to the Analysis of Algorithms" by Sedgewick

I cannot figure out why you were "pretty sure" you were wrong, because you have given a correct example, "a 3-collection from Table 8.1 is 2213, where the last letter (number 3) occurring just at the end".

Here are 2-collections.
1112, 1113, 2221, 2223, 3331, 3332.

Here are 3-collections.
1123, 1132, 1213, 1223, 1312, 1332,
2113, 2123, 2213, 2231, 2321, 2331,
3112, 3132, 3221, 3231, 3312, 3321.

There is a natural way for you to check whether your understanding is correct without any extra effort, assuming you are required or scheduled to read that section "coupon collector problem" in the book. What you could have done is to try to understand that section as much as possible, assuming whatever interpretation your could have. If you find some inconsistency, then your interpretation is probably wrong. Otherwise, your interpretation is probably correct.

For example, I also doubted my understanding of that definition of $k$-collection.

However, when I have read "if each box of a product contains one of a set of $M$ coupons, how many boxes must one buy, on the average, before getting all the coupons? This value is equivalent to the expected number of balls thrown until all urns have at least one ball or the expected number of keys added until all the chains in a hash table built by Program 9.1 have at least one key", I am confident that I got it correctly. I can imagine each letter in an $M$-collection is a box containing a coupon, where different letters mean different coupons. A ordered collection of letters is an ordered buying sequence of boxes containing coupons. So an $M$-collection means a buying sequence that gets all $M$ coupons right at its last buy. Ditto for chains in a hash table. The more I read, the more confident I become.


Local Search Optimization Algorithms in Applied Settings -- How best to explain to applied researchers?

The question is a bit unclear, but just to add my two cents:

Simulated Annealing and Genetic Algorithms are not classified as ”local” optimization algorithms. They have been designed to overcome the limitations of local searches so they are usually put in the “global” optimization basket.
The fact that they are stochastic doesn’t mean that their results are not reproducible. Standard implementations of SA and GA allow you to specify a random seed, so the optimizations are perfectly reproducible.

So you have many local optima from your algorithm. Do the “better” local optima tell you anything more than the worse ones? What is the actual, physical meaning of your optima? Is there any way you could compare your algorithm with other, established optimization procedures to assess the quality of your implementation? How many parameters (optimization variables) does your model have? Is your objective function expensive to evaluate or quick? We haven’t seen your model so it’s difficult to suggest anything about possible arguments to convince your colleagues.
That said, having an objective function full of local optima is nothing new, very many real life applications are like that. However, in almost all cases we strive for better and better optima all the time (I.e. lower objective functions in minimizations, higher for maximizations) and when we have to account for many optima (for example, for forecasting a matched model) we usually have a good, physical explanation for what we are doing.
I have to admit that your case is a bit unusual, as having orders of magnitude different optima is unheard of (at least for me). But since you haven’t provided a model nor benchmarked your algorithm against others I am afraid these is the best suggestions I can come up with.


Is there a theory/abstraction behind OOP?

There are four main approaches, though these only scratch the surface of what is available:

via lambdas and records: the idea is to encode objects, classes and methods in terms of more traditional constructs. Benjamin Pierce's work from the mid 90s is representative of this approach.
Abadi and Cardelli's object calculi (see Abadi and Cardelli's book A Theory of Objects: their main abstraction is a record of methods, and the approach is closer to the prototype-based realisation of object-oriented programming, though classes and inheritance can be encoded in terms of the more primitive elements.
Castagna's multimethod calculus (see Castagna's book Object-Oriented Programming A Unified Foundation): his approach takes multimethods are the key abstraction.
Class-based calculi (such as in Kim Bruce's book Foundations of Object-oriented Languages: Types and Semantics or Featherweight Java): these approaches aim to capture the essence of class based programming and focus on classes and inheritance.


Knuth gives a good overview on the history of lists and linked data structures. From The Art of Computer Programming, Volume I, Section 2.6:

  Linked memory techniques were really born when A. Newell, J. C. Shaw, and H. A. Simon began their investigations of heuristic problem-solving by machine.


Generate triangular surface mesh of convex hull spanned by 8 points in 3D-Space

You don't actually need the convex hull. This is a simple linear programming instance: find $a_i$ such that $$0 \le a_i \\
\sum a_i = 1 \\
\sum a_i \phi_{i, 1} \le 0 \\
\sum a_i \phi_{i, 2} = 0 \\
\sum a_i \phi_{i, 3} = 0$$ maximising $\sum a_i \phi_{i, 1}$. There are optimised LP solvers out there which you can use.


Amount of information in scaled-down images

Averaging-and-truncation certainly loses more information. It is not because you are not preserving any specific pixel: it is because you are taking an even probability distribution and giving it a strong bias in one direction.

If I have understood you correctly, you have taken the 16 possible 2x2 images and transformed one of them to white and 15 of them to black. This 15:1 split is about as bad as you can get! It destroys information, and it is the reason why your results are so bad compared to the "take top left corner".

The nearer you get to an "8:8" split, the less information you will lose. So try averaging and rounding: what I think you call "taking the median". This will split 11:5, which is less bad. It is still not very good, because the 6 cases of "2 black, 2 white pixels" all have to be translated either to black or to white - that is why you can only get 11:5 rather than the ideal 8:8 between black and white outcomes. [It would be interesting to try "use the majority value if there is a majority value; if not, use the top left"].

If you try $3\times 3$ blocks then either a clear majority of pixels will be white or a clear majority of pixels will be black: a straight 256:256 split. This is the best possible outcome, and if you simulate it then you should find it leads to the least information loss.


Is reaching in less lines semi-decidable?

It's only semi-decidable if you word your decision problem very carefully. And you have to word it in such a way that the case where both programs never reach their $n$s is in the REJECT category. Since $\infty < \infty$ is ambiguous/undefined I would explicitly mention this case in your decision problem.

Other than that, yes it's correct. Your machine halts if either $p_1$ or $p_2$ halts (viewing reaching $n$ as just another halting condition) and provides the correct answer in such a scenario. If you patch up the above issue then when neither $p_1, p_2$ halts you are in the REJECT case and thus you are allowed to never halt as well by semi-decidability.


Providing $1^n$ as input to protect against degenerate cases

Your second language is (probably) not in NP, since it allows witnesses of arbitrary size. For every size $m$ there is a polynomial $p$ such that $p(t) = m$, for example the constant polynomial $p \equiv m$. A polynomial time machine should have its running time bounded by a fixed polynomial in the input size.

Regarding $t$, if you replaced the unary encoding of $t$ by its binary encoding then you would get a problem in NEXP rather than in NP, since simulating $t$ steps of a machine scales proportional to $t$, whereas the size of the binary encoding of $t$ is only $\log t$.


Showing that a binary linear code $C$ is self-dual

$G^*$ is also a parity check matrix of the code $C^*$ since $G^*G^{*T}=0$ and $\dim\ker\left(G^{*}\right)=\text{rank}\left(G^*\right)=4$.
 Since a parity check matrix of $C^*$ is a generator matrix of $C^{*\perp}$, we get that $C^*$ is a self dual code.


How to optimally seperate a student body?

It sounds like you have properly reduced the maximum bipartite matching problem to the maximum flow problem, all you need is the reasoning to convince yourself why it is true. You are worried about the complement, so let's consider that. Remember that there is a duality among the minimum cut problem and the maximum flow problem so in finding the minimum cut you will equivalently find the maximum flow. For the definition of minimum cut:

  a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge whose cut set has the smallest number of edges (unweighted case) or smallest sum of weights possible. Several algorithms exist to find minimum cuts.

The minimum cut for the graph you have constructed will have the smallest number of edges since all the weights are uniform and therefore the smallest number of people from the two sets who want to work togethers given that:

$w(p_i, q_j) = 1 \Leftrightarrow$ person $p_i$ does not want to work with person $q_j$


Justification for the pumping lemma of context free languages

A context-free grammar has a finite number of nonterminals. This means the number of different derivation trees you can generate such that each nonterminal on each path of each tree is different is also finite: if you have $n$ nonterminals, then each path longer than $n$ will contain at least one nonterminal twice. That means all other derivations have a repeating nonterminal $A$ on some path. We can then pump by repeating the path segment from $A$ to $A$ arbitrarily often. This remains true after we make the grammar proper by removing all unproductive and unreachable nonterminals and cyclic rules.


You cannot erase the $ϵ$-production from this grammar and keep the same
language. The reason is that since you have the production $S\to ϵ$, the
language contains $ϵ$. And the only way a CF language can contain $ϵ$ is with
an $ϵ$-production.


When are Dynamic and Lexical Scoping equivalent?

If you allow one function to call another, then you have enough power to distinguish a lexically defined variable from a dynamically defined one.

def scope {
  var x = 10
  def f() {
    return g()
  }
}
def g() {
  return x;
}
scope.f()

If x is dynamically scoped, the code returns 10. If it is lexically defined, the result is an error.

Thus if you want a language where dynamic and lexical scoping behave the same, it will be a rather weak language.


Is C++ considered a language with high or low orthogonality?

By many standards, Java would not be considered weak in this respect. Java was not one of the first-generation languages. By the time it was developed, quite a few things were known about language design, and the lessons learned do show. For instance, it's pretty easy to parse.
C++ is quite a bit older, as it shares a history with C. As a result, C++ has the a preprocessor language that is quite distinct from the rest of the language. But unlike C, C++ has effectively added a third language. The C++ template system is Turing-complete, and effectively a language of its own. (Although recent C++ versions have reduced this gap).
The result? This bit of valid C++ code:
#define A 0
enum { b = 1};
const int c = 2;
constexpr int d = 3;

But note that this process is a result of the success. The most orthogonal languages are those defined as a theoretical exercise, never used, and therefore never adapted to be useful for a wide range of tasks.


What is the significance of ⟨B, s⟩ -> ⟨B', s'⟩ as the initial rule in this question about small-step semantics?

It seems you have some doubts about the first added evaluation rule
$$
\frac
{\langle B, s \rangle \to \!\, \langle B', s' \rangle}
{\langle \mathsf{assert}\ B\ \mathsf{before}\ C, s \rangle \to \!\, \langle \mathsf{assert}\ B'\ \mathsf{before}\ C, s' \rangle}
$$

It might be redundant, but I ought to point out it's one rule: the top part is called a premise of the rule, the bottom part is called a conclusion.

We call rules of this type rules of congruence (and the next two are computation rules). One needs rules of congruence to reduce subparts of a bigger expression or command, i.e. reduce something in its context. Usually, one applies rules of congruence until one can use a computation rule to dispose of some parts of the context. Here, the premise serves you as a means of reducing a Boolean expression $B$ to its value $(\mathsf{True}$ or $\mathsf{False})$.

Let me illustrate this by example: if you have a command $\mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ \mathsf{skip}$, and an initial state $s$, then you reduce it to $\mathsf{skip}$ (without changing $s$) using the second added rule:
$$
\langle \mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ \mathsf{skip}, s\rangle \to \!\, \langle \mathsf{skip}, s \rangle
$$

But what should we do if the command we've got is $\mathsf{assert}\ \mathsf{True \wedge \mathsf{True}}\ \mathsf{before}\ \mathsf{skip}$? There is no computation rules for this, i.e. rules that are able to get rid of the $\mathsf{assert}$... part. Here comes the congruence rule: first you reduce $\mathsf{True \wedge \mathsf{True}}$ to $\mathsf{True}$, using some evaluation rule defined for Booleans (not shown here) -- that's why you need the premise ${\langle B, s \rangle \to \!\, \langle B', s' \rangle}$ -- then you use the 2nd added rule to finish off your computation:

$$
\langle \mathsf{assert}\ \mathsf{True} \wedge \mathsf{True}\  \mathsf{before}\ \mathsf{skip}, s\rangle
\to
\langle \mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ \mathsf{skip}, s\rangle
\to
\!\, \langle \mathsf{skip}, s \rangle
$$


Can Depth-first search (DFS) with alphabetical traversal of neighbors be run in O(|V|+|E|) time?

No, there is no linear time algorithm (for worst case).

Note for a list of $n$ positive integers, you can construct a tree with a root and $n$ children encoded by these integers respectively and traverse this tree in alphabetical order to sort these integers. So your problem is at least as hard as sorting.


How to solve this job scheduling programming problem?

I assume your question is "how many jobs can you achieve on time ?". The idea to use something like 0/1 knapsack is good. There is actually a DP resolution of 0/1 knapsack much more efficient than "recursively select or discard each item".

Let's call $t_{max} = max(D[i])$, the end horizon of your problem.

Create a vector $A$ of size $t_{max}$, $A_i[t]$ stands for the number of achieved jobs at time $t$ after considering all jobs until $i^{th}$ one. Initially, $A_0$ is filled with 0.

Then you loop on jobs, to build $A_i$ from $A_{i-1}$:

for t from D[i] to T[i] by -1:
    A[t] = max(A[t], A[t-T[i]]+1)

Time complexity is $O(Nt_{max})$.


Are algorithms for searching text vs searching numbers fundamentally different?

There is no reason to assume that numbers and words are treated differently: for their servers, both are just strings. Different behaviour would be extra work and I don't see why that would be useful here.

There is one possible explanation for the behaviour you see: maybe they don't search for parts of words!

It is easy to preprocess texts so that finding whole words is fast. Well, looking for any substring is not that much slower (cf suffix trees) but it generates more data to store. Given the amount of data Google deals with, they might have a numbered dictionary and save tuples like (msg_id, position, word_id) (or similar)¹. Storing (matches for) all substrings would cause this data set to explode! (And don't even think about approximate search!)

You can try and verify this by searching not for mango but for ngo -- does it still find your message?

I'm quite sure Google does something far more clever.


Forward checking with conflict directed backjumping

If forward checking detects that the potential assignment of a variable $x_1$ leaves no valid assignments for the variable $x_2$, one simple strategy is to just make the assignment to $x_1$ and then queue $x_2$ as the next variable to be assigned.  When the assignment of $x_2$ inevitably fails, your backjumping machinery will do what it always does and you need not code any special information gathering related to forward checking.  In the meantime, you've saved all the time that would have been wasted doing (and undoing) a potentially exponential number of unrelated assignments that do nothing to resolve the inevitable conflict between $x_1$ and $x_2$.


Undecidable among these for turing machine

(1.1) Is it undecidable whether an arbitrary Turing machine(TM) has 15 states?

No, this is a decidable problem. Given a TM in a suitable encoding, it is fairly straightforward to determine how many states the TM has. Consider any common encoding, or define a reasonable one yourself, and then describe an algorithm that answers the question using the encoding. Hint: you can make your algorithm really simple if you define the encoding such that the first part of the encoding is an encoded list of states that are part of the TM.

(1.2) Is it undecidable whether an arbitrary TM halts after 10 steps?

I assume what you mean by this is the following: is it undecidable whether an arbitrary TM halts after exactly 10 steps for some input? The answer is that, no, this is also decidable. Consider all $\Sigma^{10}$ configurations of the first $10$ cells of the tape. For each of these, configurations, execute 10 steps according to the TM's transition table (for nondeterministic TMs, this includes all possible paths of length 10). If one of the paths halts after exactly 10 steps, output yes; otherwise, output no.

(1.3) Is it undecidable whether an arbitrary TM ever prints a specific letter?

This one is actually undecidable. Suppose it weren't undecidable. Take an arbitrary TM. Construct a new TM with a new alphabet symbol not in the alphabet of the original TM. Replace all transitions in the original TM which cause the machine to halt with transitions which cause the machine to halt and which write this new symbol to the tape. By the assumption, the problem of whether the new TM prints this specific symbol is decidable; however, solving this problem would give us a way to solve the halting problem for the original TM (since the new one printing the symbol would only occur if the original one halted). Since the halting problem is undecidable, we have a contradiction, hence, this problem is undecidable.

(1.4) Is it undecidable whether an arbitrary TM accepts a string w in 5 steps?

This is clearly decidable. Given a TM and a string, write the string on the tape and execute five steps of the TM according to its transition table.

Which one of the following is not decidable?

given a TM M, a string s and an integer k, M accepts s with k steps
equivalence of two given TMs
language accepted by a given DFSA(Deterministic finite state automata) is nonempty
language accepted by a CFG(Context free grammar) is nonempty

(2.1.) is definitely decidable as per the argument in (1.4).
(2.2.) is ambiguous; if we mean syntactically equivalent, then this should be decidable given a suitable encoding. If it means semantically equivalent, i.e., they decide/accept the same language, then this is definitely undecidable.
(2.3.) is definitely decidable, since you can always minimize the DFA and see whether it's a single state with no accepting states.
(2.4.) is definitely decidable. Begin marking symbols (terminal/nonterminal) if they lead to a string of only terminal symbols. First, mark all terminal symbols. Next, mark nonterminals which lead to a string of only nonterminals. Iteratively, mark unmarked nonterminals which lead to strings of terminals or already-marked nonterminals. Continue until you complete an iteration without marking any new nonterminals. If the start symbol is marked, then it leads to a string of terminals, which is a string generated by the grammar, so its language is non-empty. Otherwise, the start symbol doesn't lead to a string of all terminals, so its language is empty.

By process of elimination, the answer to question (2) must be (2.2) and the interpretation given to "equivalent" must be "decides/accepts the same language."


Is determining if a Turing machine runs in constant time decidable if one assumes it halts?

This answer is for the following version of the question:

  Can we decide whether an algorithm runs in constant time (that is, within $N$ steps, for some $N$), given that it is guaranteed to always halt?

This is not decidable. Given a Turing machine $T$, construct a new Turing machine $M$ which on input $t$ runs $T$ for up to $t$ steps. Then $M$ runs in constant time iff $T$ halts.


How to find the compression method used on an unknown sequence of bytes?

This file contains some repeated long byte sequences. In particular, the 66(decimal)-byte sequence beginning 49 97 CE... occurs many times, and always at an offset that's a multiple of 66.
If you decrypt the file as a bitwise Vigenère cipher with that as the key, the result has a lot of structure. It appears to be divided into 66-byte records with 64 bytes of payload followed by a 2-byte checksum. (I assume it's a checksum because it's a deterministic function of the first 64 bytes, and the first 64 bytes sometimes have simple patterns like 01 01 01... but the last two bytes always look like garbage.)
Beyond that, I can't figure anything out. Notably, while some records consist entirely of recognizable patterns (except the checksum), and some begin with recognizable patterns and end as garbage, none begin as garbage and end recognizably, which makes me think that there may be more to the encryption than a simple xor.


The Taylor series and time complexity analysis

$2^n$ can be represented as a Taylor series, which is an infinite sum of polynomials. Notably, there is no single polynomial which is equal to $2^n$.

In general, since big-O lets us get rid of lower-degree terms in the polynomial, we can say that something has polynomial time (or space or whatever you're measuring) when it is $O(n^k)$ for some fixed $k$.

Since there's no single $k$ where $\forall n \ldotp O(2^n) = O(n^k)$, we say that $2^n$ is not polynomial.


Is there a computer science theory behind automatic source code generation

I don't know anything about it but the field as a whole is called "automatic programming", which should give you pointers of where to look.


Are regular expressions a*a and aa* equivalent?

Yes, they're equivalent. Informally, it's clear that "any number of $a$s followed by one more" is the same thing as "a $a$ followed by any number more." However, there was a request in the comments for something more formal so here goes...

If $R$ and $S$ are regular expressions, then the concatenation $RS$ matches any string $w=w_1\dots w_\ell$ (where the $w_i$ are the individual characters) such that, for some $d$, $w_1\dots w_d$ matches $R$ and $w_{d+1}\dots w_\ell$ matches $S$. Here, $d=0$ and $d=\ell$ mean that we've split $w$ into $\varepsilon$ and $w$ and vice-versa.

So, consider $R=a^*$ and $S=a$. Then $RS$ matches any string $w=w_1\dots w_\ell$ such that, for some $d$, $w_1\dots w_d$ matches $a^*$ and $w_{d+1}\dots w_\ell$ matches $a$. We must have $d=\ell-1$ and $w_\ell=a$ because only the string $a$ matches $a$, and it has length $1$.  And we must have $w_1=\dots=w_{\ell-1}=a$ because that is the only length-$(\ell-1)$ string that matches $a^*$. So $w=a^{\ell}$ for some $\ell\geq 1$.

Considering $R=a$ and $S=a^*$, an almost identical argument shows that any string that matches $aa^*$ must also be $a^{\ell}$ for some $\ell\geq 1$, so the two regular expressions do indeed match the same language.

At an intermediate level of formality, you can argue that $a^*$ matches any string $a^\ell$ for $\ell\geq 0$, and $a$ matches the single string $a=a^1$.  So $a^*a$ matches any string $a^\ell a$ for $\ell\geq 0$, i.e., any string $a^{\ell+1}$ for $\ell\geq 0$, i.e., any string $a^\ell$ for $\ell>0$.  Similarly, $aa^*$ matches any string $aa^\ell=a^{1+\ell}$ for $\ell\geq 0$, i.e., $a^\ell$ for $\ell>0$.


You may find contradictory answers because there are many kinds of serial communication protocols. Some are LSB first, some are MSB first.

For example, for the old RS232 standard and siblings, the LSB is transmitted first, and the parity may be transmitted after MSB. The MSB is usually the 7th bit or the 8th bit.
The parity is not part of the source data and is not weighted, so this is not really a MSB.

Another serial protocol, CAN, used in many automotive or other embedded applications, uses MSB first.

Some have more complex interpretations, mixing LSB- and MSB- first for data and CRC, mixing the order of bytes and the transmission order of bits. Example : IP over Ethernet : Big endian data, LSB-first bits, reversed CRC.


Prove this langage isn't regular using the pumping lemma

As you know, the Pumping Lemma for regular languages states that if $L$ is a regular language, then there is an integer $p$ such that is $s$ is any string in $L$ with length $|s|\ge p$ then we can write $s=xyz$ with

$|y|>0$,
$|xy|\le p$, and
$xy^iz\in L$ for all $i\ge 0$.

If we let $s=a^nb^m$ for distinct primes $n,m\ge p$ then certainly $s\in L$ since $\gcd(n,m)=1$. Now we know that in this case $y=a^k$ with $0<k\le p$ and so if we pump $y$ we'll have $xy^{i+1}z=a^{n+ik}b^m$. Now we'll try to get a contradiction by showing that there is some $i$ for which $\gcd(n+ik,m)\ne 1$. We can get this if we can find an $i$ such that $m$ divides $n+ik$, since then we'll have $\gcd(n+ik,m)=m$.

In other words, we want an $i$ such that $n+ik\equiv 0\pmod m$. In modular arithmetic land we'll then have the following chain of equivalences:

$$\begin{align}
n+ik &\equiv 0\pmod m\\
ik &\equiv -n\pmod m\\
i &\equiv -n(k^{-1})\pmod m
\end{align}$$
The last step follows from the fact that when the modulus is prime, any nonzero value has a multiplicative inverse.

Here's an example: Suppose $p=6$, then we could pick $n=11,m=7$ and pump the string $a^{11}b^7\in L$. If it happened that $k=4$ then we could use $i=-11\cdot 2$, where the $2$ came from the fact that $4\cdot 2\equiv 1\pmod 7$. In other words, we'd have

$$
i=-11\cdot 2\equiv -22\equiv -1\equiv 6\pmod 7
$$
and then the pumped string would be $a^{11+6\cdot 4}b^7=a^{35}b^7$ and this is clearly not in $L$, since $\gcd(35,7)=7\ne 1$
$$
$$


Information theory from a (very pure) mathematician's perspective

I think you are looking for the topic of "Algorithmic Information Theory" (AIT).
This area is the collision of information theory and computer science. For example "Information and Randomness: An Algorithmic Perspective" written by cristian calude contains interesting subjects in this area. You can find more in the AIT website.


Constructing a minimum spanning tree from an all-shortest path graph?

If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a light edge thus it is also the shortest path distance.

You are almost there. Let me continue your approach.

Suppose edge $(u,v)\not\in T$. Let $P=(u_0=u, u_1, \cdots, u_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u_i, u_{i+1})$, $d_{u_iu_{i+1}}=w((u_i, u_{i+1}))\lt \sum_{0\le j\le k-1} w((u_j, u_{j+1}))= d_{uv}$, where $w$ is the weight/length function on edges of $T$.

Consider $t_0$, the point of time when edge $(u,v)$ had been  determined to be part of $T'$ but had not been added to $T'$ yet by Kruskal's algorithm. At time $t_0$, for all $0\le i\le k-1$, $(u_i, u_{i+1})$, an edge that is shorter than $(u,v)$ must have been tried, which meant node $u_i$ and $u_{i+1}$ must have been connected by a path in $K(t_0)$, the edges of $G(D)$ that had been determined to be part of $T'$ at time $t_0$. That means before $t_0$, node $u$ and $v$ had been connected by a path in $K(t_0)$, which implies that edge $(u,v)$ would not be added by Kruskal's algorithm.

The paragraph above shows that all edges of $T'$ must be in $T$. Since the number of edges in each one of them is $n-1$, $T=T'$.

Here is a direct generalization as an exercise.

Exercise. Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.


If a number $n$ has a factor $m$ in the range $n/4 \leq m \leq n/2$, then the quotient $k = n/m$ satisfies $2 \leq k \leq 4$, that is, $k \in \{2,3,4\}$. This should give you a fast algorithm for determining whether such a factor $m$ exists.


I know that NP-complete problems cannot be solved in polynomial time.

We don't know this. This is exactly the P vs NP question. NP-complete problems can be solved in polynomial time iff P=NP.

If P ≠ NP, then all problems in NP cannot be solved in polynomial time.

P is a subset of NP, so some problems in NP can definitely be solved in polynomial time.

Furthermore, if we consider the Church-Turing thesis, and if P ≠ NP, then no computational formalism (ever) can solve NP-complete problems in polynomial time.

The Church–Turing thesis isn't really relevant here, since it is about computability rather than complexity. It could be that P ≠ NP but NP-complete problems can be solved in polynomial time by randomized algorithms or by quantum algorithms (though both of these are considered unlikely).


An algorithm to know if a point $P$ is in the rectangle $ABCD$ is to check that

$\vec{AB}\cdot \vec{AP}\leq 0$,
$\vec{DC}\cdot \vec{DP}\geq 0$,
$\vec{DA}\cdot \vec{DP}\leq 0$, and
$\vec{CB}\cdot \vec{CP}\geq 0$.

Since you have the two extremity point and the width $A,B,C$ and $D$ should be easy to compute. And you can restrict the point you are checking to $(x,y)$ such that $min(A_x,B_x,C_x,D_x)\leq x \leq max(A_x,B_x,C_x,D_x)$ and $min(A_y,B_y,C_y,D_y)\leq y \leq max(A_y,B_y,C_y,D_y)$.

It may not be optimal but it should be working.

Ps: I agree with @Dukeling.

[Edit] to compute $A$

If begin and end have the same abscissa (or ordinate) then it easy. Otherwise:

Let $begin=(b_x,b_y)$, $end=(e_x,e_y)$, $A=(x,y)$ and $width/2=w$ you know that:
$$\vec{beginend}=((e_x-b_x),(e_y-b_y))$$
$$\vec{beginA}=((x-b_x),(y-b_y))$$
hence:
$$\vec{beginend}\cdot\vec{beginA}=(e_x-b_x)(x-b_x)+(e_y-b_y)(y-b_y)=0$$
hence:
$$ x = b_x -\frac{(e_y-b_y)(y-b_y)}{(e_x-b_x)} $$
Also $|\vec{beginA}|=w$ hence:
$$(x-b_x)^2+(y-b_y)^2=w$$
hence:
$$(b_x -\frac{(e_y-b_y)(y-b_y)}{(e_x-b_x)}-b_x)^2+(y-b_y)^2=w$$
Solve this equation and you have $y$, then replace the solution in $$ x = b_x -\frac{(e_y-b_y)(y-b_y)}{(e_x-b_x)} $$ and you have $x$.

Notice that you have two solution one for $A$ the other for $D$ ...

Do the same for $B$ and $C$ with appropriate vectors.


Bit complexity of $n$-th Fibonacci number using matrix multiplication

Let us recall that
$$
F_n
=
\begin{pmatrix} 0 & 1 \end{pmatrix}
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^n
\begin{pmatrix}
1 \\ 0 \end{pmatrix}.
$$
We compute the $n$-th Fibonacci number using the method of repeated squaring, applied to the $2\times 2$ matrix. The matrices encountered during this process are all of the form
$$
A_m = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^m =
\begin{pmatrix}
F_{m+1} & F_m \\ F_m & F_{m-1}
\end{pmatrix}.
$$
Repeated squaring runs in $\ell \approx \log n$ steps. In the $t$-th step, we square a matrix $A_m$ with $m = \Theta(2^t)$, and possibly multiply it by the base matrix. Since the entries of $A_m$ are $\Theta(m)$ bits long, squaring takes $\Theta(m\log m) = \Theta(2^tt)$ bit operations, and this is the dominant operation in the $t$-th step. The overall bit complexity is thus proportional to
$$
\sum_{t=1}^{\ell} 2^tt = \Theta(2^\ell \ell) = \Theta(n\log n).
$$


Feature selections : Still a high dimentionality

There seems to be a misconception.  You can use $k$-nearest neighbors with any number of dimensions.  There is no prohibition on using it with a large number of features.  And in some cases $k-NN will work well even in high dimensions (a large number of features); it all depends on the dataset, and to find out whether it will work well, you have to try it.  In general, feature selection might make the algorithm work better, or it might make it work worse -- it all depends.


Find minimum set of vertices that are reachable from all other vertices

Your algorithm is correct, provided that the following is a formal definition of your problem:

  Given a DAG $D = (V, A)$, find a minimum set $C \subseteq V$ such that for every vertex $v \in V$, either $v \in C$ or there exists a vertex $c \in C$ such that $v$ is reachable from $c$.

Let's call a vertex with indegree 0 a source and any vertex set that satisfies the reachability part a cover.

Claim.  The optimal solution is $C = \{v \in V \mid v \text{ is a source}\}$.

Claim 1.  $C$ is a solution.  Trivial since $D$ is a DAG.

Claim 2.  Every vertex $c \in C$ is in every cover.  Since it has indegree 0 it cannot be reached by any other vertex.


Constructing deterministic PDA for not regular language

Recipe in shorthand. Ignore $c$'s. Use a bottom fo stack symbol $Z$ that stays there. Keep the surplus of $a$'s on the stack. So $ZAAA$ (top of stack right) means three $a$'s more than $b$'s. If we read another $a$ push $A$, if we read another $b$ pop an $A$ (and move to another state to indicate we have now seen $b$).


Mathematical Induction Problem from Concrete Abstractions

Your induction step is recorded incorrectly.

You wrote:

$$\frac{x^{k+1} - 1}{x - 1} + k+1$$

You should have written:

$$\frac{x^{k+1} - 1}{x - 1} + x^{k+1}$$

Basically, you are proving the formula for the sum of the geometric sequence.


Performance differences between Go-Back-N and Selective Repeat ARQ protocols?

If GBN is used in tandem with AIMD for congestion avoidance, the network link will experience a large amount of latency when a packet is lost. This is because the AIMD CA mechanism will typically wait for a timeout before declaring the packet that hasn't been received as being dropped. Also, the timeout wait-time will occur every time because of the nature of GBN to send cumulative acknowledgments. Worse still, the pipeline will decrease drastically every time this occurs, causing the network to incorrectly gauge congestion.

Once you contrast the above scenario with the SR instead of GBN, it becomes apparent that the window size is no longer really an issue when compared to the latency due to the lost packets in the pipeline. However, SR handles the scenario well since it acknowledges every packet. Thus, the pipeline grows at a favorable rate (as dictated by the AIMD CA) without having unnecessary decreases in the length of the pipeline.

More differences come to light when a congestion avoidance / prevention mechanism is presented.


Finding the maximum s-t flow of a graph $G$ in $O(n+m)$ time when $G-t$ is an arborescence

Construct a new graph $T=(V', E')$ by modifying $G=(V,E)$ as follows: for each edge $(u,t) \in E$ of capacity $c$ add a new vertex $t_u$ and an edge $(u, t_u)$ of capacity $c$, then delete $t$ and all its incident edges.
Notice that $T$ is an arborescence and that the maximum flow in $G$ from  $s$ to $t$ is equal to the maximum total flow in $T$ from $s$ to the vertices in $L = \{ t_u \mid (u,t) \in E \}$.
We will now find $f^*$ in time $O(|E'|) = O(|E|)$.
In order to do so, explore $T$ with a postorder DFS from $s$ and, for each visited vertex $v \in V'$ keep track of the maximum amount of flow $f(v)$ that can be sent from $v$ to the vertices in $L$ (so that $f^* = f(s)$).
When a leaf $v$ of $T$ is visited we have $f(v) = \begin{cases}+\infty &\mbox{if } v \in L \\ 0 &\mbox{otherwise}\end{cases}$.
When an internal vertex $v$ of $T$ is visited, let $u_1, \dots, u_k$ be its out-neighbors in $T$, and let $c_i$ be the capacity of the edge $(v, u_i)$. We have:
$$
\begin{equation}
f(v) = \sum_{i=1}^k \min\{f(u_i), c_i\}
\tag{1}
\end{equation}
$$
Of course  you don't actually need to construct $T$. A slight modification of a postorder DFS visit from $s$ in $G$ suffices. Here is a possible recursive implementation in pesudocode where $t$ is  assumed to be a global variable, $c(u,v)$ is the capacity of $(u,v) \in E$, and the first call is $\mathrm{flow}(s)$.
flow(v):
  if v==t:
    return +infinity

  f=0
  for each out-neighbor u of v in G:
      f += min(c(v,u), flow(u))

  return f


NFA that ends with 0 and doesn't have 11 after the first 0

Simply remove state 2, and make a transition from 1 to 5 directly. This will get rid both of a state (state 2) and a connection (the epsilon connection)


How does sum of first $k$ integers equal $k(k+1)/2$

Let me tell you the story of young Carl Friedrich Gauss.

He was six years old and in a small school with one class for everyone from 6 to 16. His teacher needed some quiet time for some job, so he asked the kids to add up the numbers 1 to 1000.

30 seconds later young Carl Friedrich had the answer: 500,500.

How did he do it?

He changed the order and added 1+1000, 2+999, 3+998 up to 500+501. Each sum is 1001, and there are 500 sums, so the result is 1001 * 500. Obviously k=1000, so this is (k+1) * k / 2.

You can use this for adding numbers in any arithmetic progression: sum = (first + last) * count / 2.


Can Dijkstra's algorithm be modified to return paths with ascending edge-id's?

It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not dense, however, it will require extra amount of memory.

Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an $O(N \log N)$ complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with $O(M)$ complexity where $M$ is the number of edges.

The method:

Apply usual Dijkstra on the problem and find the shortest path.
Create an array of $M$ numbers initially assigned by -1.
As traversing the shortest path, change the value of each traversed edge ID
    position in the array to 1.
Scan the array for 1's to find the path in ascending order.

Note that, this is an $O(M)$ algorithm instead of $O(N)$. However, if the above assumptions are satisfied, it will work better than $O(N)$. So, it depends on how much your graph is dense.


Is there a canonical form that uses AND and XOR?

You're looking for Reed-Müller forms. The introduction to this paper summarizes some families of these forms:

An arbitrary n-variable  function $f(x_1,x_2,...,x_n)$ can be represented using the positive polarity Reed-Muller form (PPRM)
$f(x_1,x_2,...,x_n) = a_0\oplus a_1x_1\oplus a_2x_2\oplus\ldots\oplus a_{12}x_1x_2\oplus a_{13}x_1x_3\oplus\ldots\oplus a_{n-1,n}x_{n-1}x_n\oplus\ldots\oplus a_{12\ldots n}x_1x_2\ldots x_n$.
For each function $f$, the coefficients $a_i$ are determined uniquely, so PPRM is a canonical form. If we used either only the positive literal ($x_i$) or only the negative literal ($\overline{x_i}$) for each variable in Eq. (4)1, we get the FPRM. There are $2^n$ possible combinations of polarities and as many FPRMs for any given logical function.
If we freely choose the polarity of each literal in Eq. (4), we get a GRM. In GRMs, contrary to FPRMs, the same variable can appear in both positive and negative polarities. There are $n2^{n-1}$ literals in Eq. (4), so there are $2^{n2^{n-1}}$ polarities for an $n$-variable function and as many GRMs. Each of the polarities determines a unique set of coefficients, and thus each GRM is a canonical representation of a function.

1 It's not clear from the text, but equation 4 is the generic PPRM equation included in the quote


Finding the kth element of a permutation

Problem statement

Your question is unclear, but here is how I interpret it:

  Input: a positive integer $n$, and $k$ distinct values $x_1,\dots,x_k \in \{1,2,\dots,n\}$
  Output: the values $\pi(x_1),\pi(x_2),\dots,\pi(x_k)$, where $\pi$ is a random permutation on $\{1,2,\dots,n\}$

You are looking for an efficient algorithm to solve this problem.

An efficient solution

If that is indeed what you are looking for, there is a very efficient way to solve this problem.  Basically, all you need to do is randomly choose $k$ distinct integers from the set $\{1,2,\dots,n\}$.  This is sampling without replacement.  Here is a simple algorithm:

Initialize $S$ to be the empty set.
For $i=1,2,\dots,k$:

Pick $r$ uniformly at random from $\{1,2,\dots,n\}$.  If $r\in S$, pick a new $r$ (and keep repeating until $r \notin S$).
Set $x_i$ to $r$, and add $r$ to $S$.

You can use any number of data structures for storing the set $S$; it could be a bitvector of length $n$, or a hashtable.  (A bitvector is probably better if $k$ is not too much smaller than $n$, say $k \ge n/64$ or so; a hashtable is probably more efficient if $k$ is small compared to $n$.)

Performance analysis

If $k \le n/2$, the expected running time is linear in $n$, so this is very efficient.

If $k \ge n/2$, there are better algorithms.  For instance, once you reach $i \ge n/2$, then rather than choosely uniformly, you can choose uniformly at random from $\overline{S}$ (the complement of $S$).  If you use the right data structures, you can make the expected running time be linear in $n$.  (Basically, once $i\ge n/2$, you compute $\overline{S}$ and throw away $S$.  In each step, you choose a random element of $\overline{S}$, then remove it from $\overline{S}$.  Choosing a random element of a set can be done in $O(1)$ expected time.)


Yes, I think it's reasonable to consider that as a copy of the data in the RAM.  It's a copy in the sense that if you modify the data in the CPU, the data in RAM remains unchanged.
(But at the end of the day it doesn't really matter what you call it: the computer is going to do what it does, regardless of what words you use to describe it.)


Proving a language is not Turing-recognizable by reduction from $D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}$

Like any claim, you have more than one way to prove a language $L$ is unrecognisable.

In case your language is in $Co-RE$ you can do one of the following:

Show $\overline{L}$ is in $RE$ by describing a TM that accepts $\overline{L}$.
Show $\overline{L}$ is in $RE$ by reduction $\overline{L}\le_m Some-Language-In-RE$.
Show $\overline{H_{TM}} \le_m L$ or $\overline{A_{TM}} \le_m L$ or some other language you know is in $Co-RE$

Note that you must show that $L\notin R$ in order to deduce $L\notin RE$.

If $A\notin Co-RE$, you can show a reduction to your language

$A\le_m L$ where $A\notin RE$ so if $L\in RE$ you have a contradiction.

There is more than one way.
I'm not sure I understand your question, but if your task is to show $D\notin RE$.
I would show $\overline{D}\in RE$, and than show $D\notin R$.


A question about halt (or stop) of Turing machine

No, Turing machine are defined in a different way than finite-automata: they don't "stop" at the end of the input, they stop whenever they reach a final state $q\in F$. Usually, there are two final states, $q_{acc},q_{rej}$ – if the machine transitions to one of these final states it stops; but until then, it keeps running.

Therefore, $\delta(q,\cdot)$ must be defined for any $q\in Q\setminus F$ and and letter the head points on. This will tell us how the machine behaves when in the state $q_t$ (using your symbol, assuming it is not a final state; see below if it is).

regarding halting without accepting/rejecting: the answer is yes. If, say, $F=\{q_{acc},q_{rej}, q_{inconclusive}\}$, and the machine reached the third final state, we can say it neither accepted nor rejected, but it halts indeed since it reached a final state in $F$. Of course, $F$ can be as large as $Q$. It may make sense for computing other task than yes/no decision problems.


Understanding multi-variable big O (time complexity)

You can remove the $-1$ from $(n-1)$, since $(n-1)dm=ndm-dm\leq ndm$. On the other hand, you can not simplify beyond $O(ndm+mv+v^2)$ unless you know more about the relations between the variables. $mv$ and $v^2$ are incomparable, depending on the ratio between $m$ and $v$ one may grow faster than the other. Similarly, your last step (removing $ndm$ in favor of $v^2$) is also incorrect.


You are mistaken. Strings $x$ and $y$ are equivalent modulo the language $L$ iff for  all suffixes added to the words the results are both in or both outside of the language:

$x\sim_L y$ iff $xw\in L \iff yw\in L$ for every $w$.

In particular, when the strings $x$ and $y$ end in the same state for the (deterministic) automaton $M$, then $x\sim_{L(M)} y$, as they can be extended by exactly the same strings. This also holds for the dead-end state where no strings can extend the original string to acceptance.


How do I compute the luminance of a pixel?

The colors are not evenly interpreted by our eyes.  When I want to make a picture gray scale, I usually go for the following calculation of the luminance of a pixel.

luminance = (r * 0.3) + (g * 0.59) + (b * 0.11)

Read more in the Stackoverflow question Formula to determine brightness of RGB color.


Best way to merge 2 max heaps into a min heap

I guess you're thinking that there may be a faster way because if you want to merge two min heaps into a third min heap, is can be done in $O(\log n)$ by creating a $-\infty$ node in $O(1)$, making the roots of both heaps be children of that new node in $O(1)$, and extracting the min of the heap in $O(\log n)$.

But in your case, it can't be done. Clearly, building a min heap is harder than finding the minimum. But the minimum could be any of the leaves of the max heaps, so you have $O(n)$ elements of which you want to find the minimum. Clearly, you have to at least read all those elements and so you take at least $O(n)$ time. So it's $\Theta(n)$.

(Note that when merging two min heaps into a min heap, the minimum has to be one of the two roots, so it can be found in $O(1)$. But in the second case, there are too many nodes that could potentially be (i.e. are for some values of the heap) the minimum)


How do O and Ω relate to worst and best case?

Landau notation denotes asymptotic bounds on functions. See here for an explanation of the differences among $O$, $\Omega$ and $\Theta$.

Worst-, best-, average or you-name-it-case time describe distinct runtime functions: one for the sequence of highest runtime of any given $n$, one for that of lowest, and so on..

Per se, the two have nothing to do with each other. The definitions are independent. Now we can go ahead and formulate asymptotic bounds on runtime functions: upper ($O$), lower ($\Omega$) or both ($\Theta$). We can do either for worst-, best- or any other case.

For instance, in binary search we get a best-case runtime asymptotic of $\Theta(1)$ and a worst-case asymptotic of $\Theta(\log n)$.


Word ladder problem for words with different length

Your algorithm that runs breadth-first search (BFS) on the graph built with words as nodes and pairs of words that differ by one letter as edges is the natural algorithm to solve the problem, whether the words are different lengths or not.

I would just call call your algorithm as a BFS algorithm. It is classic application of BFS to search for the shortest paths between two nodes of a graph where the length of a path is simply the number of its edges.

If we let the BFS algorithm run until all nodes has been visited, then it will be able to find all shortest paths between a source node and all other nodes.

You can find some detailed comparison between BFS and Dijkstra algorithm for shortest path in a graph here.


An approximation oracle for an optimization problem $X$ is an oracle which accepts an instance of $X$ and returns an approximate optimum. The parameters $\alpha,\beta$ quantify the quality of the approximation.

Approximation oracles are a formal way of stating results of the following form:

  Given a polynomial time $C$-approximation algorithm for $X$, there is a polynomial time $f(C)$-approximation algorithm for $Y$.

Formally, we give a polynomial time $f(C)$-approximation algorithm for $Y$ which uses a $C$-approximation oracle for $X$.


Are all adjacency matrices represented by 0 and 1s?

Yes, because the (i,j)th entry simply talks about whether or not there exists an edge from vertex i to vertex j, and represents existence by a 1 and non-existence by a 0.

However, many graph representations store the edge weight instead of 1s in the matrix. This way, a single matrix can compactly represent both the edges and their weights.


Shortest path from source to destination in directed acyclic graph

If your algorithm runs in $O(V+E)$ time, and their algorithm runs in $O(V+E)$ time, I don't see any basis for calling your approach more efficient.  At least, asymptotic running time does not seem precise enough to determine which will be more efficient in practice.


Interviewer was probably fishing for words like: preorder, inorder, postorder traversal and depth-first versus breadth-first.  I am thinking of traversal as simply having an iterator over the graph that returns some vertices and edges in some particular order.  As Richerby says, you could fill books with all the various ways that this could happen.

As for searching graphs, if they didn't mean traversal; then they probably meant searching for subsets efficiently: If a graph is known to have implicit structure (ie: find all edges in: 192.168.4.0/24 -> 10.0.3.2/24 by hour, etc), then various kinds of searches over src/dst/time are often possible.  Facebook/Twitter, etc are utterly gigantic graphs of "at time T, A says X to B".


Find $k$ subsets containing a particular element quickly

Use a hash table, keyed on elements of $U$.  For each subset $S$ of $U$, say $S=\{x_1,\dots,x_\ell\}$, you'll add $S$ to the hash table $\ell$ times, once for key $x_1$, once for key $x_2$, and so on.  Now to find all subsets containing some element $e$, just look into the corresponding bucket in the hash table and you can iterate over sets containing $e$ very rapidly.

This is basically just applying the idea of "indexes" from databases to your problem.  It is straightforward and provides excellent time complexity, at the cost of modest space complexity (approximately doubling the space needed to store all of the subsets).


Prove that $ln(n)^r \in o(n^p)$ for $p>0$ and $r\in \mathbb{R}$

You just need to show that
$$
\lim_{n \to \infty} \frac{\log^r n}{n^p} = 0.
$$
This is trivial if $r \le 0$ since $\frac{\log^r n}{n^p} = \frac{1}{n^p \log^{-r} n}$ and $\lim_{n \to \infty} n^p \log^{-r} n = +\infty$.
For $r>0$, you can use  l'Hôpital's rule $\lceil r \rceil$ times to obtain:
$$
\lim_{n \to \infty} \frac{\log^r n}{n^p}
= \lim_{n \to \infty} \frac{r \log^{r-1} n}{pn^{p}}
= \dots
= \lim_{n \to \infty} \frac{\prod_{i=0}^{\lceil r \rceil-1} (r-i) \cdot \log^{r-\lceil r \rceil} n}{p^{\lceil r \rceil} n^{p}} \\
=
\frac{\prod_{i=0}^{\lceil r \rceil-1} (r-i)}{p^{\lceil r \rceil}}\cdot \lim_{n \to \infty} \frac{ \log^{r-\lceil r \rceil} n}{ n^{p}} =0,
$$
where $\frac{\prod_{i=0}^{\lceil r \rceil-1} (r-i)}{p^{\lceil r \rceil}}$ is a positive constant and
$
\lim_{n \to \infty} \frac{ \log^{r-\lceil r \rceil} n}{ n^{p}}
$
is equal to $0$ since it falls into the previous case.


Is lambda calculus suitable for expressing semantics of non-functional languages?

There are two main approaches to giving the semantics of a language that I'm aware of.  $\lambda$-calculus is a suitable candidate for expressing semantics in either approach.  (Note that my knowledge of programming language semantics is restricted to a single course that I took in the mid-1990s, so I may be missing significant developments from the past 20 years.)

The first approach is operational semantics.  According to David Schmidt's Denotational Semantics, Allyn&Bacon, 1986, page 2, operational semantics "uses an interpreter to define a language."  In this sense writing a syntax-directed translator or attribute grammar as an extension of your parser gives an operational semantics to the language.  Somewhat more abstractly, you might define a small-step operational semantics (like those on the Wikipedia page) where you define the meaning of each syntactic expression with respect to the actions it takes to transform a formally defined state or environment.  The imperative programming language Scheme (which is notable for having "first-class" functions and continuations and as being the progenitor of JavaScript) has switched to an operational semantics in their most recent standard.

The other approach is denotational semantics.  In denotational semantics you define a domain of program outcomes, and then for every syntactic structure in the program its meaning is a function that maps from an environment (a map from variable names to values) to the outcome domain.  Scheme Revision5 and earlier have denotational semantics.  The semantics of set! (Scheme's imperative construct) are given towards the end of Page 41.

I would guess that language semantics are largely used to prove the correctness of implementations, and in particular to clarify what optimizations are legal and under what circumstances those optimizations are legal.  But my only experience in this domain is with respect to compiler optimizations and the memory semantics of C++11, which does not have a formal semantics.


Without further information, it's hard to tell exactly. However, to the best of my knowledge, bit operations may be intended as follows. Consider the problem of finding the maximum element in an array of $n$ real numbers. This problem can be solved by an EREW algorithm in $\Omega(\lg n)$; moreover, no CREW algorithm can do any better.

However, this problem can be solved in $O(1)$ time with $n^2$ processors using a common-CRCW algorithm (in this model, when several processors write to the same location, they all write the same value). The key point here is that a CRCW PRAM is capable of performing a boolean AND of $n$ variables in $O(1)$ time with $n$ processors (which allows overcoming the $\Omega(\lg n)$ lower bound). I think that bit operations may refer to this powerful AND capability of a common-CRCW.

Additional information regarding the FAST-MAX algorithm can be found in the first edition of CLRS Introduction to Algorithms, chapter 30 (ALGORITHMS FOR PARALLEL COMPUTERS).


NeuroEvolution: NEAT algorithm innovation numbers

Here is what I gathered from skimming the paper for just the figure.

Your first figure, which is the figure 3 in the paper, already has the answer in its caption:

  Figure 3: The two types of structural mutation in NEAT. Both types,
  adding a connection and adding a node, are illustrated with the
  connection genes of a network shown above their phenotypes. The top
  number in each genome is the innovation number of that gene. The
  innovation numbers are historical markers that identify the original
  historical ancestor of each gene. New genes are assigned new
  increasingly higher numbers. In adding a connection, a single new
  connection gene is added to the end of the genome and given the next
  available innovation number. In adding a new node, the connection gene
  being split is disabled, and two new connection genes are added to the
  end the genome. The new node is between the two new connections. A new
  node gene (not depicted) representing this new node is added to the
  genome as well.

In figure 3, it could be deduced that the add connection mutation (top half) occur preceding  the add node mutation (buttom half).

When the add connection mutation occurred, the lowest free innovation number was 7. And so the gene created at that moment was assigned the marker of 7.
Later, when the add node mutation occurred, 2 new genes were created. And so they were assign the lowest free innovation number at the time which is 8 and 9.

The innovation number is not the indices of each gene inside the array representing a genome.

The innovation number is just a number permanently branded to each gene, telling us when the gene first occur. As if the year number when human first evolved a gene for hairless body were written down on the gene itself.

The uses of innovation is then explained around your latter figure, which is figure 4:

  The historical markings give NEAT a powerful new capability. The
  system now knows exactly which genes match up with which (Figure 4).
  When crossing over, the genes in both genomes with the same innovation
  numbers are lined up. [...]
  This way, historical markings allow NEAT to perform crossover using linear genomes with out the need for expensive topological analysis.

From this I assumed that innovation number are always ordered increasingly within a genome, but gaps in innovation numbers are allowed to occur within genome.
The order is probably ensured simply by the fact that all operations done on genome was designed to not violate this within-genome ordering.

This makes sense because each gene can be thought of as an instruction to construct a graph.
By keeping the instruction ordered by when it was introduced, it makes sure that reading instruction on genome from left to right makes sense chronologically.


It is still NP-complete. It is easy to see it is in NP. To prove its NP-completeness, we reduce the standard vertex cover problem to this problem.

Given an instance $G=(V,E)$ of vertex cover problem, we construct a new graph $G'$ based on $G$ as follows.

For each edge $(u,v)\in E$, split it into three edges $(u,u_v)$, $(u_v, v_u)$, $(v_u,v)$ where $u_v$ and $v_u$ are newly added vertices.
For each vertex $v\in V$, add three edges $(v,v_1),(v_1,v_2),(v_2,v_3)$, where $v_1,v_2$ and $v_3$ are newly added vertices.

Now we assert that $G$ has a vertex cover of size $k$ if and only if $G'$ has a vertex cover with radius 2 and of size $k+|V|$.

If $G$ has a vertex cover of size $k$, then this vertex cover as well as $v_1$'s for all $v\in V$ makes up a vertex cover of $G'$ with radius 2.

On the other hand, assume $G'$ has a vertex cover $C'$ with radius 2 and of size $k+|V|$. Note for each $v\in V$, since $(v_2,v_3)$ is covered, at least one of $v_1,v_2$ and $v_3$ should be included in $C'$. We can assume $v_1$ is always included and $v_2,v_3$ are never included in $C'$. Now the rest $k$ vertices are of either the form $u$ or the form $u_v$ where $u,v\in V$. Let $$C=\{u\in V\mid u\in C'\text{ or }u_v\in C'\text{ for some }v\}.$$

Note for each $(u,v)\in E$, $(u_v,v_u)$ is covered by $C'$, then at least one of $u, u_v, v_u, v$ is included in $C'$, which means either $u$ or $v$ is inclulded in $C$. Hence $C$ is a vertex cover of $G$, which has size no more than $k$.


What you are looking for is named "address decoding".

If a processor can address 64kB, its address bus is something like A[15:0].
If you use a 1kB memory chip, its addresses will be A[9:0].

There are several options :

Either you don't connect the bits A[15:10] of the processor. The memory will be mirrored at several "places" in the CPU address map, in this example, the same memory cell is accesssed at address 0, 1024, 2048, 3072, ... etc.
Or you use additional hardware to select the memory chip only when A[15:10]=00000, for example, to map the RAM only between 0 and 1023, allowing to connect other chips and map them elsewhere in the address map : ROM, IO ports...

If a memory location is not mapped, when an read access is attempted, it will generate random noise, some default value or repeat the last access. This was true on simple CPUs (for example the old 8bits CPUs)

In more advanced architectures (typically build with 16 or 32bits CPUs), accesses to non mapped memories generates an exception usually named "Bus Error".


Memory mapping is the (complex) process that associates an address value (usually a 32 or 64 bits number) to some existing physical location in the hardware. This location can be in RAM, in a cache of some level, or even on the hard disk ! During program execution, data can move from one location to another, and possibly be duplicated.

The system keeps track of that and makes the mapping transparent so that the program can keep using the same address. Things get tricky when the values are modified and coherence between the copies must be guaranteed.


The pumping lemma says that every (long-enough) string in a regular language can be divided in some way such that it can be pumped (subject to the other stated conditions).

Note that the statement is that every string has at least one way of dividing it up. Not every division of a string necessarily works. As you have shown, some don't work, however there is a different division (any one where $m$ is even) that does work. So the language does satisfy the pumping lemma.


lambda expressions, parenthesis, and order of application

I believe you are misunderstanding what $\lambda$-abstraction represents and are not considering its scope. First; your definition of $NOT$ is correct and $NOT$ is in normal form.

It is not true that $\lambda b. b\ (\lambda x y. y)\ (\lambda u v. u)$ is the same as $(A_1\ B_1\ C_1)$ and I give here two reasons why:

The body of $\lambda$-abstraction goes as far right as possible (after ".", until its enclosing brackets, in our case none) and therefore $\lambda b. b\ (\lambda x y. y)\ (\lambda u v. u)$ is a $\lambda$-abstraction with variable $b$ and body $b\ (\lambda x y. y)\ (\lambda u v. u)$. The string "$\lambda b. b$" in this case is not representing an identity expression, but is a part of the definition of $\lambda$-abstraction. Its $\lambda$ "belongs" to the whole $NOT$ expression. Written fully parenthesised, your expression for $NOT$ would be
$$\biggl(\lambda b. \Bigl(\bigl(b\ (\lambda x y. y)\bigr)\ (\lambda u v. u)\Bigr)\biggr)$$
If it were in fact the same as $(A_1\ B_1\ C_1)$, this could reduce to $(B_1\ C_1)$ which could then reduce to $\lambda y. y$ which is identity (which is not $NOT$) and $\lambda$-expressions have at most one normal form.

The $NOT$ operator, when applied to some expression $X$ should reduce like this:
$$\bigl(\lambda b. b\ (\lambda x y. y)\ (\lambda u v. u)\bigr)\ X \rightarrow_\beta X\ (\lambda x y. y)\ (\lambda u v. u)$$

You can try your ideas and check existing examples with pLam to help you build a similar tool by yourself. Good luck!


Can a TM recognize whether another TM recognizes a non-empty language?

I will use the following definition of $L(M)$: it is the set of inputs for which $M$ halts.

I will use the following definition of recognizable: a language $L$ is recognizable if there exists a Turing machine $M$ such that $L = L(M)$.

In order to recognize $L_1$, on input $\langle M \rangle$, we simulate $M$ on all possible inputs (using dovetailing), and if $M$ halts on any input, we halt.

In order to simulate $M$ on all possible inputs, we list all possible inputs in a sequence $x_1,x_2,\ldots$, and then work as follows:

Initiate a run of $M$ on $x_1$, and advance it one step.
Initiate a run of $M$ on $x_2$, and advance both existing runs by one step each.
Initiate a run of $M$ on $x_3$, and advance all three existing runs by one step each.
And so on.

If $M$ halts on any input, then we will eventually notice it, and then immediately halt. Conversely, if $M$ never halts, then we will also never halt.


What's the complexity class of determing the halting problem of a finite memory Turing machine?

The problem is PSPACE-complete.

The problem is in PSPACE.  You can test whether such a machine halts in polynomial space, by running the Turing machine for $2^n |Q| n + 1$ steps, where $|Q|$ is the size of the finite control, and checking whether it halts.  Why?  Each configuration of the Turing machine is determined by the values on the tape, the state of the finite control, and the position of the head, so there are at most $2^n |Q| n$ such configurations.

Any PSPACE problem can be reduced to this problem.  In particular, if you have a Turing machine that solves problem $P$ with polynomial space, then you modify $P$ to solve the problem, then if $P$ would accept, halt, and if $P$ would reject, enter an infinite loop.  Now if you could solve the halting problem for polynomial-space Turing machines, you could solve $P$.

So, this completely characterizes the difficulty of the halting problem for polynomial-space Turing machines.


You've almost solved it already. You need to define which part of your word x, y, and z represent, and the obvious partition works well here. You know, by the pumping lemma, that you can repeat y any number of times, and the new word will still be in the language.
In this case, repeat y twice. Is the resulting word still a member of the language?


Randomized algorithm for 2kCNF satisfiability problem

The analysis of Schöning's algorithm (see for example these CMU lecture notes) relies on the fact that if $\alpha$ is a satisfying assignment, $\beta$ is any assignment, and $C$ is an unsatisfied $k$-clause, then flipping a random variable decreases the distance between $\beta$ and $\alpha$ with probability at least $1/k$. In your case, you can get a better guarantee since $\alpha$ satisfies half the literals in every clause.


Matching Upper Bound for Online Problems

Since we are dealing with deterministic algorithms, the adversary can pick the hardest input possible for the online algorithm.

Since the online algorithm we are discussing is deterministic, given some input, its output can always be determined. The adversary is 'smart' in the sense that they are able to look ahead and pick input such that it gives the worst possible result for the online algorithm.

What you have proved seems to be sufficient.


How to extract best illustrative sentences from documents for a given word?

Luhn, H.P. (1958, April). The automatic creation of literature abstracts. IBM Journal of Research and Development, 2(2), 159-165.

Describes the main elements of automatically creating literature abstracts. Significant sentences are candidates for inclusion into an abstract. The measure of sentence significance is based on significant words, and the proximity of significant words within sentences. Word significance is based on its frequency within the document; the word-frequency diagram depicts the set of words to consider as significant. Word significance also applies to the creation of indexes for search and retrieval.

Consider also the presentation I created when I took a graduate course: "Term Association and Thesaurus Construction"; you might find the references there useful too.


Longest substring with consecutive repetitions

From what I understand you are looking for maximal substrings of the form $y^k$ for $k\ge 2$. By some this is called a repetition in a string. One of the first to give an algorithm for finding these is Maxime Crochemore: An optimal algorithm for computing all the repetitions in a word, Inform. Process. Lett. 12 (1981) 244-248. From what I understand his approach has been reformulated in terms of suffix trees and arrays.


Analysis quickselect: Median of Medians with duplicates

A common refinement to quicksort could also be used with quickselect to deal with duplicates. Instead of partitioning into two buckets, do so into three. This new partition is called the "fat partition". It holds items that are equal to the current pivot. When there are no duplicates, this adds 2% overhead to the sort, according to the following paper.
See https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engineering.pdf
The paper discusses several memory layouts for partition, like whether to put the fat partition in the middle or the end of the invariant array or even split it and put part at the head and part at the tail, all to reduce the number of memory swaps.
The paper quantifies the huge benefits for some extreme edge cases, like when the data is a random set of ones and zeroes. In that case, their algorithm went from being four times slower than a benchmark Unix qsort to being twice as fast, an 8x speedup by the addition of a fat partition.


Confused about XORing and addition modulo $2$

The confusion here stems from a missing word. A correct statement is "The result of XORing two bits is the same as that of adding those two bits mod 2."

For example, $(0+1)\bmod 2 = 1\bmod 2 = 1=(0\text{ XOR }1)$

and

$(1+1) \bmod 2= 2\bmod 2 = 0 =(1\text{ XOR }1)$


Note that for every number $x$ it holds that $x=2^{\log x}$. Using this, we can do the following:

$t(n)b^{t(n)}=2^{\log t(n)}b^{t(n)}=2^{\log t(n)}({2^{\log b}})^{t(n)}=2^{\log t(n)}2^{t(n)\log b}=2^{\log t(n)+t(n)\log b}$.
Now, assuming $t$ is non-decreasing, we have that $\log t(n)=O(t(n))$, so ${\log t(n)+t(n)\log b}=O(t(n))$, and we're done.


Major Field Test Sample Questions (need further clarification)

I will try my best to explain the first question.

They are basically asking what value pos need to be in order for the stack to be empty. Since we are using an array as a stack, we have a choice between 0 or N-1. Looking at the code, Pop increment pos and push decrement pos. We want to follow pop because it pops the first element and so on to the last element. If we pop all elements in the array it will equal N-1 values. The answer should be D.


What we have with

$\qquad X = AX + B$

is, quite literally, a recurrence of languages expressed in terms of the symbolic method. $B$ represents the base case of the recurrence. Arden's Lemma just tells you that the smallest fixpoint of this recurrence (read as an inductive definition) is $A^*B$.

Now, if you drop the base case and only have

$\qquad X = AX$,

there are no finite words that can be constructed in this way. Now, the "recurrence" may make sense read as a coinductive definition (that is the solution would be an $X$ containing infinite strings) but not as an inductive one. Hence, the empty set is the only one that solves the equation.


How to verify the solution to n queens problem

I suspect what they meant was that if you are given a placement of $n$ queens, you can verify in quadratic time whether that is a valid solution (i.e., none of the queens attack any of the others).

I don't know of any way to verify the count of the number of solutions in quadratic time, and I doubt that such a thing is possible in quadratic time.


Problems understanding the Union functionality of the Union-Find Algorithm

The answer to your first question is that while it takes (roughly) $N$ array accesses to perform one union operation, it takes (roughly) $N^2$ to perform $N$ of them. This is what is meant by the phrase "a sequence of $N$ union commands".

Regarding your second question, the first two operations are those that initialize pid and qid, and the body of the loop (which runs up to $N$ times) contains two more, one which compares an entry to pid, and another which assigns qid to the same entry.


Why is A implies B true if A is false and B is false?

Humans are bad at logic until they have to employ it to figure out human affairs. Think of "if $A$ then $B$" as a kind of promise: "I promise to you that if you do $A$ then I will do $B$". Such a promise says nothing about what I might do if you fail to do $A$. In fact, I might do $B$ anyhow, and that would not make me a liar.

For instance, suppose your mother tells you:

  If you clean up your room I will make pancakes.

And let us say that you did not clean up your room, but when you walked into the kitchen your mom was making pancakes. Ask yourself, whether this makes your mom a liar. It does not! She would be a liar only if you cleaned the room but she refused to make pancakes. There might be other reasons that she decided to make pancakes (perhaps your sister cleaned up her room). Your mom did not tell you "If you do not clean up the room I will not make pancakes," did she?

So, if I say

  "If the sun is green then the grass is green."

that does not make me a liar. The sun is not green (you did not clean up the room), but the grass turned out to be green anyhow (but your mom made pancakes anyhow).


what is the difference between "language" and "certificate" in complexity theory?

A (formal) language $L$ is a set of words over some finite alphabet. It can be an infinite set. Generally we're interested in the problem of deciding whether a particular word is in the language or not. For example $L$ can be the set of all Turing machines (encoded as binary strings for example) that halt after at most 100 steps when started with an empty tape, or $L$ can be the set of English words that don't contain the letter 'e'.

A certificate on the other hand is one particular string. When solving the decision problem I talked about above, namely checking whether some word $w$ is in some language $L$, sometimes the problem becomes much simpler if you have some additional information $c_w$. This is often called a certificate for $w \in L$ respectively $w\not \in L$.

For example if $L$ is the set of all graphs that can be colored with at most 3-colors, deciding whether a particular graph $G$ is in this set is NP-complete. But if I already give you a coloring $c_G$ it is very easy to check that it's a valid coloring. The coloring is a certificate for $G\in L$. A coloring has the nice property that it's short, just a couple of bits for each node of the graph. Note that in this case it's not easy to give a (short) certificate for some $G'$ that is not colorable. A very long certificate in this case would be an enumeration of all exponentially many possible 3-colorings of $G'$. Checking that each is not valid is again easy, and since the certificate $c_w$ is so long, the running time of the algorithm with input $G', c_w$ is polynomial as a function of input size.


Average number of comparisons to locate item in BST

Recall, how expected value is defined. You count the for every element $X$ in the tree the number of comparisons it takes to locate it, say $C(X)$. Then
$$E[\text{# of comparisons}]=\sum_{X\in\{A,\ldots,H\}} p_X \cdot C(X),$$
where $p_x$ denotes the probability that $X$ is chosen, which is the same for all $X$, namely $1/8$. In other words, you compute the average over the $C(X)$s.


Proving that the cover time for graph is exponential in the worst case

You do it in two steps:

First you think of a graph which you can expect to be difficult.
Then you prove your suspicion.

Let's start with the first step - do you have any graph in mind?


What constitutes one unit of time in runtime analysis?

When doing complexity calculations we generally use RAM model. In this model we assume that array indexing is O(1). Assignment statement is just like assigning some value to some variable ins array of variables. This is just for convenience. It simplifies analysis of the algorithm.  In real world array indexing takes $\approx$ O(log I) where I is number of things indexed.

We generally consider things that depend on size of input e.g. loops. Even if there is O(1) operation in the loop and it is executed n times then algorithm runs for O(n) time.

But O(1) operation outside of loop take only constant time and O(n) + O(1) = O(n).

Read about radix sort algorithm from CLRS.


Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?

If $|V|=n, |E|\ge n-1$ and  every node has at least one adjacent edge , then $G$ is connected.

No, it is not true. Here is an counterexample.

Graph made at https://graphonline.ru/en/

Exercise. Construct a simpler counterexample where $|V|=n$ and $|E|=n-1$.


Yes it can. When you take RAM model and your algorithm has a lot of multiplications (dominant operation), your multiplications take unit time. Even if the numbers are $2048$ bit numbers. But if you take multitape Turing Machine as your model, the cost of multiplication matters and will be included in complexity.

Algorithm is high level description, implementation will vary. Getting back to multiplication, algorithm describes that in one step you have to multiply two numbers, but if numbers are bigger than computer words instead of writting "*" you have to implement it.


How proof of Hoffman algorithm greedy property starts with optimal tree T?

A code tree is optimal if the average codeword length is minimal. This has nothing to do with Huffman's algorithm. Huffman's algorithm is guaranteed to produce an optimal code tree, but there might be other code trees. In fact, Huffman's algorithm could produce different code trees using different tie-breaking rules. Moreover, not every optimal code tree can be produced using Huffman's algorithm, even with an arbitrary tie-breaking rule.

Here is a formal definition of an optimal code tree. Let $\pi$ be a distribution. The $\pi$-cost of a code tree is the expected length of a codeword, where the expectation is taken with respect to $\pi$. A code tree is optimal for $\pi$ if its $\pi$-cost is equal to the minimum $\pi$-cost of any code tree.


Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

This is an interesting question.

Here is an algorithm.

Iterate through the array to obtain $m$ and $M$. If $m=M$, we are done. Otherwise, let $\delta=\frac{M-m}n$.
For $i=0,1,\cdots,n+1$, let $L_i$ be an empty list of numbers.
Iterate through the array again. For each $a_j$, if $\lfloor (a_j-m)/\delta\rfloor=k$, then append $a_j$ to $L_k$ and $L_{k+1}$.
Iterate through $L_0, L_1, \cdots, L_{n+1}$. Skip $L_k$ if there is at most one number in it. Otherwise process $L_k$ as follows.

If there are two numbers, compute their difference. If it is not more than $\delta$, we are done.
If there are three numbers or more, select arbitrarily three of them. Compute all three differences between each pair of them. There must be one pair of numbers whose difference is smaller than $\delta$. Select that pair and we are done.

It is not difficult to see the above algorithm is correct and its time-complexity is $\Theta(n)$.

The above algorithm could be sped up if $L_k$ or $L_{k+1}$ is processed just as in step 4 while we are still running step 3. It would be an interesting but hard problem to determine when will be the optimal time to start processing, assuming for example, $a_j$'s are uniformly and independently distributed in $[m,M]$. Starting from $a_{n//2}$ (or $a_{\lfloor n/\log n\rfloor}$ or even $a_{\lfloor n/\sqrt n\rfloor}$?) should improve the speed in general, I believe. However, the worst time-complexity cannot be better than $\Omega(n)$.

Instead of step 3, we could also put $a_j$ to $L_{k}$, $L_{k+1}$ and $L_{k+2}$ if $\lfloor 2(a_j-m)/\delta\rfloor=k$ and adapt step 2 and 4 accordingly.

It might be interesting how I found this algorithm. I literally recited Polya's principle, "do you know a related problem?". I recalled that finding duplicate elements in an array using hash table takes linear time of $n$. Could I apply that conclusion? Or the way of using hash table? What is a hash table and how can I create a hash here? If I can put nearby numbers in the same slot, I can considered them as the same, then the algorithm might work. The it dawned on me that I could use the location of $a_j$ as "its hash". However, two numbers that are very close could be mapped to different hashes, which breaks the promise. If one hash is not enough, how about two hashes? I could almost see the light on the other side of the tunnel. After a few minor adjustments, I arrived at the current answer. (Somehow I missed Yuval's nice method by divide and conquer, which, in hindsight, should not have been difficult to find.)

Motivated by Yuval's emphasis on randomization and practice, I would like to ask the following question.

Let $n+1$ numbers be (uniformly and) independently distributed in $[0,1]$. Is there an algorithm that finds two elements whose absolute difference is not greater than $1/n$ with sublinear average time-complexity? (I believe the naive algorithm that inserts $a_j$ into a (balanced) binary search tree works. Who has a proof?)


Context sensitive language is context free

This can be done in a similar way to the proof that it is undecidable whether the language of a context-free grammar is regular. A general statement of such undecidability properties is Greibach's theorem observed by  Sheila Greibach in 1968.

  Let $C$ be a family of languages effectively closed under union and
  concatenation with regular sets, and for which equality to $\Sigma^*$ is
  undecidable (for sufficiently large $\Sigma$). Let $P$ be a proper subset of $C$,
  which contains all regular languages, and is closed under single
  letter quotient. Then membership of $P$ is undecidable for $C$.

So, we have to check whether the context-sensitive and context-free languages meet the criteria of Greibach for $C$ and $P$.


Recover the path to a goal state in A* search algorithm

Every node should have been given a pointer to the node it was reached from. Then you only need to follow and reverse a linked list.


is the empty language L = ∅ a subset of every languages?

Yes. Remember that $A\subseteq B$ just means "every element of $A$ is also an element of $B$." In case $A=\emptyset$, this is trivially true ("vacuously true") regardless of what $B$ is.

It may also help to think in terms of counterexamples: $A\subseteq B$ is the "default" situation, and is only false if there is a counterexample: some $x\in A$ with $x\not\in B$. Since there are no $x\in \emptyset$ in the first place, there are never any counterexamples to $\emptyset\subseteq B$ (again, regardless of what $B$ is).

It's worth mentioning that there are less trivial solutions to this problem as well. For example, fix some $a\in A_{TM}$. The padding lemma then builds us a computable infinite set $A\subseteq A_{TM}$ of "equivalent versions" of $a$ (not everything "equivalent to" $a$ shows up in $A$, but infinitely many things do).

And even more is true - $A_{TM}$ is computably enumerable, and we have the following general fact:

  Every infinite computably enumerable set has an infinite computable subset.

This is a good exercise. HINT: think about the fact that any computably enumerable set which we can enumerate "in order" is computable.


How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?

Typically, by writing a recurrence relation for the running time and then solving the recurrence relation.  See How to come up with the runtime of algorithms? and Solving or approximating recurrence relations for sequences of numbers.   You might also want to read your friendly textbook and Is there a system behind the magic of algorithm analysis?.


Shortening the number of reductions to prove NP-Completeness

Yes, that's possible.

The reduction from Subset Sum to Partition is a mapping $f$ from Subset-Sum-instances to Partition-instances.  The reduction from Partition to Job Scheduling is a mapping $g$ from Partition-instances to Job-Scheduling-instances.  So, the function $g \circ f$ is a mapping from Subset-Sum-instances to Partition instances.

This gives you a direct reduction in one step; the reduction is given by the function $g \circ f$.  If you work through the details of the construction of $f$ and $g$, you should be able to figure out what $g \circ f$ is doing.  If you wanted, you could write down the definition of the function $g \circ f$ without telling anyone that it came from composing $f$ and $g$.  Whether that would be useful in any way is a different question...


Relation between interactive proof systems (IP), NP, coNP, PSPACE

IP = PSPACE is a famous result (and indeed paper) by Adi Shamir in 1992.

Furthermore, we clearly have NP $\subseteq$ PSPACE and coNP $\subseteq$ PSPACE, but we don't know how NP relates to coNP.  There are several reasons to believe that determining the relationship between NP and coNP is difficult, some of which are discussed in this recent thread.