Introduction into first order logic verification

After reading your question the only way I could see and had enough knowledge to tie the topics together was to give a hi-level set of articles that drill down from software verification ending up with trying to unite model checking and theorem proving. Hopefully my comment did that:

Take a look at Software verification  then Formal verification then Model checking  and Formal Software Verification: Model Checking and Theorem Proving

Dave has given a good answer for which I cannot do much more justice to the first part of the question than Dave had done, since I am also new to this.

Since this is your first question at an SE site, the reason I did not give an answer but a comment is because here an answer cannot be just a set of links, but must give a written answer and use links in support of the answer; thus a comment instead of an answer.

With regards to:

  Any pointers to books or articles for beginners in this matter is much
  appreciated.

Books I would suggest and use are:

Logic in Computer Science - Modelling and Reasoning about Systems 2nd Ed. by Huth and Ryan This introduces logic and moves up to model checking, but doesn't go into theorem proving. So this should cover all of your basic questions related to logic and model checking.
Principles of model checking by Baier and Katoen I just started reading this one, and it is much better than reading lots of papers and trying to see how they all fit together. This is one of the most, if not the most recommended book on the subject of model checking. It should answer your more advanced questions on model checking.
Temporal logic and state systems by Kroger and Merz I often like to have books by different authors when self-learning a subject. This one is to complement/round out "Principles of model checking"
Handbook of practical logic and automated reasoning by Harrison Being a programmer I can't recommend this book enough. The book starts off with introducing logic and moves all the way through the point of creating the kernel for a theorem prover based on the work of HOL Light. Just to highlight that the book uses working OCaml code, explains the theorems in terms I find friendly and gives you what you need to know but not so much that you can't make the connection or feel like you are running down side tracks. If is a very focused book on going from logic to a specific type of theorem prover.
How to prove it : a structured approach by Velleman To get into the Proof assistants for theorem proving you will need to live and sleep theorems.
A Introduction to Proofs and the Mathematical Vernacular by Day This is a free book that not only complements "How to prove it", it goes beyond it in sum regards. I would not be surprised to see this one become popular.

At present I cannot expand more on theorem proving because I am still learning the pro/cons and differences of each one, but the ones I am focusing in are

HOL Light because of the book by John Harrison.
Coq because it is based on Calculus of constructions
Isabelle because it is based on higher-order unification.

These proof assistants also typically have book(s), are current, popular, open-source, maintained, and have active support communities.

Note: I used worldcat.org to reference the books, but you can review them using Amazon's look inside feature.


Complexity of determining whether three points are collinear from a set of points

There is an $O(n^2)$ algorithm for the more general problem of minimum area triangle, see for example these lecture notes. The problem itself (as well as minimum area triangle) is 3SUM-hard, as shown in a survey of King on 3SUM-hard problems, where the problem is known as 3-points-on-line.

See also this stackoverflow question, where I found the links given above.


Maximal majoritarian program under incomplete voting

We can formalize this problem as follows.  Let the propositions be numbered $1,2,\dots,n$.  We have a function $f$ that, given a subset $S \subseteq \{1,2,\dots,n\}$ of propositions, returns true or false according to whether every proposition in $S$ has majority support among the survey respondents who saw every proposition in $S$.  Define $S \subseteq \{1,2,\dots,n\}$ to be a majoritarian program if $f(T)$ is true for all $T \subseteq S$.  Now we want an algorithm that, given ability to invoke $f$, finds the largest majoritarian program $S \subseteq \{1,2,\dots,n\}$.

We will of course interpret $S$ as follows: for each $i \in S$, we take whichever side of proposition $i$ has majority support (when considered in isolation; among all survey respondents who saw $i$), and take the conjunction of all of those.  Given $S$ you can easily compute $f(S)$ from the survey responses.

Here is one natural but not necessarily optimal algorithm for this.  Basically, you grow subsets from the "bottom up".  In particular, the algorithm looks like this:

Try(S):
1. If S is not a majoritarian program, return
2. If S is larger than the largest so far, remember S as the largest so far.
3. For each i in 1+max(S) .. n:
4.     Try(S ∪ {i})

You start by invoking Try({}), and when it returns, the best subset so far is the largest majoritarian program possible.  This effectively takes small subsets and tries to grow them to become bigger, but if they don't get majority support, the search is pruned and it stops trying to grow that set.

The running time could be exponential.  If you get lucky, you could hope that it runs more efficiently than that, though I don't know if you'll be lucky.

As a heuristic, you could sort the propositions by order of polarization, from most unanimous to most controversial.  That might speed up the search, or allow you to cut off the search after a certain time limit and take the best you've seen so far (with no guarantee that it is optimal, but the hope that it might be close).


The problem is similar to coin denomination with infinite number of coins available.

Let me know if this works ... http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

For every length which you encounter, you have two options, you can either use this rod or ignore this rod length and continue to the next one. In both the cases you can check if you could reach the target. If you can return true, else false.

So lets say you have a function canFindTarget( inputArray[], idx , sum ) which returns true if you can make sum using inputArray[0..idx-1] else false. Your answer would be canFindTarget( inputArray[], idx-1, sum ) || canFindTarget( inputArray[], idx, sum - inputArray[idx - 1]).


validation of a pumping lemma proof for regular languages

the union of 2 non-regular languages can be regular.
The trivial example is any non-regular language L and its complement. The union of those two is the set of all strings, which is a regular language.
There for the conclusion $L1, L2 \notin Regular \implies L1\cup L2 \notin Regular$ does not follow.


Why doesn't the assignment of processors contribute to runtime in a PRAM algorithm?

It seems this paper, which serves as a foundation for subsequent work on list ranking parallel algorithms, handles the oversight of assigning processors by assuming that the input is just given as an array containing the linked list (not necessarily in the order of the nodes in the list). This assumption of contiguous memory storage is implicitly followed in later papers such as this one.


Determine if there are 2 integers in 2 separate arrays add up to a given number

Insert the elements of the first array into a hashset S by subtracting from z. I.e., if 3 is an element of the first array, instert z - 3 into S. Then for each element in the second array, check if z - element is already in S. This procedure is O(n).


Given that you want to insert $n$ words into the Bloom filter, and you want a false positive probability of $p$, the wikipedia page on Bloom filters gives the following formulas for choosing $m$, the number of bits in your table and $k$, the number of hash functions that you are going to use.  They give
$
m = - \frac{n \ln p}{(\ln 2)^2}
$
and
$$
k = \frac{m}{n}\ln 2=-\frac{\ln p}{\ln 2}=-\lg_2p,
$$
so you should choose
$$
m=\frac{nk}{\ln 2}.
$$

That actually works out quite nicely.  You are going to get a table with about half the bits set and half cleared, so the entropy per bit is going to be maximal, and the probability of a false positive is going to be
$0.5^k$.


Write algorithm for biased toss of a coin

Let $\xi$ be a random variable uniformly distribuited in $[0,1]$ and $t$ a real value in $(0,1)$, consider the function

$$
Y(\xi;t) = \begin{cases}
1 & \xi < t \\
0 & \text{otherwise}
\end{cases}
$$

Which is a discrete random variable therefore

$$
p_Y(y) = (1-t) \delta(y) + t \delta(y - 1)
$$

This means that if pick a random number in $[0,1]$ and you later compute $Y$, this $Y$ will correspond to a randomly picked value in $\left\{0,1\right\}$, but biased accordingly to $t$. If you use @kngtu pseudocode, it's equivalent to define the distribution above where $t = 0.67$.


Kolmogorov complexity of a sequence of n bits with k ones

In Kolmogorov complexity, our measure of complexity is program length. We don't care about the resource consumption of the program (unless we're interested in resource-bounded Kolmogorov complexity). Given $n$ and $k$, a program can generate all $n$-bit strings of weight $k$, so there is no need to store the list itself as part of the program.

The formula you quote and the explanation you give seem mistaken. In order to use the program you mention to generate a specific vector, we need to give it as input $n,k,i$. It takes $K(n) \le \log n + O(\log\log n)$ bits to encode $n$ itself. Given $n$, we can encode $k$ in $\lceil \log n \rceil$ bits, and $i$ in $\lceil \log \binom{n}{k} \rceil$ bits. Overall, we obtain that the Kolmogorov complexity is at most
$$ 2\log n + \log \binom{n}{k} + O(\log\log n). $$


Why can't DFA's have 0 exiting arrows for some input symbols?

This is part of the (usual) definition of DFAs. It's hard to argue with a definition.

While it's hard to argue with a definition, one can ask why the object was defined in a certain way. Here one answer is that we want our automaton to always be at a particular state, whatever happens. In other words, we want the transition function to be a function rather than just a partial function. It is a matter of taste.

Some people allow the transition function to be partial, and still call the resulting model DFA, though this is probably less common than Sipser's definition. The two definitions are almost equivalent – accommodating a partial transition function takes at most one additional "sink" state.


Solving divide & conquer reccurences if the split-ratio depends on $n$

Let's say you have a recurrence
$$
T(n) = \begin{cases}
T(n - n^c) + T(n^c) + f(n) & \text{n > 2} \\
1 & \text{otherwise}
\end{cases}
$$
that ranges over positive reals.

