Feedback Vertex Set with vertex partitions?

Your problem reduces to Feedback Vertex Set by turning every subset $V_i$ into a clique, and creating one additional vertex $v_i$ for each subset $V_i$ that is adjacent to all vertices in $V_i$. It might be easier to think in terms of the complement problem, Maximum Induced Forest.

Since $V_i\cup \{v_i\}$ is a clique, we can select at most two vertices from this set to be in our solution (to Maximum Induced Forest). We can assume $v_i$ is always in the solution, since if less than two vertices of $V_i$ are in the solution we can safely include $v_i$, and if exactly two vertices of $V_i$ are in the solution then $v_i$ is not, but we can swap one of these two vertices (from $V_i$) with $v_i$.

A solution to Maximum Induced Forest thus selects at most one vertex from each set $V_i$ such that the result is a acyclic, and these are exactly the vertices we should select in a solution to the original problem (from the sets $V_i$ from which no vertices are selected, we can just arbitrarily select a vertex, and this vertex will be in our feedback vertex set). Conversely, it is easy to see how a solution to the original problem corresponds to a Maximum Induced Forest/Feedback Vertex Set in the graph created in this reduction.

This gives you a $O(1.7548^{n+k})$-time algorithm. If you allow parallel edges you can (instead of creating this additional vertex $v_i$) double up the edges in every clique, which has the same effect (and may give a faster algorithm, if your algorithm for solving feedback vertex set allows for parallel edges).

The problem is $NP$-hard. We can reduce from Feedback Vertex Set. To decide whether a graph has a Feedback Vertex set of size at most $s$, we create $s$ cliques of size $n+1$. We can force that one vertex of this clique is always in the solution (by including it in a singleton set $V_i$). We then create for each vertex $v$ in the original graph a set $V_i$ that contains $v$, and one vertex from each of the $s$ cliques. In at most $s$ of these sets $V_i$, we can select a vertex from each clique, but in the remaining $n-s$ sets we must select a vertex from the original graph. Therefore, we can find a solution to the original problem with feedback vertex set number $0$ if and only if the input graph had feedback vertex set number of at most $s$.


What can be said about the Fourier expansion of compositions of Boolean functions, if anything?

If $f,g$ are two $\pm1$-valued functions and $f \lor g$ is their maximum (this is the standard notation for maximum; $\land$ stands for minimum), then
$$
f \lor g = \frac{1 + f + g - fg}{2}.
$$
Since $\chi_S \chi_T = \chi_{S \Delta T}$, this shows that
$$
\chi_S \lor \chi_T = \frac{1}{2} + \frac{\chi_S}{2} + \frac{\chi_T}{2} - \frac{\chi_{S\Delta T}}{2}.
$$
You can read the Fourier expansion from this (unless $S = T$, in which case $\chi_S \lor \chi_S = \chi_S$).


can every LR(k) grammer be transformed to LR(1)

Remember that the point of parsing (in almost all practical applications) is not simply to recognize whether or not a sentence is in a language, but rather to find the parse tree corresponding to the sentence in order to do further processing (such as compilation). Or, to put it another way, few people would purchase a "compiler" which took some input and whose output was limited to one of two sentences:

That input is a syntactically valid C program
That input is not a syntactically valid C program.

By a large, the desired product is an executable, not just an assurance that the program could be compiled if you had a compiler.

So, it is true that if there is an LR(k) grammar for a language, then there is also an LR(1) grammar. But it is not the same grammar (unless k is 1) and it will therefore not produce the same parse tree.

It is possible to mechanically transform the LR(k) grammar into an LR(1) grammar in a way that the original parse tree can be recovered, but it is not a procedure you want to try by hand. (Trust me on this.)

So if you have an LR(k) grammar and you want to build a parser, you could:

Find an LR(k) parser generator
Find a program which mechanically tranforms an LR(k) grammar into the corresponding LR(1) grammar and the code necessary to transform a parse tree produced by the LR(1) grammar into the corresponding parse tree which would have been produced by an LR(k) parse. Then feed the LR(1) grammar into an LR(1) parser generator and add the parse tree recovery code to the semantic actions.

These two tasks are not particularly different. The mechanical transformation of an LR(k) grammar into an LR(1) grammar blows up the size of the grammar much in the way that the LR(k) parse tables are much larger than the LR(1) parse tables. From a practical viewpoint, it is roughly equally difficult to find an LR(k) parser generator as it is to find an automatic LR(k)→LR(1) transformer.


Connection between probabilistic algorithm and distributional algorithm

The first notion (probabilistic algorithms who are correct with high probability for all inputs) is indeed stronger. Distributional complexity relates to randomized (worst case) complexity via Yao's principle, which states that the worst case expected running time of any randomized algorithm, is no better than the expected running time of the best deterministic algorithm for any input distribution.

You can find an exact formulation in this cstheory question, where both the Las Vegas (the randomized algorithm should always output the correct answer) and the Monte Carlo case (similar to your formulation) are mentioned.

As for your question, it is not true that an algorithm which outputs the correct answer with high probability when the input is drawn according to the uniform distribution, returns the correct answer with high probability for all inputs. Consider an algorithm which answers correctly for all inputs not of the form $0^n$. For an input drawn from the uniform distribution, the probability of getting a correct answer is $1-2^{-n}$, however for inputs of the form $0^n$ you never get the correct answer.


Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$

Here is a hint. Let $w\in B$ if $w\not\in A_w$ and let $w\not\in B$ if $w\in A_w$.


Why shuffling by picking random position in all array instead of a part is not correct

Suppose that the array has length $n$. Since you are making $n$ random choices of numbers from 1 to $n$, the probability to obtain any specific permutation is of the form $A/n^n$, for some integer $A$. Therefore your algorithm could work only if $n^n/n!$ is an integer, which is only the case when $n \leq 2$.

More concretely, if you shuffle the array $1,2,3$, then you get the following results:
$$
\begin{array}{c|c}
\text{array} & \text{probability} \\\hline
1,2,3 & 4/27 \\
1,3,2 & 5/27 \\
2,1,3 & 5/27 \\
2,3,1 & 5/27 \\
3,1,2 & 4/27 \\
3,2,1 & 4/27
\end{array}
$$


If $f(n) = O(A(n))$ and $g(n) = O(B(n))$ then $f(n) + g(n) = O(A(n) + B(n)) = O(\max(A(n),B(n))$. These are standard properties of big O, which follow almost directly from the definitions.


Why is the Turing Machine a popular model of computation?

Well, a DFA is just a Turing machine that's only allowed to move to the right and that must accept or reject as soon as it runs out of input characters. So I'm not sure one can really say that a DFA is natural but a Turing machine isn't.

Critique of the question aside, remember that Turing was working before computers existed. As such, he wasn't trying to codify what electronic computers do but, rather, computation in general. My parents have a dictionary from the 1930s that defines computer as "someone who computes" and this is basically where Turing was coming from: for him, at that time, computation was about slide rules, log tables, pencils and pieces of paper.  In that mind-set, rewriting symbols on a paper tape doesn't seem like a bad abstraction.

OK, fine, you're saying (I hope!) but we're not in the 1930s any more so why do we still use this? Here, I don't think there's any one specific reason. The advantage of Turing machines is that they're reasonably simple and we're decently good at proving things about them. Although formally specifying a Turing machine program to do some particular task is very tedious, once you've done it a few times, you have a reasonable intuition about what they can do and you don't need to write the formal specifications any more. The model is also easily extended to include other natural features, such as random access to the tape.  So they're a pretty useful model that we understand well and we also have a pretty good understanding of how they relate to actual computers.

One could use other models but one would then have to do a huge amount of translation between results for the new model and the vast body of existing work on what Turing machines can do. Nobody has come up with a replacement for Turing machines that have had big enough advantages to make that look like a good idea.


Average Case Analysis for finding max and min value on an array

First, note that the first comparison will always compare $n-1$ times, independent of the distribution of the input. So, what you really want to know is how many times the second part of the if compares. For this, you can use a indicator random variable like this:

$$
X_i =
     \begin{cases}
       \text{1, if A[i] $\le$ $\max$}\\
       \text{0, if A[i] $>$ $\max$}\\
     \end{cases}
$$

So, just like you did, assuming an uniform distribution for $A[1..n]$, the expected probability is:

$$E[x] = \sum\limits_{i=1}^{n} Pr(X_i)$$

But we do not want $Pr(i=\max)$, we want $\overline{Pr(i=\max)}$, like we stated before. So, using your probability of the $i-th$ element to be the $max$ element:

$$Pr(i = \max) = 1/i$$

We have this complement:

$$\overline{Pr(i=\max)} = (1 - 1/i)$$

From which we can put in the expected probability:

$$E[x] = \sum\limits_{i=2}^{n} (1 - 1/i) = \sum\limits_{i=2}^{n}1 - \sum\limits_{i=2}^{n}1/i = n - 1 - (\ln|n| - 1 + \Theta(1))$$

So, to get the total quantity of comparisons, we can just sum the number of comparisons of the two parts. Note that the $\Theta(1)$ can absorb a constant values.

$$(n - 1) + n - 1 - \ln|n| + 1 + \Theta(1) = 2n - 1 - \ln|n| + \Theta(1)$$

And we get the expected total number of comparions:

$$2n - \ln|n| + \Theta(1)$$


Few otherwise general-purpose languages bother to deeply integrate with (relational) databases. Most languages I've seen that do do some integration (though fairly shallowly) are bolt-on abominations. Links is quite a bit more principled, and I believe can actually more or less do what you want. It's a statically typed functional language whose goal was to collapse multi-tier web applications into one coherent (source) program.

In Haskell, a general-purpose, statically typed, purely functional language with no database integration, you can use the type class system and type inference to propagate information about the used fields back to the query site. The simplest approach to this will not actually know what columns are on the table, and so will lead to queries that may access columns that don't exist. Part of the reason I think Links can do what you want is that the type systems of Haskell and Links have some relation, and Phil Wadler, one of the primary designers of Links, is also the creator of type classes. (The mechanism is different though, using row types rather than type classes. Indeed, the approach in Haskell would be more like a poor man's row types.)

