How are system calls handled in a virtual machine?

There are 3 common strategies to handle this:
1. Hypervisor traps system calls from guest:  The hypervisor checks whether the privileged instruction(effectively system call) came from the guest OS itself, or from a user-space program within the guest OS. If it's the former case, then the hypervisor will actually forward the call to the hardware, although through the virtualization instructions. If it's the latter, the hypervisor will redirect the call to the guest OS, and then proceed.
2. Binary translation: Here the hypervisor checks the code from the guest OS in what are called as "basic blocks", scanning for privileged instructions. Wherever it finds them, it replaces them with calls to it's own procedures to system calls. It then proceeds to cache these blocks & eventually builds a whole set of such blocks.
3. Paravirtualization: Here the guest OS itself is modified so that instead of making calls to the hardware, it has APIs to invoke the hypervisor to get its hardware I/O done.

Source: Modern Operating Systems by Andrew Tanenbaum


Is there a context free, non-regular language $L$, for which $L^*$ is regular?

$L = \{a^n b^n \mid n\in\mathbb{N}\}$ is context-free but not regular (classical example). So is $L' = \{a^n b^n \mid n\in\mathbb{N}\} \cup \{a,b\}$.

$L'^\ast = \{a,b\}^\ast$ is regular.


Recall that $L \in \Sigma_i^p$ iff $\bar{L} \in \Pi_i^p$. Suppose now that $\Sigma_i^p \subseteq \Pi_i^p$, and let $L \in \Pi_i^p$. Then $\bar{L} \in \Sigma_i^p$ and so $\bar{L} \in \Pi_i^p$ by assumption, implying that $L \in \Sigma_i^p$. In other words, $\Pi_i^p \subseteq \Sigma_i^p$, and so $\Sigma_i^p = \Pi_i^p$.

Here's why $L \in \Sigma_i^p$ iff $\bar{L} \in \Pi_i^p$. For concreteness, we take $i = 3$. By definition, $L \in \Sigma_3^p$ if for some P-time predicate $T$,
$$
x \in L \Leftrightarrow \exists |y| < |x|^{O(1)} \forall |z| < |x|^{O(1)} \exists |w| < |x|^{O(1)} T(x,y,z,w).
$$
Similarly $\bar{L} \in \Pi_3^p$ if for some P-time predicate $S$,
$$
x \in \bar{L} \Leftrightarrow \forall |y| < |x|^{O(1)} \exists |z| < |x|^{O(1)} \forall |w| < |x|^{O(1)} S(x,y,z,w).
$$
However, these two statements are equivalent, as a simple invocation of de Morgan's laws shows, together with the fact that P is closed under complementation (take $S = \lnot T$).


maximum matching number decreases when vertices collapse?

Try to find a proof that it can't happen! Keep trying.  Hint:

   Suppose you have a maximum matching for the collapsed graph.  Can you use that to find a matching for the original graph?  How many edges does it have?  What does that imply about your question?

If you're really stuck, try to write a program to enumerate all graphs with at most 6 vertices (say) and see if the matching number can ever increase after collapsing an edge.  That should enable you to form a reasonable conjecture, which you can then try to prove, or should give you a counterexample.


Why are strings immutable in some languages?

This issue is strongly connected to the notion of what it means to be an instance of a class. In strict Object-Oriented terms, a class has an associated invariant: a predicate which always holds true on exit from a (public) method of the class. Such a notion is central in ensuring that inheritance is well-defined, for example (it's part of the Liskov Substitution Principle).

One of the most pernicious issues with Java is that it is difficult to prevent client code from breaking class invariants.

For example, consider the following 'ZipCode' class:

class ZipCode {
    private String zipCode;

    public ZipCode(String value){
        if(!isValidZipCode(value))
            throw new IllegalArgumentException();
        zipCode = value;
        assert(invariant());
    }

    public String get() { return zipCode; }

    public boolean invariant() {
        return isValidZipCode( zipCode );
    }
}

If String were not immutable, it would be possible for a user of ZipCode to call 'get' and change the characters at any subsequent time, thereby breaking the invariant and destroying the conceptual integrity offered by the encapsulation  of the ZipCode concept.

Since this kind of integrity is essential to ensuring that large systems are valid, this answer to your question really begs the wider one of:

"Why doesn't Java support an analog of C++ const, or at least offer immutable versions of more of it's library classes?"


How many times in this pseudo-code is the function F called?

The function is called 3 times.
F(3)
F(2)
F(1)


Many filters, particularly linear time-invariant ones, are represented by a kernel function. The output of a filter at a point is calculated by a weighted average of all the points of the input where the weights are specified by the kernel function. The kernel function takes displacements from the current output point we're calculating to other points, so it is always relative to the output point.

The support of a filter is then, intuitively, the "size" of the kernel. Any displacement for which the kernel function is $0$ means that we don't have to consider the corresponding point at all when calculating the value of an output point. Therefore, the most strict definition of support is that it is the set of displacements where the kernel function is non-zero. This could be a quite complicated set in general, and so isn't particularly helpful for understanding or calculation. A looser definition would be the support is any set (of displacements) which contains all the displacements where the kernel function is non-zero. This allows us to conservatively approximate the support with some simple-to-describe shape. This will usually be something like an ellipse or rectangle or square (or their lower-/higher-dimensional analogues). Given such a class of approximate shapes, the support will usually be taken to be the smallest approximate shape which contains all the displacements for which the kernel function is non-zero.

For that page, the support is the smallest ellipse which contains all the non-zero inputs of the kernel function. For discrete kernels that are typically used to implement these filters on a computer, usually a rectangular support is used. This allows calculating the weighted average by iterating only over the points in a (typically much smaller) sub-rectangle of the input, rather than iterating over the entire input while multiplying most values with zero. It also means the kernel function can be described by only specifying its values for that rectangle, and this is usually represented by a matrix called the mask in the 2D case.


How many "compressible" strings are there?

A simple counting argument shows that the number of strings of length $N$ such that $K(S) \leq M$ is at most $2^{M+1}$.

Conversely, considering the program $\Pi$ that gets an integer $r$ and a string $x$, and outputs $x$ together with $r$ many zeroes. Going over all strings of length $\ell$, this gives us $2^\ell$ many strings whose complexity is at most $\ell + O(\log N)$. Choosing $\ell = M - O(\log N)$, this shows that the number of strings of length $N$ such that $K(S) \leq M$ is at least $2^M/N^{O(1)}$.

This answers your first two questions up to a small multiplicative error. I suspect that the answer to the third one depends heavily on $N$.


Partitioning a bipartite graph to get disjoint components of same size

Your problem is NP-hard, even for any fixed $k \geq 3$ by a straight-forward reduction from 3-SET-COVER. Quick explanation: nodes of $S$ are triplets, nodes of $T$ are set elements and each triplet connected to all elements it contains.

I am still thinking about the case when $n$ is fixed.


Tree search returning parents and children

Given a tree, expressed with parent pointers, you can easily add child pointers: just traverse all nodes, and when you encounter a node $n$, look up its parent $p$, then add a child pointer from $p$ to $n$.

Given a tree and a search condition, you can find all matches by iterating over all nodes to see which ones satisfy the search condition.  If you've augmented the tree to contain both parent pointers and child pointers, for each matching node, you can return its parent and its children using those pointers.


Why can't a compiler create universal N-bit code (e.g. 32-bit, 64-bit, etc.)

The instruction set for a 32-bit processor is different from the instruction set for a 64-bit processor.  The 64-bit instructions can't be executed on a 32-bit processor.  So, the program really does need to be compiled to something different: if you take a program compiled for a 64-bit processor, and try to run it on a 32-bit processor, the processor won't run it, because it doesn't understand the new 64-bit instructions.


Confusion in the added loop of the Halting Problem

What we show is that this augmented $H$ can not even exist. You gave me $H$, and I gave you back an augmented $H$, called $\hat H$. We can build this $\hat H$ by adding the extra loop and if statement, but its easy to show that this augmented $\hat H$ will never be able to exist: $\hat H(\langle \hat H\rangle)$ is not either rejecting or accepting, nor stuck in an infinite loop, but we know that any TM must be either one of those.
Therefore, we get a contradiction to the existence of $H$: we showed that if $H$ exists, then some other $\hat H$ exists, but also $\hat H$ couldn't ever exist.


Algorithm to explore every node in a graph

The standard way to solve this is called whatever-first search. (Because depth-first and breadth-first and best-first and others are all special cases of it.)

The algorithm goes like this:

Pick a starting node
Add the starting node to a "bag" (arbitrary data structure)
While the bag isn't empty:
    Take a node out of the bag
    Mark this node as "explored"
    [Do whatever you like with this node]
    Add all this node's unexplored neighbors to the bag

The choice of "bag" is up to you. A stack makes depth-first search, a queue makes breadth-first search, a priqueue makes best-first search, and so on, but you can use anything you like, as long as you can put things into it and take things out of it.


Karatsuba Multiplication Rule in dividing a Number in two parts

The most common approach is to take the longest number, and divide it in half (rounding an odd number of digits arbitrarily). So for

x = 12345
y = 2478

you would get a=12, b=345, c=2, d=478. Since the number of digits in x is not even, we are free to choose whether to split into a=12 and b=345 or a=123 and b=45; it makes no difference to the running time. For your second example

x = 12456778
y = 241

you would get a=1245, b=6778, c=0, d=241.


K shortest paths - any relation between K and % of graph nodes in discovered paths?

It seems to me the relation depends purely on how the graph is made. Think about a cycle. The shortest path between two adjacent vertices contains 2 vertices while the second contains n vertices


Is a language of some deciders decidable?

I don't fully understand the details of your question (especially the notation that you've used).

However, the language you're asking about appears to be finite (something like the language of descriptions of all Turing machines that halt for all inputs and have at most 100 states), and every finite language is decidable.  You could, in principle, produce a list of all the strings in your language, and then just design a Turing machine that accepts exactly that list of strings.

Note also that reducing $L$ to the halting problem wouldn't prove that $L$ is undecidable, since every recursively enumerable language reduces to the halting problem. You'd just be showing "If I could solve the halting problem, I could solve $L$, too." That's a bit like saying, "If I was the world's strongest man, I could lift an apple." Maybe you don't need to be so strong to do such a simple thing? If you want to prove that $L$ is undecidable by reductions, you need to reduce an undecidable language to $L$: then, you're saying, "If I could decide $L$, I'd be able to decide this undecidable language, and I know I can't do that."


How important is to formulate a convex optimization for a proposed algorithm?

I don't know whether any of us can predict how reviewers or your community will react, especially without seeing the manuscript; probably your best bet is to talk to your advisor or to collaborators or colleagues and ask them for their advice.  You might also ask them if they'd read a draft of your paper.

My expectation is that it might depend on whether your field values provable results ("theory"), or pragmatic empirical results ("engineering").  The benefit of a convex formulation is that it allows proving some theorems about the approach, e.g., that it will always find the optimum under certain conditions.  The benefit of your approach is that it seems to get better results in practice, at least on the workloads you've been testing it on.  I can't tell you which your community will value more highly.