What can we do with this function? Well, not a lot unless we superimpose certain structures upon it. I came from a numerical analysis background, which is paved with numerical recipes that somehow works even when the underlying problem is either not smooth enough (doesn't matter, let's still throw Newton's method at its divided differences) or too complicated to analyze (sort of like this problem). My gut reaction towards these problems is to make some handwaved assumption, cross our fingers, and hope for the best. In this case, it seems to give relatively good bounds.

In particular, I want to make two major assumptions. One of these assumptions is more or less baseless, but we won't get very far without it. The other has a somewhat nice visual intuition that you can hopefully grok, but it is still more handwavy than anything else.

I will assume that $T(n)$ is "smooth-ish". It's fairly easy to see that $T(n)$ is not everywhere differentiable. In fact, it isn't even continuous, since for $f(n) = \log(n)$ and $c = \frac{1}{2}$, $\lim_{n \to 2^-} T(n) = 1$ and $\lim_{n \to 2^+} T(n) = 2 + \ln 2$. Therefore, given the iterated maps generated by $n \mapsto \sqrt{n}$ or $n \mapsto n - \sqrt{n}$, $T(n)$ will contain a discontinuity at $n$ if its iteration tree contains $2$ somewhere in its trajectory. That is a lot of discontinuities, it might even give Dirichlet's function a run for its money. If we're getting to the point where we are comparing a function's behaviors to that of the prototypical example of a nowhere-continuous function, isn't it laughable to try to claim that it is "smooth-ish"? Well, it turns out that in practice, the effects of these discontinuities asymptotically diminishes, to the point that your graph looks almost smooth when $n$ tends towards infinity! Therefore, I propose that we put down our pitchforks and just look the other-way in this circumstance. In particular, I will assume that at any point of interest $n$ that is sufficiently far away from the origin, $T(n)$ is differentiable, or at least approximately differentiable around some neighborhood.
I will also assume an even stronger stance of smoothness when $n$ is sufficiently far away. Suppose that $\alpha(n)$ is some sublinear function such that $n > \alpha(n)$ (for example $n^c$), then the derivative $T'(\xi \in (n - \alpha(n), n)$ does not vary significantly when $\alpha(n)$ is slow enough. Intuitively, as $n$ gets larger, the relative size of the neighborhood $(n - \alpha(n), n)$ decreases (since its size is just $\alpha(n)$, which grows much much slower than $n$ does). Eventually, the size of this neighborhood becomes so insignificant (relative to $n$) that the rate of change of $T(n)$ within this neighborhood no longer changes all that dramatically.

Now, both of these properties are assumed, and I have zero idea how to go about actually proving either in any rigorous way. But like I said before, let's cross our fingers and hope for the best.

Let's start with the recurrence relation:
\begin{align*}
T(n) &= T(n - n^c) + T(n^c) + f(n) \\
T(n) - T(n - n^c) &= T(n^c) + f(n) \\
n^c\frac{T(n) - T(n-n^c)}{n^c} &= T(n^c) + f(n)
\end{align*}
Now, I'll assume that $T$ is smooth enough on the interval between $n - n^c$ and $n$. Appealing to one of our classical analytic tools, the mean-value-theorem, gives us
$$
\frac{T(n) - T(n-n^c)}{n^c} = T'(\xi \in (n - n^c, n)).
$$
Furthermore, when $n$ is sufficiently large, we assume that $T'(\xi)$ is approximately the same throughout this interval, and hence takes the value of any of the finite differences within this interval as well. This then means that
$$
T'(\xi) \approx \frac{T(n) - T(n - \epsilon)}{\epsilon} ~~~~ \epsilon < n^c
$$
In particular, take $\epsilon = 1$ to get a one-step divided difference approximation
\begin{align*}
n^c (T(n) - T(n-1)) &\approx T(n^c) + f(n) \\
T(n) - T(n-1) &\approx \frac{T(n^c) + f(n)}{n^c} \\
\end{align*}
We can telescope this out to get
$$
T(n) \approx \sum_k^n \frac{T(k^c)}{k^c} + \sum_k^n \frac{f(k)}{k^c}
$$

Perturbing $T(n)$ reveals that $T(n)$ has two asymptotic phases, depending on the asymptotic nature of $f(z)$.

When $f(n) = o(n^c)$ ($f$ is faster than $n^c$), then the right sum dominates, and we have $T(n) = \Theta\left(\sum\limits_k^n \frac{f(k)}{k^c}\right)$  which can often be approximated with the integral $\int\limits^n \frac{f(x)}{x^c} dx$.

When $f(n) = \omega(n^c)$, then the left sum dominates the right. Here, we have to analyze the sum
$$
\left(\sum_k^n \frac{T(k^c)}{k^c}\right) + F_c(n)
$$
where $F_c(n) = \int\limits^n \frac{f(x)}{x^c}dx$.

By virtue of the smoothness argument, we can once again look at this as a left-anchored Riemann sum, approximating the integral $\int_n \frac{T(x^c)}{x^c} dx$. Applying a similar mean-value-theorem over the integral gives
$$
\sum_k \frac{T(k^c)}{k^c} \approx \int^n \frac{f(x^c)}{x^c} dx = n\frac{T(\xi < n^c)}{\xi^c}
$$
We can just go ahead and approximate this by $n\frac{T(n^c)}{n^c}$, which gives the approximation
\begin{equation}
T(n) \le n M \frac{T(n^c)}{n^c} + F_c(n)
\end{equation}
for some constant $M$ that bounds the series.

Now, suppose that we have the iterated sequence $(n, n^c, n^{c^2}, n^{c^3}, \dots, n^{c^k})$ where $n^{c^k} < 2$, then we can use this sequence to telescope the above inequality to get:
$$\label{eqn:meh}
T(n) \le n \left(\sum_i^{k-1} \frac{M^i}{n^{c^i}}F_c(n^{c^i}) + \frac{M^k}{n^{c^k}}\right) \tag{*}
$$
Once again, we can bound the $F_c(n^{c^i})$ term by some constant to find that
$$
T(n) = O\left(F_c(n) + n F_c(n^c) \left(M n^{-c} + M^2 n^{-c^2} + \dots + M^k n^{-c^k}\right)\right)
$$
where $k = \log_c\left(\frac{\log(2)}{\log(n)}\right)$. Simplifying a bit and coalescing some of the $Mn^{-c}$ terms together (in particular, we know that $n^{-c^k}$ is a constant), we get
$$
T(n) = O\left(n k F_c(n) M^{k} \right)
$$

However, this bound is relatively loose, and you should refer to $(\ref{eqn:meh})$ whenever possible.

Be aware that in no way is this rigorous. I have not provided any support that this ought to work beyond some clumsy approximations. Nevertheless, if you just need a quick asymptotic guess for the sake of informal analysis, then you can actually see that this scheme works well (for large enough values of $n$, usually $n > 10$ suffices) in practice.

Anyways, for all of the choices of $c$ and $f$ that I've tried, the following computation
\begin{align*}
\hat T(n) &= n \sum_k^{\log_c \log_n 2} \frac{M^k}{n^{c^k}} F(n^{c^k}) \\
F(n) &= \sum_k^n \frac{f(k)}{k^c}
\end{align*}
where
$$
M \approx \frac{\sum_k \frac{T(k^c)}{k^c}}{n \frac{T(n^c)}{n^c}}
$$
seems to give good approximations. This technique also generalizes to recurrences of the form
$$
T(n) = T(n - \alpha(n)) + T(\beta(n)) + f(n)
$$
which can be approximated with
\begin{align*}
\hat T(n) &= n \sum_k^{\#_\beta(n)} \frac{M^k}{\alpha^k(n)} F(\beta^k(n)) \\
F(n) &= \sum_k^n \frac{f(k)}{\alpha(k)}
\end{align*}
where $\alpha^k(n) = \alpha(\stackrel{k}{\cdots}(\alpha(n)))$ and $\#_\beta(n)$ denotes the number of elements of the sequence $n, \beta(n), \beta(\beta(n)), \dots, \beta^{\#_\beta(n)}(n)$ such that the last term is between $1$ and $2$.


Showing filling a container with rectangles is hard by reducing from SUBSET-SUM

Hint: Follow frafl's advice and set $b_i = h = 1$.


Consider Lagrange's four square theorem. It states that if $B = \{1^{n^2}| n \geq 0\}$ then $B^4 = \{1^n | n \geq 0\}$. If $B^2$ is regular, take $A = B$ else take $A = B^2$. Either way, this proves the existence of irregular $A$ such that $A^2$ is regular.


Using A* path finding is giving me inaccurate results

Let's start this off with a quick review of A*. A* is a pathfinding algorithm that builds on some of the benefits that greedy searches and dijkstra searches have. Make sure that your implementation correctly combines both basic heuristics A* uses:

g(N) = the cost to get from the starting node to the next node N
h(N) = the estimated cost to get to the goal from N

By expanding the nodes with the lowest g(N) + h(N) first, A* quickly converges on the most efficient path when some costs are unknown. It's great for any graph search and I've used it to implement backtrackers for constraint solving.

Now, our review's over. Let's get to your problem!
You're trying to have a character visit certain subgoal nodes on the graph and finish on the goal node. This is actually a variant of the famous "Travelling Salesperson Problem". It is an example of an NP-complete problem, which means that even A* isn't going to help you solve it quickly; you'll be doing a lot of backtracking or trial-by-error no matter what algorithm you use.
In order to adapt A* to this problem, you will need to rewrite the logic for exiting the search. Instead of checking if N_i == Blue_1, you need to check if {Blue_1, Pink_1, Pink_2, Pink_3} is a subset of the path.
Right now your calculation for h(N) is based on Euclidean distance from Blue. Not a bad start, but it's not as efficient as simply setting h(N) = 0 on this problem; dijkstra search is better than a too-greedy A*. Because you aren't actually aiming for the blue node, you have an 'inadmissable' h(N) so you'll miss the optimal path sometimes:

"If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal."

You can get an admissible heuristic by setting h(N) = the distance to the nearest sub-goal. Once all sub-goals are reached, set h(N) = the distance from the blue goal. This means that each node in the pathfinder needs additional metadata. Add a field to pathfinding nodes that tracks which goals have already been hit.


Quick groupby - is this a well known algorithm?

Asymptotically and under usual assumptions, the problem you state is as hard as sorting, by reduction from duplication.

If you had a $o(n \log n)$ algorithm to solve your problem, you could combine it with a constant number of array scans to produce a $o(n \log n)$ time procedure to test whether the array contains a pair of identical elements, in contradiction with the well-known $\Omega(n \log n)$ lower bound on that problem.

I don't think there's much to be gained with custom-tailored algorithms in practice, either: a well-optimized implementation of a generic sorting algorithm should be -- without further assumptions -- as efficient as you can get.


Yes. (you are right, the "$\mid$" sign is a classical notation for the alternative rules for a variable.)


What theorem are these? (from Scott Aaronson's blog)

The first excerpt hints at Barrington's theorem. The second is probably about natural proofs.


Algorithm for splitting an array into k sub-arrays

Insert$(x)$ can be implemented in $O(k \log(n/k))$ time. I will use the terms subarray and group interchangeably.

Let $n$ be the number of elements in the data structure before the insert operation. We will maintain this invariant: each subarray contains either $\lfloor n/k \rfloor$ or $\lceil n/k \rceil$ elements. The elements of each subarray are stored in a min-heap and in a max-heap that support element deletion.

Insert $x$ into the unique group $i$ whose minimum element is smaller than $x$ and such that the minimum element of the next group (if any) is larger than $x$.

Notice that if, before the insert operation, $i$ contained $\lfloor n/k \rfloor$ elements then the operation cannot possibly violate the invariant.
This means that if the invariant is violated then $\lfloor n/k \rfloor < \lceil n/k \rceil$, $i$ contained $\lceil n/k \rceil$ elements, and there is a group $j \neq i$ that contained $\lfloor n/k \rfloor$ elements.
Let $j^*$ be the value of $j$ that satisfies the above conditions and minimizes $|j^*-i|$.

We can restore the invariant as follows:

If $j^* < i$ then all groups $h \in \{j^*+1, \dots, i-1\}$ have $\lceil n/k \rceil$ elements. For each $h= j^*+1, \dots, i$ do the following: pick the minimum element $m$ from group $h$ (this can be done in $O(\log n/k)$ time by a pop() operation on the min-heap of $h$ and a delete($m$) operation on the max-heap of $h$) and add $m$ to group $h-1$ (this amounts to adding $m$ to both the min-heap and the max-heap of group $h-1$).
If $j^* > i$ then all groups $h \in \{i+1, \dots, j^*-1\}$ have $\lceil n/k \rceil$ elements. For each $h= i, \dots, j^*-1$ do the following: pick the maximum element $M$ from group $h$ and add it to group $h+1$.


$$5\log_2(2n)+7=5\log_2 n+5\log_2 2+7=5\log_2 n +12$$
Since for example $12\le 12\log_2 n$ for $n\ge 2$, it follows that
$$5\log_2 n +12\le 5\log_2 n +12\log_2 n=17\log_2 n $$
for $n\ge 2$. This yields $O(\log n) $.


Identify objects (bus) on the map based on coordinates (lat, lon)

Have the app record the GPS location once per second, save it, and once every 30 seconds, update that trace of the locations over the past 30 seconds.  Or, just upload the location every second.  The bandwidth requirements for that are small.  Then, if you have multiple users in the same location (within a fixed radius, say within 100 ft of each other), and with a velocity within some fixed range (say, between 20-60 mph), declare them to be on a bus together.  That should be fast, and doesn't require knowing the number of buses.

This problem doesn't need a solution with a fancy algorithm; straightforward solutions should suffice.


How Cellular Automata is related to Automata Theory?

There's no particular relationship. "Automaton" just means "machine" and it's unfortunate that we use the term "automata theory" to describe the study of one particular kind of automaton, rather than using a more specific name.  (You can imagine a parallel universe in whcih automotive engineering is called "machine theory" and other mechanical engineers are standing around saying, "We build machines, too!")

Having said that, I assume there's some relationship between cellular automata and automata-theory automata. It's well-known that some automata are Turing complete, in the sense that you can code up a Turing machine as an input to the automaton, set it running and decode what the cellular automaton does as being the operation of the Turing machine. It would not be surprising (to me, as a non-expert in cellular automata) if there are cellular automata that have the same expressive power as regular expressions, i.e., if there are cellular automata that can simulate automata-theory automata but not simulate anything more powerful.


It does not reach a constant ceiling, but the modulo gate cannot depend on the input's length, e.g. $\bmod n/2$ gates are not allowed. You must decide on the constants while constructing the circuit, independently of the input/input size. See the definition in Arora and Barak's book, where they first define $ACC0(m_1,...,m_k)$ which corresponds to circuits with $\bmod m_1,...,\bmod m_k$ gates, and then define $ACC0$ as the union of $ACC0(m_1,...,m_k)$ over all integer $k$-tuples.


Proving that the continuation of a non-regular language is not ω-regular

If $L'$ is regular then it is easy to extend a DFA for $L'$ to a deterministic Büchi automaton for $L$. For the other direction, start with a (general) Büchi automaton for $L$. Call a state winning if the automaton accepts starting at the state upon reading $x^\omega$. Remove all $x$ transitions and make winning states accepting to obtain an NFA for $L'$.


Polynomial time solution for bipartite matching

This actually has nothing to do with the stable marriage problem; it's an instance of bipartite matching.  (It's not related to stable marriage, becuase you don't have an ordering on the preferences of which box each item is matched to; you just have a list of what's allowed or disallowed.)

There are efficient algorithms: use the Hungarian algorithm, or any other algorithm for finding a maximum matching in a bipartite graph.  See https://en.wikipedia.org/wiki/Bipartite_matching#In_unweighted_bipartite_graphs, https://en.wikipedia.org/wiki/Hungarian_algorithm, and https://en.wikipedia.org/wiki/Assignment_problem.


Does exponential time always beat polynomial time? $n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$

"exponential time always beats polynomial" we understand as for $a>1$ and any $k\in \mathbb{R}$ we have $n^k \in O(a^n), n\to \infty$.
But if you consider substitution of $n$ with some arbitrary function, then, of course, generally,   $n^{f(n)} \in O(a^{g(n)})$ will be wrong.  We can even reverse functions with appropriate substitution: $n^{f(n)}=n^{\log_na^n} = a^n $ and $a^{g(n)} = a^{\log_a n^k} = n^k$.
Your example $\sqrt{n}$ vs $2^{\sqrt{\log_2 n}}$ is not polynomial vs exponential, but polynomial vs some elementary function.
Addition.
Now let's compare $\sqrt{n}=2^{\log_2 \sqrt{n}}$ and $2^{\sqrt{\log_2 n}}$. As exponential with base $2$ is strictly increasing, then it is equivalence to compare $\log_2 \sqrt{n}$ and $\sqrt{\log_2 n}$. Considering function $f(x)=\log_2 \sqrt{x} - \sqrt{\log_2 x}$, for $x>1$, we have $$f'(x)=\frac{1}{2x\ln 2}-\frac{1}{2x\ln 2\sqrt{\log_2 x}} = \frac{\sqrt{\log_2 x}-1}{2x\ln 2\sqrt{\log_2 x}}$$
So $f$ is decreasing on $(1,2)$ and increasing on $(2,+\infty)$. As it easy to see, that $f(1)=f(16)=0$, then we can conclude that on $(1,16)$ function is negative and on $(16,+\infty)$ function $f$ is positive, so $$\sqrt{n}=2^{\log_2 \sqrt{n}} \gt 2^{\sqrt{\log_2 n}}$$ for $n \gt 16$. This gives $2^{\sqrt{\log_2 n}} \in O(\sqrt{n})$.
Additionally, if we consider $g(x)=\frac{\log_2 \sqrt{x}}{\sqrt{\log_2 x}}$, then
$$\lim\limits_{x \to +\infty}\frac{\log_2 \sqrt{x}}{\sqrt{\log_2 x}}= \lim\limits_{x \to +\infty}\sqrt{\log_2 x}=+\infty$$
which gives $2^{\sqrt{\log_2 n}} \in o(\sqrt{n})$.


Can we solve this problem more efficiently than trying all possible combinations

I am going to prove that a special case of this problem is NP-hard and hence we can not aim for a polynomial time algorithm for the general case (unless P=NP).

Assuming each word has length exactly 1. This means each word is only one letter and each sentence is a combination of letters. We are looking now for a set of at most $k$ letter that construct as many sentences as possible. In other words, we are looking for the maximum number of sentences that can be constructed with $k$ letters and hence have union at most $k$. This problem is very similar to the NP-hard minimum $k$-union problem and can also be proven hard using the NP-Hard maximum clique problem (See this question for more information).

Note that heuristics can be used to improve the running time if you are not looking for an optimal algorithm. However, a better greedy heuristic than sorting the words from the largest frequency is looking for sentences with the shortest total lengths and high number of intersections with other strings. In this case however, it would only make sense if your algorithm breaks before trying all possible values.


Shortest path from $s$ to $v$ in unweighted simple directed graphs

Create a new graph $G' = (W,F)$ as follows:

For every every $v\in V$, create three vertices $v_0,v_1,v_2$ in $W$. The index $i$ in $v_i$ represents the fact that any path to this vertex uses exactly $i$ red edges.
For every edge $(u,v)\in E\setminus E'$, create the edges $(u_0,v_0)$, $(u_1,v_1)$ and $(u_2,v_2)$ in $F$.
For every edge $(u,v)\in E'$, create the edges $(u_0,v_1)$, $(u_1,v_2)$ in $F$.

Now you just have to compute the length of the shortest path from $s_0$ to any other vertex in your new graph $G'$ (if the vertex is unreachable then let this distance be $+\infty$). The length of the corresponding shortest path from $s$ to $v$ in $G$ is then the minimum of the lengths to $v_0,v_1$ and $v_2$.


Sufficient condition for simple graph isomorphism?

There are two non-isomorphic graphs with 16 vertices in which each vertex has 6 neighbors and 9 vertices at distance 2: the Shrikhande graph and the $4\times 4$ rook's graph.


You are correct that additions operator is produced first when you
derive. But when you parse, you do the opposite (reduction), and the
multiplications are recognized first, wich is precisely what you want.

THis need a bit of discussion, when you compare top-down and bottom up
parsing, but basically the bottom of the tree must be know correct
before the top can be.

More to the point, this is a consequence of the fact that the parse
tree produced with such a grammar will be structured to conform the
operator operand structure defined by priorities, up to idosyncrasies
of a CF grammar definition, which are ironed out in an abstract syntax
tree (AST). In other words, this gives the parse tree a shape that is close
to the shape desired for the AST (Thanks to Raphael for suggesting
comparison with the AST).

This is why such a grammatical definition is simpler to use to
generate the AST. More importantly, it was much more convenient in
older compilers and interpreters that did not use AST, as the parse
tree reflected the priority structure.

For example, the parse tree for x + x * x is

   E
 / | \
E  +   T
|     /|\
T    T * F
|    |   |
F    F   x
|    |
x    x

And the AST for x + x * x is

   +
 /   \
x     *
     / \
    x   x

It is derivable from the parse tree by moving all operators up one
edge on the preceding node, and then ignoring all non-terminals,
making each linear downward path a single edge. Essentially the same
shape.

This AST is the expression tree defined by the priorities, from which the meaning of the expression can be derived (by homomorphism), from which it can be evaluated or compiled.


Library functions are functions that somebody else coded, and are available for use.

User-defined functions are functions that the user defines. This is the case of the C/C++ main().

You can think of main() as a placeholder or hook. The user supplies it, but the standard library knows to call it after initializing itself.


Sanity check about a linear programming problem

I’d say the program is always feasible because x = y = 0 is a solution.

Most pairs a, b give a unique solution. Only certain pairs don’t.

Now it depends on the definition of “unbounded”. If we talk about the goal function, the minimum is always bounded by 0. If we talk about the points (x, y), they are unbounded if a <= 0 or b <= 0.


Reconstruct directed graph from list of ancestors for each node

Such a list can yield more than one graph. Consider 4: 1 2 3, 3: 2 1, 2: 1. One graph is $1\to 2, 2\to3, 3\to4$. A second graph is $1\to 2, 2\to3, 3\to4 , 2\to4$.


Showing $A-B$ is a CFL where $A$ is a CFL and $B$ is finite

Hint: If $A$ is context-free and $R$ is regular then $A \cap R$ is context-free.


Median of Medians Recurrence Relation for 3-grouping

You can use the inequality $\log (1+x) < x$ (valid for $x > 0$, where $\log$ is the natural logarithm), which follows from a Taylor expansion, to reason as follows:
$$
\log \left(\frac{n'}{3} + 1\right) =
\log \left(\frac{n'}{3} \cdot \left(1 + \frac{3}{n'}\right)\right) = \log \frac{n'}{3} + \log \left(1 + \frac{3}{n'}\right) < \log \frac{n'}{3} + \frac{3}{n'}.
$$
This shows (after some calculation) that you can remove the $+1$ and $+4$ in return for an additional constant additive term, that is, you can estimate your final line by
$$
c \left(\frac{n'}{3}+1\right) \lg \frac{n'}{3} + c\left(\frac{2n'}{3}+4\right) \lg \frac{2n'}{3} + M + c_1 n',
$$
where $M>0$ is some constant.


Definition of “K-fairness” with respect to concurrency?

Perhaps you should look for "bounded fairness", the property that something happens within the next $k$ times, where $k$ is the bound.


Detecting palindromes in binary numbers using a finite state machine

In a nutshell: As presented, with a single row of tiles, the tiling system is equivalent to a finite state automaton. It cannot recognize the set of palindromes which is context-free, but not regular.
However, if the tiling system is extended, allowing as many rows as needed (possibly with the addition of a column on each side), then it becomes as powerful as a linear bounded automaton, recognizing context-sensitive languages, and thus also palindromes. The last section is a simple set of tiles to recognize palindromes.

Recognizing palindromes with a single row of tiles

Regarding your tiling system, I am missing some
details. Is the number of tiles finite, or just the number of
different tile designs. More precisely, while the number of designs can be finite, i.e. the same for all sequences to be recognized, the number of tiles  of each design should be sufficient in number, which may depend on the sequence to be recognized, though each recognition would use only a finite number of tiles.

If the number of tile is finite, less than some fixed number $n$ that is independent of the sequence to be recognized, you can at
best recognize finite sets of sequences, which is much less than all regular languages.

Second point:  is the number of different colors
can be set at any value, the same for all sequences of the language to be recognized. If not you cannot recognize all regular languages.

If you have any number of tiles, finite number of designs, any number
of colors, that is indeed equivalent to finite state automata, where
the colors stand for the states, and the tiles stand for the
transitions.

I am assuming you have only a single row of tiles, with the blue at bottom, as seems to be implied by your drawing.

I do wonder whether It helps understanding. Maybe so?

As you said, palindromes do not form a regular set. One disputable
intuitive explanation is that palindrome recognition implies counting,
and finite state machines cannot count. But there are formal ways of
proving that.

The language of palindromes is actually a Context-Free (CF)
language. Context-free languages are strictly a superclass to regular
languages recognized with finite state automata. So any regular
language is context-free, but the converse is false. For example the
language of palindromes is CF but not regular.

Thus, palindromes cannot be recognized with a single row of tiles.

What more could be said.

Finite state automaton (FSA) is implicitely the name of a device that
has only a finite number of states, used to control a reading head
that read-input from left to right on a tape, without ever leaving the
input string area, and never writes.

Finite state machines are usually considered as doing the same, except
that some can also write on an output tape.

If we are not too attached to established terminology, we could try to
relax some of these constraints, while keeping the finite number of
states.

A first attempt could be to allow the head to move in any direction.

That gives you what is called a two-way finite state automata. They
seem more powerful, but it can be proved that they do no more than
FSA (whether deterministic or not).

Another possibility is to allow the automaton to overwrite the tape it
is reading, but still without ever leaving the area that was occupied
by the input string. This is called a linear bounded automaton
(LBA). The LBA is actually one of the most powerful automata there
is. They recognize all the context-sensitive (CS) languages, which
include the CF languages.

The problem is that they are so powerful that they are difficult to
control, analyze or use.  But they will recognize palindromes with a
finite number of states.

I have been excluding other type of automata which do have a finite number of state for control, but use unlimited memory, which one could perceive as having unbounded number of states.

Extending the tiling system

In FrankW's answer, it is shown that, by extending the tiling system
with several rows, one can recognize palindromes. He has there a very
interesting idea, which I am trying to push here.

It can be pushed further. If you allow an arbitrary number of rows,
and add a column on each side, it seems that the tiles can actually
mimic a linear bounded automaton.  Hence, it becomes a very powerful
computational system.

I am saying "it seems" because I did not go through all the tedious
details of the construction, but only tried to convince myself.

However, rather than go through even the basic aspects of the construction, which are already complex, I
will rely on existing results in automata theory.

A row of tiles may be seen as the configuration of a one-dimensional
bounded cellular automaton (BCA). Columns represent the evolution of individual cells.

The colors of left and right sides of tiles represent the information exchanged
between adjacent cells, while the top and bottom colors represent the state
of the cells before and after transitions.

So it seems that a BCA can be simulated by the extended tiling system.

David Milgram showed in 1976 that BCA can simulate a LBA.

Hence the extended tiling system can simulate a LBA.

The extended tiling system is therefore a very powerful computational
system, that can recognize context sensitive languages.

Hence the extended tiling system can recognize palindromes, among many other things.

Now, I am not giving you the details of the recipe to recognize palindromes and other things in this way, simply because it is very complicated, and no one would read it anyway, if I were able to write it without bugs.

A set of tiles to recognize palindromes

The general construction is far too complex to be used. However, here
is a simple set of tiles to recognize palindromes on the alphabet
$\{0,1\}$ as requested.

As one might expect it is symmetrical.

R and B stand for red and blue

Matching leftmost and rightmost symbol 1, and removing them

 1      1      0     1
R 1    1 1    1 1   1 R
 R      1      0     R

Matching leftmost and rightmost symbol 0, and removing them

 0      1      0     0
R 0    0 0    0 0   0 R
 R      1      0     R

Filling in the sides with fully red tiles

 R
R R
 R

Creating the bottom line in blue

 R
R R
 B

But this has nothing to do with finite state machines, as far as I can tell.


Determine whether the $k^{th}$ smallest element in max-heap is greater than a given number

Here is an attempt at disproof:

Suppose we have a max-heap of $n$ elements such that $k<\log n$ and I inform you that the $k^{th}$ smallest element is at the greatest depth of the tree. Without this detail, it could be elsewhere in the tree, but if we cannot solve this special case in time $O(k)$, the more  general case will take at least as much time - otherwise, we could use the algorithm for the general case to solve this specific case.

Note that in a max-heap, no node will give a bound on how small its children will be (but rather only how large). Thus, if we know the $k^{th}$ smallest is at the greatest depth, no node except those at the greatest depth will provide any information as to the location of the $k^{th}$ smallest element. There are $\log n$ children at the greatest depth and no particular ordering among them (which is one of the key characteristics which differentiates a heap from a sorted binary tree). Thus, you'll need to check all $\log n$ elements before you can determine whether the $k^{th}$ smallest is greater than an arbitrary number.

Hence, no comparison based algorithm with time complexity less than $O(\log n)$ exists to determine for a given max-heap whether the $k^{th}$ smallest element is greater than an arbitrary number.


Single-source shortest paths with even weight

Forget the even-length requirement for a moment and consider how something like Dijkstra's algorithm works.  As the algorithm progresses, you have essentially two types of vertex: the ones for which you've already figured out the shortest path, and the ones for which you only have an upper bound (i.e., the shortest path you've seen to that vertex so far).

Modify it so there are three types of vertex: ones for which you've figured out the shortest even-length path, ones for which you've figured out the shortest path but it was odd, and ones for which you only have an upper bound for the shortest path and shortest even path.


The following is unsatisfiable:
$$
(x \lor y) \land (x \lor \lnot y) \land (\lnot x \lor z) \land (\lnot z \lor w) \land (\lnot z \lor \lnot w) \land (y \lor w).
$$
This contains every variable exactly three times, not all of them of the same polarity. If you allow variables to appear less than three times, you can drop the last clause $y \lor w$.


Understanding pipeline stalls (bubbles) based on stage

A CPU pipeline has a number of stages.

The exact stages vary between CPUs and some CPUs have very many stages, but obviously the first stage must be Instruction Fetch (IF) and the second stage must be Instruction decode (ID).
If an instruction is not in the cache it cannot be fetched and delays occur.
Let's call our missing instruction $A$.

The only way for the next instruction $B$ to not be delayed is if $B$ is in the cache and the CPU supports out of order instruction and $B$ does not depend on the outcome of instruction $A$ and the CPU allows fetching from memory and the cache at the same time and the CPU knows where $B$ is located.

Phew that's a lot of if's.
Let's unpack the various issues.

Cache
Because barring jumps instructions are fetched sequentially it's moderately unlikely that $A$ is not cached, whilst $B$ is. But it does happen.

Out of order support
Most CPU's support OoO execution, so there are no problems there.

Independent instruction
Some instructions have no dependencies. e.g. xor rax,rax will zero out rax no matter what.
However we don't know what instruction $A$ does. If it's an unconditional jump it may just jump over $B$.
Still the CPU might elect to execute B speculatively, if the gamble pays off valuable time is gained.

Fetching from memory and cache at the same time
Current x86/x64 CPU's do not support this.
The reason why will become clear in the next paragraph.

Where is $B$ located?
The x86 architecture has a variable length instruction.
A x86/x64 instruction can be anywhere between 1 and 15 instructions long.
Only when the pipeline gets to the Instruction Decode (ID) stage does the CPU know how long the instruction is.
So there is no way for the CPU to know where $B$ starts until $A$ has been decoded.
In normal execution the CPU solves this by either (a) pre-decode instructions and store the instruction lengths in the cache (as meta data), or (b) fetch large chunks of data in one go and parallel decode this or both.
Intel uses strategy b, AMD uses a+b.

However it is impossible to know where $B$ starts without knowing the instruction length of $A$.
There are 15 possible lengths and the CPU will not start 15 possible speculative executions, that's would just be a waste of silicon :-).

If the x86 architecture had fixed instruction length then speculative execution would have been an option. The fetch and decode stages pose no problem and perhaps even more stages could be performed.
However CISC and variable instruction length throws a big spanner in the works.

  Can a pipeline stall be triggered at any given stage in the clock cycle, or is it restricted to the fetch and execute stages?

The details are very complex, but, yes, a stall can and does occur at every stage.
Common stall reasons are:

mispredicted jumps. This causes a stall because the pipeline needs to be emptied and reread from some as yet unknown address.
instruction $B$ depends on the outcome of instruction $A$. This is called a dependency chain. These chains can be arbitrary long.
both instructions $A$ and $B$ require some piece of expensive hardware. The CPU has only one of these available and thus $B$ must wait for $A$ to finish.

  If a pipeline stall occurs due to two stages trying to use the same resources for instruction, does the clock cycle delay by one cycle

That depends if the resource allows pipelining.
In modern CPU's the answer is yes. Expensive hardware is capable of pipelined operation.
E.g. two multiplication instructions will execute in 4 cycles given that a MUL reg,reg has a 3 cycle latency and a third unrelated instruction can execute in parallel.

  would it stall for an infinite amount of time until a new instruction was in line from main memory - potentially causing the last operation to never execute?

Yes, e.g. if the memory has been swapped out to disk and the disk takes indefinitely long the CPU will just wait.
Well the hardware will generate a page fault exception, but that's beside the point


1D Peak-finding problem, how to derive the formula?

Your guess is absolutely correct. The time taken to process an array of length $n$ is the time taken to choose which half to recurse on, plus the time taken to do the recursion. Doing the recursion takes time $T(n/2)$, since $T(m)$ is, by definition, the time taken to process an array of length $m$. Choosing which half to recurse on takes some constant number of steps, which is what $\Theta(1)$ means.  So this gives us that $T(n) = T(n/2) + \Theta(1)$. And, implicitly, $T(1)=\Theta(1)$ since, if the array has length one, there's no recursion to do.

How to solve that recurrence to get $T(n)=\Theta(\log n)$ is covered by our reference question. A rough-and-ready way to see it is to observe that the length of the array halves on each recursive call, so the number of recursions before we reach a single-element array is the answer to the question "How many times can I divide $n$ by two before I get $1$?", which is $\log_2 n$.


CFL not closed under intersection while Turing Decidable are

Yes, all CFLs are Turing-decidable but a subset of an intersection-closed class of languages is not necessarily intersection-closed. CFLs and Turing-decidable languages are just one example of this.  In fact, this is not an unusual situation:

Theorem. Let $\mathcal{L}$ be an intersection-closed class of languages containing languages $L_1$ and $L_2$ such that $L_1\cap L_2\neq L_1$ and $L_1\cap L_2\neq L_2$.  There is a class $\mathcal{L}'\subset\mathcal{L}$ that is not intersection-closed.

Proof. Just take $\mathcal{L}' = \mathcal{L}\setminus \{L_1\cap L_2\}$.  $\mathcal{L}'$ contains $L_1$ and $L_2$ but does not contain their intersection, by construction. $\quad\Box$

The simplest possible example is the class of languages $C = \big\{\emptyset, \{a\}, \{b\}\big\}$.  This is closed under intersection but the subclass $C' = \big\{\{a\}, \{b\}\big\}$ is not, since $\{a\}\cap\{b\}=\emptyset\notin C'$.

Conversely, a superset of an intersection-closed class of languages is not necessarily intersection-closed.  Here's an example. Let $\mathcal{R}$ be the class of all Turing-decidable languages. Fix some coding of Turing machines and let $H$ be the language of codings of all Turing machines that halt when given empty input. It is well known that $H$ is undecidable, so $H\notin\mathcal{R}$.  I claim that $\mathcal{R}' = \mathcal{R}\cup\{H\}$ is not closed under intersections. To see this, let $h$ be any string in $H$ (for example, $h$ could be the coding of some program that just loops for all input). The language $L = \{w\mid w\neq h\}$ is clearly in $\mathcal{R}$.  $L\cap H\neq H$, since $h\in H$ but $h\notin L\cap H$. And $L\cap H\notin\mathcal{R}$ since the language of all Turing machines except for $h$ that halt when given empty input is also undecidable. Therefore, $\mathcal{R}'$ is not closed under intersections, since $L\in\mathcal{R}'$, $H\in\mathcal{R}'$ but $L\cap H\notin\mathcal{R}'$.


Number of leaf nodes in n-element red-black trees

By definition, a red-black tree is a full binary tree in which each node is assigned either red or black and the leaves are labeled as NIL-node while internal nodes are labeled as non-NIL node. In a full binary tree all of the nodes have either 0 or 2 children. Thus, assuming that a full binary tree has n internal nodes, the number of leaf nodes will be n + 1. So what you are asking is: if red-black tree has n non-NIL nodes why does it have n+1 NIL-nodes ?


Finding both the longest and shortest path in a convex polygon

The shortest path will be made out of straight lines connecting A, B and the vertices of S.

The most simple solution is to check a bunch of paths, starting with path AB; then AXB and AYB where X and Y are the topmost and bottommost points of S; then extending to the left or right neighbors of X and Y, if some intersections happen.

A smarter solution would be to find the points P, minimizing and maximizing the angle between $\vec {AP}$ and $\vec {AB}$. Those will be the points where your path enters and leaves S.

The longest path is, obviously, infinite.


Are references of any use without updating?

References are useful even if you don't update the object, since copying objects takes memory and time. When passing a reference, only a pointer is passed. But suppose that you were passing a string - it could take far longer to copy the entire string. This is why language like C++ support constant references, which are references that cannot be updated.


Showing that an equivalence relation on programs need not be a congruence

Let $x,y$ be two fixed distinct variable names.

Call $P$ and $Q$ equivalent iff $Q$ is obtained from $P$ by optionally swapping the variable names $x$ and $y$. That is, either $Q=P$ or $Q=P\{x/y,y/x\}$ where the latter uses simultaneous substitution.

It is an equivalence. Reflexivity follows by construction. For symmetry, $P\equiv Q$ swaps if $Q\equiv P$ swaps. For transitivity, we consider the four cases: in the swap-swap case we get the same program back.

It is not a congruence since

$$
x:=x+1 \equiv y:=y+1 \quad \mbox{ but }\quad (x:=0;x:=x+1) \not\equiv (x:=0;y:=y+1)
$$

Less formally, you can build many examples as follows. Take $f : \mathbb N \to \mathbb N$ to be a function which does NOT in general satisfy

$$
f(n)=f(m) \implies f(n+1)=f(m+1)
$$

Say, $f$ is a hash function.

Then, we can say $P\equiv Q$ whenever $f(\# vars(P))=f(\# vars(Q))$, where $\#vars$ counts the number of variables.

This is an equivalence (trivially), but not a congruence since if we add another fresh variable to both $P,Q$ we increment their variable count by one, but $f$ does not preserve that value in general.


See: Hurtado and Noy, Graph of triangulations of a convex polygon and tree of triangulations, Computational Geometry 13 (1999) pp179–188.
Section 3 of that paper gives a relatively straightforward method for constructing all triangulations of $n+1$-gons given all triangulations of $n$-gons.


What are algorithms for computing contours from given edges?

This problem is not surprisingly called Concave Hull
You might be also interested in alpha shapes
CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS by Adriano Moreira and Maribel Yasmina Santos


Runtime of algorithm to transpose a graph

It all depends on how exactly you store the graph. For example:

If you store the graph as an adjacency matrix, the complexity is $\Theta(|V|^2)$.
If you store the graph as a linked list of edges per vertex (i.e., adjacency lists), then the complexity is $\Theta(|V|+|E|)$.
If you store the graph as a linked list of all edges (and don't store the vertices explicitly), then the complexity is $\Theta(|E|)$.

The representations usually used are the first two. I have never heard of the third being used. In most cases, the number of edges exceeds the number of vertices, and so there would be the third method would have no advantage over the second one, but it would have many disadvantages.


n mod 4 asymptotic analysis best case and worst case

Best case and worst case are about the complexity for a fixed input length. As an example, suppose we are sorting an array of length $n$. There are many possible arrays of length $n$. On some of them the algorithm will be faster, on some it will be slower.

In your case, in contrast, the running time doesn't depend on the input, but only on its length. Therefore the best case and the worst case are both
$$
\begin{cases}
\Theta(n^2) & \text{if } n \equiv 0 \pmod{4}, \\
\Theta(n^3) & \text{if } n \equiv 1 \pmod{4}, \\
\Theta(n^4) & \text{if } n \equiv 2 \pmod{4}, \\
\Theta(n^5) & \text{if } n \equiv 3 \pmod{4}.
\end{cases}
$$


Is this an instance of a well-known problem?

Isn't this a case of max-flow?

Model your problem as a bipartite graph, from ball to boxes, with an edge from each ball to the boxes with matching colour. Each of these edges has capacity 1. Now add source and target vertices. From source to each ball with capacity 1. From each box to target, capacity is the capacity of the box.

Now you want to enumerate all solutions to this max-flow problem (i.e., output all flows whose value achieves the maximum possible). But that might be a lot of solutions!

(edit) A recent update has added scores to the balls, and the target is to maximize the scores of the balls that are put into the boxes. I would suggest maximal bipartite matching where you have as many copies of nodes for each box as the capacity of that box. As there will be balls that do not fit into the boxes I would suggest adding boxes for overflow balls (to obtain complete matching, when necessary). Wikipedia suggests the Hungarian algorithm.


How do I show that an equivalence class of a language containing an empty string is infinite

Let $A$ be the alphabet. I suppose that the equivalence you are referring to is the equivalence $\sim$ defined on $A^*$ by $u \sim v$ if and only if, for all $x \in A^*$,
$$
  ux \in L \Leftrightarrow vx \in L
$$
Now suppose there is a word $u \in A^+$ such that $u \sim \varepsilon$. Then by definition, $x \in L$ if and only if $ux \in L$. It follows by induction on $n$, that for all $n > 0$, $x \in L$ if and only if $u^nx \in L$ and thus $[\varepsilon]$ contains $u^*$. If the alphabet is nonempty, it follows that $[\varepsilon]$ is infinite.


An online algorithm to maintain the Pareto frontier elements

You can find an answer to this in "Dynamic Planar Range Maxima Queries", by Brodal and Tsakalidis. They support insert and remove in $O(\log n)$ time. That paper points to several previous papers that addressed the question as well.

In particular, I expect the simplest solution can be found in sections 8 and 9 of "Maintenance of Configurations in the Plane", Technical Report RUU-CS-79-9, by Overmars and van Leeuwen, (mirror). Their solution takes $O(\log^2 n)$ for each insert or remove.


Prove L to not context free using pumping lemma on language L

Hints

What is the language $K = L \cap 0^*10^*1$ ?
Apply the pumping lemma to $K$ (or to $L$ directly).


Minimising sum of consecutive points distances Manhattan metric

Your problem is very close to TSP on the plane with the L1 metric. For this problem, there is a PTAS due to Arora, while the problem itself is probably NP-hard. Practically speaking, if your goal were indeed TSP rather than its "Hamiltonian path" variant, you could apply any approximation algorithm that works for metric TSP.


What is the difference between $x:A$ and $x \Xi A$?

$x:A$ is a statement about objects in the formal system, like, for example, $\vdash 2+4:\texttt{int}$, whereas
$x\Xi A$ is an expression in the formal system, like $\texttt{if}~ 2 + 4 ~\texttt{==}~5 ~\texttt{then}~ e_1~ \texttt{else} ~e_2$.


How can I use prefix sum of an array to solve this problem?

Consider a new type of query (t2q, type 2 query) of the form $(index, value)$ where we add $value$ to all items from $index$ to the end.

Then the original type of query (t1q, type 1 query) is equivalent to 2 t2q. $(lower, upper, value) \equiv (lower, value) \oplus (upper+1, -value)$. Notice that the second t2q cancels the first t2q over all items that should not be affected

Now, 2 t2q with the same $index$ could be reduced to a single t2q easily. $(index, valueA) \oplus (index, valueB) \equiv (index, valueA+valueB)$. Therefore, we have at most $N=\text{size of our vector}$ type 2 queries. In other words, we can store all those queries in a vector. And if there is an $index$ with no query associated, we just create a "dummy query" using the identity element of our operation (zero in this particular problem).

$$
(index, value) \equiv t2q[index]=value
$$

Next, a particular item in our vector $v[j]$ is only affected by a t2q iff $index <= j$. In other words, $v[j]$ is affected by all type 2 queries with lower $index$. To calculate the value of a particular $v[j]$ just add all $values$ of t2q with lower $index$ and add the value of $v[j]$ which is zero.

$$
v'[j] = v[j] + \sum_{i=0}^j{t2q[i]} = \sum_{i=0}^j{t2q[i]}
$$

If we iterate from the beginning, then each item can be calculated in $\mathcal{O}(1)$ if we store the previous sum. And simultaneously, we look for the maximum.

$$
v'[j+1] = \sum_{i=0}^{j+1}{t2q[i]} = t2q[j+1] + v'[j]
$$

Edit

This approach will take $\mathcal{O}(M+N)$-time and $\mathcal{O}(N)$-space, because we first process every query in $\mathcal{O}(1)$ (updating two positions in our vector), adding $\mathcal{O}(M)$, and then we spend $\mathcal{O}(N)$ looking for the maximum.

Like you said, there are $\mathcal{O}(M)$ values different than zero in $t2q$. We can ignore those zeros using a Self-balancing Binary Search Tree instead of a vector. Then we go from $\mathcal{O}(1)$ to $\mathcal{O}(lg\,M)$ while updating every entry (process every query) and from $\mathcal{O}(N)$ to $\mathcal{O}(M)$ for store all those entries.

So now, we first spend $\mathcal{O}(M\,lg\,M)$ to process all queries ($\mathcal{O}(M)$ insertions of $\mathcal{O}(lg\, M)$. Then we traverse in-order looking for the maximum using the previous idea in $\mathcal{O}(M)$.

$$
v'[j] = t2q[j] + v'[i] \, \text{iff} \, (index, 0) \, \forall i < index < j
$$

Finally, this new approach takes $\mathcal{O}(M\,lg\,M)$-time ($\mathcal{O}(M\,lg\,M)$+$\mathcal{O}(M)$) and $\mathcal{O}(M)$-space. Even better, is (reasonably) independent $N$ (now we can handle $N \approx 2^{64}$).


How does Logical Block Addressing affect OS disk scheduling optimizations such as SCAN (Elevator Algorithm)?

You are right, this could be a problem.

In older disks, the physical block number corresponds to the actual location of the block on the disk.  So, that algorithm makes sense.

Newer disks do fancier stuff.  They have firmware that might remap blocks around to different locations, so that the physical block number no longer corresponds to the actual location of the block on disk in all cases (two blocks with similar physical block number might be far apart in actuality).  Because this can screw up OS scheduling algorithms, disk firmware generally tries to avoid this situation where possible, but it can happen.

It gets especially tricky with SSDs, which have very different performance properties than hard disks, but which must (for backwards compatibility) use an API originally designed for magnetic disks.  So, modern SSD's do clever things to try to ensure that typical OS scheduling algorithms will still yield reasonable results, even though the physical block number doesn't necessarily correspond to the actual physical location of where the data is stored on the SSD.


Coloring grid with flexible number of colors and flexible number of occurrence per color

You're asking for a $k$-coloring of a grid graph (with some extra constraints on how many times each color is used).

One approach is to encode this as an instance of SAT or integer linear programming (ILP), and let a SAT/ILP solver look for a solution for you.  For instance, you could introduce zero-or-one variables $x_{r,s,t}$, where $x_{r,s,t}=1$ if row $r$ column $s$ has color $t$, and then write down constraints to capture that this is a valid coloring (i.e., $x_{r,s,t} + x_{r',s',t} \le 1$ when $(r,s)$ and $(r',s')$ are adjacent, $\sum_t x_{r,s,t} = 1$, and $\sum_{r,s} x_{r,s,t} \le i_t$), then feed it to an ILP solver.

Related (but different): Number of ways to fill a 2xN grid with M colors, Counting Colorings of a Grid.


Hash table open addressing without dummy

I came up with and algorithm of moving the last non-Null element of the probe sequence to the place of the deleted element to make the probe sequence contiguous. But this would make it impossible to retrieve the moved element if its hash index value was greater than that of the removed element.
So is there any correct algorithm for this?

Yes. There is a "shift deletion" scheme, that is described, for example, in this answer.
BTW, in the state of the art open-addressing hash table implementations, SwissTable and F14 "dummy" elements rather than "shift deletion" are used, but insertion of "dummy" elements (or "tombstone" or "deleted", as they are also called) is avoided very often in practice.


Hint: consider cases where every weight is very large.


Mapping categorical data in K-nearest neighbour

You can map M to 0 and F to 1.  In general, if you have N categories, you can map each category to a number in the range 1,2,..,N.  If N=2, this is fine for a k-nearest neighbor classifier.

If N>2, this is not a good idea for a k-nearest neighbor classifier, as it makes some assumptions (e.g., that the first category is more similar to the second category than the third).  If you want to use a k-nearest neighbor classifier and you have no knowledge about the meanings of the categories, the best you can do is to use a one-hot encoding.  If you do have some knowledge about the meanings of the categories, the best you can do is to define a distance function or similarity function between categories, and use that directly (instead of mapping the categories to numbers).


Is it NP-complete to decide if chromatic and clique numbers agree?

Your problem is NP-complete. See for example this question on ResearchGate.

Your problem is in NP because to show that $\omega(G) = \chi(G)$ it is sufficient to exhibit a $k$-clique and a $k$-coloring, for some $k$.

Your problem is NP-hard by reduction from 3COL. Given a graph $G$, first check whether it contains a $K_4$, and if so output some trivial No instance (say a $5$-cycle). Otherwise, add a triangle to your graph. The original graph is 3-colorable iff the new one satisfies your condition.


How to prove the optimality of the "patience sort" algorithm?

The weak duality principle says that given any play of patience solitaire, the number of piles (at the end) is no less than the length of any Increasing Subsequence (IS) of the initial sequence of cards.
In particular, the min number of piles is no less than the length of the longest IS of the initial sequence of cards. That is, the weak duality implies the following direction of the strong duality:
$\quad$  Min number of piles $\ge$ max length of an IS.

Claim: We have
$\quad$  Min number of piles $\le$ max length of an IS.
Proof. Instead of proving using variables that represent general situations, I will use proving by illustration, which should convince a reasonable human.
Look at this picture, which is also embedded in the question. It shows the situation at the end of patience solitaire using greedy algorithm, starting with sequence 6,3,5,10,J,2,9,A,K,7,4,8,Q of spades.
Consider the queen of spades. At the time when it was to be placed on the last pile, it must appear later than all cards in the previous piles in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards in the piles before the last pile. In particular, it must be larger than the uncovered card in the second last pile, which was the 8 of spades. So, we have
$\quad$ $8,$ Q
as an IS of the initial sequence.
Consider the 8 of spades. At the time when it was to be placed on second to last pile, it must appear later than all existing cards in the piles to its left in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards to its left. In particular, it must be larger than the uncovered card immediately to its left, which was the 7 of spades. So, we have
$\quad$ $7, 8$
as an IS of the initial sequence.
Consider the 7 of spades. At the time when it was to be placed on third to last pile, it must appear later than all existing cards in the piles to its left in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards to its left. In particular, it must be larger than the uncovered card immediately to its left, which was the 5 of spades. So, we have
$\quad$ $5, 7$
as an IS of the initial sequence.
And so on.
In the end, combining all ISs obtained, we will have,
$\quad$ $3,5, 7, 8,$ Q,
as an IS of the initial sequence.
We can see that every pile contributes exactly one item to the IS. Hence, the number of piles is the same as the length of that IS. So, the number of piles (at the end of greedy algorithm) is at most the length of the longest IS of the initial sequence.
So, the min number of piles for all playing strategies, including the greedy algorithm, is at most the length of the longest IS of the initial sequence. $\quad \checkmark$.
The proof above is basically an expansion of the instruction, "follow pointers to obtain IS whose length equals the number of piles" in the lecture note from Princeton quoted in the question. By the way, we can also use the subsequence $3,5,10,$ J, A or one of many other subsequences to the same effect.

Combining both "$\ge$" and "$\le$", we should obtain the equality in the strong duality. Moreover, the proof above shows the greedy algorithm finds both numbers (or, that one number).

Exercise (easy):
Let $P_1, P_2, \cdots, P_k$ denote the piles we have obtained at the end of the greedy algorithm in its natural order. Show that card $c$ is in $P_i$ iff the longest IS of the initial sequence that ends at $c$ is of length $i$.


How many possible policies in a Markov Decision Process?

Looks like you are a bit confused by the notion of MDP policy. There's a detailed discussion with lots of examples in this question.

A policy is any possible strategy in a given environment. Example: "go $East$ in any state" is a valid strategy in your MDP (though maybe not optimal), as well as "go $West$ in any state".

So there are 3 states and 2 possible actions per each, hence $2^3=8$ possible strategies: $EEE$, $EEW$, ..., $WWW$.


Is a single string enough to prove regular expressions inequivalent?

Does it suffice to show that a single string is not present in the language and hence its different from the rest?

Yes. It's actually a very neat proof.

Formally speaking, you have found $w \in \{a,b\}^*$ with $w \in L_1$ but $w \not\in L_2,L_3,L_4$. That is sufficient to show that $L_1 \neq L_2$, $L_1 \neq L_3$ and $L_1 \neq L_4$.

You have not shown that $L_2 = L_3 = L_4$. The phrasing of the question seems to suggest as much (MC questions are boring!) but you may want to prove that as an additional exercise.

   Hint: Translate into NFA, determinize, minimize, check for isomorphy.


Compute the union of two sets between two endpoints minimizing communication complexity

You can do this with $O(K \log N)$ bits of communication on average, where $K$ is the size of $|(A\setminus B) \cup (B\setminus A)|$, assuming you are willing to use a non-interactive protocol and are willing to accept a randomized protocol.

Let $H(\cdot)$ denote a randomized hash function.  Do binary search on $i$ to find the smallest $i$ such that $H(a_1,\dots,a_i) \ne H(b_1,\dots,b_i)$, i.e., (ignoring hash collisions) such that $a_i \ne b_i$.  Then you know that $a_1=b_1$, ..., $a_{i-1}=b_{i-1}$ and $a_i \ne b_i$.  Thus $a$ can send $a_i$ to $B$.  You can use a $O(\log N)$-bit hash function and the probability of a hash collision can be made exponentially small.  This takes $O(\log N)$ iterations of binary search, and in each iteration of binary search you send a $O(\log N)$-bit hash, so in all you send $O((\log N)^2)$ bits of information.  At the end we have sent one of the $K$ elements from $A$ to $B$.  Now you can repeat on the remaining elements (after discarding $a_1,\dots,a_i$ from both $a$ and $b$'s sets).  You repeat at most $K$ times, so this gives a protocol that requires sending $O(K (\log N)^2)$ bits.

You can reduce this to $O(K \log N)$ bits by using a shorter hash.  First do binary search using a 1-bit hash, to find the smallest $i$ such that $H(a_1,\dots,a_i)_1  \ne H(b_1,\dots,b_i)_1$, where $H(\cdot)_b$ denotes the first $b$ bits of the hash $H(\cdot)$.  This  takes $O(\log N)$ iterations.  Then, by using backtracking, you can find the smallest $i$ such that $H(a_1,\dots,a_i)_2  \ne H(b_1,\dots,b_i)_2$ , using on average $O(1)$ iterations.  Then find the smallest $i$ such that $H(a_1,\dots,a_i)_4  \ne H(b_1,\dots,b_i)_4$, and so on, in each stage doubling the length of the hash.  Each stage uses on average $O(1)$ iterations.  If you sum the series of the number of bits sent, it sums  to $O(\log N)$.

Thus, we get an improved protocol that requires sending $O(K \log N)$ bits on average.  It does require interaction between $a$ and $b$ to enable the binary search, and it is randomized.

I don't know whether there is a non-interactive protocol with similar complexity, or whether the protocol can be derandomized to achieve $O(K \log N)$ bits in the worst case rather than in the average case (or rather than an exponentially small probability of sending more than $O(K \log N)$ bits).


What's the big deal with the knapsack problem?

I think mainly the techniques that are covered in that section (dynamic programming and greedy algorithms) are very important.

There are several other properties. First of all, integral knapsack problem belongs to the famous class of problems called NP-complete (there is no known polynomial time algorithm for them), while the fractional knapsack is polynomial time solvable using a greedy algorithm. Thus, as an algorithm designer, you need to be able to recognize the difference between the nature of these two problems in order to solve them.

Also, one interesting point is that, although the dynamic programming technique is psuedo-polynomial time for the integral knapsack problem, it can be run exponentially in general case.


Why doesn't Dijkstra's use a shortest-path first search?

Congratulations! You have discovered an interesting variation of Dijkstra's algorithm.

However, it is misleading to state the standard version of Dijkstra's algorithm (stDA) described here as mentioned in the question does not use a shortest path first search. You might have overlooked the following statement in that article

  We now need to pick a new current node. That node must be the unvisited node with the smallest minimum distance.

In fact, using a shortest path first search so that the weight of each edge is checked at most once is the hallmark of Dijkstra's algorithm. That is the main reason that your algorithm can be labelled as a variation of Dijkstra's algorithm.

While the neighbours of each node are selected in no specific order in stDA, the same unorderly selection is also done in your algorithm in the following lines

        for v2, v1_to_v2_dist in graph[v1].items():
            # code to record the distance to v2 via v1.

Instead of including each vertex exactly once in the priority queue of unvisited vertex as in stDA,  your algorithm pushes each vertex multiple times, once for every path that could possibly be the shortest path to that vertex at the moment that path is found. (This might make your algorithm slightly slower than stDA, since the number of operations to insert a new  distance-vertex pair into the bigger min-heap in your algorithm will probably be more than the number of operations in the stDA needed to update the shortest distance so far to that vertex. For example, when the new distance is not shorter than the shortest distance so far.)

Instead of the separate relaxation step as in the stDA, your algorithm cleverly accomplished the object of the relaxation step in the same step that selects the shortest path to an unvisited vertex by also ignoring all other paths to visited vertices. It is fair to say your algorithm includes the relaxation step implicitly.

Overall, your algorithm is slightly easier to code than the stDA.


checking whether turing machine passes at least k>2 states before accepting a word

Clearly $L$ is acceptable (just simulate $M$ and keep track of the number of distinct states encountered during the simulation). We now show that it is not decidable.
If $L$ were decidable, you would be able to solve the Halting problem as follows:
given a TM $T$ and an input $x \in \Sigma^*$, construct a TM $M$ that ignores its input, simulates $T$ with input $x$ and, when the simulation is complete, accepts.
You can further ensure that, if $M$ accepts, then it also traverses at least $3$ distinct states by just transitioning from the initial state to another (distinct) state before starting the simulation of $T$.
Now check whether $\langle M, 3 \rangle \in L$. If the answer is affirmative, then there is some $w \in \Sigma^*$ for which $M(w)$ accepts, showing that $T(x)$ halts.
If the answer is negative then $M$ never halts, showing that $T(x)$ does not halt.


How many pairs of brackets are sufficient to make Brainfuck Turing complete?

I'm not 100% sure that it's impossible to do this with two sets of brackets. However, if the cells of the BF tape allow unbounded values, three sets of brackets are enough. (For simplicity, I'll also assume that we can move the tape head left past its starting point, although because this construction only uses a finite region of the tape, we could lift that restriction by adding sufficiently many > commands at the start of the program.) The construction below requires assuming Artin's conjecture to be able to compile arbitrarily large programs; however, even if Artin's conjecture is false, it will still be possible to show Turing-completeness indirectly via translating an interpreter for a Turing-complete language into BF using the construction below, and running arbitrary programs via giving them as input to that interpreter.

The Turing-complete language that we're compiling into unbounded BF is The Waterfall Model, which is one of the simplest known computational models. For people who don't know it already, it consists of a number of counters (and initial values for them), and a function $f$ from pairs of counters to integers; program execution consists of repeatedly subtracting 1 from every counter, then if any counter $x$ is 0, adding $f(x,y)$ to each counter $y$ (the program is written in such a way that this never happens to multiple counters simultaneously). There's a Turing-completeness proof for this language behind my link. Without loss of generality, we'll assume that all counters have the same self-reset value (i.e. $f(x,x)$ is the same for all $x$); this is a safe assumption because for any specific $x$, adding the same constant to each $f(x,y)$ will not change the behaviour of the program.

Let $p$ be the number of counters; without loss of generality (assuming Artin's conjecture), assume that $p$ has a primitive root 2. Let $q$ be $p(1+s+s^2)$, where $s$ is the lowest power of 2 greater than $p$. Without loss of generality, $2q$ will be less than $2^p$ ($2q$ is bounded polynomially, $2^p$ grows exponentially, so any sufficiently large $p$ will work).

The tape arrangement is as follows: we number each counter with an integer $0 \leq i < p$ (and without loss of generality, we assume that there's a single halt counter and number it $2$). The value of most counters is stored on tape cell $2^i$, with the exception of counter 0, which is stored on tape cell $2q$. For each odd-numbered tape cell from cell -1 up to and including $2^{p+1}+2p+1$, that tape cell always holds 1, unless it's immediately to the left of a counter, in which case it always holds 0. Even-numbered tape cells that aren't being used as counters have irrelevant values (which might or might not be 0); and odd-numbered tape cells outside the stated range also have irrelevant values. Note that setting the tape into an appropriate initial state requires initialising only finitely many tape elements to constant values, meaning that we can do it with a sequence of <>+- instructions (in fact, only >+ are needed), thus no brackets. At the end of this initialisation, we move the tape pointer to cell -1.

The general shape of our program will look like this:

  initialisation [>>>[ >$\times(2^p-1)$ [ <$\times(2p)$ ]>-] adjustment <<<]

The initialisation puts the tape into the expected shape and the pointer on cell -1. This is not the cell to the left of a counter (0 is not a power of 2), so it has value 1, and we enter the loop. The loop invariant for this outermost loop is that the tape pointer is (at the start and end of each loop iteration) three cells to the left of a counter; it can be seen that the loop will thus only exit if we're three cells to the left of counter 2 (each other counter has a 1 three cells to its left, as to have a 0 there would imply that two counters' tape positions were 2 cells apart; the only two powers of 2 that differ by 2 are $2^1$ and $2^2$, and $q$'s binary representation changes from strings of $0$s to strings of $1$s or vice versa at least four times and thus cannot be 1 away from a power of 2).

The second loop repeatedly loops over the counters, decrementing them. The loop invariant is that the tape pointer is always pointing to a counter; thus the loop will exit when some counter becomes 0. The decrement is just -; the way we get from one counter to the next is more complex. The basic idea is that moving $2^p-1$ spaces to the right from $2^x$ will place us on an odd-numbered cell $2^p+2^x-1$, which is to the right of any counter ($2^p$ is the last counter, $2^x-1$ is positive because $x$ is positive); modulo $2p$, this value is congruent to (by Fermat's Little Theorem) $2^x+1$. The innermost loop repeatedly moves left by $2p$ spaces, also not changing the index of the tape cell modulo $2p$, and must eventually find the cell congruent to $2^x+1$ modulo $2p$ that has the value (which will be the cell to the left of some counter); because of our primitive root requirement there's exactly one such cell ($2q-1$ is congruent to $-1$ modulo $2p$, and $2^{\log_{2,p}(r)+1}-1$ is congruent to $2r-1$ for any other $r$, where $\log_{2,p}$ is the discrete logarithm to base 2 modulo $p$). Additionally, it can be seen that the position of the tape pointer modulo $2p$ increases by $2$ each time round the middle loop. Thus, the tape pointer must cycle between all $p$ counters (in order of their values modulo $2p$). Thus, every $p$ iterations, we decrease every counter (as required). If the loop breaks partway through an iteration, we'll resume the decrease when we re-enter the loop (because the rest of the outermost loop makes no net change to the tape pointer position).

When a counter does hit 0, the middle loop breaks, taking us to the "adjustment" code. This is basically just an encoding of $f$; for every pair $(x,y)$, it adds $f(x,y)$ to the tape element which is the same distance left/right of the current tape pointer as counter $y$'s tape location is left/right of counter $x$'s tape location (and then removes the tape pointer back to where it started). Whenever $x\neq y$, this distance turns out to be unique:

The difference between two powers of 2 is a binary number consisting of a string of 1 or more $1$s followed by a string of 0 or more $0$s (with the place values of the start of the number, and the start of the $0$ string, depending on the larger and smaller respectively of $x$ and $y$); thus all those differences are distinct. * As for the difference of a power of 2 and $q$, it must contain at least two transitions between strings of $1$s and $0$s ($q$ contains at least four such transitions, the subtraction can only remove 2), thus is distinct from all differences of two powers of two, and these differences are obviously also distinct from each other.

For $x=y$, we obviously find that the distance moved is 0. But because all $f(x,y)$ are equal, we can just use this as the adjustment for the current cell. And it can be seen that the adjustment code thus implements the "when a counter hits 0" effect for every counter; all the cells that actually represent counters will be adjusted by the correct amount, and all the other adjustments will affect non-counter even-numbered cells (the difference between two even numbers is even), which have no effect on the program's behaviour.

Thus, we now have a working compilation of any program in The Waterfall Model to BF (including halt behaviour, but not including I/O, which isn't needed for Turing-completeness) using only three pairs of brackets, and thus three pairs of brackets are enough for Turing-completeness.


Using oracle machine to speed up tree solution search

Here is an algorithm that will work in some cases: guess the first $n-k$ bits of the solution; fix them; and then solve the sub-problem where you ask what the remaining $k$ bits are.  In other words, iterate over all $2^{n-k}$ possibilities for the first $n-k$ bits, and for each such choice, use your oracle to find the remaining $k$ bits.

This works assuming fixing some bits of the problem leads to a sub-problem of the sort that can be solved by your oracle.

(I'm also assuming you can verify whether a candidate solution is correct in $O(1)$ time, you can find a correct solution in $O(2^{n-k})$ steps.  This seems to be required to achieve your $O(2^n)$ running time for tree search.  If the problem is in NP, then there's a way to verify in polynomial time, so instead of $O(2^{n-k})$ you have $O(2^{n-k} \cdot \text{poly}(n))$.)


Master theorem with $T(n) = 6T(n/10) + \lg^2 n$

Yuval Filmus pretty much showed the way in the comment above. I will just elaborate on his approach.

First, we raise both to the power lg610.

(nlg106)lg610 = n(lg106 x lg610) = n

and,

(lg2n)lg610 = (lg n)2 x lg610 = (lg n)2.57

Now, taking log of both of these, we get
lg(n) and 2.57xlg(lg(n)) respectively.

lg(n) is asymptotically greater than lg(lg(n)), and thus, our case is proved.


Forming polylines from a list of individual lines

Loop over all invidivual lines. If a point of the line is the same as one of the polylines head or tail, extend the polyline

(My emphasis). How are you doing that test? To take $\Theta(n^2)$ time, I think you must be testing each point by linear scan in $\Theta(n)$. Use a decent hashmap instead and it will take $\Theta(1)$ on average.


How to satisfy bounded waiting in case of deadlock?

You are correct.

Consider the simple synchronization algorithm which denies entry to all processes.

In this case we have both deadlock and bounded waiting, since any process $p$ is not bypassed by some process $p'$ before entering the critical section, so you could say bounded waiting is satisfied with the constant function $f=0$.


Prove that there exists a machine which decides an infinite subset of halting problem

Let $M$ be a TM which accepts all inputs. Then $\{ \langle M, w \rangle \mid w \in \{ 0, 1 \}^\ast \}$ is an infinite subset of $H$ and (easily) decidable.

Going further, let $M_w$ be a TM which halts if and only if its input is not equal to $w \in \{ 0, 1 \}^\ast$ and let it be such that $\langle M_w \rangle$ is computable from any $w$ (e.g., $w$ is a substring of the description of $M_w$). Then the set $\{ \langle M_w, w' \rangle \mid w, w' \in \{ 0, 1 \}^\ast \}$ is another infinite subset of $H$ which is decidable. The description for a decider could be, for example: Given $\langle M_w, w' \rangle$, compute $\langle M_{w'} \rangle$ and accept if and only if it is equal to $\langle M_w \rangle$.

A warning: in the question text you referred to "a machine that decides any infinite subset of $H$". Indeed, no such machine exists (since $H$ is an infinite subset of itself); however, this is not what the question title (presumably the intended question) is implying.


It totally depends upon the particular implementation. In linked-lists which support circularity (where the first element, possibly a sentinel, links back to the last one) the task can indeed be achieved in $O(1)$ time, for it requires fetching a pointer to the tail of the list; on the other hand, on implementations which do not support doubly-linked elements or other fancy mechanisms, a full iteration to the back of the structure might be necessary, thus requiring $O(n)$ time.
On a side note, the term list refers to an ADT (Abstract Data Type), which is merely a type coupled with a set of operations and specifications. Thus, the term list does not inherently have to be linked to the pointer-based implementation; in fact, an ADT implementation such as Java ArrayList may be also realized on arrays, giving a random-access time complexity on any location (including the tail) in $O(1)$ time.


For x86 if the hardware page table walker tries to load a page table entry from a speculative access (or hinted by a prefetch instruction) and the Present Bit is zero, then a page-fault exception is generated (Intel® 64 and IA-32 Architectures Software Developer’s Manual, Vol. 3A, 4.7 PAGE-FAULT EXCEPTIONS).

The OS then handles this exception by using OS-specific structures to find where the page is stored and return it to memory. (An OS can choose to mark a page as not present even though it is still in memory. This could be used to give the page a brief last chance before being victimized with potentially less overhead in the common case of the page not being reused before another free page is required.)

A transfer from a hard drive is almost certain to use DMA as such is more efficient. (Network storage using something like ISCSI or a network file system would typically have more processor involvement since such protocols are not typically implemented as part of the networking hardware interface.)

Other ISAs with hardware page table walkers would behave similarly. (An ISA whose hardware page table walker uses hashed page tables like Power Servers and Itanium [which also has the option of using linear page tables] can have a page table miss from a conflict in the hash table. Such page tables are sometimes used as "software TLBs" in that software fills the page table and like a TLB the page table can suffer a miss, which is different than a hit with the page table entry marked invalid/not-present.)

With a software page table walker (e.g., older MIPS, Itanium using linear page tables when the virtual address associated with the location of the PTE is a TLB miss), the software would typically check to ensure the page table entry was marked as valid/present before inserting it into the TLB (loading an invalid PTE usually only makes sense for a sectored TLB entry where multiple PTEs are cached with a single virtual address tag). This avoids an additional exception.


Direct encoding of the solution into the chromosomes in a Random-Key Genetic Algorithm

As said elsewhere. Genetic algorithms are more art than science. The encoding and evaluating of chromosomes can be anything you like. The only "unacceptable" techniques are the ones that don't work.


Closest pair of points between two sets, in 2D

Yes, this can be $O(n \log n)$ time.  Build a Voronoi diagram for $T$.  Then, for each point $s \in S$, find which cell of the Voronoi diagram it is contained in.  The center of that cell is the point $t \in T$ that is closest to $s$.

You can build a Voronoi diagram in $O(n \log n)$ time, and each query (find the cell containing $s$) can be done in $O(\log n)$ time, so the total running time is $O(n \log n)$ time.


Find all words of length $k$ in lexicographic order

You can do it either inductively or recursively.
Inductively, you just write out the numbers from $0$ to $n^{k-1}$ in base $n$, adding $1$ to all digits.
Alternatively, you can simulate a counter in base $n$ – that would be faster.
Recursively, you can proceed as follows:

Generate all solutions for $k-1$, and output them with prefix 1.
Generate all solutions for $k-1$, and output them with prefix 2.
...
Generate all solutions for $k-1$, and output them with prefix $n$.

Alternatively:
– Generate all solutions for $k-1$.

For each solution $s$, output $s1, s2, \ldots, sn$.


Is true that $L_1 = \{01^*0\}$ is $m$-complete in the class of decidable languages?

Your approach can't succeed. You're asked whether every decidable language reduces to $L_1$ but your approach is to try to show that some undecidable language doesn't reduce to it. That would show nothing about decidable languages.

But are you sure that your definition is correct? Every language except $\emptyset$ and $\Sigma^*$ is $m$-complete by the definition you give.


Algorithms : most lightweight circle in directed graph that goes through specific vertex

Just add a node k1 to your graph, that has exactly the same connections as k, with the same weights (you can keep only the edges going to k1 if you'd like), and query the shortest path from k to k1 in your (slightly) extended graph. Your cycle is exactly this path, only replacing back k1 with k at the end of the path.

Your algorithm would be slower and would not always give the right answer: even if v is the closest node to k, maybe it is not in the best cycle (you could for instance have k->v cost 1, v->k cost 100, and k->u and u->k both cost 2 or some u).


Graph theory, $n$ people sitting around table

Point 3. If the seats are unlabelled, the number of arrangements is $\frac{(n-1)!}{2}$.

Explanation: put a hat on one of the person and take it as the leader. Then you have $n-1$ choices for the person to his right and so on. But each arrangement is counted twice if you consider that circular arrangement $(a,b,c,d)$ is the same as the circular arrangement $(a,d,c,b)$.

Point 2. Answer is no. Take four people. They can only share one meal in your conditions. The people facing each-other will never eat side by side :-(

Point 1. You basically want to partition the edges of the complete graph on $n$ vertices into $k$ hamiltonian cycles. An obvious upper bound is then that $nk \leq {n \choose 2}$ so that $k \leq \left\lfloor \frac{n-1}{2} \right\rfloor$. This upper bound is met when $n$ is a prime number (take a first cycle then people at distance 2 then people at distance 3...)


For every imperative function, is there a functional counterpart with identical performance or even instructions?

Performance is not a property of language, it is a property of specific programs within a language. Some languages might be very fast at some things and slow at others.
For example, Chez-Scheme can sometimes find performance comparable to C, not because the language is more efficient, but because defensive practices that programmers often use in C are less necessary in scheme.
Likewise, there are times when Haskell can do very efficient parallelism or concurrency, not because it is faster than C, but because the immutability guarantees of the language allow the programmer to avoid things like locks and other synchronization techniques.
And, performance varies from implementation to implementation. I can hand-roll a C interpreter, but it will certainly not be fast. C is not fast, GCC and Clang are.

What is considered a "functional" language? Every practical functional language has some facilities for mutable state: OCaml, Haskell, Scala, Lisp, Scheme, etc. Tail recursion gives something roughly equivalent to mutation inside of a for-loop. But when this is not enough, functional languages give the programmer access to mutable state. In the case of Haskell, this is controlled by the type system, so there is never implicit mutable state, but mutation is very much allowed and even encouraged in Haskell. Look at any Haskell code, and you will see the IO monad everywhere. Likewise, ML languages distinguish between types T and ref T, so you can tell by the types whether a variable is mutable or not.

There is no "optimal" compiler, thanks to Rice's theorem. All compilers, imperative or functional, are "best effort:" the use conservative approximations to optimize code.
If we had an optimal compiler, the answer would be that every program always ran using the most efficient instructions possible, and it wouldn't matter what language you coded your problem in. The optimal sequence of instructions computing a problem does not depend on the source language. But if we had this, then this compiler would compile every non-halting program into while(0), which means we could detect non-halting programs, which is impossible.

For Turing Machines and the lambda calculus, I think it is fairly trivial to implement a lambda calculus interpreter for Turing Machines that is asymptotically equivalent to a universal Turing-machine. Big-O complexity isn't what people mean when they say "Functional languages are slow". Usually they are talking about constant overhead, which is very different. We don't have as good of ways to mathematically model this, so we usually just end up using experiments to measure precise performance.


Finding optimum point that minimizes maximum distance

you can use Floyd Warshall algorithm to find distance of every pair and then just use a simple for to find the sum of distance of any of vertices  and print the minimum of them


Longest path of a DAG containing a single node?

You have not misunderstood anything, there is simply a discrepancy of notation: sometimes the length of a path is measured as its number of edges, sometimes as its number of nodes, depending on context. In your implementation, it doesn't matter which convention you use, as long as you are consistent throughout your algorithm. Then if you use the second convention and your algorithm returns $3$ for a particular vertex, it means the longest path to that vertex has three nodes: $abv$. If you use the first convention (which is what this Wikipedia article uses, but not your professor), the algorithm should return $2$, because the longest path has two edges.

If this is an assignment, and your professor uses the convention that paths are measured by their vertices, and says that you should too, then you should too.


Is the Tomasi-Kanade factorization still commonly used as a modern computer vision technique?

The Tomasi-Kanade algorithm is probably not used too much these days, though it is an important algorithm that provides a lot of insights and opens interesting avenues of research.  I would say that the main drawback of the algorithm is not that it assumes an orthographic camera, but that it requires a full data-matrix, in which all points are visible in every view.  This is usually not realistic in practice.
The most significant step to address the first issue was the Sturm-Triggs extension of the algorithm to true perspective camerad (i.e. the pinhole camera model).  There were several follow-ups to this, trying to improve on the original method, including papers by Shyjan Mahmood, John Oliensis and others, to a point where the algorithm works well for the perspective model, as long as points are visible in all views.
The situation where there are gaps in the data is addressed by the research topic of low-rank matrix factorization with missing or noisy data.  Unlike the low-rank factorization of a full data matrix, where a least-squares solution is available using SVD (as in the original Tomasi-Kanade algorithm) low-rank factorization of a matrix with holes, or per-entry weights, is NP hard.  Nevertheless, various methods of trying to do this have been proposed, and a good place to look at this is the paper "Damped Newton Factorization for matrix factorization ..." by Buchanan and Fitzgibbon.  This discusses and compares various methods.
Essentially the same sort of algorithm is used for dynamic structure and motion, or multi-object structure and motion.  A good place to start looking into that is the work of Rene Vidal, who has looked at these problems in great depth.