That said, it's not clear how desirable this actually is, especially when given a clean, modular syntax for making queries e.g. something like C#'s Linq. Using Linq is like your solution of passing in the list of required fields except you have the full flexibility of, at least, Linq's query syntax and so you aren't just slinging strings about and thus can't typo one of the fields. You're still required to change the query to return the appropriate fields, but often you do want some awareness and control over the query. (This is especially true if the code isn't validated against the schema and so typoing a field name can lead to non-existent column names in the query.)


Here is a simple implementation strategy.

Find all three-letter truncatable words.  Every three-letter word is truncatable, so this is a linear scan through the dictionary to find the three-letter words.  Store them in a hashtable.

Find all four-letter truncatable words.  You can check whether a four-letter word wxyz is truncatable by checking whether wxy is a truncatable word; the latter can be checked by looking it up in the previous hashtable.  So, this can be done with a linear scan through the dictionary.  Store all four-letter truncatable words in a hashtable.

Find all five-letter truncatable words, by a linear scan plus a lookup in the hashtable for four-letter truncatable words.  Note that given a word vwxyz, it suffices to check whether vwxy is truncatable (you don't need to check vwx).

Find all six-letter truncatable words.

And so on.  Finish when you've exhausted the length of words in the dictionary.


Is the set of non-deterministic Turing machines countable?

Why is the class of DTM countable? Because you can code every DTM as a string (the program) over some alphabet. Now you can sort these strings lexicographicaly. Then the function
$$f(i\in \mathbb{N}):=\text{the $i$th string in the sorted sequence of DTMs},$$
is a bijection between the natural numbers and the set of DTMs. Hence the set of DTMs is countable.

Now here is the point. You can argue the same for NTMs. Hence the set of DTMs and NTMs are both countable and therefore equinumerous.


How do I tell if a comparison network sorts?

In general, verifying whether a particular comparison network is indeed a correct sorting network is a Co-NP complete problem. If you want to check by testing, then you need to try exponentially many tests.
In particular, there exist sorting networks that sort all but a single value correctly, so you can't hope to test whether the network is correct or not simply by feeding it a few inputs.
One standard method is to test whether it correctly sorts all $2^n$ inputs that are composed solely of zeros and ones.  If it does, then it turns out that it will sort all inputs (even ones that aren't limited to zeros and ones).  However, this requires exponentially many tests.  Moreover, the number of tests cannot be reduced significantly: for zero-one inputs, it is possible to prove that at least $2^n-n-1$ tests are needed, in order to verify that the sorting network is correct.
Alternatively, one can use tests where the inputs are permutations of $1,2,\dots,n$.  This reduces the number of tests needed somewhat, but you still need exponentially many tests.  In particular, $C(n, \lfloor n/2 \rfloor)-1$ tests are necessary and sufficient.
For proofs of these facts, see the following papers:
On the Computational Complexity of Optimal Sorting Network Verification.  Ian Parberry.  Parle'91 Parallel Architectures and Languages Europe, 1991.
Bounds on the size of test sets for sorting and related networks.  Moon Jung Chung and B. Ravikumar.  Discrete Mathematics, vol 81, pp.1--9, April 1990.


Example of decidable set whose preimage is not decidable

Consider the set $S$ consisting of everything, and the partially computable function $f$ which on input $n$ simulates the $n$th Turing machine, returning whatever the machine outputs (if it ever halts!). The preimage of $S$ under $f$ is the set of all halting Turing machines, which isn't decidable.


Is the heap in "Data Structures Algorithms in Java" by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?

You have a tree made out of nodes at depths $0, 1, \ldots, h$ where $h$ is the height of the tree. The textbook is saying that the number of nodes at depths $0, \ldots, h - 1$ is equal to $2^h - 1$: notice the difference here between the $h-1$ and the $h$. This is easy to check by just looking at your picture, or using the formula for the sum of a geometric series:
$$ 2^0 + \cdots + 2^{h-1} = \frac{2^h - 1}{2 - 1} = 2^h - 1.$$
I think that a good rule of thumb for distinguishing between height and depth is that depth is the more useful one (the number of nodes on a complete level at depth $d$ is $2^d$, and a node's depth does not change as the tree grows), while the height $h$ is only really useful when looking at the tree as a whole (and is just the upper bound for depths).


Difference between a lambda term and a lambda expression

Books on lambda calculus define only lambda terms. Some programming languages may call anonymous function lambda expressions.


Regular expressions, is it always true that (r U s)* = r* U s* U (rs)*?

Consider the alphabet $\Sigma = \{a,b\}$, and the regular expressions $r = a$ and $s = b$. Then $(r+s)^* = \Sigma^*$ whereas $a^*+b^*$ and $a^*+b^*+(ab)^*$ are both smaller.


Number of combinations to put n items into 2 bags

You forgot the "1 outside" case.

[2][] 1 outside
[][2] 1 outside


I think it is $\sf{NP}$-complete: as noticed by Raphael, Hamiltonian cycle on grid graphs with holes problem is NP-complete (Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Paths in Grid Graphs. SIAM J. Comput. 11(4): 676-686 (1982)).

So given a grid graph $G$ with holes, you can easily build an equivalent Hidoku game where the initial fixed cells fill all the even diagonals; the empty odd diagonals form an undirected graph that is equivalent to the original grid graph $G$ and the Hidoku has a solution if and only if the original grid graph has an Hamiltonian path.

Figure 1: a grid graph with holes and the equivalent $12 \times 12$ Hidoku puzzle (blue cells represent the initial fixed numbered cells ($1$ is the first, $144$ is the last), white cells are the cells that the player must fill, purple line indicates the sequence of the initial fixed numbered cells).

Auxiliary (filled) lines can be added to the bottom or right side to make it a square.

Another example of reduction from a grid graph to an Hidoku puzzle: the 6x4 grid graph is embedded in a larger 13x13 grid; the even diagonals are filled with fixed numbers, and the remaining free cells are equivalent to the original grid graph.

The full picture with transformation can be downloaded here.

Some additional notes to complete the answer:

the problem is also known as Hidato; the board can have an arbitrary shape (but as a generalization of the square case, it remains NP-hard);
as correctly evidenced by Steven Stadnicki in his answer it is not obvious that the problem is in NP if the initial partially filled grid is not given as an $n \times n$ array of integers but is given in some succinct representation; however it is clearly in NP if the initial board is given using the reasonable list of integers representation;
I think that the original rules of the game  say that the solution should be unique; so the problem is in US (US-hard), and unlikely to be in NP.

In summary, if we drop the unique solution constraint and specify the initial board with a list of $n^2$ integers the game is $\sf{NP}$-complete.


First of all, let me correct the recursion for the running time of merge sort:
$$
T(n) = \begin{cases} T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta(n) & \text{if } n > 1, \\ \Theta(1) & \text{if } n = 1. \end{cases}
$$
The corresponding recursion for depth is:
$$
D(n) = \begin{cases} \max(D(\lfloor n/2 \rfloor), D(\lceil n/2 \rceil)) + 1 & \text{if } n > 1, \\ 0 & \text{if } n = 1. \end{cases}
$$
(The value of $D(1)$ could also be $1$, depending on how you define depth.)

The solution of this recurrence is $D(n) =\lceil \log_2 n \rceil$.

When $n$ is a power of 2, you can calculate the depth of the recursion tree by noticing that the value of $n$ decreases by a factor of 2 at each level. For the general case, the main observation is that the depth is monotone in $n$, using which you can easily conclude $D(n) \leq \lceil \log_2 n \rceil$ by considering the smallest power of 2 which is at least $n$.


You can build a graph from this by identifying a name for each vertex, and then identifying for each edge the names of the start vertex and end vertex for that edge.

I suggest you name a vertex by the set of edges that are entering that vertex.  For instance, the name for vertex $x_5$ in your picture would be "$a_4,a_5,a_6$" if we assume that $a_4,a_5,a_6$ are the names of the three edges that go to $x_5$ -- and similarly.  (If you like, you can use the SHA256 hash of the list of edges as the name of the vertex, instead of using the list itself as the name -- that will make the names shorter but won't change anything).

Given your table, we can easily identify the set of all vertex names.  Then, for each edge $e$, you can identify the name of its start vertex (by looking at the list of direct predecessor edges of $e$) and the name of its end vertex (by looking at any successor edge $e'$ of $e$, i.e., any edge $e'$ such that $e$ is a direct predecessor of $e'$, and then finding the name of the start vertex of $e'$).

This gives you a description of the graph as a set of edges, where each edge is represented by the name of its start vertex and the name of its end vertex.  From this, you can easily construct an adjacency list representation of the graph.  This then gives you the output you were seeking.


Is the language of words having same number of a's and b's context-free?

This language L = { w | w has equal number of as and bs and w≠ ε (since you put a +)  } is a CFL
A PDA would work as follows :
On reading a :
If the stack is empty or the top of the stack is a push a
If the top of stack is b pop b push nothing
On reading b :
If the stack is empty or the top of the stack is b push b
If the top of stack is a pop a push nothing
At the end of input if stack is empty accept else reject


$n^{\log_6 8} = n^c$ for some $c>1$ (you can tell that $\log_6 8 > 1$ from the fact that $8>6$). Then $n^c = \omega(n \log n)$.
Indeed:
$$\lim_{n \to +\infty} \frac{n^c}{n \log n} = \lim_{n \to +\infty} \frac{n^{c-1}}{\log n} = \lim_{n \to +\infty} \frac{(c-1)n^{c-2}}{1/n} = \lim_{n \to +\infty} (c-1)n^{c-1} = +\infty.$$


Checking whether the win-loss standings of a league are possible

This can be modelled as a Max-Flow problem.

As a preprocessing step, make sure that the number of games is equal to the sum of the number of wins (if not, you know something is wrong).

Let $G$ be a set of vertices corresponding to the games played, and $P$ a set of vertices corresponding to the players. Let $s$ and $t$ denote two additional vertices (source and sink).

Now for every game $g\in G$ played between $p1\in P$ and $p2\in P$, add an edge from $s$ to $g$ with capacity $1$ and edges from $g$ to $p1$ and $g$ to $p2$ also with capacity $1$. This models the fact that the game can give one point to either player.

Then for every player $p\in P$ add an edge from $p$ to $t$ with capacity equal to the reported number of wins for player $p$. This models the fact that this player should win at most this number of games.

It is easy to see from here that if the reported scores are possible, there will be a saturating flow from $s$ to $t$ and reciprocally. So all you need to check is if the maximum $s,t$-flow in this graph is equal to the number of games played.

Alternatively, you could also have a graph with one vertex per game and a number of vertices for each player corresponding to the number of wins, connect them the same way as before, and look if the number of edges in a maximum matching is equal to the number of games (but this is almost the same thing really).


Can we count the number of times a particular state in a DFA is running in a loop?

First of all, let me mention that the definition of DFA is final. The definition specifies everything that counts as a DFA. If you modify the model, it is no longer a DFA. However, your question makes sense if we interpret it as trying to change the model while keeping the class of languages accepted by the model.

There are several ways to interpret counting. If you could keep track of the number of loops through a state and then still remember it when you exit the state, then (depending on your exact rules) you could accept the language $a^n b^n$. So any mechanism that allows this is ruled out.

Another interpretation is that the state keeps a loop counter $C$, and it can base its decisions on the value of $C$ (that is, allow the transition function to depend on the auxiliary information $C$). This is also too powerful – you can accept every unary language (i.e., a language over $\{0\}$) using this mechanism.

What if we just allow the state to remember some information about $L$? Say that we partition $\mathbb{N}$ (the natural numbers) into finitely many sets $S_1,\ldots,S_d$, and we want to allow our transitions to depend also on which class $C$ lies in (here it doesn't really matter whether we are counting how many times we were at a state overall, or in the current run).

Let's do the case $d=2$ first. We can think of this as defining a unary language $L$ (which we identify with a subset of $\mathbb{N}$), and allowing transitions to depend on whether $C \in L$ or not. In this case, the resulting automaton model (for some fixed $L$) remains equivalent to DFAs precisely if $L$ is regular (exercise).

The general case is similar, and left to the interested reader.


Sudoku Puzzles in O log n time although inefficient

Such an algorithm can solve Sudoku, but it will be very slow in practice.

By definition, Sudoku is on a 9x9 grid, so there are only a fixed (finite) number of possible puzzles.  Your algorithm encodes all of them.  Therefore, your algorithm takes constant time, i.e., $O(1)$ time.

What this is telling you is that asymptotic analysis is not a useful tool for analyzing the running time of a Sudoku solver, as asymptotic running time focuses on how the running time grows as you increase the size of the input.  With Sudoku, you can't increase the size of the input; the size of the input is fixed.  Thus it doesn't even make sense to talk about asymptotic running time for solving Sudoku puzzles.

Some people do analyze a generalization of Sudoku, where instead of a 9x9 grid, we have a $k^2 \times k^2$ grid, where $k$ can be any integer.  Then one can consider asymptotic running time.  However, your algorithm can't be applied to this generalization of Sudoku, as there are infinitely many puzzles for this generalization, so you can't hardcode them all in the code of your algorithm -- every algorithm must be of finite length.  Thus, in that setting, while asymptotic analysis does apply, your algorithmic approach no longer works.


Runtime of sorting a partially-sorted array

Your argument is not correct: Even if the subarrays a[0] to a [k-1], a [k] to a [2k-1] and so on are sorted, that doesn't make the whole array sorted. For example if k = 3 you could have [1, 2, 10000, 3, 4, 10001, 10002, 10003, 10004] and there's still a lot of sorting to be done.

You basically have k sorted sequences of length about n/k, so you have k sequences to merge, which you should be able to do in O (n log k).


Bit complexity of O(1) time range query in a $k$-ary array

You can save a lot more on memory if you just allow logarithmic time complexity. You can implement a kD segment tree that will need N * 2^k bits memory, and runs in logarithmic time complexity for both subtasks, and linear time complexity for building the tree.

If you strictly want O(1), precompute everything.


Complexity of divide and conquer algorithm with a quadratic merge function

Let $S(n) = T(n)/n^2$. Then
$$
S(n) = \frac{T(n)}{n^2} = \frac{2T(n/2)}{n^2} + 1 = \frac{2(n/2)^2S(n/2)}{n^2} + 1 = \frac{S(n/2)}{2} + 1.
$$
Assuming a base case of $S(1) = 2$ and that $n$ is a power of $2$, one can prove by induction that $S(n) = 2$. Indeed, this holds for $n = 1$, and if it holds for $n/2$, then $$S(n) = S(n/2)/2 + 1 = 2/2 + 1 = 2.$$
We conclude that if $T(1) = 2$ and $n$ is a power of $2$ then $T(n) = 2n^2$.

What happened here? First we had one call to a routine that takes time $n^2$. Then we had two calls to a routine that takes time $(n/2)^2 = n^2/4$, taking a total time of $n^2/2$. Then we had four calls to a routine that takes time $(n/4)^2 = n^2/16$, taking a total time of $n^2/4$. And so on. The amount of work at each level decreases exponentially, and so the total amount of work stays $O(n^2)$ although there are $\log n$ different levels.

If we replaced $2T(n/2)$ by $aT(n/b)$, then the behavior of the recurrence would depend on the relation between $\log_b a$ and $2$. This is covered by the well-known master theorem.


Calculating execution time for recursive algorithm

I'm assuming that the one if statement is not supposed to be on the same line as the comment... if that is intentional it does change things up somewhat :)

int search(int a[], int l, int r, int x) {
1.    int m = (l+r)>>1;
2.    if (l > r) return -1; // not found
3.    if (a[m] == x) return m;
4.    if (a[m] > x) return search(a, l, m-1, x);
5.    return search(a, m+1, r, x);
}

I am also assuming T(n) means you are looking for the worst-case scenario (eg. the number you are searching for was the last one you checked, or was not found at all). The most straight forward way of solving these is to simply trace it through line by line, keeping track of the values of the variables in a table, until you notice a pattern emerge. Now, note that finding a pattern by itself never proves that the pattern you found is actually correct, but it will give you a good place to start, and will frequently (but not always) even yield the correct solution to the problem.

So, that being said, here's the gist of how I traced through it, minus a table with variable values like r/2, r/4, etc.

m is being set to halfway between l and r in line 1 (I suppose doing it with a bitshift is more efficient...)
The worst case would definitely involve running the search again. However, you can tell that this time either r is going to be halfway closer to l (line 4) or l is going to be halfway to r (line 5)
m is being set to halfway between l and r again, and so on, until m cannot be cut in half anymore (this will occur in line 2 where l > r)

m keeps getting cut in half again and again until it cannot get cut in half. This pattern implies that maybe (probably) T(n) = O(log2 n). If you need to prove its correctness you would need to do a more formal direct proof than a trace. You could use Master's Theorem to prove its correctness as well.

If you are going to be doing a lot of these or if you need to prove the correctness of these it may be worth your time to look up how Master Theorem works, as getting your mind around that will make these a lot easier.


When $k,s$ are upper-bounded by a constant, the problem can be solved in polynomial time.

Call a multiset $T$ good if its sum is at least $s$, and if removing any one element causes the sum to fall strictly below $s$, and if all elements are in the set $\{1,2,\dots,k-1\}$.  How many good multisets are there?  Well, since $k$ and $s$ are constants, the number of such multisets is also a constant.  (A very crude upper bound is $k^s$, which is a constant.)

Let's write down an integer linear program that is equivalent to your problem.  We'll have an integer variable $x_T$ for each good multiset $M$, constrained so that $x_T \ge 0$.  The idea is that $x_T$ will count the number of times $T$ appears in the partition that constitutes the solution to your problem.  We obtain $k-1$ linear equations of the form

$$\sum_T m_T(i) x_T = m_S(i)$$

for each $i \in \{1,2,\dots,k-1\}$, where $m_T(i)$ denotes the multiplicity of $i$ in $T$.  Now our goal is to maximize $\sum_T x_T$, the number of multisets in the resulting partition.

Thus, we obtain an integer linear program in constant dimension: i.e., it has (at most) a constant number of variables and (at most) a constant number of linear inequalities.  It is known that integer linear programming in constant dimension can solved in polynomial time.  Therefore, your problem can be solved in polynomial time, too.

Of course, this doesn't necessarily mean the algorithm will be efficient in practice.  The constants that are hidden by asymptotic analysis are potentially huge.

As a side note, if $k,s$ are part of the input (not fixed) and all integers are provided in binary, the problem is NP-hard.  The special case where $s = \frac12 \sum_{i \in S} i$ is equivalent to the partition problem, which is NP-complete so your problem is NP-hard as well, assuming $k$ is part of the input.  So your promise that $k,s$ are upper-bounded by a constant makes a crucial difference to the complexity of your problem.


Why there is no direct connection between the data bus and the accumulater register

The answer as in many cases: Someone thought it was a good idea.

Someone may have evaluated cost and benefits and may have decided that the benefits were not worth the cost.


Given a tournament with $2^n$ vertices, show that there is a sub-tournament with at least $n + 1$ vertices that is acyclic

A tournament is a loop-free directed graph $G=(V,E)$ in which, for each pair of distinct vertices $u,v \in V$, exactly one of $(u,v)$ and $(v,u)$ is in $E$.

The proof of your claim is by induction.

For $n=0$ the claim is true since a tournament $G$ with $2^0=1$ vertices is trivially acyclic, and its only sub-tournament with $0+1=1$ vertices is $G$ itself.

Assume now that the claim holds up to some $n \ge 0$ and consider a tournament $G=(V,E)$ with $|V|=2^{n+1}$. Pick an arbitrary vertex $v \in V$, and partition the vertices of $V \setminus \{ v \}$ into two sets $L = \{ u \in V \setminus \{ v \} \mid (u,v) \in E \}$ and  $ R =\{ u \in V \setminus \{ v \} \mid (v,u) \in E \}$.
One of $L$ and $R$ must contain at least $\left\lceil \frac{|V \setminus \{v\}|}{2} \right\rceil = \left\lceil \frac{2^{n+1} - 1}{2} \right\rceil=2^n$ vertices. Arbitrarily select $2^n$ vertices from this set, and call the set of the selected vertices $S$.
By inductive hypothesis $S$ contains an acyclic sub-tournament $S'$ of size $n+1$, and since either $S' \subseteq S \subseteq L$ or $S' \subseteq S \subseteq R$, we have that $S' \cup \{v \}$ is also acyclic. This proves the claim since $|S' \cup \{v \}| = |S'| + 1 = n+2$.


Minimal DFA that accepts binary strings whose decimal equivalent is divisible by 32

Binary numbers that are divisible by 32 are ending in zero's. You can just keep track of how many consecutive zero's we have seen. If you want to answer the same question for the decimal alphabet, yes, then you need to worry about remainders modulo 32. The phrase "decimal equivalent" is a bit confusing here: divisibility of a number does not change when choosing another representation.

After building the automaton you can minimize it using standard constructions, to see if you cannot do with less states. Perhaps the same approach works for $2^n$, but then you not have a single "concrete" automaton. Alternatively you might use the theory of Myhill-Nerode equivalence classes of the language, to show the number of states is at least a certain number.


No, it is not necessary to remember all $y$'s tried before. In order to remember that I've tried the numbers $1,2,\ldots,200$, I do not need to remember $3,4,5,6,\ldots,199$. If you try them in order, just remembering the last one is enough.


You should read more precisely the definition of amortized analysis. As we have $X$ operations here, the time complexity of these operations should be divided by the number of operations to find the amortized complexity of the algorithm. Hence, $\frac{O(2X)}{X}$ is the amortized complexity of the insertion algorithm which is $O(1)$.


Here is how to draw the suffix tree for the example $abaab\$$ mentioned in the lecture notes appearing in greybeard's comment.

Root. There are two characters appearing in the word, $a,b$, so the root has two outgoing edges, labeled $a$ and $b$.

Root->a. Following $a$, we have both characters $a,b$ appearing in the word. So this note has two outgoing edges, labeled $a$ and $b$.

Root->a->a. There is only one suffix $aab\$$ starting with $aa$, so we replace this node with a leaf, and modify the edge label to $ab\$$.

Root->a->b. There are two suffixes $abaab\$$ and $ab\$$ starting with $ab$. Correspondingly, we add two children with edges labeled $aab\$$ and $\$$.

Root->b. Following $b$ we have the two suffixes $baab\$$ and $b\$$. Correspondingly, we add two children with edges labeled $aab\$$ and $\$$.

The general method is similar. At each node $w$, we add children corresponding to all possible continuations of $w$ in the word. If there is only one continuation possible, we modify instead the edge label. This algorithm is easy to implement by hand, but could be hard to implement in linear time on a computer.


We first need to clarify what we mean by "does this hold if we have an infinite chain?".
We interpret it as an infinite sequence of functions $\{f_i:\mathbb{N}\to\mathbb{N} \mid 1\leq i\}$ such that for all $i$ we have $f_i(n) = O(f_{i+1}(n))$. Such a sequence might not have a last function.

We can look at the limit of the functions in the sequence, i.e. $f_\infty(n) = \lim_{i\to \infty} f_i(n)$. However it is possible that the limit does not exists. And even in the case that it exists we might not have $f_1(n) = O(f_\infty(n))$. For example consider the sequence of functions $f_i(n) = \frac{n}{i}$.
For each $i$,
$f_i(n)=\Theta(n)$ and therefore $f_i(n) = O(f_{i+1}(n))$.
However $f_\infty(n)=\lim_{i\to\infty}f_i(n)=0=\Theta(1)$
thus $f_1(n) \neq O(f_\infty(n))$.

On the other hand we can look at the limit of the sequence of the classes which doesn't need to be equal to the class of the limit of the functions.
We have $f_i \in \mathcal O(f_{i+1})$, therefore $\mathcal O(f_i) \subseteq \mathcal O(f_{i+1})$ and $f_j \in \lim_{i\rightarrow\infty} \mathcal O(f_i) = \limsup_{i\rightarrow\infty} \mathcal O(f_i) = \liminf_{i\rightarrow\infty} \mathcal O(f_i) = \bigcup_{n \in \mathbb{N}}\bigcap_{k>n}\mathcal O(f_k)$ for all $j$. The limit superior contains all elements (functions in this case) which occur infinitely often and the limit inferior contains all elements which occur in all $\mathcal O(f_i), i \ge n_0$ for some $n_0$ (which may depend on the element). Since the sequence of classes is monotonically increasing both exist and they are equal. This justifies the usage of $\lim$.


Mimimum spanning tree with a constraint on number of certain types of edges

Let us take Kruskal's algorithm for an example. Apparently, OP refers to the adjusted version such that when we choose among edges of equal weight, we will pick the ones in $A$ before the ones in $B$ as long as at least one edge in $A$ is left available. If the MST we arrive in the end has no more than $c$ edges in $B$, then that MST is the output. Otherwise, the output is empty, indicating no such MST has been found. Let us name this algorithm $A$-favoured Kruskal's algorithm.

To prove that $A$-favoured Kruskal's algorithm will find a satisfying MST whenever there is one is, in fact, not trivial even if we have been enlightened with or especially when we are distracted by the  general techniques on how to prove greedy algorithm is correct.

Here goes my proof. Let us fix the weighted graph $G$ so that we will often be referring to $G$ implicitly. Let $R$ be a particular run of Kruskal's algorithm that produces $m$, an MST. Let $RA$ be a particular run of $A$-favoured Kruskal's algorithm that produce $ma$, another MST. ($RA$ may or may not be the same as $A$ and $ma$ may or may not be the same as $m$). Suppose $w_1\lt w_2\lt\cdots$ is the increasing sequence of all distinct edge weights. Break up the while loop of $R$ into smaller loops $R_1\lt R_2\lt\cdots$. For each $i$, $R_i$ iterates over all edges of weight $w_i$. For each such edge, $R_i$ adds it to the growing forest if it connects two different trees and ignores it otherwise. Let $F_i$ be the forest obtained at the end of $R_i$. Let $E_0=G$. For $i\gt0$, let graph $E_i$ has the same vertices as $G$  and all edges of $G$ except the edges of weights greater than $w_i$.

Using induction on $i > 0$, we can see that each connected component of $F_i$ (, which is a tree) is its corresponding connected component of $E_i$ minus some edges (the edges that were discarded because they did not connect different connected components(trees)). Let $g_i$ be the number of edges in $A$ of weight $w_i$ that are selected into $m$ during $R_i$. We can see that $g_i$ cannot bigger than $h_i$, the largest number of edges in $A$ of weight $w_i$ that can be added to $H_{i-1}$ without causing a cycle. In fact, $h_i$ is the decrease from the number of connected components in $E_{i-1}$ to the number of connected components in $E_{i-1}$ with all edges in $A$ of weight $w_i$ added. So $h_i$ depends only on $G$, $A$ and $i$. Note that $g_i$ will be $h_i$ if $R$ is actually a run of $A$-favoured Kruskal's algorithm, such as $RA$. So
$$\#\{\text{edges in } A \text{ and } m\} = \sum_{i}g_i
\leq \sum_{i}h_i = \#\{\text{edges in } A \text{ and } ma\}$$

Note that all MSTs can be found by Kruskal's algorithm. For a proof, you can check any MST is reachable by any MST algorithm with some minor exceptions. So we have shown that of all MSTs, $ma$ has the most edges in $A$. Since the number of edges in $ma$ is the same, $ma$ has the least edges in $B$. Proof is completed.

Indeed, we have proved more. Any run of $A$-favoured Kruskal's algorithm will produce an MST with the same number of edges with any given weight in $A$ and in $B$.


Efficiently compute parallel matrix-vector product for block vectors?

You can do this as a parallel sum. You want to compute

$$w_i = \sum_{j=1}^P e_{ij} v_j,$$

where processor $j$ has the vector $v_j$.

One way to do this is to have each processor compute $e_{ij} v_j$ locally.  Then, use a binary tree to compute the sum.  In particular, processor 1 sends $e_{i1} v_1$ to processor 2, which computes the sum $e_{i1} v_1 + e_{i2} v_2$; processor 3 sends $e_{i3} v_3$ to processor 4, which computes the sum $e_{i3} v_3 + e_{i4} v_4$; and so on.  Then, processor 2 sends $e_{i1} v_1 + e_{i2} v_2$ to processor 4, which computes the sum $e_{i1} v_1 + e_{i2} v_2 + e_{i3} v_3 + e_{i4} v_4$; and so on.  Repeat until you have computed the final sum.  Basically, this is just parallel sum of some vectors (parallel aggregation).

This requires sending $\Theta(NP)$ data over the network, and $\Theta(\log P)$ rounds of communication.  Each processor only needs memory for $\Theta(N)$ data.  So, it looks like it meets all your requirements.  It may still be hard on the network, but that seems unavoidable given what you are trying to compute.  You'll do this $P$ times, to compute $w_1,\dots,w_P$, so in total it will require $\Theta(NP^2)$ data on the network, $\Theta(P \log P)$ rounds of communication (though they can be parallelized down to $\Theta(\log P)$ if the network is fast enough), and $\Theta(N)$ space on each processor.


Can a schedule with cyclic precedence graph still be serialisable?

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

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

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

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

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

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

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

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

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

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

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

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


Can a DPDA be created for a Language which includes the null string?

Yes, we can simply make the starting state an accept state. With no input (i.e. empty string) the machine halts immediately, and accepts.


Recursive language with non-recursive subsets

Hint. Take a very big recursive language over any alphabet you like. Verrrry big. Something so big it has all kinds of subsets.


In order to prove that your modified Turing machine is equivalent to a standard Turing machine, you need to do two things:

Given a standard Turing machine $T_1$, give a modified Turing machine $T_2$ such that $L(T_1) = L(T_2)$.
Given a modified Turing machine $T_3$, give a standard Turing machine $T_4$ such that $L(T_3) = L(T_4)$.

Good luck!


Given a function and its complexity, what is the complexity of its circuit?

There is no mapping from algorithmic complexity to circuit size. A counterexample: consider the language of strings of all ones, $1^n$, for only those $n$ such that the $n$-th Turing Machine rejects the string $1^n$ within $2^{2^n}$ time. Then this function requires $\Omega\left(2^{2^n}\right)$ time to compute on any machine, but the circuit for it only has size $O(n)$, because you can "hard-wire" the answer into the circuit, which then only checks that all the inputs are $1$.

D.W. provides a construction from an algorithm to a circuit. However, note that this gives only an upper bound, which is not necessarily tight. In particular, no function requires circuits of size larger than $O\left(\frac{2^n}{n}\right)$, because that is the size of a circuit which simply enumerates that function's truth table for inputs of size $n$.

Consequently, if an algorithm takes $O(2^{2^n})$ time, then you can use D.W.'s construction for a circuit of size $O(2^{2^n}\log(n)^2)$, but it is immediate that this bound is not tight; there is also a circuit of size $O(\frac{2^n}{n})$, and there may be a much smaller circuit for it, as in the example above. What we really want to know when we ask what is the size of this function's circuit is a lower bound: a minimum size for any circuit.

Circuit size lower bounds is a particularly enigmatic part of computational complexity about which very little is known. For example, we do not know whether or not SAT can be solved with $O(n)$-size circuits, and we have not ruled out that each problem in NEXP can be solved with polynomial-size circuits.


One technique is to start out with a context-free grammar, and apply an algorithm to get a corresponding PDA. Often, writing a grammar might be a bit easier than writing the PDA directly. In this case, it seems (to me) to be fairly easy to arrive at the grammar $S \rightarrow aaSbb \mid aab$, from which a PDA follows by construction (see this, for example, for some info on how to do such a conversion, if this is new to you)

If you want to build the PDA directly, another way to think about it is to start from the end of strings, and ask yourself what needs to be on the stack to make it easy to tell you need to accept the string. In your case, if you're looking at the last part of the string - say, you've started seeing $b$'s, what would it be really helpful to have on the stack? Well, the easiest thing would be to have $2n-1$ symbols on the stack. If we can arrange that, then when we get to $b$'s we can simply pop one symbol off the stack for every $b$ we read, and accept if the stack is empty when we're done with the input. How can we leave $2n-1$ symbols on the stack after reading $2n$ of the $a$ symbol? Well, we could put a symbol on the stack each time we read an $a$, and then, before we start reading $b$'s, remove one symbol from the stack. We get three phases to the computation: (1) read an even number of $a$'s and push a symbol onto the stack for each $a$ you read; (2) remove one symbol from the stack; (3) read $b$'s until the stack is empty and/or you run out of input. We'd get a PDA like this:

q    s    e    q'    s'
--   --   --   --    --
q0   Z    a    q1    aZ
q0   a    a    q1    aa
q0   a    -    q2    -
q1   a    a    q0    aa
q2   a    b    q2    -
q2   Z    -    q3    Z

We have start state q0 and accepting state q3. Entries of - in the e column indicate $\lambda$-transitions, whereas entries of - in s' indicate popping a symbol off the stack.


Why cannot we reduce the Emptiness problem of LBA to the Acceptance problem of LBA?

Since the acceptance problem for LBAs is decidable, if you could reduce th emptiness problem to the acceptance problem, then the emptiness problem for LBAs would be decidable. However, the emptiness problem for LBAs is not decidable. This shows that we cannot reduce the emptiness problem to the acceptance problem.

It seems that you are confused about the direction of the reduction. When reducing problem A to B, we show how to solve problem A using problem B, not the other way around.


Polynomial time algorithm - Matching pairs of vertices

The idea is to use recursion. Let us suppose that the children of the root $r$ are $v_1,\ldots,v_d$, and let $S_1,\ldots,S_d$ consist of those elements of $S$ in the subtree rooted at $v_1,\ldots,v_d$, respectively.

One easy case is when $r \notin S$ and $|S_i|$ is even for all $i$. In this case, we can simply recurse on the subtrees. There are two complications that arise in the general case:

Some $|S_i|$ might be odd.
The root might belong to $S$.

The two complications are related, but let us tackle them one by one. Suppose first that $r \notin S$. If $|S_i|$ is odd for some $i$, then we would like to fix that. The only reasonable way is to add $v_i$ to $S_i$ if $v_i \notin S_i$, and to remove $v_i$ from $S_i$ is $v_i \in S_i$. We now solve the modified problem recursively, and have to somehow derive a solution for the original problem.

Let us introduce some notation: $O$ is the set of $i$ such that $|S_i|$ is odd, and $S'_i$ is the set $S_i$ after modification (adding or removing $v_i$). Consider a solution for the new instance. We will derive a solution for the original instance by pairing up the indices in $O$. Suppose that we chose to pair $i,j$, and consider the solutions for $S'_i,S'_j$. There are three cases to consider:

$v_i \in S_i$ and $v_j \in S_j$. In this case we add a path from $v_i$ to $v_j$ via $r$.
$v_i \notin S_i$ and $v_j \notin S_j$. In this case we add a path from $v_i$ to $v_j$ and "erase" $v_i,v_j$. That is, in the solution to the new problem, $v_i$ is connected to some $w_i$ in its subtree, and $v_j$ is connected to some $w_j$ in its subtree. We connect $w_i$ and $w_j$ via the path $w_i-v_i-r-v_j-w_j$.
$v_i \in S_i$ and $v_j \notin S_j$. In this case we add a path from $v_i$ to $v_j$ and "erase" $v_j$. That is, in the solution to the new problem, $v_j$ is connected to some $w_j$ in the subtree. We connect $v_i$ and $w_j$ via the path $v_i-r-v_j-w_j$.

When $r \in S$, we only have to modify the above strategy a little. We arbitrarily pair $r$ with some $i \in O$, and then proceed much as above. This time there are only two cases:

$v_i \in S_i$. In this case we simply connect $r$ and $v_i$.
$v_i \notin S_i$. In this case we add the edge between $r$ and $v_i$ and "erase" $v_i$. That is, in the solution to the new problem, $v_i$ is connected to some $w_i$ in its subtree. We connect $r$ and $w_i$ via the path $r-v_i-w_i$.


Algorithm to reconstruct sentence from shuffled string

This is NP-hard, so it's very unlikely there's a polynomial-time solution.  To see this, notice that any instance of the NP-hard problem Exact Cover can easily be encoded as an instance of your problem in such a way that there is a solution to this encoded instance if and only if there is a solution to the original Exact Cover instance.


Is an $\mathcal{O}(n\times \text{Number of clusters})$ clustering algorithm useful?

To answer your last question: In real problems, the number of clusters $c$ is usually much less than $n$.

To compare to other algorithms, the running time of a naive implementation of the standard $k$-means algorithm is $O(ncdt)$ (here your $c$ is often called $k$, so $c=k$, and $t$ is the number of iterations needed for $k$-means to converge; $t$ is often much smaller than $n$ and roughly a small constant, but certainly not always).  There are ways to speed it up further.  It tends to be very fast in practice.

For high-dimension spaces, such as you are working in, one can also apply various dimension-reduction techniques on all the values, and then do cluster the reduced-dimension values.  This sometimes gives additional performance improvements.

To answer your first question: We can't tell you whether your algorithm is useful if you don't show us the algorithm.  Sorry, but that question just isn't well-suited for this site.  Some questions aren't, no matter how much you'd love to know the answer.

Perhaps you'd like to ask a new question about what is the state of the art in clustering for Euclidean metrics, for some class of parameters and some distribution on the inputs.  Except... make sure you go do your research first.  There's a lot that has been written on the subject of clustering, so go read about standard clustering algorithms first, and then make sure to tell us what research you've done when you ask the new question.  (In fact, you probably should have done that for this question, too...)


A problem $A$ is NP-complete if and only if $A'$ is in NP?

This is false. Take $A'=\emptyset$: then we have $A'\in\mathrm{NP}$ but $A=\Sigma^*$ is not $\mathrm{NP}$-complete.

  If there is an NP-complete language $L$ whose complement is in NP, then the complement of any language in NP is in NP.

This follows from the following three facts, which you should attempt to prove yourself.

The complement of an $\text{NP}$-complete problem is $\text{co-NP}$-complete;
if any $\text{co-NP}$-complete problem is in a class $\mathcal{C}$ that is closed under polynomial-time reductions, then every $\text{co-NP}\subseteq\mathcal{C}$;
$\text{NP}$ is closed under polynomial-time reductions.


What's the purpose of Karger's algorithm?

Even in an unweighted graph, your suggested algorithm doesn't work:  take a graph of 6 vertices with triangle a, b, c, and triangle d, e, f, with an edge between c and d.  Vertices a, b, e, and f each have minimal degrees of 2, but cutting the graph between the two triangles gives a cut of 1.


(Finite Automata) Why the following is a NFA?

Here is a similar question:

Which of the following are rational numbers: $$ 1, \frac{2}{3}, \sqrt{2}. $$

The correct answer is that both $1$ and $\frac{2}{3}$ are rationals, despite the fact that $1$ is also an integer.
One thing which is confusing here is that none of the given examples are DFAs or NFAs. Rather, they are pictorial representations of automata. Most of these pictorial representations can be interpreted as NFAs, and some can also be interpreted as DFAs. There would be no ambiguity if the automata were given as tuples, since the transition function of a DFA has signature $Q \times \Sigma \to Q$, whereas the transition function of an NFA has signature $Q \times \Sigma \to 2^Q$.


Hindley-Milner system with let expansion

I think something somewhat trivial is happening here, that is if the let binding is not used, then you can let bind an ill-typed term, e.g. if:

$t =\ $let x = (if 3 then 4 else false) in 5

then $t^* =\ $ 5 which is well-typed in $\mathrm{HM}$, even though t is not. If every let-binding is used, though, then this pathology can't happen.


How To Show That B is Semi-Decidable Given A

A language is semi-decidable if there is a Turing machine that halts for all strings in the language, and doesn't halt for strings not in the language.

You are given that $A$ is semi-decidable. Therefore there is a Turing machine $M$ that halts on an input $x$ iff $x \in A$. Your goal is to construct another Turing machine $M'$ that halts on an input $x$ iff one of the prefixes of $x$ is in $A$. In other words, $M'$ should halt on $x$ iff $M$ halts on one of the prefixes of $x$.

You take it from here.


Compressed self-indexes such as the FM Index allow arbitrary substring searches in near entropy-compressed space.  These are essentially compressed suffix arrays or suffix trees, which have a lot of literature.

Basic substring search can be o(k) or o(k log n) in time for length k, depending on what data structures are chosen (different types of rank/select data structures).  There are a range of issues that arise depending on whether one wants simple boolean containment predicates, the offset of each occurrence, or more complicated suffix tree operations; the former can be done in less space and time than the latter.

There's also an entire book about searching and selective decompression of strings: "Compressed Data Structures for Strings: On Searching and Extracting Strings" by Rossano Venturini, published 2014 Springer Science & Business Media.


There are many ways to model polymorphism via domain theory, let me just describe one that is easy to understand, so you can think about it yourself. It's a "PER model".

Take any model of the untyped $\lambda$-calculus, for instance a domain $D$ such that $D \to D$ is a retract of $D$ (for instance, take $D$ such that $D \cong \mathbb{N}_\bot \times (D \to D))$. Let $\Lambda : D \to (D \to D)$ and $\Gamma : (D \to D) \to D$ be the retraction and the section, respectively.

We are going to interpret the types as partial equivalence relations (PER) on $D$. Recall that a PER is a relation which is symmetric and transitive, but it need not be reflexive. To each type $\tau$ we thus assign a PER $\sim_\tau$. Think of $x \sim_\tau x$ as "$x$ is an element of $\tau$" and $x \sim_\tau y$ as "$x$ and $y$ are equal as far as $\tau$ is concerned".

We can have some basic types (but need not), for instance if we make sure that $\mathbb{N}_\bot$ is a subdomain of $D$ via an embedding $\iota : \mathbb{N} \to D$ then we may define $\sim_\mathtt{nat}$ by
$$x \sim_\mathtt{nat} y \iff \exists n \in \mathbb{N} . x = \iota(n) = y.$$

Given PERs $\sim_\tau$ and $\sim_\sigma$, define the function space PER $\sim_{\tau \to \sigma}$ by
$$x \sim_{\tau \to \sigma} y \iff
  \forall z, w \in D . z \sim_\tau w \Rightarrow \Lambda(x)(z) \sim_\sigma \Lambda(y)(w)$$

The terms are interpreted as untyped $\lambda$-calculus terms as one would normally interpret them in $D$.

Here's the punchline. You may interpret polymorphism as intersection of PERs, that is:
$$x \sim_{\forall X. \tau(X)} y \iff
  \text{for all PERs $\approx$, $x \sim_{\tau(\approx)} y$}.
$$
We can caclulate the PER corresponding to $\forall X. X$: it is the intersection of all PERs, but that is going to be the empty PER. Calculating $\forall X . X \to X$ is an interesting exercise. Calculating $\forall X . X \to X \to X$ is a difficult exercise (which kept me busy for a week when I was a student of domain theory).

If we want recursion in our language then we need to account for fixed points. One possibility is to restrict PERs to those which contain $\bot_D$ and are closed under suprema of increasing chains. More precisely, take only those PERs $\approx$ for which

$\bot_D \approx \bot_D$, and
if $x_0 \leq x_1 \leq x_2 \leq \cdots$ and $y_0 \leq y_1 \leq y_2 \leq \cdots$ are increasing chains in $D$ such that $x_i \approx y_i$ for all $i$, then $\sup_i x_i \approx \sup_i y_i$.

We can now interpret $\mathtt{fix}_{\tau} : (\tau \to \tau) \to \tau$ by applying the Kanster-Tarski theorem about existence of fixed points, just like we do in ordinary domain theory. This time, $\forall X . X$ is not empty, as it contains precisely $\bot_D$.


Algorithm to find the mode in a unimodal array

Almost correct. Just a small correction. It should be

if A[mid] > a[mid+1]

If two consecutive elements are increasing then they are in the increasing portion of the array, so the mode is to the right. Hence the correction.


The extension of a code is itself a code

Cover and Thomas are using here the following definition of a code: given a domain $D$ and an alphabet $A$, a code is a mapping from $D$ to $A^*$. That is, a code assigns every element of $D$ a word over $A$. The extension of the code is a code from $D^*$ to $A^*$ defined by concatenation.

For example, let $D = \{a,b\}$ and $A = \{0,1\}$, and consider the code $C$ given by $C(a) = 0$, $C(b) = 00$. Its extension $C^*$ is a function from $\{a,b\}^*$ to $\{0,1\}^*$ obtained by replacing each $a$ by $0$ and each $b$ by $00$. For example, $C^*(ab) = C(a)C(b) = 000$. Since $C^*(ba) = C(b)C(a) = 000$ as well, the code $C^*$ is singular.

A code $C$ is uniquely decodable if there do not exist two sets of words $x_1\ldots x_n$ and $y_1\ldots y_m$ such that $C(x_1)\ldots C(x_n) = C(y_1)\ldots C(y_m)$. This is exactly the same as saying that $C^*$ is non-singular, since the condition is completely equivalent to $C^*(x_1\ldots x_n) = C^*(y_1\ldots y_n)$.


Processes don’t use real RAM addresses. If they did, virtual memory couldn’t possibly work.

If the data is actually in RAM, then the data of process A at A’s location 1000 is not the same and therefore not stored in the same place as the data of process B at B’s location 1000

So the mapping must change when we switch from process A to process B. Address 1000 must be mapped to different addresses in RAM or not in RAM at all.

And processes are not loaded into RAM, they are loaded into address space, that is a mapping between address space and RAM or virtual memory is set up. This allows having processes larger than RAM and allows switching between processes with large amounts of data quickly.


4-partition elements summation NP completeness

Let's say that the numbers $a_1,\ldots,a_n$ are non-negative, and sum to $A$. They induce a probability distribution on $\{1,\ldots,n\}$, in which the probability of $i$ is $a_i/A$.

Given a partition $S_1,S_2,S_3,S_4$, let $I$ be a random variable distributed as above, and let $X$ be the index of the set to which $I$ belongs (so $X \in \{1,2,3,4\}$).
Your condition then reads $$ H(X) \geq K, $$
where $H(\cdot)$ is the entropy function.

This suggests choosing $K = 2$, since we know that $H(X) = 2$ iff $\Pr[S_1] = \Pr[S_2] = \Pr[S_3] = \Pr[S_4]$.

We can now describe a reduction from PARTITION to your problem. Given an instance $b_1,\ldots,b_m$ of PARTITION, where $b_1,\ldots,b_m$ are non-negative integers summing to $B$, create an instance of your problem by adding two copies of $B/2$, and by taking $K=2$. The list $b_1,\ldots,b_m,B/2,B/2$ can be partitioned into four parts with equal sum (i.e., $H(X) \geq 2$) if $b_1,\ldots,b_m$ can be partitioned into two parts with equal sum.


Reducing a system of two boolean algebra assertions to a single one

No.  There is no such binary operation.

This is easy to prove with a counting argument.  Given a candidate binary operation $?$, count the number $n$ of boolean values $x,y$ such that $x?y$ is true.   Out of the 16 possible values for $a,b,c,d$, exactly $m=n^2+(4-n)^2$ of them will satisfy $a?c = b?d$.  The possible values for $m$ are $m \in \{16,10,8\}$.  However, there are only 4 possible values of $a,b,c,d$ such that $a=b$ and $c=d$, which is not in the set of possible values for $m$.

Or, you could do as David Clarke suggests and write a tiny program to enumerate all possibilities.  Frankly, you probably should have done that before asking in any case; that would have helped you ask a more specific question, such as "I know no such binary operation exists; can you give me any insight why not?".


Count pairs of nodes in a tree that are connected by a path whose labels have gcd 1

If there are a lot of large numbers on the edges I do not know, but if the number of different prime factors on the edges is limited there seems to be an efficient algorithm.

The approach is as in Longest path in an undirected tree with only one traversal.

Make the tree rooted, so you can work bottom up. In each node $v$ keep for each possible number $d$ the number of successor nodes in the tree that have a path up to $v$ with gcd $d$. If we move up in the tree we extend the paths of the children (taking into account the values on the edges) to the parent, and count the paths that connect two successors that run via the parent (if the ggd's are $1$).

Each node is visited only once, but there is quite some work between edges at each node.

Example.

At node $g$ we store $1$ incoming path with gcd $3\cdot 5$, and  $1$ incoming path with gcd $3\cdot 7$: $[3\cdot 5\to 1, 3\cdot 7 \to 1]$.
At node $h$ we store: $[5\to 1, 5^2\to 1, 7 \to 1]$.
At node $i$ we store: $[3\cdot 7\to 1, 5\to 1, 5\cdot 7 \to 1]$.

With this information we obtain zero paths via $g$ with gcd $1$, two paths via $h$ with gcd $1$, and one path via $i$ with gcd $1$.

We now move the path info upwards. One new path from $g$ to $j$ with gcd $3^2\cdot 7$, and we add the info from $g$ after performing the gcd with the last edge:  $[3\to 1, 3\cdot 7 \to 1, 3^2\cdot 7\to 1]$.
One new path from $h$ to $j$ with gcd $2\cdot 5$, and we add the info from $h$ after performing the gcd with the last edge:  $[5\to 2, 1 \to 1, 2\cdot 5\to 1]$.
One new path from $i$ to $j$ with gcd $3^2\cdot 5$, and we add the info from $h$ after performing the gcd with the last edge:  $[3\to 1, 5 \to 2, 3^2\cdot 5\to 1]$.

Altogether we store at $j$:  $[3\to 2, 3\cdot 7 \to 1, 3^2\cdot 7\to 1,5\to 4, 1 \to 1, 2\cdot 5\to 1, 3^2\cdot 5\to 1$. This info is bounded by the possible divisors of the edge labels.

We finally compute the `via' count at $j$ by considering the lists at pairs of children. Quite some work. All paths from $g$ and from $h$ have gcd $1$, so we count $3\cdot 4 = 12$. I count $6$ between $h$ and $i$, and $3$ between $g$ and $i$.


Context-free grammar for $ \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, l \geq \min(n,m)\}$

Let us start by noticing that $X \to a^+$, $Y \to b^+$, $Z \to c^+$. Furthermore, $A \to a^n X b^n$ and $B \to a^m Y c^m$. Therefore $S$ generates words of the following two forms:
$$
a^na^+b^nbc^+ \\
a^+a^mb^+c^mc
$$
You take it from here.


What is the name of this code transformation that uses associativity of addition?

According to LLVM it is called "Reassociate expressions" and uses the flag "-reassociate"
According to here:

-reassociate: Reassociate expressions
This pass reassociates commutative expressions in an order that is designed to promote better constant propagation, GCSE, LICM, PRE, etc.
For example: 4 + (x + 5) ⇒ x + (4 + 5)
In the implementation of this algorithm, constants are assigned rank = 0, function arguments are rank = 1, and other values are assigned ranks corresponding to the reverse post order traversal of current function (starting at 2), which effectively gives values in deep loops higher rank than values not in loops.


Classification training data, but regression prediction

This is still a binary classification task.  In the abstract, there are two ways to handle this:

Most classifiers can output a predicted class and a confidence score (which indicates how confident the classifier is in its prediction).  If you don't need a probability, you can use the confidence score.  If you want to turn it into a probability, you can use various calibration procedures to turn this into a probability in the range [0,1].
Some classifiers can output a probability directly.  Generative models in particular are good at this.  For instance, logistic regression outputs both a predicted class and a probability for the class.

If you construct a neural network with $k$ outputs, one per class, using a softmax output and train it to minimize the cross-entropy loss function, then you can interpret the output as a probability distribution on the classes (though beware that it might be biased or over-confident).  The softmax ensures the outputs are normalized to be in the range [0,1] and to sum to one.

In your case, you can try both approaches (two outputs with softmax; or a single output with a sigmoidal activation function).  The only way to know which will perform better is to try both, but personally, I'd lean towards using two outputs and softmax.


Disabeling interrupts to solve critical section issue on multiprocessor system

We are generally concerned about controlling concurrent access to kernel data structures.  User-level processes don't have access to kernel data structures, so they can't do any harm from user space.  The only risks are (1) if a user process does a syscall or causes a context switch to kernel mode, (2) if an interrupt arrives.  (1) could be guarded by explicitly checking for a lock, or by other methods.  (2) could be guarded by disabling interrupts, if you had a way to disable them on all cores.


Polylogarithm growth rate proof using Polynomial growth equation

Here is the starting point. For all real constants $a$ and $b$ such that $a > 1$,
$$\lim_{n\to\infty}\frac{n^b}{a^n} = 0\,.\tag{3.10}$$

Let $c=\log_2 a$, i.e, $a=2^c$. Since $a>1$, we have $c>0$. Equation (3.10) becomes
$$\lim_{n\to\infty}\frac{n^b}{a^n} = \lim_{n\to\infty}\frac{n^b}{2^{cn}}= 0\,.\tag{cs.1}$$

Let $m=2^n$, i.e, $n=\log_2 m$. Then equation (cs.1)
becomes
$$ \lim_{n\to\infty}\frac{n^b}{2^{cn}} = \lim_{m\to\infty}\frac{(\log_2 m)^b}{2^{c\log_2 m}} = \lim_{m\to\infty}\frac{(\log_2m)^b}{m^{c}}= 0\,.\tag{cs.2}$$

Note that equation (cs.2) is, after $m$ is renamed to $n$ and $c$ is renamed to $a$,
$$\lim_{n\to\infty}\frac{(\log_2 n)^b}{ n^a}=\lim_{n\to\infty}\frac{{\lg}^b n}{ n^a}=0\tag{cs.3}$$
where $a>0$.

What is done in CLRS is a shortened version of above transformations.

Be careful. $(\log_2n)^b={\lg}^bn\not=\log_2n^b=\log_2(n^b)$, where each of two equalities is just a change of notation. $\log_2 (b^n)$, which is equal to $n\log_2 b$, is a linear function of variable $n$ while $(\log_2 n)^b$ is a polylogarithm function of variable $n$.


To expand out my comment into an answer: the multiplicative form of Chernoff's bound says that if the expectation $X=\sum_{i=0}^n X_i$ for the sum of independent random binary variables is $\mu$, then the probability of straying 'too far' from that expectation goes as: $Pr(X\gt (1+\delta)\mu) \lt \left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu$.

Now, imagine a procedure where, given a string $\sigma$ to test, we run $n$ trials of our $BPP(0.90, 0.95)$ algorithm (for some $n$ to be chosen later) and accept iff at least $0.925n$ of those trials accept $\sigma$.  We can use Chernoff's bound to find the probability of failure in terms of $n$ as follows:

Let $X_i$ denote the outcome of the $i$th trial, and thus $X=\sum X_i$ the number of trials that succeed.  We can assume conservatively that our probability for false positives is $.9$; this means that if we make $n$ independent trials on a string $\sigma\notin L$, the expected number of successes is $\mu = E(X) = 0.9n$.  (Note that a false positive probability less than $.9$ will lead to an even lower expected value and thus to even tighter bounds on the estimates to come.)  Now, let's look at the probability that we have more than $0.925n$ false positives (i.e., that $X\gt 0.925n$).  We take $\delta = \left(\frac{0.925}{0.9}\right)-1 =\frac{1}{36}$; then  $\left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right) \approx.99961\lt \frac{2999}{3000}$ and so we have $Pr(X\gt 0.925n)\lt\left(\frac{2999}{3000}\right)^{0.9n}$.

From here it should be clear that by taking $n$ large enough we can reduce this probability to $\lt\frac{1}{3}$.  Thus, for this sufficiently large $n$, if we accept the string $\sigma$ only if the number of successful trials on $\sigma$ is greater than $.925n$, then our probability of accepting a string $\sigma\notin L$ drops below $\frac{1}{3}$.  Note that this $n$ is constant, not dependent on our problem size; since we're running our polynomial $BPP(0.9, 0.95)$ algorithm a constant number of times, the total running time of our new procedure is still polynomial.  A similar analysis going the other direction will show that the probability of a 'false negative' (that $X\lt.925n$ for a string that is in our language) will be bounded by $c^n$ for some $c$, and so again we can take $n$ large enough to bound the probability of a false negative by $\frac{1}{3}$ (or, in other words, to ensure at least $\frac{2}{3}$ probability of accepting on a string $\sigma\in L$).  This shows that $BPP(.9, .95)\subseteq BPP(\frac13, \frac23) \equiv BPP$, and Yuval's comment shows how to prove the reverse equivalence through a similar procedure.

Canonically, this is known as probability amplification and it's an immensely useful method for dealing with probabilistic classes.  The specific constants are less important, obviously, then the fact that Chernoff's bound lets us bound our 'false result' probabilities by some exponential function of the number of trials, so they can be made arbitrarily small with only a modest number of trials.


The first thing to recognize is that this is a permutation matrix where each row and column contains a single $1$ entry with the remaining entries being $0$.  This follows from the fact that $x$ and $y$ represent classical bit strings and $f$ is a classical boolean function.

Let's take the basic case where $x$ is from the space of $n$ bit strings, $y$ is a single bit, and $\mathcal{f}$ maps $\{0,1\}^n$ to $\{0,1\}$. The operation then functions on $n+1$ bits and is represented by a $2^{n+1} \times 2^{n+1}$ matrix. If you let the binary number $xy$ index the matrix columns, then for column $xy$ set row $x(f(x) \oplus y)$ to 1 and all other rows to 0.

Let's look at an example from Deutsch's algorithm. Let $x$ be from $\{0,1\}$ and $f$ be bit negation, i.e. $f(0) = 1$ and $f(1) = 0$.  From here we compute, for each row, the column number containing the 1.

$\begin{array}{cc}
\mbox{column} & \mbox{row with 1} \\
00 & 0(0 \oplus 1) = 01 \\
01 & 0(1 \oplus 1) = 00 \\
10 & 1(1 \oplus 1) = 10 \\
11 & 1(1 \oplus 0) = 11
\end{array} $

This gives us the matrix

$ \left( \begin{array}{cc}
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{array} \right) $

This generalizes to when $y$ is more than a single bit.


What does machine code actually look like while being run?

The best answer I can give is, it doesn't really "look" like anything. The instruction currently being executed by the CPU is represented by a series of wires, some of which have a high voltage, some of which have a low voltage.

You can interpret the high and low voltages as zeroes and ones, but you can equally well interpret groups of high and low voltages as hexadecimal digits, or as an assembly instruction like ADD $0 $1 (which is closest to how the CPU interprets it). These numbers and mnemonics themselves are conveniences for humans to read; internally, it's nothing but voltages on wires.

Out of these options, binary is "closest to the metal", in that the zeroes and ones map directly to the high and low voltages on the wires. But none of the others are incorrect, and they're frequently more useful: there's a reason people look at hex-dumps of executables, but almost never binary-dumps.


Solve Hamilton Circuit with Hamilton Path

Does a graph have a hamiltonian cycle if for anyone of its edges, it has a hamiltonian path after the removal of that edge?

Note that any hypohamiltonian graph must be such a graph. Is it even true that every hypohamiltonian graph has a hamiltonian cycle?

Not necessarily.

A counterexample is the Peterson graph, which is hypohamiltonian but not hamiltonian.


Find the fastest duration for a certain distance in a walk

I suggest you use exactly your algorithm, except use binary search during your binary search.  You will want to store the events in an array rather than a linked list, to allow efficient random access into it.  The total running time will be $O(n \log n)$, where $n$ is the number of events in your data structure.  That seems quite reasonable, and this should be quite efficient in practice.


By far the most important in that list is probability -- learn as much probability as you can.  Numerical analysis might also be of a little bit of use.  The others probably won't be directly relevant to most of the practice of machine learning, but hey, become more comfortable with mathematics is probably useful in general.


Alright, it was all in the diagram:

We need to copy the descendants of the nodes in the path to make sure we don't end up with a single node having two parents


Proving that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular

A unary language (i.e., a subset of $0^*$) $L$ is regular iff the set $S = \{ n : 0^n \in L \}$ is eventually periodic. In particular, if $L$ is regular then either $S$ is finite or $S$ has positive density (in the following strong sense: $|S \cap [n]|/n$ converges to a positive number). However, in your case the set $S$ is infinite yet has density zero.

In the same way, we get that the following languages are not regular:
$$
\{0^{\lfloor n\log n \rfloor} : n \in \mathbb N\},
\{0^{n^2} : n \in \mathbb N\},
\{0^{2^n} : n \in \mathbb N\},
\{0^{n!} : n \in \mathbb N\}
$$
and so on.


A language is recursive if a Turing Machine decides it: On input w, the TM always halts, and accepts if w is in the language, and rejects if w is not in the language.

So to show that the language is recursive, you just need to show that your Turing Machine gives the correct answer on every input string (accepts if # of a's equals # of b's, rejects otherwise). That will also show that it halts on all inputs, so you're done.

As Hendrik says in the comment, a Turing Machine should have both an accept state and a reject state. (That's what it means to accept/reject -- to enter the appropriate state.)

So first, you'll need to make this change.

Then, to prove your construction correct, you use the following type of proof. First, suppose I have a string $w$ that does have an equal number of a's and b's. Then I will show that, when I feed $w$ into my TM, it halts in the accept state. Second, suppose I have a string $x$ that does not have an equal number of a's and b's. Then I will show that, when I feed $x$ into my TM, it halts in the reject state.

You should convince yourself that this proof accomplishes what I said is required above!

But note your TM is not quite there yet: Consider what will happen on input string "bbb"!


How would Computer Science help the world in the novel coronavirus outbreak

During a recent Hackathon I witnessed, a team prepared a gadget like a smart watch. The goal is to check how many times does a person cough, to track fever and such. A really cheap piece which can be worn by everyone. The data that can be attained would yield geo-coordinates of the societies and getting affected and need attention. It can help prioritize areas of immediate concern.


What are current approaches to auto-parallelisation?

Automatic parallelization in the most general terms is extracting a dependency graph from the execution sequence of the program and executing distinct paths in this graph in parallel with synchronization introduced at the nodes of the graph where the paths merge.

Our ability to extract the dependency information varies depending on the programming language used. Functional languages have no side effects that makes it easier to parallelize. It is more difficult with imperative languages.
Several programming languages were proposed where parallelism may be implicit. Such as array programming languages.

Autoparallelization of inherently sequential programs like programs written in C or FORTRAN attracts significant practical interest. One classical reference work on the subject is Michael Wolfe's "Optimizing Supercompilers for Supercomputers" based on his 1982 PhD thesis [1].

One of the key areas of the work is parallelizing multidimensional loops. Observe that loop indices are often used in linear combinations inside loops (e.g. for a $N\times N$ matrix $a$ in a C language program a[I][J] is a reference to an element that lies at position a + I * N + J). Therefore dependencies between iterations can be expressed as linear equations. Thus the ability to solve systems of linear equations efficiently is important for autoparallelizing compilers.

In an important general case finding depdendencies between operators in a loop requires finding all solutions of a system of linear equations in integers. There exists no polynomial algorithm for finding a solution of such a system of equations, therefore approximate tests are employed, that can detect independence. An important class of tests are derived from Banerjee Inequality.

The essense of the method is as follows. Let $x$ and $y$ be vectors of unknowns of dimension $d$, and $\textrm{A}$, $\textrm{B}$ be some linear operators. For loop dependencies the values of indices usually have upper and lower bounds. Suppose $m_i \leq x_i,y_i \leq M_i$.

To test if a system of linear equations $\textrm{A}x - \textrm{B}y = c$ has a solution we find the upper bounds $UB_j$ and lower bounds $LB_j$ of $\textrm{A}x - \textrm{B}y$ for all possible values of $x$ and $y$, $m_i \leq x_i,y_i \leq M_i$ and test if $c$ lies within the bounds. If it does not, then there is no solution, and two memory references are independent, hence can be executed in parallel. This test is incomplete, but can be efficiently computed.

Different data-dependence heuristics are compared on real and synthetic benchmarks [2]. A recent overview of data-dependence analysis techniques can be found in the publications from the UCSD Kremlin project [3].

M. Wolfe, Optimizing Supercompilers for Supercomputers, 1989
K. Psarris, K. Kyriakopoulos, An Experimental Evaluation of Data Dependence Analysis Techniques, IEEE Transactions on Parallel and Distributed Systems, March 2004 (vol. 15 no. 3), pp. 196-213
S. Garcia, D. Jeon, C. Louie, M.B. Taylor, Kremlin: Rebooting and Rethinking gprof for the Multicore Age, PLDI'2011


NFA-$\epsilon$ extended transition function for inverted strings

First, there's a typo at your definition of $\hat\delta$. Case $\hat\delta(q,\alpha x)$ should be $\bigcup_{p_i \in \hat\delta(q,\alpha)}ECLOSURE(\delta(\color{green}{p_i},x))$ (green for highlighting the difference).

The equivalent definition in terms of a string given as $(x\alpha)$, where $x\in\Sigma$ and $\alpha\in\Sigma^*$, is
$$
\hat\delta(q,x\alpha) = \bigcup_{p_i \in ECLOSURE(\delta(q,x))} \hat\delta(p_i,\alpha)
$$


Multi-dimensional Neural Network for fingerprint matching

Based on my skim of the paper, I suspect that this is just a standard neural network (in which the entire image is fed into the neural network as an input, one input line per pixel in the image), and they have invented a fancy-sounding name for a standard use of neural networks.  You could of course contact the authors to ask them this question, but that's what it looks like to me.

To replicate their work, I suggest you read Section 5.1 very carefully and use the descriptions there to replicate their work.


How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack?

First, precompute the weights of every subset of $B$.

Sort them by weight and put the weights and subsets in parallel arrays so that $W[i] = weight$ and $S[i] = subset$.

Then make another parallel array so that $BEST[i]$ is the index $j$ of the set of greatest value such that $j<=i$.  You can do this with a single scan from $i=0$ upward, remembering the greatest value seen so far at every step.

Now, to search $B$, you do a binary search in $W$ to find the maximum permissible weight, and get the best set from the same index in $BEST$


NPC-problem reduction to triangle-free 3-colorability

We reduce from 3-coloring, following Kráľ, Kratochvíl, Tuza and Woeginger, Complexity of Coloring Graphs without Forbidden Induced Subgraphs. We will need to use a gadget $H$, with the following properties:

$H$ is a 3-colorable triangle-free graph.
There are two vertices $a,b \notin H$, not connected by an edge, such that any 3-coloring of $H$ gives $a,b$ different colors.

Given such a gadget $H$, here is how to reduce 3-coloring to triangle-free 3-coloring. We start with a graph $G$. We construct a new graph $G'$ as follows. The graph $G'$ will have all vertices of $G$, together with some new vertices. For each edge $e = (x,y) \in G$, there is a copy $H_e$ of $H$. We identify $a_e$ (the copy of $a$ in $H_e$) with $x$, and $b_e$ with $y$. This completes the construction.
The new graph is triangle-free. Indeed, suppose that it contained some triangle $u,v,w$. Since the vertices $u,v$ are connected, they must reside in some copy $H_e$ of $H$. Since $(a,b) \notin H$, at least one of these vertices doesn't belong to $V$, say $u \notin V$. Since all neighbors of $u$ are in $H_e$, it follows that $u,v,w$ all reside in $H_e$, contradicting the triangle-freeness of $H$.
If $G$ is 3-colorable, then we can easily complete a 3-coloring of $G$ to a 3-coloring of $G'$ by using a 3-coloring of $H$ (by symmetry, it doesn't matter what colors $a,b$ get, as long as the colors are different). Conversely, the restriction of any 3-coloring of $G'$ to $V$ is a 3-coloring of $G$.
To complete the proof, we need to describe the gadget $H$. Our starting point is any critically 4-colorable triangle-free graph $H'$, such as the Grötzsch graph; here critically 4-colorable means that the graph is not 3-colorable, but becomes 3-colorable if we remove any edge.
We take any edge $(a,c) \in H'$ and replace it by an edge $(b,c)$, where $b$ is a new vertex (in particular, $(a,b)$ is not an edge). The resulting graph $H$ is still triangle-free. Since $H'$ was critically 4-colorable, the graph $H$ is 3-colorable: take a 3-coloring of $H' \setminus \{(a,c)\}$, and color $b$ appropriately. Any 3-coloring of $H$ must give $a,b$ different colors, since otherwise its restriction to all vertices but $b$ would be a 3-coloring of $H'$.


Showing that the language $L = \{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \}$ is decidable or undecidable

I strongly believe it is decidable, but I found it quite convoluted. I'll give a sketch of proof.

Lemma: Every Turing Machine that doesn't terminate either moves left at some point or is very silly.

Let $M_\leftarrow$ be a TM that never moves left. If $M_\leftarrow$ never moves left, we don't care about what it writes on the tape, because it can only ever read the last symbol it wrote. In particular, we may see $M_\leftarrow$ as a finite transition system which set of states are the pairs $(q \in Q, \sigma \in \Sigma)$ where $q$ is the current state of $M_\leftarrow$ and $\sigma$ is either the last symbol written by $M_\leftarrow$ or the blank symbol if $M_\leftarrow$ just moved to the right. Therefore, checking if the graph of the transition system is cyclic decides whether or not $M_\leftarrow$ terminates, qed.

Theorem: $L$ is decidable.

Let $H$ be the problem of deciding whether or not a machine that never moves left terminates. By the lemma above, there exists a machine $M_H$ that takes as input another machine $M$, some input $x$ and:

if $M$ never moves left on input $x$, returns $\textsf{YES}$ if $M$ terminates and $\textsf{NO}$ otherwise,
if $M$ on input $x$ moves left at some point, returns $\textsf{YES}$.

We will show that we can use $M_H$ to construct a family of machines $M_k$ that decides whether or not a machine moves left at least $k$ times. Let $\langle M, x \rangle$ be the input.

First of all, we have $M_k$ construct a universal machine $U$, and use $U$ to compute $M_H$ on input $M$. If the result is $\textsf{NO}$, it means that $M$ never moves left on input $x$: we accept $\langle M, x \rangle$. If the result is $\textsf{YES}$, it means that either $M$ terminates on input $x$ or moves left at some point.

We use $U$ to simulate $M$ on input $x$. After finitely many steps, either $M$ terminates or moves left. In the first case simply accept. If a left move happens, we save the current state of the tape, and return the result of $M_{k-1}$ with the modified tape as input, which is by inductive hypothesis computable, qed.


Proving equivalency of regular expressions

Conceptually, the simplest approach is:

Convert both regular expressions to NFA.
Determinise both NFA.
Minimize both DFA.
The regular expressions are equivalent if and only if the minimal DFA are isomorphic.

The requisite algorithms and theorems are taught in (about) every introducory class to formal languages resp. automata and can be found in (every) textbook on the topic. In fact, the point of this exercise probably was to come up with this approach, combining results from the course. Sorry for spoiling it.


Fastest (fast enough to compute) algorithm for finding permutations

Suppose you are working with an alphabet of size $d$.  Then each word can be represented as its characteristic vector.  A characteristic vector $v \in \mathbb{N}^d$ is a vector, where the $i$th entry counts the number of times the $i$th letter appears in the word.  For instance, the word $abbad$ would have characteristic vector $(2,2,0,1)$ if the alphabet is $a,b,c,d$.

As Yuval explains, you want to find all strings which satisfy the following two properties: (1) they are a rearrangement of the list of letters, (2) they are a concatenation of up to $n$ words from the list of words (the same word can be used several times).

Looking at characteristic vectors, you can think of the problem as follows: you are given vectors $v_1,\dots,v_k$ (corresponding to the list of words) and a vector $w$ (corresponding to the characteristic vector for the list of letters), and you want to find non-negative integers $a_1,\dots,a_k$ such that

$$a_1 v_1 + \dots + a_k v_k = w.$$

You also want $a_1 + \dots + a_k \le n$ (to satisfy requirement (2) above).  You want to enumerate all solutions $a_1,\dots,a_k$ that satisfy these requirements.

This turns out to be an instance of enumerating lattice points in a convex polytope, for which there are well-studied algorithms.  See the following paper for an overview:

Effective lattice point counting in rational convex polytopes.  Jesús A. De Loerab, Raymond Hemmecke, Jeremiah Tauzera, Ruriko Yoshida.  Journal of Symbolic Computation, vol 38 no 4, Oct 2004, pp.1273-1302.  https://www.sciencedirect.com/science/article/pii/S0747717104000422

You could try applying one of those algorithms to your problem to see how well they work.

Alternatively, it's also possible to solve the problem by repeatedly invoking an ILP solver.  You can use an ILP solver to test whether any solution exists, and the largest value of $a_1$ such that a solution exists.   Then,  if at least one solution exists, you enumerate $a_1=0,1,2,\dots$, and for each value of $a_1$, plug in the value of $a_1$ and recursively invoke the same algorithm to enumerate all solutions for $a_2,\dots,a_k$ (such that $a_2 v_2 + \dots + a_k v_k = w - a_1 v_1$ and $a_2 + \dots a_k \le n - a_1$).  This might be inefficient, though.


Whats the logic between MAR, MBR and Control Bus

The RAM typically has a input pin called MW for "memory write" (maybe with inverted logic, then written with an overbar), to distinguish between read and write operations.

Control will probably use an extra wire to the RAM. In theory, you could use an usused high address bit for that, too, but I guess that would be considered to be a very questionable design - in fact "invalid" memory addresses are used for other strange things, like talking to non-memory devices such as line printers.

An address decoder will select the appropriate memory cell.

After that, the rest will depend on the MW bit... on the writing side, if it's static RAM (SRAM), you can use MW for enabling ("gating") the flipflop S (set) pin. On the reading side, you could use a transmission gate to connect or disconnect the RAM output from the data bus (logic gates won't do here, as the RAM output has to be decoupled from the data bus, unless you are actually reading values).


Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$

Hint: Try converting both functions to the form $e^{f'(x)}$.


What do queues and stacks correspond to in math?

As a practical matter, how you treat data structures mathematically largely depends what you're trying to do.

For example, suppose that you're trying to reason about the correctness of programs that use stacks and/or queues. In that situation, you'd want to treat the stack/queue as an abstract object, and axiomatise its properties. So you develop (say) a theory of stacks which can be layered on top of a general theorem prover.

You can do this quite straightforwardly in constructive type theories, such as the calculus of constructions. It's worth taking a look at the theories that come with Coq (the proof management system); it has a theory of strings, a theory of lists, a theory of maps, and so on.

Having said that, stacks and queues in some contexts do model mathematical objects. I'm going to run with the example of pushdown automata. In this case, the stack symbols are a fixed finite set (and they have no structure; it makes no sense to do maths on the stack symbol names themselves!), and so the stacks form an interesting algebra.

I'm going to start with regular languages, which we can axiomatise as a Kleene algebra. A Kleene algebra is an idempotent semiring plus the Kleene star operator. The two ring-like operations $\cdot$ and $+$ correspond to concatenation and set union, and $0$ and $1$ correspond to the null set and the empty string.

We know that DFAs and regular expressions are basically the same thing. We also know that pushdown automata are like DFAs, only they also do stack operations. There's no reason why we can't put stack operations in regular expressions; in this way, we could express context-free languages using a regular expression-like operation.

So let's do that. We'll denote a stack push of symbol $i$ using the notation $\left\langle i \right|$ and a pop using the notation $\left| i \right\rangle$. Now we need to work out how these stack operations work algebraically.

Terminal symbols commute with stack operations, in the sense that reading as symbol followed by a stack push or pop is the same as doing the stack operation followed by reading the symbol:

$$a \left\langle i \right| = \left\langle i \right| a$$
$$a \left| i \right\rangle = \left| i \right\rangle a $$

Finally, we need to work out what happens when two stack operations meet. A push of a symbol followed by a pop of the same symbol is equivalent to reading the empty string (i.e. doing nothing):

$$\left\langle i \right| \left| i \right\rangle = 1$$

However, pushing a symbol followed by trying to push a different symbol cannot happen. This is equivalent to the empty set (i.e. the language with no strings in it):

$$\left\langle i \right| \left| j \right\rangle = 0, \hbox{if}\,i \ne j$$

In other words, we're looking at something very like a vector space. Strings of terminals behave like scalars, and stack operations behave like vectors and one-forms. When a push meets a pop, they behave like an inner product where the basis vectors are orthonormal.

Moreover, if the stack is nonempty, then any pop followed by a push of the same symbol should be a no-op:

$$\left| 1 \right\rangle \left\langle 1 \right| + \left| 2 \right\rangle \left\langle 2 \right| + \cdots + \left| n \right\rangle \left\langle n \right| = 1$$

Using this algebra, we can (say) express $a^n b^n$ as $\left\langle 1 \right| (a \left\langle 2 \right|)^* (b \left| 2 \right\rangle)^* \left| 1 \right\rangle$. It's a little unwieldy, but it works.

Attentive readers might have caught on why I used this notation (lovingly stolen from Mark Hopkins): this is a Dirac algebra, as used in quantum mechanics.

It turns out that the analogy goes quite deep. A Turing machine can be thought of as an automaton with two stacks, and if you allow gradations between $0$ and $1$, you can axiomatise quantum Turing machines.

However, this is not the point I'm trying to get across. The point is that in this case, the stack operations form an interesting algebra which was discovered in a completely different context.

This alone answers your question with a resounding "it depends".


Your current approaches are very ad hoc, so they don't sound promising.  Instead, I think you're going to need some domain knowledge.  I suggest you start by characterizing the process by which the graph was generated.  First, try to develop a probabilistic model that describes the distribution on such graphs (absent noise).  Then, develop a probabilistic noise that describes the noise.

Suppose $X$ is a random variable that represents the original graph, and $Y$ is the random graph after adding noise to $X$.  You observe the value of $Y$, say $y$.  Now your goal is to estimate $X$.  So, this becomes a probabilistic inference problem. One approach will be to use maximum likelihood methods: find the value $x$ that maximizes $p(x|y)$ (where $p(x|y) = \Pr[X=x|Y=y]$).  To do this, you'll need to know the probability distribution $p(x)$ on $X$ and the probability distribution $p(y|x)$ on $Y$ (conditioned on $X$); then you can use Bayes rule and find the $x$ that maximizes the likelihood value $p(x|y)$ by noting that

$$\begin{align*}
p(x|y) &= p(y|x) p(x)/p(y)\\
&= {p(y|x) p(x) \over \sum_{x'} p(y|x') p(x')}.\end{align*}$$

Since $y$ is fixed, the denominator is a constant (it does not depend on $x$).  Therefore, maximizing $p(x|y)$ is equivalent to maximizing $p(y|x) p(x)$.  So, once you have a probabilistic model for $X$ and $Y$ and know the distributions $p(x)$ and $p(y|x)$, you can then try to infer the original noiseless graph by finding the value $x$ that maximizes $p(y|x) p(x)$.


Does an ADT have multiple or only one representations/implementations?

ADT is a specification. It can have many implementations. For an example, see this answer.


Genetic Algorithm Neural Network- Inputs for evolving creatures

If I understand well, your neural net have 4 inputs. But let's take this example :

The black circle is your creature
Grey circles are your sensors
Green circle is food
Red circle is a trap

Does the left sensor "see" the trap closer than the food ?

If yes, you're doing it wrong

A better way to do it would be to "simulate" real eyes, like this, where each sensor can only see what is in its field of view

Your neural net can take 2 inputs per sensor, as you did, with the distance to the closest food/trap it can see.

A second thing to try would be to only take in account the closest item for each sensor.

Another interesting thing to do would be to decrease the fitness over time, avoiding passive bots