This looks like an instance of the assignment problem.  (No, it doesn't require a square matrix.)


How to express a type that represents an associative array whose keys determine the type of the value?

What happens if I try to get Bar before it has been set? If you expect a compilation error, then you are not talking about a single type, but instead a sequence of types, where the type changes after each call to the set method. Look into 'strong update' and 'linear types'.
Why not just use a record type?
type MyRecord = { Foo : Error, Bar : number }


Looking for the name of this job scheduling algorithm

I don't know the name of the problem, but I do know the solution - this is the same problem that I had to solve for my algorithms course, just different terminology. The problem allows for a greedy choice. If you merely wanted a hint, then stop reading here because below is the solution.

Greedy choice: you schedule the job with maximum profit on its deadline. (If jobs should be finished before the deadline, e.g. job 1 should be done before $t = 2$, then simply subtract one from the associated deadline.)

The algorithm is pretty much working backwards in deadlines, (starting at the latest deadline) scheduling the job with highest profit available on that deadline (this boils down to the greedy choice).

I will leave the proof of the greedy choice as an exercise (read, I don't have a proper keyboard available, which isn't too great for my RSI, so I cannot write it now).


How would I simulate a network to explore the percolation threshold of a network connected by the knight's move?

First of all, you don't simulate an infinite board. You simulate larger and larger boards, until the percolation threshold seems to stabilize. For a given size of board, you need to decide on what event signifies that percolation happens. One common option is that the top of the board is connected to the bottom of the board. For each probability $p$, you estimate the probability that this happens by doing many samplings. You then use binary search to estimate the probability $p_c$.

Here are some more details. Suppose you've decided on some board size. The first step is to compute all the edges, that is all pairs of vertices connected by a knight's move. Given a probability $p$, you run the following experiment many times. Put in each edge with probability $p$ independently. Then check (using DFS/BFS or equivalent) whether the top of the board is connected to the bottom of the board (that is, add a new "top" vertex connected to all vertices at the top of the board, add a similar "bottom" vertex, and check whether the two are connected). Do this many times, and estimate the probability $\theta(p)$ that "bottom" is connected to "top". Then use binary search on $p$ to find a value of $p$ such that $\theta(p) \approx 1/2$, say. This is your estimate for the critical probability.


Does there exist a subset of substrings for reconstructing another string?

If reusing strings in $A$ is allowed you can solve it with dynamic programming: First, store strings in $A$ in a prefix tree (just a reversed suffix tree link), and recursively detrmine if $S[i:end]$ can be constructed from $A$: Let $\ell$ be the length of the string, and wlog assume $S$ is appended by $\$$ and $A\gets A\cup \{\$\}$. Moroever, let $m[i]\in\{0,1\}$ indicate if $S[i:\ell]$ can be constructed by elements in $A$. Initialize $m[i]\gets \infty$ for $i=0,\dots, \ell-1$ and $m[\ell]=1$ (because $S[\ell]=\$$).
Now, suppose $f(i)$ is the function that recursively computes $m[i]$ if it hasn't been computed already. When $f(i)$ is called, start at the root of the suffix tree of $A$, and traverse $S[i], S[i+1], \dots$ on the suffix tree until index $j$ , such that the corresponding node is in $A$, and recursively call $f(j)$. If returns $1$, set $m[i]=1$ and return $1$. Otherwise, repeat the process with traversal of $S[j+1], S[j+2], \dots$ until another member in $A$, or a leaf is reached. If there was no success, set $m[i]=0$ and return $0$. To decide the problem, call $f(1)$. The worst case complexity is the complexity is $\ell d$, with $d$ being depth of the suffix tree (longest sequence in $A$), plus the cost of construction of the prefix tree.

The worst-case scenario in many cases will be avoided because the recursive call search stops as soon as one solution is found. So in practice, the $\ell d$ part might be much less. The construction of the suffix tree can be expensive depending on $A$. But if $A$ is used for several strings $S$, the cost is amortized. If $A$ is really big and $S$ is short, it might be better to just sort elements of $A$ and do a binary search instead of traversal.


In which O-class does my Θ-result belong?

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

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


Does hardness of a special case imply hardness of a general case?

If frafl's answer doesn't give it away immediately, perhaps think in the reverse direction, if the special case is NP-hard, what would be implied by the general case being in P?


Distribution of random Fourier coefficients

Each Fourier coefficient on its own is the average of $2^n$ independent uniformly random $\pm1$ variables. Its distribution is roughly normal with mean $0$ and variance $2^{-n}$.


What helpful solution does the Halting Problem give to computing?

The halting problem is an example of a problem that a computer cannot solve. On the face of it, it might seem that computers can do anything, given enough resources and time. However, Turing showed that this intuition is false. Later on this was made more tangible by showing that a computer cannot decide whether a given Diophantine equation has solutions in the positive integers.

This is similar to Gödel's incompleteness theorem, which shows that the axiomatic method doesn't provide an answer to all possible questions. In fact, no finite list of axioms is enough to determine the truth of every statement regarding the natural numbers. Later on, a natural example emerged in the realm of set theory, namely the continuum hypothesis.


You asked two questions.  What you are missing is that those two questions are unrelated.

Question 1:

  $$L_{1}\leq_{p}L_{2}$$

  If $L_2$ is stated to be in $\textbf{NP}$, is it necessarily true that $L_1$ is $\textbf{NP}$-Complete?

No.  Consider the case where L1 and L2 are the same easy problem.

Question 2:

  I need to show the following for an assignment, but I'm having a dispute with a fellow student because he claims that I can't claim that $L_1$ is $\textbf{NP}$-Complete...

    Suppose that $L_1\leq_p L_2\leq_p L_3$. Also suppose that $L_3$ is in $\textbf{NP}$. Explain how to solve $L_1$ deterministically in exponential time.

  I say […] that since $L_3$ is in $\textbf{NP}$, $L_2$ also has to be in $\textbf{NP}$, and so therefore $L_1$ has to be in $\textbf{NP}$. And if that's the case, then $L_1$ can easily be converted to a deterministic algorithm through a breadth first search through the non-deterministic computation tree. Is there something I'm missing?

There is nothing wrong with your proof.  (Okay, I would not call the exponential-time simulation of a nondeterministic polynomial-time Turing machine “breadth-first search,” but that is a separate issue.)  As your fellow student said, it is true that you cannot claim that L1 is NP-complete, and indeed you have never claimed that L1 is NP-complete, so your proof for Question 2 does not contradict the answer to Question 1.


Is Palindrome subset of a regular language regular?

The subset of all palindromes in L is obviously not usually regular, take the simple example $a^*ba^*$ where the subset of palindromes $a^nba^n$ is not regular. But that is not the question. The question is about the set of all left halves of palindromes in L.

Assume you have an FSM for L (that is an FSM describing and defining L). You can take that FSM and use a simple algorithm to determine if w is in M:

Given a state S, define succ(S, a) as the state that the FSM will transition to from state S with input a, or nil if there is no transition for a. For a set of states T, define pred(T, a) as the set of states S such that succ(S, a) is not nil and an element of T.

To determine if w is in L, you would start with S = $S_0$. Then for every symbol s in w, you replace S with succ(S, s), exiting the loop if S is nil. Finally, w is in L if and only if S ≠ nil and S is an accepting state.

To determine if w is in M, you start with S = $S_0$ and T = set of accepting states. Then for every symbol s in w, you replace S with succ(S, s) and T with pred(T, s), exiting the loop if S is nil or T is empty. Finally, w is in M if and only if S ≠ nil and S is an element of T.

Instead of using this algorithm, you can quite easily construct an FSM for M.


For a language $L$, let's write $\|L\|_n$ for the number of length-$n$ strings it contains.  So $L$ is sparse if there is a polynomial $p$ such that $\|L\|_n\leq p(n)$ for all $n$. The key point is that, for a language to be sparse, we must be able to pick just one polynomial that works for all $n$: you're not allowed to use a different polynomial for each $n$.

For example, suppose that you wanted to prove that the language of strings over $\{0,1\}$ with at most two $1$s is sparse.  You can't say "Well, for $n=3$, there are seven valid strings, and $7 < n+5$ for $n=3$. And for $n=4$, there are eleven valid strings, and $11 < n^2-4$ for $n=4$, and..." You have to pick just one polynomial that works for all values of $n$: in this case, $n^2$ works, so the language is sparse.

So, for a non-sparse language, $\|L\|_n$, when considered as a function of $n$, must grow faster than any possible polynomial. The simplest examples of functions that grow faster than polynomials are exponentials. Conveniently, $\{0,1\}^*$ has $\|\{0,1\}^*\|_n=2^n$ for all $n$. So, whatever polynomial $p$ you pick, $\|\{0,1\}^*\|_n>p(n)$ for all large enough $n$. Therefore, $\{0,1\}^*$ is not sparse.

Another example of a non-sparse language is the complement of a sparse language. If $\|L\|_n\leq p(n)$ for all $n$, then $\|\overline{L}\|_n\geq 2^n-p(n)$ and this grows faster than any polynomial if $p$ is a polynomial.


Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints

Edit: See my answer to the same question on math stackexchange here. I've copy and pasted the answer again for ease of use.

There has been a recent line of work investigating algorithms for submodular optimization problems when the objective may take negative values. So far, the non-negativity that we can handle is when the submodular objective decomposes into the sum of a monotone submodular and an arbitrary modular function. The optimization problem is
$$ \max_{S \in \mathcal{I}} g(S) - c(S) \enspace,$$
where $g:2^V \rightarrow \mathbb{R}_+$ is a non-negative and monotone submodular function, $c:2^V \rightarrow \mathbb{R}$ is a modular function, and $\mathcal{I} \subset 2^V$ is a matroid on the ground set $V$. Note that if $c$ takes positive values, then the entire submodular objective $f = g - c$ is non-monotone and may take negative values.  The first approximation result was given by Sviridenko, Vondrák, and Ward in 2014 who showed that one can use a continuous extension & rounding approach to obtain a set $S$ such that
$$ g(S) - c(S) \geq (1 - e^{-1}) g(OPT) - c(OPT) $$
They applied this result to obtain tight approximation guarantees for monotone submodular maximization and monotone supermodular minimization with bounded curvature. They also show that this approximation is tight in the sense that no algorithm making polynomially many queries to $g$ and $c$ can do better. Then in 2018, Feldman gave an algorithm that also goes through the continuous domain but is more efficient in that it by-passes a certain "guessing step" in the previous algorithm. Most recently, Harshaw, Feldman, Karbasi, and Ward in 2019 gave a series of much faster algorithms which do not go through the continuous extension, but are based on greedily optimizing a "distorted surrogate objective" which changes thoroughout the algorithm; however, their results apply only when the modular function is non-negative and the constraint is a cardinality constraint. They also extend the analysis to show that when $g$ is $\gamma$-weakly submodular, then one may obtain the analogous approximation
$$ g(S) - c(S) \geq (1 - e^{-\gamma}) g(OPT) - c(OPT)  $$
Moreover, this extended approximation guarantee is tight in the value oracle model.

There is the hardness result by Uriel Feige which shows that even verifying that $f(S) \geq 0$ for some $S$ is NP-Hard. So, the decomposition into a sum of submodular and monotone functions really is crucial in all these algorithms.
I don't know how much further one can push the decomposition approach.


Given a binary min-heap, getting a sorted array of the $\log n$ smallest elements

Consider another min-priority queue $q$. The result will be in array $a$.

Push the top of the heap into $q$.
For $i$ from $1$ to $\log n$:

Set $a_i = \text{pop}(q)$.
Push the two sons of $a_i$ in the heap into $q$.

$q$ may be implemented with a min-heap of size  $O(\log n)$, so the overall complexity is $O(\log n \log \log n)$.


Throughput increase/decrease by how much percent

The max delay isn't 200 and 350. In both cases, there is also a stage with a delay of 400ps, the clock speed is limited by that stage as well. The clock speed cannot be faster than 1/400ps = 2.5GHz either way, otherwise the slowest stage would break.


Is an expression in normal form if terminates on normal order but not applicative?

The expression $(\lambda x.y \  (\lambda x.(x \  \ x) \  \lambda x.(x \ \  x)))$
is not in normal form because it can be further reduced using the β-rule.

Also, as you noted, Applicative Order is not a normalising reduction strategy. For the expression $(\lambda x.y \  (\lambda x.(x \  \ x) \  \lambda x.(x \ \  x)))$ it fails to find the normal form. This is because $(\lambda x.(x \  \ x) \  \lambda x.(x \ \  x))$ is a non-terminating argument, it has no normal form, then it will loop forever.

On the other side, Normal Order is a normalising reduction strategy because it will always find the normal form, if it exists of course. In fact this a practical consequence of the second Church-Rosser theorem. For the expression $(\lambda x.y \  (\lambda x.(x \  \ x) \  \lambda x.(x \ \  x)))$ it finds the normal form. In this case, since $\lambda x. y$ is a constant function, it will ignore its (non-terminating) argument.


Misunderstanding Turing's Halting-Problem Argument

"So what am I missing?"  Nothing.    Computerphile should have defined H++ by  H++(x) = H+(x,x) ,  and then run H++ on itself.


Are all data structures in the von Neumann architecture based on the array, or array-like?

Your question is a bit vague, but it seems that you're missing one mechanism: dynamic memory allocation. Some data structures such as linked lists are heavily based on dynamic memory allocation, and so although linked lists are very similar to arrays in function, they are implemented very differently.

Dynamic memory allocation is treated as a primitive in C. System libraries are supposed to implement the malloc() and free() primitives, with the support of the operating system. While eventually memory is accessed (in the CPU level) as one long array (perhaps some of it implemented as virtual memory), this is all hidden under the hood as far as the C programmer is considered (unless they choose to tinker with it).


Pseudo random, unqiue integer numbers in a given range

Without loss of generality, we can assume you need numbers in the range $\{0,..,n-1\}$.  (Just add the appropriate offset.)

This can be solved by constructing a random permutation $f:\{0,\dots,n-1\} \to \{0,\dots,n-1\}$, then outputting the values $f(0),f(1),f(2),f(3),\dots$ as your sequence of pseudorandom numbers.  Those numbers won't repeat until each number in the range has been defined.  If $f$ can be computed efficiently, this will be fast.

So how do we construct such a random function $f$?  One approach is to use format-preserving encryption, a technique from cryptography that allows you to construct a function $f$ that is a bijection on the set $\{0,\dots,n-1\}$ (for any $n$ of your choice), and that appears pseudorandom.  There are many FPE algorithms.

See https://blog.cryptographyengineering.com/2011/11/10/format-preserving-encryption-or-how-to/ and https://crypto.stackexchange.com/questions/tagged/format-preserving for more (e.g., https://crypto.stackexchange.com/q/41450/351, https://crypto.stackexchange.com/q/504/351, https://crypto.stackexchange.com/q/29073/351, https://crypto.stackexchange.com/q/20035/351, https://crypto.stackexchange.com/q/16561/351, https://crypto.stackexchange.com/q/18988/351).


The problem "Does the largest clique have a size ≤ k" is in co-NP - if the answer is NO then there is a clique of size > k, and guessing that clique proves that the answer is NO.

But the problem here is "Does the largest clique have a size of exactly k". If the answer is NO then it could be that the largest clique has size k-1 and there are no cliques of size k, k+1, k+2 etc. Sure, you could guess a clique of size k-1 - but that doesn't prove a clique of size k doesn't exist. And you can't guess a clique of size k+1 because no such clique exists.


NP-hardness of existence of spanning tree with given maximal degree

Hint for part 1: What does it mean when $G$ has a spanning tree where every node has at most 2 neighbors?

Hint for part 2: Suppose you know that it is NP-hard to show that $G$ has a spanning tree where every node has at most 2 neighbors. Can you reduce this problem of at most 2 neighbors to the current problem of at most 5 neighbors?

This post is made out of user53923's comment as I have verified it is useful.


Is it possible to compute how many iterations this algorithm will take?

There might be no clean formula for that.

The values of $x,y,z$ after the $n$th iteration of the loop are $x_0 + (n+1) y_0 - 2n(n+1)$, $y_0 - 4n$, and $z_0 - 2n$, respectively, as can be verified by induction, where $x_0,y_0,z_0$ are their initial values (before the first iteration of the loop).   The loop terminates for the smallest positive integer $n$ such that

$$x_0 + (n+1) y_0 - 2n(n+1) + y_0 - 4n \equiv 0 \pmod{z_0 - 2n}.$$

There might not be any nice expression for the smallest $n$ that satisfies that equation, in terms of $x_0,y_0,z_0$.  It's also not obvious to me whether such an $n$ always exists, i.e., whether your loop will always terminate.

I'm glossing over a serious issue that you haven't addressed in the question: what is the meaning of $(x+y) \bmod z$ when $z=0$ or when $z<0$?  It's not clear, and that will affect the answer.


a conjunctive normal form that is a tautology

Take any clause in the formula. If all variables in that clause are different, we can always assign $0$ to a non-negated variable and $1$ to a negated variable. This makes that clause $0$. Therefore, it makes the CNF formula $0$. Thus, tautology is not possible unless there is $A \vee \neg A$ in every clause.
This is probably what Kyle Jones stated in his comment.


How should I "read" a dereference operator?

I always read
*y =1
as: assign the value $1$ to the memory location pointed by y.

Why?

y is a pointer type variable, so it has an address as a value. It another words, it points to this address. When we want to, indirectly,  manipulate the memory area pointed by y we use *y. Hence *y=1 tells that the value $1$ should be stored in the memory location pointed by y.


Minimum cost to convert one array to another

Let distinct elements of $B$ be $b_1,b_2,\ldots$ where $b_1>b_2>\cdots$. There must be an optimal solution where it first sets a range to $k_1$ then set a range to $k_2$ and so on, such that $k_1\ge k_2\ge\cdots$ (otherwise one can swap related operations to meet the constraint without changing the result), and $k_1,k_2,\ldots\in\{b_1,b_2,\ldots\}$ (otherwise, say $k_i\notin\{b_1,b_2,\ldots\}$, one can delete the $i$th operation without changing the result).

Using the property above, we have the following greedy algorithm.

Let $B[i_1],B[i_2],\ldots$ ($i_1<i_2<\cdots$) be the greatest elements, i.e. $b_1$. The algorithm firstly sets $A[i_1],A[i_2],\ldots$ to $b_1$ using as little operations as possible. More specifically, it checks whether $A[i_1]>b_1$ to see whether an operation is required to set $A[i_1]$ to $b_1$. If so, it then checks whether $A[i_1+1],\ldots,A[i_2-1]\ge b_1$* by range minimum query to see whether this operation can be merged with the operation corresponding to $A[i_2]$. It then goes on with $A[i_2],A[i_3],\ldots$ For example, say

A: 3 3 3 3 2 1 3
B: 2 1 2 1 2 1 2

Now $b_1=2$ and $i_1=0, i_2=2, i_3 = 4, i_4=6$. It requires 2 operations to set $A[i_1],A[i_2],\ldots$ to $b_1$: first setting $A[0], \ldots, A[2]$, then setting $A[6]$.

The algorithm then repeats the above process for $b_2,b_3,\ldots$

This algorithm runs in $O(n\log n)$.

*Note, for example, when dealing with $b_2$ instead of $b_1$, no operation can be performed on a range containing $i_j$ for some $j$, otherwise $A[i_j]$ will be less than $B[i_j]$ and cannot be recovered. Therefore we must also check this constraint here. This can be done by maintaining a sorted index array of all elements greater than $b_m$ when dealing with $b_m$.


Context-free grammar for all words not of the form w#w

If a word is not of the form $w\#w$ then one of the following must happen:

It contains no $\#$.
It contains more than one $\#$.
It is of the form $x\#y$, where $x,y \in \{0,1\}^*$ and $x \neq y$, in which case one of the following must happen:

$|x| > |y|$ or $|x| < |y|$.
$x_i = 0$ and $y_i = 1$ for some $i$, or vice versa.

The only case which is non-trivial to handle is the last one, in which case we have a word of the form
$$
x_1 0 x_2 \# y_1 1 y_2,
$$
where $|x_1| = |y_1|$. We can split this into
$$
x_1 \;\; 0x_2\# \;\; y_1 \;\; 1y_2,
$$
where $|x_1| = |y_1|$. This should make it clear how to construct a CFG for such words.

Altogether, we obtain the following grammar:
\begin{align}
&S \to A \mid B \mid C \mid D \mid E \mid F \\
&A \to 0A \mid 1A \mid \epsilon \\
&B \to A\#B \mid A\#A\#A \\
&C \to A0G \mid A1G \\
&D \to G0A \mid G1A \\
&G \to 0G0 \mid 0G1 \mid 1G0 \mid 1G1 \mid \# \\
&E \to E_11A \\
&E_1 \to 0E_10 \mid 0E_11 \mid 1E_10 \mid 1E_11 \mid 0A\# \\
&F \to F_10A \\
&F_1 \to 0F_10 \mid 0F_11 \mid 1F_10 \mid 1F_11 \mid 1A\# \\
\end{align}
In this grammar:

$A$ generates words without $\#$
$B$ generates words with more than one $\#$
$C$ generates words of the form $x\#y$ with $|x| > |y|$
$D$ generates words of the form $x\#y$ with $|x| < |y|$
$E$ generates words of the form $x_10x_2\#y_11y_2$ with $|x_1|=|y_1|$
$F$ generates words of the form $x_11x_2\#y_10y_2$ with $|x_1|=|y_1|$
$G$ generates words of the form $x\#y$ with $|x| = |y|$


How to write regular expression excluding certain pattern aba from albhabet set {a,b}?

Maybe the easiest (though not necessarily fastest, if done by hand) way to do this is to make use of the many equivalent formalisms for regular languages:

Create an NFA that accepts all words that contain the pattern. (This NFA will consist of a chain of transitions that are labeled with the pattern and additionally can loop in the initial or final state on every symbol.)
Transform that NFA into a (complete) DFA using a standard algorithm.
Make all the accepting states of the DFA non-accepting and vice versa.
Translate the inverted DFA into a RE using a standard algorithm.


Defining nullable symbols and the first set of a grammar

A nonterminal $X$ is nullable if you can generate the empty word from it. For example, since $A \to \epsilon$, we see that $A$ is nullable, while since the only production involving $B$ is $B \to b$, we see that $B$ is not nullable.

In class, you were shown algorithms for determining which nonterminals are nullable. These algorithms are important for computers implementing parsers. Human beings can also use these algorithms to determine which nonterminals are nullable, but (i) outside of a classroom setting, humans never have the urge to determine which nonterminals are nullable, (ii) often it can be determined by "direct inspection".

The first set of a nonterminal consists of all initial terminals in words generated by $X$ (including $\epsilon$, if $X$ is nullable, at least in some definitions). For example, since the only word generated by $B$ is $b$, then $\mathrm{FIRST}(B) = \{ b \}$. Similarly, the productions of $A$ immediately imply that $\mathrm{FIRST}(A) = \{ \epsilon, a, (\}$. Continuing, since $S \to AB\$$ is the only production of $S$, then since $A$ is nullable and $B$ isn't, $\mathrm{FIRST}(S) = \{ a,(,b \}$. This is the same as $\mathrm{FIRST}(T)$. Here I am implementing the FIRST algorithm in my head, without ever looking at it. Algorithms are necessary for computers, not necessarily for humans.

Summarizing, I suggest focusing on the definitions of nullable and FIRST rather than on the algorithms that can be used to compute them. It is much more important to understand what you're doing (and why) then to memorize some algorithm which you will never ever use in the future.


Polynomial Computation of the probability of a number of independent events

You can use dynamic programming. For parameters $m,\ell$, define
$$ q_{m,\ell} = \sum_{I \in \cal I_{m,\ell}} \prod_{i \in I} p_i \prod_{i \in [m] \setminus I} (1-p_i). $$
This satisfies the recurrence
$$
q_{m,\ell} = p_m q_{m-1,\ell-1} + (1-p_m)q_{m-1,\ell}
$$
with initial values $q_{0,0} = 1$ and $q_{m,\ell} = 0$ for $\ell < 0$ and $\ell > m$. This gives an $O(n^2)$ time algorithm.

The same idea can be expressed using generating functions:
$$
\prod_{i=1}^n (1-p_i + p_i x) = \sum_{k=0}^n \Pr(N_k) x^k.
$$


Algorithm to find optimal currency denominations

This is related to the well-known change-making problem. So well-studied, in fact, that this question has been investigated for $m \leq 7$ [1] using brute force. As of 2003, the hardness of finding optimal denominations appears to be an open problem.

If you check the articles citing Shallit, it seems as if denominations enabling greedy change-making strategies were of particular interest. It is clear that such denominations have advantages in practice.

What This Country Needs is an 18c Piece
 by Jeffrey Shallit (2003)


Let $k_i = 2^i$, and define $m$ to be the minimum value such that $n-(m-1) \leq k_m$. It's not hard to check that the running time of $f_2$ is $\Theta(k_1 + \cdots + k_{m-1})$. Since $k_i$ grows exponentially, $k_1 + \cdots + k_{m-1} = \Theta(k_m)$, and so the running time of $f_2$ is $\Theta(k_m)$.

It remains to find the minimum integer value of $m$ which satisfies $n-m < k_m = 2^m$. Clearly this minimum value is at most $\log_2 n$, implying that $2^m \leq n$. This also means that the critical value of $m$ satisfies $2^m > n-\log_2 n = \Omega(n)$. Therefore $k_m = \Theta(n)$, and so the running time of $f_2$ is $\Theta(n)$.

Regarding the space complexity, it is proportional to the depth of the recursion, which as we have seen is very close to $\log_2 n$.


What is the difference between derivative free optimization and derivative optimization in terms of advantages/disadvantages?

Actually, derivative methods such as random search shorten the time allocated for function evaluation if the problem is big. On the other hand, derivative-free methods take much time to complete function evaluation that leads to a dramatic increase in optimization time.


Resulting complexity class for allowing two passes over witness in NL?

Any finite number of passes will still give you NL. Here is why two passes give you NL — the general case is very similar. You can guess the state of the work tape after the first pass and them simulate the two passes in parallel. In the end you verify that the state of the work tape after the first pass in indeed what you guessed earlier.


You should first state the deadlock freedom property and the starvation freedom property more precisely.
I use the definition in the Book: The Art of Multiprocessor Programming; Section 2.2.

Freedom from Deadlock If some thread attempts to acquire the lock, then some thread (not necessarily the thread referred to in the if statement; emphasis added) will succeed in acquiring the lock.
Freedom from Starvation Every thread that attempts to acquire the lock eventually succeeds.

Note that by definition, starvation freedom implies deadlock freedom. Thus, if a mutual exclusion algorithm suffers from deadlock, it also suffers from starvation.
A direct argument is that: deadlock means that some thread attempts to acquire the lock, but no threads succeed. That is a special kind of starvation.


Do height-balanced binary trees have logarithmic depth?

Let us denote by $N_h$ the minimum number of leaves of a tree in your family of height $h$. Clearly $N_0 = 1$, and
$$ N_h = N_{h-1} + \min_{0 \leq d \leq c} N_{h-1-d}. $$
(Here $N_h = 0$ if $h < 0$.) You can prove inductively that $N_h$ is monotone, and so for $h \geq c+1$,
$$ N_h = N_{h-1} + N_{h-1-c}. $$
This is a recurrence relation whose solution is $N_h = \Theta(\alpha^h)$, where $\alpha$ is the maximal real root of $x^{c+1} - x^c - 1= 0$; for example, when $c = 1$, $x$ is the golden ratio.

Since the number of leaves in a tree of height $h$ is $\Omega(\alpha^h)$, it follows that a tree containing $n$ leaves has height $O(\log n)$.


"The questioner asked my why private IP address is determined in such range"
IMO a good answer is "Because it has been established in RFC-1918; which is a "Best Current Practice" RFC :-)
The three ranges allow private networks to "resemble" the class A-B-C subdivision (and probably this is what the questioner wanted to hear from you). See older RFC791: .... To provide for flexibility in assigning address to networks and
allow for the  large number of small to intermediate sized networks
the interpretation of the address field is coded to specify a small
number of networks with a large number of host, a moderate number of
networks with a moderate number of hosts, and a large number of
networks with a small number of hosts..... Also see Wikipedia Classful network for more details / references.
The reasons for the particular numbers are not well known (and are only interesting from a historical-folklore point of view), and probably the main criteria was to use address spaces that were free/unused at the moment.

10.x.x.x comes from the old ARPANET and is easy to remember
172.x.x.x was marked by IANA as "Special purpouse" block of IP addresses
192.168.x.x was used by Sun in its workstations (?!?)


An approximation algorithm for a maximization algorithm has an approximation ratio of $\alpha \geq 1$ if whenever the true answer is $m$, the algorithm is promised to return a solution with value at least $m/\alpha$.

In your case, $m = 13$ and $\alpha = 1.5$, and so by definition, the algorithm must return a clique whose size is at least $13/1.5$. Since the size of the clique is an integer, if a clique is of size at least $13/1.5 \approx 8.6$, then it is in fact at least $\underline{\quad}$ (fill in the blanks).


This is not how memory access works. For each character read, you need (1) to read the character, (2) to access the transition table at the appropriate state and character. In your case it seems that we're not counting (1), and so (2) is the single memory access. The speed of this access depends on how big the transition table is. If it is small enough to fit in cache (which is usually the case), then after several transitions, the entire transition table would be in cache and so would be accessed quickly. If it is too big, you will have cache misses and everything would be slower. But in both cases only the particular cell is accessed! However, data is stored in caches in chunks knows as cache lines, which could explain your confusion (cache lines are not big enough to hold the entire transition table). Note also that there are several levels of cache.


Is a device with restrictive execution policies Turing-complete?

First, Apple may wish to restrict applications, but in practice, all versions of the iPhone can be jailbroken: you can then upload arbitrary machine executables. Whether the phone vendor likes or dislikes that you jailbreak the phone is immaterial to evaluating its computing power. But, for the same of the argument, let's add the hypothesis that the iPhone is not jailbroken, and more generally that you only use the iPhone in ways that are approved by Apple.

Whether you can load your code without Apple's approval or not is not relevant. The iPhone is Turing complete if there is some way of programming every computable function and of encoding arbitrarily long inputs and outputs. Turing completeness doesn't say that the encoding has to be what you consider the most natural, which is to install arbitrary machine code.

There is a killer argument which shows that the iPhone, like any other computer, is not Turing-complete: it only has a finite amount of memory. Therefore, the class of computing power is that of a finite automaton, no more.

If the iPhone was allowed to rely on an external storage medium that allowed to store an arbitrarily large amount of data (finite, but whose length is not bounded by the input size), and if network access was allowed, then it would be Turing-complete. One way would be to browse a website containing a Turing machine emulator or other Turing-complete computation mechanism, with input being defined as typing in a form and output being defined as changing the content of the page.

There are other ways of encoding Turing machines that don't require network access or non-default apps to begin with. You would need an iPhone augmented with an infinite tape to pull it off, though, so such an encoding would have to specify how the tape is used in addition to the use of actual iPhone features.

For example, you can type arbitrary JavaScript in bookmarklets in the web browser. If we ignore the problem that a concrete physical device has a finite amount of memory, JavaScript is a Turing-complete language. If you treat the bookmarklet arguments as input and the target URL as output, you can implement a universal Turing machine. JavaScript cannot i
nteract with all hardware devices, but as far as pure computing power is concerned, it is sufficient to perform any calculation.


Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum

You are counting the number of ordered pairs of sets $(A,B)$ such that the elements of $A$ (and of $B$) sum to $n(n+1)/4$.
Simply divide the result by $2$ to account for symmetries.

Besides, your algorithm has complexity $\Omega(2^n)$ so I doubt you'll meet the time constraint in the link you provided.

You can get an $O(n^3)$-time dynamic-programming algorithm as follows:

   Let $OPT[n, x]$ be the number of ways the numbers in $\{1, \dots, n\}$ can be partitioned into an ordered pair of sets $(A,B)$ such that the elements of $A$ sum to $x$ and those of $B$ sum to $n(n+1)/2 -  x$.

 Then, $OPT[0, 0] = 1$, $OPT[n][x] = 0$ if $n<0$ or $x<0$, and

 $$OPT[n,x] = OPT[n-1, x-n] + OPT[n-1, x]$$

 Now, assuming that $n(n+1)/2$ is even, the solution you are looking for is: $\frac{1}{2}OPT[n][ n(n+1)/4 ]$.


How to make a NFA (or DFA) from $\varepsilon$NFA?

I think the following should work. For each state q, define E(q) to be the set of all states reachable from q by following zero or more ε-transitions. Then, create a new NFA as follows:

The set of states in the NFA is the set $\{ E(q) | q \in Q \}$.
The start state is $E(q_0)$.
For each state $E(q)$ in the new NFA, the transitions are given as follows: for each state $r \in E(q)$ that has a transition to a state $s$ on a character $a$, add a transition from $E(q)$ to $E(s)$ on $a$.
The accepting states in the NFA are the states containing at least one accepting state in the original NFA.

The basic idea behind the construction is to have each NFA state correspond to a set of states in the ε-NFA. This effectively simulates taking all possible ε-transitions at each point in time.


Here's a hint: we know that $L = \{x^m y^m \mid m ≥ 1 \}$ is a non-regular language.

Is there some part of $I = \{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0\}$ which looks similar to $x^m y^m$?

Could you somehow extract that part?

If you could, could you use the fact that $L$ is not regular to conclude that the extracted part is not regular?

Given this, can you then conclude that $I$ is not regular?


The simplest Face Recognition 101 would be run a PCA on the data, followed by a K-nearest neighbor classification.

but now there are more advanced techniques that you pick along, it might be using "better" classifiers like SVMs or Neural Networks or apply Bayesian learning, but then, as you move up the knowledge tree, you will realize you need your data itself to be more robust.. so you will then want to learn about about SIFT and other techniques.

One of the nice places you can start looking for papers and algorithms is face-reg

Have fun learning :)


Difference between HSI and YCbCr for pattern recognition by color

I'm not an expert, but judging from the Wikipedia articles, YCbCr is used for image compression (JPEG and television [YPbPr]), while HSI is used in computer vision. Since you're doing computer vision, if we believe Wikipedia then you should use HSI. Of course, you could always experiment with both representations and all six dimensions. See what works best. If you're fitting a linear model, then it doesn't really matter, and you can even use RGB.


First, let's talk about what a histogram of directions is.  You can think of the image as a 2D discrete function of x and y: I(x,y). You can take partial derivatives of this function: Ix and Iy. So at each pixel you have the gradient, which is the vector (Ix(x,y), Iy(x,y)). If you compute the magnitude of the gradient, and look at it as an image, you will see the edge map. If you compute the orientation of the gradient at each pixel, you get the edge orientation at that pixel. This is what you take a histogram of.

You divide the range of orientations into some number of bins (let's say 8). Then you look at a single cell. Inside the cell you compute the gradient of every pixel, take its orientation, and add it to the appropriate histogram bin. You can also weigh the contributions by the gradient magnitude, so that pixels with stronger edges contribute more to the histogram.  Once you are done, the histogram encodes the distribution of edge orientations within the cell. Dividing the image into cells preserves some of the spatial layout of the edges.

The size of the cell is a parameter, which you can tune. Typically, it is set to 8x8. If the cell is too small, then you do not have enough pixels for a meaningful histogram. If the cell is too large, then you lose too much of the spatial information.


Is the language L = {(a,b)* | #a * #b is an odd number} regular?

It is.

Since only the product of two odd numbers is an odd number, you can construct a DFA that only accepts when #$a$ and #$b$ are (both) odd.

The followings states would be:

$Q_1$ : #$a$ even, #$b$ even
$Q_2$ : #$a$ even, #$b$ odd
$Q_3$ : #$a$ odd, #$b$ even
$Q_4$ : #$a$ odd, #$b$ odd (an accepting state)

The transitions are fairly simply, and I'll leave them to you.


Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state

Indeed, as you say, a PDA can accept by final state or by empty stack. The two acceptance criteria can be effectively translated into one another. Main ingredient of that translation is to clearly mark the bottom symbol of the stack, so the PDA knows when the stack will be empty. In that way it will not accidently block or accept when not planned.

True, given a CF grammar you can construct a single state PDA, accepting by empty stack. In that simulation the contents of the stack correspond to the part of the string not rewritten in a leftmost derivation. If the CFG you start with is in Greibach Normal form, then the PDA can be constructed to be "real-time" i.e., it has no $\epsilon$-moves.

The point is to combine both ideas. Thus mark the last nonterminal. When it is removed (not replaced by another nonterminal), then move to the second state, the final accepting state (at the same time emptying the stack).

For the CFG from your example $S\to aSB, S\to aB, B\to b$ this can be obtained by changing the grammar a little and making a "marked" copy $\bar X$ of each nonterminal $X$ to indicate bottom of stack: $\bar S\to aS\bar B, \bar S\to a\bar B, \bar B\to b, S\to aSB, S\to aB, B\to b$. Production $\bar B\to b$ is the final one. $\bar S$ is the new start symbol.


Informed search with a lower-bound heuristic?

After some consideration, this appears to be an alternative formulation of the depth-first variant of the Branch-and-Bound algorithm.


Finding paths of certain length in trees

Idea: Root the tree in an arbitrary node. For every node, count

paths in its subtrees,
paths that start in a subtree and end in the root, and
paths that start in one subtree, traverse the root and end in another subtree.

That is, for a given node $v$ with children $u_1, \dots, u_m$, the number $p(v,k)$ of paths of length $k$ (counting nodes) in the subtree $T_v$ rooted in $v$ is

$\qquad\displaystyle\begin{align*}
  p(v,k) &= \sum_{i=1}^m \biggl[ p(u_i,k) \biggr] \\
         &\ + \sum_{i=1}^m \biggl[ p_r(u_i,k-1) \biggr] \\
         &\ + \sum_{i=1}^{m-1}  \sum_{j=i+1}^m \sum_{l=1}^{k-2} \biggl[ p(u_i,l) \cdot p(u_j,k-1-l) \biggr]
\end{align*}$

for $k \geq 2$; we anchor the recurrence in $p(v,1) = 1$ for all $v$. For the paths ending in the root, we get the (simpler) recurrence

$\qquad\begin{align*}
  p_r(v,k) &= \sum_{i=1}^m p_r(u_i,k-1)
\end{align*}$

which also anchors in $p_r(v,1) = 1$.

These recurrences immediately imply a recursive algorithm (computing both simultaneously).

The runtime is in "$\Theta(m^2k)$" per node of degree $m$; hence, on trees with finitely bounded degree, the algorithm runs in time $\Theta(nk)$. Otherwise, it may take time $\Theta(n^2k)$ (e.g. on stars).


What is the asymptotic behaviour of a sum of powers of three?

First, your assumption, I'm more concerned with just finding big oh, since that can be used to find big omega is a bit dangerous. You could indeed easily find a $O()$ upper bound for your sum, $S(n)=3^1+3^2+3^3+\cdots+3^n$ by observing that each term is less than $3^n$ so you could have
$$
3^1+3^2+\cdots+3^n\le \underbrace{3^n+3^n+\cdots+3^n}_{n}=n3^n=O(n3^n)
$$
but that's a huge overestimate (try it for, say, $n=5$) and so will almost certainly not serve as a suitable big-Omega bound*. Instead, you could simply use the formula for a geometric series and get an exact value, but suppose you didn't know that formula (or were prohibited from simply invoking it).

On the way to finding a good estimate, you could always try this helpful idiom: We've written $S(n)=3^1+3^2+3^3+\cdots+3^n$ and so we also have $S(n+1)=3^1+3^2+3^3+\cdots+3^{n+1}$ so
$$\begin{align}
S(n+1)-3S(n)&=(3^1+3^2+\cdots+3^{n+1})-3(3^1+3^2+\cdots+3^n)\\
 &=(3^1+3^2+\cdots+3^{n+1})-(3^2+3^3+\cdots++3^{n+1})\\
 &= 3
\end{align}$$
But we also know that $S(n+1)=S(n)+3^{n+1}$ so we have
$$
3=S(n+1)-3S(n)=S(n)+3^{n+1}-3S(n)=-2S(n)+3^{n+1}
$$
and so with a little algebra we find
$$
S(n) = \frac{3^{n+1}-3}{2}=\frac{3}{2}(3^n-1)
$$
Since we have an exact value for the sum, we can easily see that $S(n)=\Theta(3^n)$. However, if you need to establish explicit constants to show $S(n)\ge c\,3^n$ (for big-omega) and $S(n)\le d\,3^n$ (for big-o) it's not too difficult. (Hint, can you see that you can use any $d\ge 3/2$?)

$^*$As an aside, you might have been misled in your choice of replacements at the very start by the proof that $1^k+2^k+3^k+\cdots+n^k\le n^k+n^k+\cdots+n^k=n^{k+1}$ which does indeed lead to a big-Theta estimate, though for a different sum.


What's the value of this game (rebalancing counters)?

Let's collect what facts we can determine:

The sum of all counters $S$ will change by $T-P$ with each cycle of $T$ steps, where $P$ is the number of positive counters at the final step of the cycle.
If you end a cycle with $P=T-1$, you have $S\le(T-1)(M-1)$. During the following cyle you can reach $S=(T-1)M$ after $T-1$ steps, but in the next step you will have to increase a $T$-th counter, so the decrease after that step will return to $S=(T-1)(M-1)$. So $(T-1)M$ is an upper bound for $S$ (and thus also for $P$).
Assume there is an optimal strategy, that never reaches $S=(T-1)M$. The step where that strategy reached its highest value of $S$, has to be the penultimate step of a cycle, and the cycle before that one has to have ended with $P\le T-1$. By inserting a cycle that simply increases some or all of the nonzero counters before the cycle that reaches maximum $S$, we can increase the maximum value of $S$ for that strategy without influencing the maximum value of $P$.
Thus we can restrict our search for an optimal strategy to strategies that start by bringing $T-1$ counters up to $M$ and then try to distribute the sum amongst as many counters as possible.
The maximum value of $P$ will be reached at the penultimate step of a cycle. (At any other point we can raise it by increasing counters that were previously 0 until that step of the current cycle.) We denote by $X$ the number of cycles (including the incomplete one) in the distribution phase.
We can assume that any counter we increase during the distribution phase will be nonzero in the $X$-th cycle. Otherwise not spending these increases would not alter the outcome. For the same reason we can assume that each nonzero counter is at value 1 in the $X$-th cycle.
From the previous item we can conclude that any counter increased in the 1st cycle has to be increase $X$ times, any counter increased for the first time in the 2nd cycle has to be increased $X-1$ times and so on. This implies that it is beneficial to start increasing each counter as late as possible.
In the last cycle we cann set $T-1$ counters to 1. In the cycle before that, we can set $\frac T2$ counters to 2, and so on, until in the first $\frac XT$ cycles we can set one counter to $X$. This shows that it is beneficial to make $X$ as large as possible.
$X\le M$, since after the $M$-th cycle all the initial counters will reach 0 (or we have to spend increase operations on them that we could instead have spent to increase other counters).

Since the optimal moves from our considerations describe exactly the strategy from the question, we can conclude that this strategy is indeed optimal.


Let $D$ be the grammar, $S \mapsto01S1\mid SS\mid\epsilon$.
Then each word $w$ generated by $D$ is a mixture of equal number of $01$'s and $1$'s such that in any prefix of $w$ there are at least as many 1's as 0's but at most twice as many 1's as 0's.

Let $H$ be your grammar, $S \mapsto01X\mid011X$ and $X\mapsto 01X1\mid ϵ$.
Then each word generated by $X$ is some number of 01's followed by the same number of 1's. So each word $w$ generated by $H$ starts with 01 or 011, followed by some number of 01's, followed by the same number of 1's.

Both $D$ and $H$ are CFGs. While $D$ is ambiguous as illustrated by $011\ \  011011=011011\ \ 011$, $H$ is unambiguous.

The word 010111011 is generated by $D$ but not by $H$. The word 01011 is generated by $H$ but not by $D$. Hence, the language generated by $D$ and the language generated by $H$ are not the same.

It should not be hard to prove the various claims in the above paragraphs. Yuval Filmus' idea to treat 01 as one symbol might be helpful.

Is the language generated by $D$ inherently ambiguous? Here is the spoiler.

   No. In fact, there is a deterministic grammar $S \mapsto \epsilon\mid 01S1S $. The language is actually isomorphic to the celebrated dyck language.


What kind of data structure should be used for working with dynamic sets where elements follow "normal distribution" and why?

A hash function might not map the nearby elements to the same bucket. For example suppose the hash function is $h(x) = x^2 \mod p$ where $p$ is some prime number say $97$. Suppose $x$ follows normal distribution with values between $1$ to $1000$. And, suppose that most of the values are concentrated around $500$.
If you compute the hash values at $x = 499$, $x = 500$, and $x = 501$,
the hash function gives the following values: $h(499) = 2$, $h(500) = 31$, and $h(501) = 62$. Note that, although the input values are close to each other, their mapped values are not close to each other and they lie in completely different buckets.
Designing a good hash function that uniformly maps the values across the table, mostly depends on a particular use case. But, you can always make your hash function more complex by adding more terms to it, for example, by adding more terms of the form $x^k$ to it, etc. It will hopefully provide a uniform spread of values across the table.


How the language $\{a^nb^mc^nd^m | n \geq1, \ m\geq1\}$ is used to check whether formal and actual parameters are equal?

The language

$$L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$$

abstracts agreement of parameter and argument count for the case where there are exactly two procedures, one with $n$ parameters, declared with $a^n$ and used with $c^n$, and the other one with $m$ parameters, declared with $b^m$ and used with $d^m$. Each procedure is called exactly once and the calls are interleaved with the declarations. The interleaving makes it impossible for a context-free grammar to specify agreement.

One might be tempted to generalize to more uses of each procedure:

$$L'=\{a^nb^m\omega \mid n \geq1, m\geq1, \omega \in \{c^n,d^m\}^*\}$$

or more procedures (I'm not going to try writing that one out), but it just serves to make everything more complicated to no purpose.

The simple example is easily proven to not be context free, and the simplification can be justified by observing that context-free languages are closed under substitution which is a very powerful and useful proof technique. (The fact that declarations and uses can be reduced to repetition of a simple symbol is also justified by substitution. A starting point for Algol-style languages might be to remove all the parameters/arguments from a declaration/call, leaving only the commas and parentheses. For S-expressions it's even simpler.)

So the abstraction provides a simple proof (as well as some intuitive basis) for why parameter/argument agreement cannot be incorporated into a context-free grammar.


$f \in O(g)$ means there's $n_0$ and $c>0$ such that $n>n_0$ implies $f(n) \leq cg(n)$.

Note that for $n>2$, we have $n^2 \geq 3n$.

Then, for $n>2$, we have:
$$
\begin{align}
2(n^2 - n) & = n^2 - 2n + n^2 \\
& \geq n^2 - 2n + 3n\\
& = n^2 + n\\
\end{align}
$$

Summarizing: for $n>2$, we have $n^2+n \leq 2(n^2-n)$. Thus $n^2+n \in O(n^2-n)$.


Kernelization trick, for neural networks

I think you might be confusing the terminology in a way that is making the issue confusing. SVMs work by defining a linear decision boundary, i.e., a hyperplane. We can define this hyperplane in terms of inner products between the points. Therefore, if we define this inner product to be in some high-dimensional, or even infinite dimensional space, what looks like a hyperplane in this new space is a not necessary linear in the original feature space. So everything is still linear, the only thing we've done is to implicitly (via the new inner-product) embed the points in some higher dimensional space. Maybe you already know all this.

There are 2 issues to consider with respect to neural networks. The first was brought up by @Yuval Filmus, because of the hidden layer neural networks depend on more than just the inner products between the points. If you remove the hidden layer, you just have something like logistic regression, of which there are kernelized versions. Maybe there is a way to get around this, but I don't see it.

Secondly, you mention preprocessing the input by projecting into a higher, but not infinite, dimensional space. Neural networks define a decision surface and this surface is not constrained to be linear. This means the gain from projecting the points into a higher dimensional space will be different, i.e., it may make it easier to find a good set of weights, but we haven't necessarily made our model any more powerful. This follows from the Universal approximation theorem that tells us given a large enough number of hidden units we can approximate any function (under some restrictions). This last statement is rather vacuous and I kind of hate to mention it. By not telling you anything about how to find the right weights it doesn't bring much to the table from an application perspective.


Find maximal subset with interesting weight function

Definitely NP-hard, since it can be used to encode a maximisation form of Vertex Cover in which we ask for the maximum number of edges that can be covered by any subset of $k$ vertices: The input matrix here is just the incidence matrix of the graph, with vertices in the rows and edges in the columns.


Hint: For EXTRACT-MIN, instead of thinking in terms of shifting rows/columns, try to replace the element at $(1,1)$ by $+\infty$. Now you just want to swap $+\infty$ with one of his neighbour until you get the invariant of a Young tableau. How can you decide where to move it?


Any reason why Turing Machine would prevail on recursion theory?

With Turing machines you can talk about computer concepts such as running time and space usage. This is harder with $\mu$-recursive functions.


Difference between a skiplist and an Indexable skiplist

An Indexable Skiplist is a skiplist with the added property that it can quickly lookup the $m$th entry (in order) in a skiplist in $O(\log n)$ time in a skiplist of $n$ entries.  In other words, it takes a skiplist that is not an indexable skiplist $O(n)$ time, on average, to find the $m$th element in order in a skiplist, while an ordered skiplist can do this in logarithmic time.

It does this by keeping track of the width of the links in the skiplist.


What you require is the lexicographic ordering. Let me describe this.
Suppose the speeches have two attributes. The first one is "speaker's name" and the second one is the "length". For simplification, let me define the speaker's name by the integer value instead of a character string. Now, suppose the speeches are represented using the following tuples: $(0,0)$, $(1,2)$, $(0,3)$, $(1,4)$, $(2,3)$, $(2,4)$, and $(1,1)$. Here, the second speech has the speaker's name: $1$, and length $= 2$.
Requirement 1: You simply want to sort the speeches by the "speaker's name".
Just consider the first attribute for comparing any two speeches and apply any sorting algorithm. You will get the following ordering: $(0,0)$, $(0,3)$, $(1,2)$, $(1,4)$, $(1,1)$, $(2,3)$, and $(2,4)$.
Requirement 2: You want to sort first by the "speaker's name" and then by the "length". This is the requirement that you have mentioned in your question.
Now, define a new comparison operation between two tuples as follows: $(a,b) < (c,d)$ if and only if $(a<c)$ or $(a = c$ and $b<d)$
Here, we are comparing by giving the "first attribute" more priority. And if the first attribute value is the same, we compare based on the "second attribute".
Smilarly, you can define $(a,b) > (c,d)$ if and only if ($a>c$) or ($a = c$ and $b>d$).
Now, you can simply use any sorting algorithm by replacing the standard comparison operation with the above-defined comparison operation.
You will get the following ordering: $(0,0)$, $(0,3)$, $(1,1)$, $(1,2)$, $(1,4)$,  $(2,3)$, and $(2,4)$.
Requirement 3: Suppose, you want to sort by the length and then by the speaker's name
Simply, define the comparison operation between two tuples as: $(a,b) < (c,d)$ if and only if $(b<d)$ or $(b = d$ and $a<c)$. Now, again you can use any standard sorting algorithm by replacing the standard comparison operation with this comparison operation.
You will get the following ordering: $(0,0)$, $(1,1)$, $(1,2)$, $(0,3)$, $(2,3)$, $(1,4)$,  and $(2,4)$.

Similarly, you can define a new comparison operation for the multiple attributes based on your requirements.


Is there an efficient way to cluster a graph according to Jaccard similarity?

Any hierarchical clustering algorithm should meet your needs.  There are many efficient methods for hierarchical clustering; you can use any of them for your application.

With agglomerative (bottom-up) clustering, you simply keep merging clusters until all clusters have at least $k$ nodes.

With top-down clustering, you keep splitting clusters, except that if the algorithm tells you to split some cluster in a way that would leave one of its subclusters with fewer than $k$ nodes, you cancel the split and mark that cluster as finalized.

In general, hierarchical clustering gives you a tree.  You can pick any consistent cut through the tree that leaves all clusters of size $\ge k$.  So, it is easy to adapt any hierarchical clustering algorithm to satisfy your requirement that all clusters have at least $k$ nodes.  Many of the hierarchical clustering methods let you use any pairwise distance function, so you can use them with your Jaccard similarity metric.


If you unroll the formulae you get:
$$T(n) = T(n-1) + c \cdot log(n) = \sum_{i=2}^{n} c\cdot log(i) + d = O(n \cdot log(n)) $$

Last equality is true from the following fact:
$$\sum_{i=1}^n log(i) \ge \sum_{i=\frac{n}{2}}^n log(i) \ge \frac{n}{2} \cdot log(\frac{n}{2}) = O(n \cdot log(n))$$
$$\sum_{i=1}^n log(i) = log(n!) \le log(n^n) = n\cdot log(n) = O(n\cdot log(n))$$


Are there ways to automatically (no human testing) measure a $9 \times 9$ Sudoku puzzle's average hardness for a human to solve?

There are have been many such attempts. Most of them try to derive deduction rules which humans seem to use to solve Sudoku puzzles.

My money is on this approach:

Mária Ercsey-Ravasz & Zoltán Toroczkai (2012), The Chaos within Sudoku, Scientific Reports 2:75, Nature.

The idea is based around the notion of transient chaos in a dynamical system.

In dynamical systems, when you change the state, there is often a period of time where a transient signal dominates, before the system manages to get itself into a steady state solution. If the dynamical system is nonlinear, the transient may be chaotic.

This is different from a chaotic attractor (e.g. the Lorentz attractor), in that the steady state that the system is eventually drawn to isn't chaotic, just the transients.

The time that the system takes for the transients to die down is called the escape rate. What the authors found is that if you turn the puzzle into a SAT problem, and then turn that into an equivalent dynamical system (where the attractor of the dynamical system is the solution to the SAT problem), the escape rate of the system correlates quite well with how Sudoku puzzles are rated for hardness.

The interesting thing about this approach is that it's independent of Sudoku. Any puzzle which can be turned into a SAT problem fairly directly (the SAT problem and the puzzle can't diverge too far) can be analysed in the same way.


Binary Tree Multithreaded Time Complexity

[..], then wouldn't the big $\mathcal{O}$ time complexity be $\mathcal{O}(\log n)$

People often forget that big-$\mathcal{O}$ notation only is meaningful in a certain context, here this becomes obvious:

You are probably used to count some set of instructions (like comparing, adding etc.) as one unit - called unit cost model - each instruction happening sequentially. In that model you're right, traversal and outputting every vertex of a binary tree is $\Omega(n)$ (ie. you cannot do better than linear).

However when talking about parallel algorithms and their complexity things change, first of all you will need to specify $p$ how many processors you use1. You will also need to specify  whether multiple processors have exclusive or concurrent access for reading/writing.

You were probably talking about the CREW (concurrent read, exclusive write) PRAM and assumed $p = n$ in your question:

  you could never traverse an entire tree in less than $\mathcal{O}(n)$

In total all the processors will have looked at $\mathcal{O}(n)$ vertices in the binary tree, this does not change and is called the work.

You were right that the time complexity (refered to as depth) is $\mathcal{O}(\log n)$ for that algorithm.

To illustrate my point even more, assume that the binary tree is given as an array with a certain order and still using $n$ processors with a CREW machine. Now, every (numbered) machine can simply lookup the value at its position in that array.

This algorithm has still $\mathcal{O}(n)$ work, but $\mathcal{O}(1)$ depth.

Conclusion

Always be aware of the context (eg. what model, what input format) since this has a great influence on the complexity. Once you introduce parallelism things become different and it's important to be precise about what assumption you make and how many processors an algorithm uses.

1: From now on I will assume a parallel random-access machine since it's very simple but still useful.


NLP Classification: rule-based approach providing high precision but low recall

I dont have enough reputation to add this as comment. Maybe this survey of text classification algorithms (including rule-based approach) could help you http://www.time.mk/trajkovski/thesis/text-class.pdf


Are regular and context free languages closed against making them prefix-free?

Can't we make the same thing with a pushdown automata for context free languages ?

No. Your construction needs to start with a deterministic automaton, and PDAs cannot be determinized.


Why is a negative number a pseudo-positive number in ones' complement?

You are asking two questions:

How can I prove that negative numbers are stored as pseudopositive?
Why are negative numbers stored as pseudopositive?

The answer to the first question is that no proof is needed, since one's complement is a way of representing signed numbers as unsigned numbers, and it specifies that negative numbers are stored in this specific way. There is nothing to prove here, just read the definition of one's complement. In other words, this is true by definition.

Regarding the second question, storing numbers in this way facilitates arithmetic. For example, to add two numbers, you just add them as unsigned numbers, with an extra little fiddling depending on the sign bits; in two's complement you don't even need the extra fiddling.


Which is the best data structure for searching under these conditions

Edit: Seems like my proposed structure is not more efficient than a HashMap with additional entries like (A3,B1,Cany,Dany).

Typical values

There are F=20 factors (A, B, ..., T)
Each factor has V=1000 values (A1, A2, ..., A1000).
A lot of combinations (A524,...,T123) do no appear at all. The data structure should be sparse.

Suggestion: Use the following tree structure

Non-root Nodes represent a factor-value (for instance A1).
There can be multiple nodes per factor-value.
Per Node Xx we store

The number of (...Xx, Yany, Zany, ...) in the structure
A HashMap from Y1,...,YV to the corresponding nodes.

Example

We have the factor-values
A1–A3, B1–B2, and C1–C4.
In our text, the following combinations appeared:
2 times (A1, B1, C1),
1 time (A1, B1, C4),
4 times (A1, B2, C4)

Then our tree looks like the one in the picture below.

The counter per node is green, the hashmap is red.

Operations and costs

Insertion is O(F). Query (using "any" or not, and using threshold or not) is O(F).
In case the number of factors F is constant, operations are O(1).

Insertion

We found x new occurrences of combination (Aa, Bb, ..., Nn) and want to update the structure.

curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., N_n)
    nextNode := curNode.hashMap[nextFactorValue]
    if (nextNode == null)
        nextNode := new Node(nextFactorValue)
        curNode.hashMap[nextFactorValue] := nextNode
    endif
    curNode.count := curNode.count + x   // update the "any" counts
    curNode := nextNode
endfor
curNode.count := curNode.count + x     // update the concrete count

Should you want to decrement the stored counts, you may want to remove nodes once their counter hits 0.

Query

Retrieve $count(a,b,...,i)$ = number of found (Aa, Bb, ..., Ii, jany, ..., Nany)

curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., I_i)
    nextNode := curNode.hashMap[nextFactorValue]
    if (nextNode == null)
        return 0
    endif
    curNode := nextNode
endfor
return curNode.count

Query with threshold

Compute $
count_t(a,b,...,m,n) =
\begin{cases}
count_t(a,b,...,m),& \text{if } count(a,b,...,m,n)<t\\
count(a,b,...,m,n),& \text{otherwise}
\end{cases}
$

curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., N_n)
    nextNode := curNode.hashMap[nextFactorValue]
    if (nextNode == null || nextNode.count < t)
        return curNode.count
    endif
    curNode := nextNode
endfor
return curNode.count


A doubt regarding the acceptance of $\epsilon$ by an automaton testing divisibility of numbers

It is rather standard to assume that 0 represents zero (and is divisible by two). Also it is usually assumed that decimal numbers do not start with 0.

I once presented a finite state automaton without these assumptions, where I took  $\varepsilon$ as a representation for zero, and likewise 0000, and my students protested.


You are asking a lot of questions. Let me answer some of them.

Let us denote the contents of the Boolean matrix $X$ after $t$ iterations by $X^{(t)}$. The first algorithm uses the recurrence
$$
\begin{align*}
&X^{(0)}(i,j) = A(i,j), \\
&X^{(t+1)}(i,j) = X^{(t)}(i,j) \lor \bigvee_k \bigl(X^{(t)}(i,k) \land A(k,j)\bigr).
\end{align*}
$$
You can prove by induction that $X^{(t)}(i,j)$ is true iff there is a directed path from $i$ to $j$ of length at most $t+1$.

The second algorithm uses the recurrence
$$
\begin{align*}
&X^{(0)}(i,j) = A(i,j), \\
&X^{(t+1)}(i,j) = X^{(t)}(i,j) \lor \bigvee_k \bigl(X^{(t)}(i,k) \land X^{(t)}(k,j)\bigr).
\end{align*}
$$
You can prove by induction that $X^{(t)}(i,j)$ is true iff there is a directed path from $i$ to $j$ of length at most $2^t$.

Since $2^t$ grows much faster than $t+1$, the second algorithm will use less iterations. The worst case number of iterations in the first algorithm is $n$, whereas in the second algorithm this goes down to $O(\log n)$.


Depth of any node x in Weighted Quick-Union Algorithm

If the size of a tree starts at 1 and doubles $i$ times, it will be $2^i$ (at least -- there might be other size increases as well). If $i>\log_2N$ this would give a size $>N$ -- more than the total number of nodes.


Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points

How about:

Build a weighted complete bipartite graph where the left vertex set is $S$, the right vertex set is $G$, and the weight of the edge between $s \in S$ and $g \in G$ is the 3-D Manhattan distance from $s$ to $g$.
Solve the assignment problem for this graph.

This finds the exact minimum. It does unfortunately take about $O(n^3)$ for a typical network flow algorithm, though.


Question about proof of Kannan's Theorem

Following your way:

Let us denote by $C_{n,s,i}$ the i'th $n$ inputs, $s$ size circuit (relative to the lexicographic ordering of the strings describing such circuits), Then:

$x\in L \iff \exists i \hspace{1mm} \phi\left(C_{|x|,|x|^{k+1},i}\right)\forall j<i : \neg \phi\left(C_{|x|,|x|^{k+1},j}\right)\land C_{|x|,|x|^{k+1},i}(x)=1$.

$\phi(C)$ is a formula which states that $C$ cannot be computed by an $n^k$ size circuit, and can be written as a $\Pi_2$ statement (as you did in your original post).

The idea is the same as yours, trying to decide some language in $SIZE(n^{k+1})\setminus SIZE(n^k)$. The only addition is using the lexicographic ordering and forcing minimality. This way we force that for any length $n$ string, the quantification over the circuit index $i$ yields the same circuit.

After grouping the quantifiers (and moving $\forall j<i$ right after $\exists i)$ you get a $\Sigma_4$ formula.


What is the field studying the search and generation of computer programs?

What you are describing is a Kolmogorov complexity approach. The Kolmogorov complexity of an integer sequence (or a string) is the size of the minimal program computing it (in some fixed Turing-complete language). Here we're looking for the minimal program which generates $n+1$ numbers, the first $n$ of which are the given sequence.

Kolmogorov complexity is not computable - that is, one cannot compute the size of a minimal program computing a given sequence. The implementation you mention computes a restricted version of Kolmogorov complexity in which the programs are very simple (and always halt).

Another (non-computable) approach is the universal probability distribution in which a given integer sequence of complexity $x$ is given a probability in proportion to $2^{-x}$. By conditioning on the first $n$ numbers produced, we can construct a probability distribution on the next number. By restricting the set of programs, we can make this distribution computable (though perhaps not efficiently).


Which hazards are solved by instruction reordering?

Instruction reordering in cpu-pipelines doesn't solve any hazards problem.

Register renaming eliminates write-after-write data hazards on registers and write-after-read data hazards on registers.

Speculative execution tries to find some useful work to do in the presence of control hazards.

Instruction reordering only works between instructions that are already completely independent of one another (either because they work with completely different registers or because after register renaming they don't need any of the same registers).  At best I would say that instruction reordering solves a "bookkeeping hazard" (I just made that term up).  The reason you would not do instruction reordering dynamically in the pipeline is if the bookkeeping hardware to do instruction reordering is too expensive for one reason or another.  Issuing instructions in-order is cheaper (in terms of hardware) than implementing the queues and logic to do out-of-order issue.


3SAT_1 is easy, and a variant of 3SAT_2 is NP-complete. My guess is that 3SAT_2 is also NP-complete. Update: my guess is proved below.

Let $C = x\lor y\lor z$ be a clause. Then $\lnot C = \lnot x \land \lnot y \land \lnot z$. An assignment makes every clause of $\phi$ false if it makes all their negations true. The conjunction of the negation of all clauses is just a big conjunction. A conjunction is satisfiable if and only if it does not contain a variable and its negation. So 3SAT_1 is in P (in fact it's in AC$^0$).

The variant of 3SAT_2 asks whether $\phi$ has an assignment that makes exactly $8/9$ of the clauses true. This is clearly in NP. To reduce 3SAT to this variant, take the formula $\phi$, and for each clause $C$ in $\phi$ add the eight clauses
$$(x_C \lor y_C \lor z_C) \land \cdots \land (\lnot x_C \lor \lnot y_C \lor \lnot z_C).$$
In any assignment, exactly seven of these are correct. In total we have $9|\phi|$ clauses. Of the $8|\phi|$ that we added, exactly $7|\phi|$ are always correct. Hence $\phi$ is satisfiable if and only if in the new formula one can satisfy exactly $8|\phi|$ constraints, which are $8/9$ of its clauses.

Update: Here is a reduction from 3SAT to 3SAT_2 itself. Given a formula $\phi$, consider two cases. The first case is when we can falsify all clauses in $\phi$ at once. As shown above, in this case each variable appears only positively or only negatively, and so setting it appropriately, the formula is satisfiable. Otherwise, add $|\phi|$ clauses of the form $x \lor y \lor z$, where $x,y,z$ are new variables. In any assignment either all of these are satisfied, or all are not satisfied. Since the original clauses cannot be all falsified at once (by assumption), the new formula can be half-satisfied if and only if the original one is satisfiable.


$O(n\log n)$- algorithm for finding tree root

Routine 1
Firstly, observe that only the root node disconnects the tree into exactly two equal connected components of size $2^{k-2}-1$. All other nodes disconnect the tree into three or zero connected components. We have the following $\mathcal{O}(n)$ approach to check if a given node is the root.

Let the node to check be $x$.
Pick another node $y \not= x$
Iterate through all other nodes $z \not\in \{x,y\}$ and ask if $x$ disconnects $y$ from $z$.
If there are $2^{k-2}-1$ nodes in the connected component of $y$, then $x$ is a root, else it isn't.

Routine 2 Now, let's present an $\mathcal{O}(n)$ algorithm to identify leaves. Observe that a random node has $\ge 0.5$ probability of being a leaf node. Hence our algorithm is -

Pick a random node in the tree, say $x$.
Pick another random node $y$.
If $x$ does not disconnect $y$ from $z$, for all valid $z$, then $x$ is a leaf node in the tree.
Repeat steps 1, 2 and 3 till you obtain a leaf.

The expected number of queries used by this algorithm is $\mathcal{O}(n)$.

Routine 3 Now let's make the next observation. There are $2^{k-1}$ nodes in the last level of this complete binary tree. Colour these leaf nodes with two colours, red and blue. A leaf is coloured red if it belongs in the left sub tree of the root and blue otherwise. Using Routine 2, we will try to find a pair of leaf nodes one of which is red and the other is blue in $O(n)$ queries. Here is how -

Find any leaf node using the algorithm in Routine 2. Call this leaf node $u$.
Find a different leaf node, call this $v$.
$u$ and $v$ are of different colour if and only if exactly $2k-1$ nodes  can disconnect $u$ from $v$, i.e., the nodes on the path that connect $u$ to $v$ (We assume that deleting $u$ will disconnect $u$ from $v$). This can be verified in $\mathcal{O}(n)$ queries as well by iterating over all nodes once.
Repeat steps 2 and 3 till you find the desired leaf node.

The probability that a random node is a leaf node and is of a different colour than $u$ is $\ge 0.25$. Hence the expected number of queries asked in this algorithm is also $\mathcal{O}(n)$.

Now that we have our two leaf nodes of different colours, we are ready to make the final observation, i.e., the root node must be one of the $2k-1$ nodes that can disconnect $u$ from $v$. Thus there are $2k-1 = \mathcal{O}(\log{n})$ candidates for the root node. We can iterate through each of them and check if they are the root using Routine 1.

Thus this algorithm uses $\mathcal{O}(n\log n)$ queries.

EDIT The final step can be improved to $\mathcal{O}(\log^2{n})$ by running Routine 1 on just the $2k-1$ candidates to find the node that splits the path from $u$ to $v$ into two equal connected components. Thus the problem can be solved in $\mathcal{O}(n)$ queries as well.


If you want to prove that a problem is NP-complete, you don't get to make up your own definition of NP. NP is the class of problems that can be solved by a nondeterministic Turing machine in time bounded by some polynomial function of the length of the input.

Specifically, you don't get to use oracles, you don't get to use some other measure of the size of the input (e.g., the logarithm of its length) and you don't get to make random access to the  contents array: you have to walk the head of the Turing machine there, one cell at a time.

Your problem is, as you say in your first sentence, clearly in P. It is, therefore, very unlikely to be NP-complete, since that can only happen if P=NP.


How does BIRCH (Balanced Iterative Reduction Using hierarchical) CF Tree insertion algorithm work?

Since you mentioned you haven't read it yet, I suggest you start by reading the original paper (which was linked to from the Wikipedia page).  For research-level contributions, that's often a helpful place to start, if you're having trouble finding a place to learn more.

Wikipedia also links to some slides on BIRCH.  That might be worth reading first to get an overview for what they're trying to achieve, before reading the original paper -- but you'll still need to read the original paper.  The slides are not a substitute for the paper, especially if you want to know the specifics of the algorithm.

You should not expect a textbook or slides to give this level of details.  They might try to give you the general idea or the overall intuition, but if you want to know the full details, it's likely that you'll need to read the original paper.  It's not unusual to find that you need to go to the primary sources, for recent research like this.


Given an array $A$ and an index $c$, prove there always exists a subarray whose sum $\pmod {i} = 0$

Let's try to do it, no induction involved.

Suppose you augment your initial list $A = [a_1, a_2, ..., a_m]$ with a new element at the beginning $a_0 = 0$, $A' = [a_0, a_1, ..., a_m]$.

Now build partial sums of $A'$, such that $P_i = \sum_0^i a_j$. Notice that the sums of elements in the initial list from positions $b$ to position $e$ is $\sum_b^e a_i = P_e - P_{b - 1}$. Notice $P_0 = 0$ is defined since we added $a_0$. This is a very common trick when you care about the sums of intervals.

Back to the problem, you need to proof there exist two index $i < j$ such that $c | (P_j - P_i)$. This is equivalent to say that there exist two index $i < j$ such that $P_i \equiv P_j \mod c$. We only care about remainder of each element in $P$ if they are divided by $c$, and moreover we should only show that at least two elements have the same remainder.

Now notice the number of different remainders given $c$ is at most $c$ and the length of the list $P$ is $|P| = m + 1$. Since $c \le m < |P|$ by the Pigeonhole principle you can guarantee at least two elements in $P$ have the same remainder.


Huffman coding for non-dyadic distribution

Huffman's algorithm solves the following problem. Given a distribution $P=(p_1,\ldots,p_n)$, find a prefix code $w_1,\ldots,w_n$ which minimizes the expected codeword length $$ \sum_{i=1}^n p_i |w_i|. $$
If $p_i = 2^{-\ell_i}$ then the optimal solution has $|w_i| = \ell_i$, and the resulting expected codeword length is exactly the entropy of $P$, but Huffman's algorithm works for any distribution.
If we call a distribution in which $p_i = 2^{-\ell_i}$ dyadic (there is no common term in the literature), then Huffman's algorithm "rounds" an arbitrary distribution $P$ into a dyadic distribution $Q$ which minimizes the Kullback–Leibler divergence $D(P\|Q)$.
We can get closer to the entropy of $P$ by encoding together groups of symbols. If you encode $m$-tuples of symbols together, then the expected codeword length per symbol (i.e., dividing the expression above by $m$) is at most $H(P) + 1/m$, and in particular, it tends to the entropy as $m \to \infty$. Shannon's source coding theorem shows that you cannot go below the entropy using any encoding scheme, so using Huffman coding in blocks is asymptotically optimal as the block size goes to infinity.


Path on an edge-colored DAG using exactly $k$ colors

Here is a reduction of CNF-SAT.

In a given CNF formula, assume we have variables $x_1, \dots, x_n$ and clauses $C_1, \dots, C_m$.

We construct a DAG with edge colors as follows.

We have $m$ colors, and each color corresponds to a clause.  In our DAG, we have vertices $v_0$, $v_1$, ..., $v_n$, and $v_0$ is the source and $v_n$ is the sink.  (There will be more vertices in our DAG.)

From $v_{i-1}$ to $v_{i}$, we have a pair of vertex-disjoint paths (you may think they are parallel), one for TRUE and one for FALSE corresponding to the assignment to $x_i$.  On the path for TRUE, we have edges with the colors corresponding to the clauses with $x_i$ appearing as positive literals.  On the path for FALSE, we have edges with the colors corresponding to the clauses with $x_i$ appearing as negative literals.

A path exists from $v_0$ to $v_n$ with $m$ colors if and only if the given formula is satisfiable.


Retrieving data from website - Parser vs AI

It depends what to use on what you are doing. I divide this problem in two categories.

1.Site without changing structure

Suppose, you are building a app which takes data from your national weather department site and normally which has same structure throughout decade. Here using AI for finding data is stupid thing. You should use conventional parsing technique here. and also your are getting data from number of sources but has fixed structure then you can go with this approach.

2.Site with changing structure

As per your example, I believe approach 1 is not so useful. because there are lots of site to parse and these site changes there structure periodically. So I believe using AI for parsing data from these sites is beneficial. I believe you used Optical Character Recognition. you will need similar functionality to your system. Your AI system first load page and see how it looks in browser (not code). Then finds appropriate fields from page using Named Entity Recognition from text which found using OCR

I think applying Named Entity Recognition to directly parsed code is sufficient to find different fields like item name, price, specifications, type etc


Prove multiple cell move instructions don't increase power of Turing Machines

A quick answer: the control of every TM is finite, so given a TM $M$, the jumps in its transition table are finite. Suppose that it has the following jump transition:

on state_x: if read symbol a -> write b, jump 3R, goto state_y

then you can simulate it using 3 single step transitions :

on state_x: if read symbol a  -> write b, move R, goto state_x2
on state_x2: if read symbol <anysymbol> -> write <anysymbol>, move R, goto state_x3
on state_x3: if read symbol <anysymbol> -> write <anysymbol>, move R, goto state_y

In general if $len$ is the length of the jump of a transition, you can simulate it adding $len-1$ new states to $M$ and the new states are used simply to move the head for $len-1$ more steps and finally enter the same target state of the original jump transition.

To be pedantic, you need to add additional states only for distinct triples (jump length, jump direction, target state). For example if a transition has (jump 5, right, and goto state z) the added single step states can be reused on every transition with the same value of jump  length, jump direction and target state.


Chinese postman problem, but criteria = visit each vetex at least once

Let $G$ be an edge-weighted graph. Create a new graph $G'$ in which the weight of the edge $(x,y)$ is the cost of the shortest path between $x$ and $y$ in $G$. The problem you are interested in is the traveling salesman problem (TSP) on $G'$.


I guess this optimality depends on how you define "the least replacement solution". I'm taking it to mean minimum insertions / deletions. If you prefer minimum number of swaps necessary, take a look at step 4.1 and 4.2 and you may be able to optimize it for such, though I don't show it here.

If it is ensured that no additional $x_k$ and its partial constraints will cause a cycle, then this becomes relatively easy. Consider a topological ordering $\{x_1, x_2, \ldots, x_i, \ldots, x_j, \ldots\}$ where $x_i$ and $x_j$ have no transitive relation. We now have five options for additional constraints to be added:

$x_k$ with no constraints: put $x_k$ anywhere in the ordering.
$x_k > x_i$: put $x_k$ anywhere after $x_i$ in the ordering.
$x_k < x_j$: put $x_k$ anywhere before $x_i$ in the ordering.
$x_i < x_k < x_j$: put $x_k$ anywhere in between $x_i$ and $x_j$ in the ordering.
$x_j < x_k < x_i$: this is the only case where we will need to rearrange existing nodes because $x_i$ and $x_j$ are out of order currently.

For case 5 we will first worry about the fact that we are transitively adding an edge $x_j < x_i$, then after re-ordering, this will resolve to case 4. Do the following:

Let $A_i$ be all elements reachable ("after") in the DFS starting at $x_i$ of the current partial ordering.
Let $B_j$ be all elements on any path from the root to $x_j$. This can be computed in linear time by doing a DFS on the reverse partial ordering, starting at $x_j$.
Note that if $x_j \in A_i$ then this violates our original assumption. If $x_i \in B_j$, this also violates our original assumption. So we know $x_j \not\in A_i$ and $x_i \not\in B_j$.
Greedily move all elements in $B_j$ before all elements in $A_i$. This can be done by doing one of the following which has minimum insertions:

Move all elements in $B_j$ that are after $x_i$ in the ordering, before $x_i$.
Move all elements in $A_i$ that are before $x_j$ in the ordering, after $x_j$.

You can show that the minimum of these two will be a lower bound for the number of insertions / moves necessary.

After you have separated $B_j$ into the first half of the order and $A_i$ into the second half, this case reduces to case 4 as described above. Overall this will take $O(n + m)$.


Can we convert an NFA to a regular expression of polynomial length?

Using the concept of star height, Gruber and Holzer showed in Finite Automata, Digraph Connectivity, and Regular Expression Size that there exists a constant $C>1$ and a sequence of languages $L_n$ over $\{0,1\}$ which can be accepted by DFAs having $n$ states, but for which every regular expression has length at least $C^n$.