Analysis of sorting Algorithm with probably wrong comparator?

The question seems ill-defined. A faulty/probabilistic comparator will have a radically different impact on different sort algorithms. Each algorithm will have a different, and potentially very complex, analysis.

One possibly interesting note is that you will get exactly reverse sort order when p=0. When p=0.5 the result will be unbiased on ascending vs descending, but the resulting permutations will not be equally likely.


How to sort $N$ fractions from finite set

You can sort all $11^2$ possible fractions, and create a table mapping $p/2^q$ to its position in this ordering, and another table going the other way. Then you can use counting sort to handle $N$ fractions in time $O(11^2 + N)$. (Here the underlying constant is universal, not depending on the size of the domain.)


Understanding how to decide whether a language for a DFA is decidable

Let me rephrase the question:

  Is there an algorithm that, given a DFA, decides whether its language is $\{0,1\}^*$?

Such algorithms do exist, hence the corresponding set is decidable.

I'm not sure what your instructor means by "high level description of a Turing machine", but what they should have meant is "describe an algorithm that solves the problem". Hopefully you already know how to do that.


I think this is a common misconception among undergraduates about $\mathcal{O}$, $\Omega$, and $\Theta$. It is not like these symbols represent worst, best, and average case running time, respectively. They are just upper and lower bounds on running times and you can have lower and upper bounds on all of those cases.
In some sense, $\Omega$ is just the pessimistic view of the worst case running time. This shows that in the worst case (e.g. the word+pattern of your problem) you cannot expect a running time that is faster than $c \cdot mn$ for some constant $c$. However, the first paragraph of Proving the Theta suggests that they also show that the algorithm is guaranteed to run in time $\mathcal{O}(mn)$, this is the optimistic view, stating that you will never find and example where the running time is worse than $c' \cdot mn$ for some constant $c'$. Both parts combined give you that the running time is in $\Theta(mn)$.


$$\begin{align*}
\log n! &=\sum_{i=1}^n\log i \\
                   &\geq \sum_{i=\lceil n/2\rceil}^n \log i \\
                   &\geq \sum_{i=\lceil n/2\rceil}^n \log \tfrac{n}{2} \\
                   &\geq \tfrac{n}{2}\log \tfrac{n}{2} \\
                   &= \tfrac{n}{2}\big(\log n - \log 2)\\
                   &= \Omega(n\log n)\,.
\end{align*}$$


Prove Vertex-Cover of maximum degree 3 is NPC

Hint: Here is how to handle vertices of degree 4 (taken from Alimonti and Kann).

Let $v$ be a vertex of degree $4$, with neighbors $x_1,x_2,x_3,x_4$. Replace $v$ with a path $v_1-w-v_2$ and connect $x_1,x_2$ to $v_1$ and $x_3,x_4$ to $v_2$ (arbitrarily). A vertex cover in the original graph containing $v$ corresponds to a vertex cover in the new graph containing $v_1,v_2$. A vertex cover in the original graph not containing $v$ corresponds to a vertex cover in the new graph containing $w$. In total, we get that the original graph has a vertex cover of size $k$ iff the new graph has a vertex cover of size $k+1$.

The same idea works for vertices of higher degree.


Finding the time complexity of fibonacci sequence

The analysis is not accurate although the result is correct. You could write it more accurately by replacing $=$ with $\le$

$T(n) \le c(1+2+..+2^{n-1})$ ( $\le$ since not all level have same number of children, consider the most right-handed path, n is decreasing by $2$ every step ).

Indeed a more careful analysis can get you a tighter bound as mentioned in the comment. The idea is, the time $T(n)$ is computed with $T(n-1) + T(n-2)$ the same way as the actual fibonacci $F(n)$, and since $F(n) = O(\phi^n)$ for $\phi = (1+\sqrt{5})/2$ as the closed form.

Thus $T(n) = O(\phi^n)$ which is slightly smaller than $2^n$


The number of iterations is:
$$T = \frac{2N}{2} + \frac{2N}{2 * 4} + \cdots + 1$$

The number of elements in the above formula is $\log_4(2N)$. After simplification, we will have:

$$T = N(1 + \frac{1}{4} + \cdots + \frac{1}{4^{\log_4(N)}}) = \Theta(N)$$

As $1 + \frac{1}{4} + \cdots + \frac{1}{4^{\log_4(N)}} < 2$ is a geometric series with step of $\frac{1}{4}$ in asymptotic sense.


() = ( − 2) + 4, giving asymptotic bounds

Take the first example. Start calculating T (100) = T (98) + 4 = T (96) + 4 + 4 = T (94) + 12 = T (92) + 16 ...

Seriously, that's the first thing you do. You have a problem, you try what happens. At this point it should be absolutely obvious to you what happens, right? I hope I don't have to write down the solution?

The next one: T (100) = 3 T (99) + 3 = 9 T (98) + 9 + 3 = 9 * T (98) + 12 = 27 * T (97) + 39 = 81 * T (96) + 120 ... Slightly more complicated, but you see that one of the numbers is a power of 3, and the other one is slightly less obvious $(3^k - 3) / 2$. Figure it out from there.

The next one: Well, I'll start with 512. T (512) = $2 T (64) +  4 * 512^2$ $2 * (2 T (8) + 4 * 64^2) + 1024^2$ = $4 T (8) + 8 * 64^2 + 4 * 512^2$ = $4 * (2 T (1) + 4 * 8^2) + 8 * 64^2 + 4 * 512^2$ = $8 T (1) + 8 * 8^2 + 8 * 64^2 + 4 * 512^2$ - it should be clear what the dominating factor is in this equation.

This is all mathematically trivial. All you had to do to solve these problems is to not look at them and be stunned by the strange formulas but having a go and starting to calculate and see what happens.

PS. The answer was intended to demonstrate that seemingly hard problems can often be attacked quite easily, that overcoming your fear of the unknown and jumping in and seeing what happens is often enough. That is much, much more important than solving one particular problem. You may call this a "waste of time", but I Don't Think So.

The quoted "reference answer" may answer the question, but doesn't inspire anyone to try finding the answer themselves.


Given this transition system, for which states are these (very basic) LTL formulas fulfilled?

Note that questions of the form "am I correct" are generally not acceptable on this site. Still, your question shows an effort, so here are some answers:

As for your classification to LTL/CTL - you are correct.

Let's look at (b) - it interprets to "always b", which means that in every path starting from the state, b must always hold. This is not the case for any state in the system (since every path eventually reaches s2, in which b does not hold).

As for (e) - it means that in every path, in every suffix, $bUa$ hold, so in every suffix it is true that b holds until a holds. In this system, you are correct that all states satisfy this.

(c) is perhaps easier than the other two - it reads as "next next a", and a state satisfies it if in every path from it, in two steps you will reach "a". In this system, every path gets within two steps to s2, s3, or s4, all of which have "a", so the formula holds.


Why do i have to show that a problem L $ \in $ NP before i start a polynomial reduction?

Because a problem L is NP-complete if and only if:

L is in NP
L is NP-hard: every problem A in NP can be polynomially reduced to L.

So to show that L is NP-complete, you have to demonstrate both the properties.


Are C standard library functions considered part of C programming language

The “C programming language“ is defined by a document that defines the syntax and the semantics of programs, and the C standard library. So both are part of the “C programming language”.
However, in CS the term “language” is used in a different way, as a set of strings. You can define a language based purely on the syntax In the C Standard document - that allows you to distinguish between strings that are formally in the language and those that are not, but you still have no clue what a program would do.
You can also incorporate some semantic rules, so that for example int a[-10] or int i = "String" are not considered to be part of the language.


Why is the lower bound for sorting strings Ω(d + nlogn)?

The time complexity you indicated is the lower bound of your specific problem. A lower bound is the worst-case running time of the most optimized TM that recognizes membership in the language.

Lover bound for sorting algorithms is $\Omega(n \log n)$ this means that it is not possible to do better than this and all the sorting cases (instances) may have a temporal complexity $t \geqslant\Omega(n \log n) $.

For a simple proof of the former lower bound you can take a look at this.


Does the process exiting from critical section will always call signal instruction?

Assuming s is a binary semaphore.

If s=0, a V(s) will be successful operation making s=1

If s=1, a V(s) will be successful operation making s=1

If s=0, a P(s) will be unsuccessful operation by retaining s=0

If s=1, a P(s) will be successful operation by making s=0

  s=0
  V(s)
  < Critical Section >
  P(s)

Let process ${p_1,p_2,p_3,.,p_k,.,p_n}$ are waiting go get a chance to access CS (Critical Section).

For the first time $p_1$ tries V(s), successfully increase s by 1,and get an access to CS.

While $p_1$ still in CS $p_k$ tries V(s), successfully increase s by 1 and get an access to CS and so on.

With V(s) at the entry of the CS, will never guarantee blocking others from getting into CS.

With this implementation all process waiting to access CS will get into CS, thus violation mutual exclusion.

Here talking about exiting operation P(s) is useless as it doesn't help the event by any means.

  s=1
  P(s)
  < Critical Section >
  V(s)

Here, if $p_1$ tries P(s) for the first time, successfully decease s by 1 and get access to CS.

With P(s) at the entry of the CS, will guarantee blocking others from getting into CS.

While $p_1$ still in CS $p_k$ tries to enter CS by executing P(s), but fails as s=0 already and cant decrease anymore.

Thus always guarantee mutual exclusion.

See what happens if we doesn't have signal operation at CS exit:

  s=1
  P(s)
  < Critical Section >
  // remove exit operation V(s)

Without $p_1$ signaling, non of the waiting process ${p_2,p_3,.,p_k,.,p_n}$ can access CS. no one can execute the entry operation P(s),since 's' value is still 0.

All processes waiting for CS will be blocked infinity.

Thus, deadlock kind of event happens here where resource is available but cant be accessed.


Dynamic graph (?) - combination of connections between vertices that for each 3 exist min 1 edge

Your condition on the graph is the same as requiring its complement to be triangle-free. It is known that there are a lot of triangle-free graph. Indeed, since every bipartite graph is triangle-free, if we fix a partition of the vertex set into two sets of size $n/2$ (assuming for simplicity that $n$ is even), then we already get $2^{n^2/4}$ triangle-free graphs. It turns out that there aren't that much more, see this question on mathoverflow.

Perhaps you'd be interested in a paper on generating maximal triangle-free graphs up to isomorphism (in your case, you will be generating minimal graphs satisfying your condition), whose number is more manageable.


Although I can't do the proof completely right now, maybe looking at $(L_A^* L_B)^+ \subseteq (L_A \cup L_B)^*L_B$ and $(L_A \cup L_B)^*L_B \subseteq (L_A^* L_B)^+$ helps here. So from left to right: If you take a word $w \in (L_A^* L_B)^+$, can you split it up into $0..m$ subwords of the form $(L_A \cup L_B)$ and one postfix-subword of form $L_B$? I hope this helps you.


Prove that every undirected connected graph with $|V | > 2$ results in a connected graph if two vertices removed..

Hint: Find the connected graph's spanning tree (using an algorithm like breadth-first search). Consider the endpoints of a longest path in this spanning tree.


Minimal set of subintervals that 'covers' any subinterval in K subintervals

Let's consider the case $K = 2$. Given an interval $[1,n]$ of length $n$, we can construct the required set as follows:

If $n = 1$, take the entire interval.
Otherwise, let $m = \lfloor n/2 \rfloor$, and take the following intervals:

A solution for $[1,m]$.
A solution for $[m+1,n]$.
All intervals of the form $[i,m]$.
All intervals of the form $[m,j]$.

Denoting by $A(n)$ the number of intervals constructed in this way, we get the recurrence
$$
A(n) = A(\lfloor n/2 \rfloor) + A(\lceil n/2 \rceil) + n,
$$
with initial value $A(1) = 1$. The solution of this recurrence is $A(n) = \Theta(n\log n)$.

Now let us proceed to prove a matching lower bound. Let $\ell_i = 2^i-1$, and let $I$ be the maximum value such that $\ell_i \leq n/2$; note that $I = \Theta(\log n)$. For each $1 \leq i \leq I$, consider the $n/2$ intervals $[1,\ell_i],\ldots,[n/2,n/2+\ell_i-1]$ of length $\ell_i$. Each of these is the union of at most two intervals in $S$, one touching the left endpoint and one the right endpoint (possibly the same one). One of these intervals must have size at least $2^{i-1} > \ell_{i-1}$. In total, this gives a collection of $n/2$ intervals in $S$ of length between $\ell_{i-1}+1$ and $\ell_i$; each such interval is repeated at most twice (since one of its endpoints is a matching endpoint of one of the original $n/2$ intervals). This shows that $S$ must contain at least $n/4$ intervals of size between $\ell_{i-1}+1$ and $\ell_i$, and so $\Omega(nI) = \Omega(n\log n)$ overall.

Here is a better construction for $K=4$. Divide the interval $[1,n]$ into $m=n/\log n$ subintervals $I_1,\ldots,I_m$ of length $\log n$. We construct the required set as follows:

Apply the construction recursively inside each $I_i$.
Every prefix and suffix of each $I_i$, $2n$ intervals in total.
The $K=2$ construction applied to $[1,m]$ and then blown up to $I_1,\ldots,I_m$ by replacing each interval $[i,j]$ to $I_i,\ldots,I_j$.

Let us first show that we can cover each interval $I$ using at most 4 intervals in the set. If $I \subseteq I_i$ for some $i$, then this is clear. Otherwise, suppose that $I \subseteq I_i \cup \cdots \cup I_j$, where $i$ is maximal and $j$ is minimal. So $I$ consists of a suffix of $I_i$, all the intervals $I_{i+1},\ldots,I_{j-1}$ (if any), and a prefix of $I_j$. We can cover the middle part using 2 intervals, and the two ends using 2 more intervals, for a total of 4.

Let us denote by $B(n)$ the number of intervals used in this construction. This quantity satisfies the recurrence
$$
B(n) = \frac{n}{\log n} B(\log n) + O(n).
$$
Opening this up, we get
$$
B(n) = O(n) + \frac{n}{\log n} O(\log n) + \frac{n}{\log n} \frac{\log n}{\log \log n} O(\log \log n) + \cdots,
$$
where the hidden constant is the same for all big O’s. The number of summands is $\log^* n$ (which is the number of $\log$s you have to apply to $n$ to reduce it below some constant), and so
$$
B(n) = O(n\log^* n).
$$
We can repeat this construction once again, for $K=6$, to get the inverse of one level higher on the Ackermann hierarchy. Perhaps in this way we can get a set of $O(n)$ intervals for $K=\omega(1)$ growing extremely slowly (inverse Ackermann); verifying this would require a slightly more careful analysis.


are the activations of hidden nodes in an ANN binary or real valued?

When you do thresholding your activation function becomes a step function. The problem with that is that step functions are not differentiable, so you would not be able to do basic gradient descent to learn the parameters. You can see the sigmoid as a continuous approximation of a step function.


Is it possible to have 2 languages with different syntax but the same semantics?

Sure. I think it may be hard to answer the question using production languages since you are unlikely to find two "real" languages with identical semantics or identical syntax.

Let's consider a simpler example to illustrate the concepts. Take JSON (which I suppose isn't a programming language, per se, but the idea carries over). Now, change it so that instead of separating key-value pairs with colons we use equals signs and instead of separating items with commas we use semi-colons. Now it looks like this:

{
  "name" = "Bob";
  "age" = 23;
  "titles" = [ "Mr."; "Dr."; "Sir" ]
}

This is clearly semantically the same as the following, syntactically different string:

{
  "name" : "Bob",
  "age" : 23,
  "titles" : [ "Mr.", "Dr.", "Sir" ]
}

A bit of a simple example, but it should illustrate the point.

As far as the other direction is concerned, that is also true. For example, consider the standard for loop found in many languages:

for (int i = 0; i < 10; i++) {
  // do something...
}

This loop runs the initialization step once at the beginning, tests the condition before each iteration of the body, then runs the update step at the end of each iteration. But I could define a language with the same syntax but where the condition is evaluated at the end of the iteration and the update occurs at the beginning. The standard version is semantically the same as:

int i = 0;
while (i < 10) {
  // do something
  i++;
}

whereas my new definition is equivalent to

int i = 0;
do {
  i++;
  // do something
} while (i < 10);

which is clearly different.


Unknown representation of number as bits

They've split an 8-bit byte into two four-bit nibbles (sometimes spelled "nybble").  The brackets denote multiplication; it's just saying that
$$10110010 = 10000\times 1011 + 0010\,,$$
(written all in binary to avoid having two different bases in the same expression).  This is just like saying, in decimal, that
$$837\,487 = 1000\times837+487\,.$$
There isn't really anything to find out.


computability - decidability of a prefix language

Pick some self-terminating encoding of Turing machines. (That means that the encoding of one Turing machine is never a prefix of the encoding of another.) Consider the language $L$ consisting of strings $Mn$, where $M$ is an encoded Turing machine, $n$ is interpreted as a number, and $M$ halts within $n$ steps (on the empty input).

Does that answer your question?


Proving ALLTM complement not recognizable

First, there is a small typo in (1) - if $\alpha$ is not a legal encoding, then you should return something that is in $ALL_{TM}$ (since you are reducing to the complement).

For your question: the key point here is that a TM does not always halt on its input. Thus, the phrase "otherwise accept" in your suggestion for (2) is not computable. If you run $M$ on $\epsilon$, and $M$ does not halt, then the lanugage of $M'$ will be $\emptyset$, which makes the reduction fail.

In general, when you perform reductions that output a machine that simulates another machine, you must always consider the possibility that the latter will not halt. If this poses a problem (as it does here), a good trick to circumvent it is to limit the step number, and since often you want this limit to exist, but to be ``unbounded'', then using the input for the machine as a limit is a good idea.


Algorithm to identify top $\log n$ elements in $O(n)$ time

For every $k$, you can find the $k$th largest element in $O(n)$, using a linear time selection algorithm. You can then find the $k$ largest elements by scanning the array.


Conditions for a node to be a leaf node on DFS tree

A node v is a leaf node on the DFS tree if and only if f[v] = d[v] + 1.

The proof is obvious once you follow the DFS, marking each node's discovery time and finishing time. A leaf is defined as a node that has no children.
Let $v$ be a node.

Suppose $v$ has children in the final DFS tree. That is, we will go forward to a child $u$ of $v$ right after we have discovered $v$. That is, $d[v]+1 = d[u]$. The finishing time of $v$ must come after that. So f[v] $\gt$ d[v] + 1.
Suppose $v$ has no children in the final DFS tree. That is, we will go backtracking once we have discovered $v$. That is, we will finish $v$ right after we have discovered it. That is,  f[v] = d[v] + 1.

For people who are not familiar with discovery time and finishing time of a node v associated to a DFS, you can check either Stanford course note or Carnegie Mellon course note. Of course, you may just search by yourself.


Construction of a Deterministic Tree Automaton (DTA)

Your model is a bottom-up tree automaton. Let $P$ be the set of states of the finite state automaton for regular $L$. Now a state of the tree  automaton at a vertex $v$ of the tree contains all $P \times  P$ pairs $(p,q)$ such that there is a path from $p$ to $q$ on the string specified by the leaves under $v$. This can be deterministically evaluated in a bottom-up fashion.

More precisely, with every vertex $v$ we associate a binary relation $R(v)$ over $P$, thus $R(v) \subseteq P\times P$. Thus $(p,q)\in R(v)$ iff there is a path from $p$ to $q$ on the leaves under $v$.

For a leaf $v$ labelled $a\in \Sigma$ this means that $R(v) = \{(p,q)\mid (p,a,q) \in \delta\}$, where $\delta$ is the transition relation of the automaton for $L$.

If $u$ is a binary vertex (labelled by $*$) with children $v,w$, then the relation $R(u)$ is the compostition of $R(v)$ and $R(w)$.

We accept at the root $r$ if $R(r)$ contains an accepting pair $(p,q)$ where $p$ is the initial state and $q$ is final.


I am as puzzled as you are. Indeed, that looks wrong, as far as I can see. The mentioned relation can indeed have infinite descending chains, otherwise we could not have "cycles" which are needed for (mutual) recursion.

What should be ruled out is the presence of infinite descending chains involving infinitely many constants $K$. This is however a different requirement from well-foundation.


How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in a undirected graph?

You don't need to adapt the algorithm, any maximum flow algorithm for directed graphs works by replacing the edges with a forward and backward arc as you suggested. Denote this directed graph $D=(V,A)$. Take the capacities $C(u,v)=C(v,u)$ of both arcs equal to the original edge. Then, let $F(u,v)$ be the maximum flow returned by your algorithm on the directed graph.

To find the cut you need the (directed) residual graph $G_f$ which can be constructed explicitly from the flow by taking $D$ with capacities $C_f(u,v) = C(u,v) - F(u,v)$. Now find the set $S$ of vertices reachable in $G_f$ from $s$, where you can only cross arcs with positive capacity, and let its complement be $T=V\setminus S$. Then $(S, T)$ gives a minimum $s-t$ cut.

To see why this works, note that the capacities in the residual graph give the additional amount of flow in each direction that can be sent over an edge. That is, given the flow already in place, and if you assume that opposite flows cancel each other out. This means a saturated edge has 0 residual capacity in the direction of the flow and double its original capacity in the reverse direction (as $F(u,v)=-F(v,u)$).

Any vertex reachable from $s$ in $G_f$ can receive more flow. Since $F$ is a maximum flow, $t$ cannot be in $S$. Similarly any edge between $u \in S$ and $v \in T$ must be saturated with flow in that direction, otherwise $v$ would be reachable from $s$. Now suppose the capacity of the cut-set is larger than the $s-t$ flow, then the flow from $S$ to $T$ is larger than the flow from $S$ to $t$, which means there must be flow back from $T$ to $S$ which is a contradiction. Since any $s-t$ cut is at least as large as the maximum $s-t$ flow it follows $(S,T)$ is a minimum $s-t$ cut.


Is there a graph product that is multiplicative in independence number?

Consider $G = K_2$, for which $\alpha(G)=1$.  The only product defined in terms of subgraphs of $K_4$ and for which $\alpha(G \times G) = 1$, is the strong product (⊠).  This doesn't quite work, since $\alpha(C_5 ⊠ C_5) = 5$, which is not a perfect square.

However, denoting the lexicographic product by $\circ$, there is an easy proof due to Geller and Stahl that $\alpha(G \circ H) = \alpha(G)\alpha(H)$.

So you want the lexicographic product.


Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?

First off to answer your main question: there is no flaw in the proof.

The point where you are not following the reasoning of the proof is that:

E belongs to a cycle in the graph and to the MST.
Not every other edge of the cycle are in the MST.

If you look at your drawing, then either one of the edges towards the rest of the MST is redundant. Because not all edges of the cycle are in the graph results in that if you remove E you get two subtrees.

To answer your question about why the proof begins with assuming that e belongs to the MST: Proof by contradiction starts with assuming the opposite of what you are trying to proof. Then you reason with that assumption until you run into a contradiction.
A contradiction means that your assumption must be false. If you assumption is false, then the opposite of your assumption is true.

If you just look for images and MST examples there are enough examples with a cycle. Try to follow the reasoning of the proof and you will see why it is sound.


How can I determine if two vertices on a polygon are consecutive?

As the polygon is convex, it is simple! Two vertices are consecutive if all other vertices are located on the same side of the line that goes through these two points. This means that the cross product of the vector feom one of the pionts to the other one with the vector from the first point to any other one in the polygon have the same sign (all negative or all positive). For example, if those two points are called $P_1$ and $P_2$, you should compute all cross product of $\langle P_1, P_2\rangle$ with $\langle P_1, P_i\rangle$ ($P_i$ here means all other vertices).

Also, as discussed in the comment, we have some degenerate cases. The degenerate case is a common phenomenon in computational geometry, that is mostly handled separately. Here, the degenerate case is three points are located on a line.


Connection of "modern" runtimes and number of steps on a Turing machine

Your premise that turing machines can implement algorithms with the same efficiency as a modern computer is not correct.

Turing machines can simulate 'enhanced' turing machines that have the properties of modern computers (e.g. random access into memory, multiple memory spaces, etc) with only polynomial slowdown.

However, not all problems can be solved exactly as fast on a turing machine. For example, consider the problem PALINDROME to determine if the input is a palindrome. On a modern computer there is an obvious $O(n)$ algorithm, where you just read the front and back character, and if they match recurse on the inner substring. This problem is known to require $\Omega(n^2)$ time for a classical turing machine to solve. This means turing machines are decidedly "weaker" by some amount compared to an ideal modern computer.


Is it correct to say that since the SHA256 function domain is finite we can build a DFA that calculates this function (i.e. trivially a giant lookup table)?

Theoretically, yes, that's correct. It would require a lookup table of  $2^{2^{64}}$ entries, roughly, encoded as a DFA.

To be more picky, it depends on the notion of "DFA calculating a partial function". In particular, on what we require the DFA to do outside the domain of the function.

If we require non-termination, as we do for TMs, then a DFA can never implement a non-total function since it can not diverge. So, no DFA can compute SHA256.

If we instead only require to reach an "error" state outside the domain (or no requirement at all), then a DFA can compute SHA256.

I'd lean towards the latter interpretation, but here we need indeed to be a little careful with words.

  Furthermore, if we eliminate the limitation on the length of the input, is it correct to say that SHA256 function belongs to the class of $\mathcal{PR}$ primitive recursive functions?

That's correct.

As a general "cannon" result, if an algorithm $A$ has a complexity function which is bounded above by some $\mathcal{PR}$ function $f$, then $A$ implements a function which belongs to $\mathcal{PR}$.

This is because in $\mathcal{PR}$ we can realize the single-step function for TM, mapping a TM configuration to its next one. Then we can recurse on the single-stepping function $f(n)$ times, and read the result in the final configuration.

Corollary: $TIME(O(2^{2^{2^{2^n}}})) \subseteq \mathcal{PR}$.

The unlimited SHA256 surely falls in that obscene time bound.


ML to approximate a dampened harmonic oscillator from a related curve

I would suggest that you try to learn the function $f$ that maps the parameters of the pmf to the parameters of the dampened harmonic.

For each example, you can presumably derive the parameters of the Weibull distribution for the pmf.  You can also presumably derive the parameters of the dampened harmonic (by curve-fitting, or other means).  So, each example gives you one input-output pair for $f$.

Now, try to learn $f$ from these input-output pairs.  You should start by visualizing the function $f$, to try to understand how each output of $f$ depends on the inputs of $f$, and then you can probably select an appropriate (nonlinear) regression model.  k-nearest neighbors regression might be worth a try in this context.


You can show that $\mathrm{BTM}$ is undecidable with a simple reduction from $\mathrm{ATM}$.

Let $\langle M,w\rangle \in ATM$. We define the reduction function $f$,  $\mathrm{HP} \leq \mathrm{BTM}$ as follow:

$f(\langle M,w\rangle) = M_w $, Where $M_w$ on every input $x$, runs $M$ with input $w$. if $M$ stopped, then $M_w$ accepts $x$. if $M$ rejects, then $M_w$ rejects. Clearly, if $\langle M,w\rangle \in ATM$ then $L(M_w) = \Sigma^*$, and in particular $101 \in L(M_w)$. if $\langle M,w\rangle \notin ATM$ then   $L(M_w) = \emptyset$, and $101 \notin L(M_w)$.

Because $\mathrm{ATM} $is undecidable, so is $\mathrm{BTM}$.

It should be intuitive that $\mathrm{BTM}$ is undeciadble, because given a turing machine $M$, you can't tell if $M$ will halt with input $101$


Determining the classification of languages

Here are two hints

If $\bar L$ would be decidable (recursive), then so would be $L$, and you just argued that $L$ is not even recursively enumerable. Maybe you have a closer look on what $\bar L_0 \cap \bar L_1$ really is. For example
$\bar L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$ does not halts on $w$}\} \cup \{ \langle M, w, x \rangle \mid x\not=0\} $.
If you want to argue formally correct that a language is not recursively enumerable, or decidable, then try to use a reduction, for example the many one reduction. Reduce  a a problem, whose status you know, to $L$ and you can say something about $L$.


How is the formal definition of NP-hard equivalent to this colloquial one?

Why is reducibility an adequate measure of difficulty?

It's not; it provides a relative measure of difficulty, relative to the kind of reduction under consideration.

  To me, the most natural measure of difficulty is worst-case asymptotic complexity.

That's the idea, but for NP-complete problems in particular we do not know their (worst-case asymptotic time) complexity. By introducing a relative measure of hardness, we can say "A is at least as hard as B" without knowing how hard either of them really is.

  having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

That's not the idea behind Karp reductions which we use to define NP-hardness. Read up on the definition.

  this complexity is "the worst" possible in NP

There is no such thing as a worst possible complexity; all polynomial complexities are allowed, and there are problems of arbitrary polynomial complexity. You find proofs for this fact in textbooks on the matter.

  It seems at least plausible to me that there might exist two NP problems A and B which both have the same worst-case asymptotic complexity, and that this complexity is "the worst" possible in NP, but the problems are so different that having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

Keep in mind that complexity classes like P and NP are rough; they ignore polynomial factors. So say we have $\Theta(n^k)$ algorithms for NP-complete $A$ and $B$. We know that $A \leq_p B$ and vice versa, but all that tells us that we can use the algorithm for one to solve the other with polynomial overhead. The degree of this overhead is not specified, and may very well be in $\omega(n^k)$.

Bottom line, you have not yet understood/absorbed the basics and struggle with your faulty intuition contradicting statements you find. I recommend you check out our reference material which covers a wide array of basics and common misconceptions.

Keep in mind that the theory around P and NP defines a measure of hardness. There are certainly others, and some are more appropriate for making some decisions than others.


Is this an unambiguous CFG that is not LR(k) for any k?

Just as a slight nit, those aren't $LR(1)$ item sets, because they don't include the following terminal symbol
With that proviso, your reasoning looks good to me. Of course, the language is not inherently nondeterministic because you can rewrite $B$ as:
$$B \rightarrow \epsilon\,|\,Bbb$$
The palindrome language $L = \left\{ w w^R\,|\,w \in \Sigma^* \right\}, \left| \Sigma\right| > 1$ is the classic example of an inherently nondeterministic language. There exists an unambiguous grammar for $L$, but there is no $LR(k)$ grammar for any $k$.


AVL Tree rotations : How to balance below AVL Tree with imbalance at root node

Oh, my goodness. That AVL tree tutorial at tutorialspoint is so misleading that it is the reason why you became confused. Please ignore that tutorial.

Please study the AVL tree insertion article at GeeksForGeeks instead. Or check some textbook such as Introduction to Algorithms by By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. This recommendation should be one of the best help you can get from asking a question.

In the graph you last uploaded, https://i.stack.imgur.com/0HivT.png, the change from the first tree directly to the last tree is called a right rotation by almost every textbook, tutorial and articles I have seen. The tree in the middle never appears. The tree in the middle is just an extra unnecessary distracting step.


Proving Clique Number of a Regular Graph

Let $G$ be a $d$-regular graph on $n$ vertices containing an $a$-clique $A$, and let $B$ denote the other $b:=n-a$ vertices. Suppose that $a>b$.

Let $e$ be the number of edges connecting $A$ to $B$. Every vertex in $A$ has $a-1$ edges going to the other vertices in $A$, and so $d-(a-1)$ edges going to vertices in $B$. Hence $e = a(d-(a-1))$. Similarly, every vertex in $B$ has at most $b-1$ edges going to the other vertices in $B$, and so at least $d-(b-1)$ edges going to vertices in $A$. Hence $e \geq b(d-(b-1))$. It follows that
$$ b(d-(b-1)) \leq a(d-(a-1)). $$
Subtracting the left-hand side from the right=hand side, we get
$$
0 \leq (ad-a^2+a)-(bd-b^2+b) = (ad-bd)-(a^2-b^2)+(a-b) = (a-b)(d-a-b+1).
$$
Since $a > b$, it follows that $d \geq a+b-1 = n-1$. In other words, $G$ is the complete graph.

Summarizing, if a regular graph contains a clique on more than half the vertices then it is the complete graph. Therefore the clique number of a regular graph is either at most $\lfloor n/2 \rfloor$ or $n$.

Let us now show that the upper bound $\lfloor n/2 \rfloor$ is tight. That is, for every $n$ there exists a regular graph on $n$ vertices whose clique number is $\lfloor n/2 \rfloor$.

When $n$ is even, there exist regular graphs on $n$ vertices with clique number $n/2$, for example two disjoint copies of $K_{n/2}$.

When $n=4m+1$, there exist regular graphs on $n$ vertices with clique number $2m$: take two disjoint copies of $K_{2m}$, add a new vertex connected to $m$ vertices from each copy of $K_{2m}$, and add a matching between the remaining $m$ vertices of each copy of $K_{2m}$. When $m=1$, this gives the 5-cycle.

When $n=4m+3$, the following construction gives a regular graph on $n$ vertices with clique number $2m+1$. Take two disjoint copies of $K_{2m+1}$, say on vertices $x_1,\ldots,x_{2m+1}$ and $y_1,\ldots,y_{2m+1}$. Connect $x_i$ to $y_i$ for all $i$, and connect $x_i$ to $y_{i+1}$ for $i=1,\ldots,m$. Finally, add an additional vertex connected to $x_{m+1},\ldots,x_{2m+1}$ and to $y_1,y_{m+2},\ldots,y_{2m+1}$.


What would remain of Quantum Computing if quantum states were real numbers?

The gate set Hadamard + Toffoli is universal for quantum computation [1] and only uses real number coefficients (some negative). So all quantum algorithms can be run without involving imaginary numbers.

That being said, you will pay some representation overhead if you stick with just H+Tof. For example, you need an extra ancilla qubit and essentially every encoded operation will act on this qubit. This creates a false dependency between most operations, preventing parallelism and locality.

[1]: https://arxiv.org/abs/quant-ph/0301040


Decidability of Unary Languages / One-to-One Mapping

Instead of mapping the string $x\in\{0,1\}^*$ to $1^{\mathrm{bin}(x)}$ (where $\mathrm{bin}(x)$ is the number denoted by interpreting $x$ as a string in binary, map it to $1^{\mathrm{bin}(1x)}$. Now every string in $\{0,1\}^*$ maps to a unique number of $1$s.


Prove the equality of two concatenations of words

Suppose without loss of generality that $|y'| \geq |x|$. If we write $y' = xa$ then $ax' = y$. The equalities then become

$xau'x' = xuax'$.
$xav'x' = xvax'$.
$xaw'x' = xwax'$.
$xav'u'x' = xuvax'$.
$xaw'v'x' = xvwax'$.

Cancelling $x,x'$, we get

$au' = ua$.
$av' = va$.
$aw' = wa$.
$av'u' = uva$.
$aw'v' = vwa$.

Using $y' = xa$, (5), (1), and $y = ax'$, we get
$$ y'w'v'u'x' = xaw'v'u'x' = xvwau'x' = xvwuax' = xvwuy. $$
This is close to what we want, only we got $vwu$ instead of $uvw$.

Plugging (2) into (4) gives $uva = av'u = vau' = vua$, and so $u$ and $v$ commute. Similarly, plugging (2) into (5) gives $vwa = aw'v' = wav'=wva$, and so $v$ and $w$ commute. The set of words commuting with $v$ forms a commutative monoid (since all are powers of some primitive word), and so $u$ and $w$ also commute. Therefore $vwu = uvw$, completing the proof.


Here are some answers and hints to pursue your reflexions.

$\mathtt{Assignment}$

What $\phi([x \leftarrow E])$ means. You said yourself that the semantic of the precondition confuses you that was what the assignment $x := E$ was doing. But in fact your are precisely pointing out the crux of this rule: it affects the precondition exactly as the assignment would do it. This is the core reason of why this rule is actually sound.

Let study an exemple and leave the abstraction for a bit.
Take the program $P = (z:=x+1)$.

Suppose we want to prove the postcondition $\phi(z) := \{z=2\}$
Intuitively what do we need to prove this ?  Obviously we need $x$ to be equal to $1$. Let see how it translates in Hoare's logic. The assignment rule tells us that the triple:
$$
\{\phi[z \gets x+1]\} (z:=x+1) \{\phi(z)\}
$$
is valid.

Unrolling the syntax gives:
$$
\{(z=2)[z \gets x+1] \} (z:=x+1) \{x=2\},
$$
that is
$$
\{x+1 = 2 \} (z:=x+1) \{z=2\},
$$
and a bit of meta-logic says:
$$
\{x = 1 \} (z:=x+1) \{z=2\}.
$$

Which is what you wanted.

In an nutshell the assignment intuitively says: "The postcondition is true as soon as when I replace everything by the value of E in it, it is true"

$\mathtt{Conditionals}$

First of all $B$ is not a variable but a boolean predicate (like $X==1$ for instance).

$\{\phi[B]\}\ P_1\ \{\psi\}$ doesn't make any sense. $\phi$ is a predicate, so does $B$, so that you can't apply one to another.
For instance if $\phi = (x==1), B = (y==2)$ you can speak of $\phi\wedge B$ but $\phi[B] has absolutely no meaning.
$\{\phi \land B\}$ is true says $\phi$ is true and $B$ is true.
With my previous instances:  $\{\phi \land B\}$ as precondition asserts that on the one hand $(x==1)$, and on the other $(y==2)$. Nothing else.

$\mathtt{Iteration}$
 This one is subtle. As long as it terminates, you can have arbitrary many iterations BUT still a finite number. Think of a while as a for loop on which you don't know a priori the number of runs in this case. To see why the rule is sound, think of it as a nested sequence of if :

if B then
     P
     if B then
         if B then
            P
            if B then
                 .....

And use a recurrence + conditional+ composition to convince you that the rule does what it is supposed to do.

If it doesn't terminates you can't say anything a priori so it doesn't matter. Remark that the rule DOES NOT say that the loop terminates.

$\mathtt{Weakening \to Strengthening}$
  It is the causal reasoning. Let us unroll the rule: Suppose that $\phi$ is true. Then $\phi$ is also true since  $\phi \Rightarrow \phi_1$. But the Hoare triple
$\{\phi_1\}\ P_1\ \{\psi_1\}$ is valid by hypothesis. Then $\psi_1$ is true. But we know that $\psi_1\Rightarrow \psi$. Hence $\psi$ is true as well: we just proved that $\{ \phi \} P \{\psi\}$ is a valid triple.


Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete

Hint: Directed reachability is NL-complete.


Can I write a regular expression or regular grammar for this language?

This language is context-free but not regular. It is isomorphic to the problem of matching open and closed parentheses: (n)n which is a well-known non-regular language. To prove this yourself, you would use the pumping lemma for regular languages.

Every regular grammar describes a regular language.
This language is not regular.
Therefore, there cannot be a regular grammar that describes it.


Is shuffling a set of items after popping an item meaningfully more random than doing it once, before starting?

Say we have $n$ people. After shuffling the whole list (once), every person occupies every position with probability $1/n$.

Shuffling before each draw means every choice is uniformly random; that is, because the choices are now stochastically independent, being drawn as $i$th person has probability

$\qquad\displaystyle \frac{1}{n-i+1} \cdot \prod_{k=1}^{i-1} \Bigl(1-\frac{1}{n-k+1}\Bigr) \quad=\quad \frac{1}{n}$.

So no, shuffling repeatedly does not "add" any randomness -- whatever that would mean. It's uniform, i.e. "fair", to begin with, so what would "more random" mean?

The correct statement is: repeated shuffling does not change the distribution. Which means it is unnecessary, but also not harmful if it eases the mind of laymen participants.


Yes, there can be many DFAs for a language. Many will be silly though, one way to get another is to add unreachable states to any DFA for the language). It is also possible to have more than one sensible DFA:

These two DFAs both accept $\{a,b\}^{\ast}$.
On the other hand each DFA accepts exactly one language (i.e. no DFA accepts zero languages, or two or more languages) .


How to prove that a custom iterative algorithm will determine all shortest paths to a graph node?

You can prove by induction that for every iteration $i$, the array $A$ during this iteration, $A_i$, contains the weights of some paths originating at $t$. More formally, for all $v\in V$, $A_i[v]$ is either $\infty$ or the weight of some path from $t$ to $v$.

Now, it is easy to show that the values of $A_i$ are monotonically non increasing, which combined with the above statement implies that the algorithm terminates. I leave the details to you.


Difficulties proving when a language is in P or is NP-complete

The language $L_1$ is in P since you can brute force an optimal vertex cover in each connected component.
The language $L_2$ is NP-hard by reduction from vertex cover. Roughly, given an arbitrary graph, we have to make it connected and to add another connected component, controlling the change of the minimum vertex cover throughout the process.


What type of algorithms are faster with a quantum computer?

Shor's algorithm which puts FACTORING in BQP (bounded error quantum polynomial-time, effectively the quantum equivalent of P) also can be used to solve the DISCRETE LOGARITHM problem, where we want to find an integer $k$ such that $a^{k} = b$ where $a$ and $b$ are given, in (quantum) polynomial time. The DISCRETE LOGARITHM problem has the same status as the FACTORING problem in that we don't know whether they are polynomial-time solvable, so this might not be a speed up.
Grover's algorithm gives a quadratic speed up in searching unsorted lists (which can be used as a speed up for a lot of algorithms).
Simulating quantum systems is also in BQP, but exponentially slower on a classical TM.
Solving Pell's equation (not really one equation) is in BQP, another exponentially speed-up.
There's also a number of other, more obscure, problems that are in BQP, but appear not to be in P. Wocjan and Zhang give a good starting point to dig them up.


Turing machine halting in at least 100 steps on all inputs

You have not correctly computed $\overline{L}$. It contains

machines which halt in less than 100 steps for some input (which is a finite set of possibilities, as you say), and
machines which don't ever halt for some input.

The second part requires a solution to the halting problem, so $\overline{L}$ is not decidable (nor recursively enumerable).


For every context-free grammar, is there an equivalent grammar in Chomsky normal form?

Depends on how strict you interpret "equivalent". A CFG in ChNF cannot generate the empty string. If you want to have a more precise statement:

  For every CFG $G$ there is a grammar $G'$ in ChNF such that
  $L(G) = L(G') - \{\varepsilon\}$.

So now we have two choices.

Either to accept the loss of the empty string, which in practise is not a big deal. Or we have to adapt the definition to make room for generating the empty string in a special way. This usually means we allow a production $S\to \varepsilon$ where $S$ is the axiom, provided $S$ does not occur as right hand side of productions.

This is a matter of taste: there is no "best" definition. Personally I think having a special production for $\varepsilon$ is not elegant, and prefer a notion of equivalence "upto the empty string".


Alternative proof for the undecidability of $A_{TM}$

There is no paradox. We have made an assumption, namely that the halting problem is solved by some Turing machine, and using it reached a paradox. Hence our assumption must be wrong. In the same way, Russell's paradox is a proof that the collection of all sets not containing themselves is a proper class.

In both cases, the paradox is solved by concluding that some object cannot exist. In the case of Russell's paradox, we can give a description of the object - properties it satisfies - but it doesn't exist as a set. In the same way, the halting problem is definable, but there is no Turing machine that accepts it.

In recursion theory we can breathe life into it by making it an oracle, and consider the implications. Similarly, in set theory we can consider relativized versions of Russell's set (relativized to some set "sub-universe"), though due to the axiom of regularity the result isn't interesting.


Fast algorithm to find points on one side of hyperplane?

The keywords you may be looking for are simplex range searching and half-space range searching. See chapter 16 of Computational Geometry: Algorithms and Applications. If you are interested in general simplices (intersections of multiple half-planes), then there are two data structures in particular that might interest you: partition trees and cutting trees.

In the following paper describing partition trees, we have query time of $O(n^{1-1/d}(\log n)^{O(1)})$, preprocessing time of $O(n \log n)$, and space requirement of $O(n)$.

Matoušek, Jiří. "Efficient partition trees." Discrete & Computational Geometry 8.1 (1992): 315-334.

In a cutting tree, you consider the dual case (each point in your input is represented by a line in the dual plane) and you tradeoff space for query time. You get $O(\log n)$ query time at a cost of $O(n^{2+\epsilon})$ space.

However, if you really only care about a single half-plane in your query, you can do better. In The Power of Geometric Duality, Chazelle gives an optimal data structure for half-space range queries with $O(\log n + k)$ query time and $O(n)$ space.


Does iterated PSPACE trace equal ELEMENTARY?

Yup. If you have two algorithms $A,A'$ both in PSPACE, and you run $A'$ on the output from $A$, the resulting algorithm is in EXPSPACE.  Think about it: how much space is used by them together?  Well, it's the amount of space for $A$, plus the amount of space for $A'$.  If the input is length $n$, then the output of $A$ is at most $2^{p(n)}$, so the amount of space used by $A'$ is $q(2^{p(n)}$, where $p,q$ are polynomials.  Thus the computation is in EXPSPACE.

Also, any computation in EXPSPACE can be expressed in this way.  Suppose you have any language that can be computed in EXPSPACE, i.e., in $2^{p(n)}$ space.  Then you can take $A$ to copy its input to the output, then output a string of $2^{p(n)}$ 1's; then $A'$ can do the computation itself, and since the input to $A'$ has length $2^{p(n)}$, $A'$ will use space polynomial (in fact linear) in its input length.

You are also correct about the iteration of three of these; the result is in 2-EXPSPACE.


Asymptotic notation for multivariable functions is defined analogously to its single variable counterpart. In the single variable case, we say that $f(n) \in O(g(n))$ if and only if there exists constants $C,N$ such that for all $n > N$ we have  $f(n) \leq Cg(n)$. In other words $f(n)$ is upper bounded by some multiple of $g(n)$ for all $n$ larger than some fixed $N$.

In the multivariate case, the definition is nearly the same, except you have a few more variables to worry about. Let's suppose $f(n,m)$ is a function of two variables. We want to bound $f$ from above by another function of two variables. So we say that $f(n,m) \in O(g(n,m))$ if and only if there exists constants $C,N$ such that for all $n>N$ and $m>N$ we have $f(n,m) \leq Cg(n,m)$. The definition is nearly exactly the same, except now all of our variables must be greater than our fixed constant $N$.

The wikipedia article used $\overrightarrow{x}$ to mean a vector in $\mathbb{R}^d$ which would mean that $f$ and $g$ were multivariable functions of $d$ variables (i.e. $f,g:\mathbb{R}^d \rightarrow \mathbb{R}$). Saying that $x_i > N$ for all $i$ meant that each component of $\overrightarrow{x}$ had to be greater than $N$.


Deadlock avoidance: How does the system know in advance about the number of resources required by a process?

For many systems, it's impossible to know (for instance, your home computer). In a very controlled system, you could know in advance about the number of resources that a process requires and when these requests occur (for example, an embedded system).

You could probably create some sort of heuristic for what resources might be requested in the future based on previous knowledge (such as past program execution or code analysis) for the impossible cases. I'm not sure how much this is done in practice though.


Combining Production Rules using Reinforcement Learning

this writeup by Kenan Deen solves the Tower of Hanoi problem with reinforcement learning and Markoff decision processes.

Tower of Hanoi – Reinforcement Learning

there is some other research on using genetic programming in "solving" (successfully playing) video games. these approaches do find "subroutines" that can be regarded as subgoals. for example, in playing pacman, an algorithm might have a subroutine/ subgoal that eats ghosts if they are blue, otherwise, run away from them. the sample algorithms are sometimes encoded as LISP-like trees. see eg

Evolving diverse Ms. Pac-Man playing agents using genetic programming / Lucas.
possibly the earliest case of this technique for solving pacman was reported by Koza in 1992 in the book Genetic Programming: on the programming of computers by means of natural selection


If $L_1L_2$ is regular language then $L_2L_1$ is regular to?

I was posting only a hint, then I saw other full answers, so this is a full (hidden) succinct solution :-)

   Let $L_1 = \{ 1^p \mid p \text{ is prime}\}$, $L_2 = \{ 1^* 0 \}$; we have $L_1 L_2 = \{ 11^+ 0\}$ which is regular, but $L_2 L_1 = \{ 1^* 0 1^p \mid p \text { is prime}\}$ which is not regular.


The invariant states that if at some point of the algorithm, $d_1,d_2$ are in different blocks, then in every croip, $d_1,d_2$ are in different blocks. The contrapositive of the invariant states that if $d_1,d_2$ are in the same block of some croip, then they are always in the same block during the running of the algorithm.

Now consider a block $S$ of your algorithm and a block $T$ of an arbitrary croip. We want to show that either $T \subseteq S$ or $T \cap S = \emptyset$. If not, then take some $d_1 \in T \setminus S$ and some $d_2 \in T \cap S$. Since $d_1,d_2 \in T$, they are in the same block of some croip, and so the contrapositive of the invariant states that they are always in the same block during the running of the algorithm. But $d_1 \notin S$ while $d_2 \in S$, and we reach a contradiction. We conclude that either $T \subseteq S$ or $T \cap S = \emptyset$.


Reduction from Clique to IS degree at most 4

As you stated, this is not a correct reduction, because you would need to solve Clique for any graph (or prove that Clique with graphs of degree at most 4 is $NP$-complete).
Actually, the question 8.6.b stands true if the graph have degree at most 3. I think the intention of the author for solving this exercice is to use the remark stated at the beginning of the exercice (which you cropped): "$\textsf{3SAT}$ remains $\textsf{NP}$-complete even when restricted to formulas in which each litteral appears at most twice".
You should then make a reduction from $\textsf{3SAT-2LITmax}$ (a convenient name I came up for the problem I just described), using the same kind of reduction to prove $\textsf{NP}$-hardness of $\textsf{IS}$ from $\textsf{3SAT}$.


Why is the running time of heapsort $O(n\log n)$?

Each call of MAX_HEAPIFY takes time $O(h) = O(\log n)$, where $h$ is the depth of the heap. Note that big O is an upper bound on the running time, not the exact running time. It is also true that the running time of MAX_HEAPIFY is $O(n)$, for example.


Verification wanted: Show the language $L=\{0^m1^n \enspace | \enspace m \neq n\}$ is not regular

This is a very hard one to prove via the pumping lemma, as you have to construct a string that eventually gives you something of the form $0^{n}1^{n}$ for some $n$ when you pump it the right number of times. As Renato notes, your decomposition (at the time of writing this answer) is incorrect. We'll come back to this.

A simpler way is to use the closure properties of regular languages. In particular, regular languages are closed under complementation and intersection, so

If $R$ is regular, then $\overline{R} = \Sigma^{\ast}\setminus R$ is also regular.
If $R_{1}$ and $R_{2}$ are regular, then $R_{3} = R_{1} \cap R_{2}$ is also regular.

So we assume that $L = \{0^{m}1^{n} \mid m \neq n\}$ is regular. Then by (1), $\overline{L} = \Sigma^{\ast}\setminus L$ is regular. In particular note that $\overline{L}$ includes all strings of the form $0^{n}1^{n}$.

The language $A = \{0^{a}1^{b} \mid a,b \in \mathbb{N}\}$ is regular (we can show this via a regular expression, DFA or regular grammar for the language, e.g. $0^{\ast}1^{\ast}$).

Then by (2) $\overline{L}\cap A$ must also be regular, but this is the language $\{0^{n}1^{n}\}$, which is not regular (and much easier to prove via the pumping lemma!).

As noted in the question you linked however, it is possible to do it with the pumping lemma, but you need to pick your starting string carefully. As we only have two sections to the string, the obvious approach is to have a string of the form $0^{p}1^{x}$ for some $x$, so then we know that $y = 0^{k}$ for some $k\leq p$. Now the trick is to pick $x$ such that we can pump the string some number $y$ times and get $p + (y-1)\cdot k = x$. Of course we don't know what $k$ is - it could be anything from $1$ to $p$, so $x$ needs to take this into account. Hence $x$, in part, needs to (almost) be a multiple of every number from $1$ to $p$. So if we pick $x = p + p!$, we can say that for every $k$, there exists a $y$ such that $p + (y-1)\cdot k = p + p!$. In particular $y = \frac{p!}{k}+1$.

So then our starting string is $s=0^{p}1^{p+p!}$. By the pumping lemma if $L$ is regular, we can break $s$ up in $xyz$ such that $|y| \geq 1$, $|xy| \leq p$ and $xy^{i}z \in L$ for every $i \in \mathbb{N}$, but we have just shown that for $i = \frac{p!}{k}+1$, we get the string $0^{p+p!}1^{p+p!} \notin L$. Hence $L$ violates the pumping lemma, can thus can't be regular.


Binary operators with higher precedence than unary operators

In Perl, the 'not' operator has lower precedence than +. The expression (false + not 1) evaluates just fine.


Is there a correspondence between the syntaxes and the type systems of programming languages?

You seem to have a misunderstanding of the purpose of abstract binding trees (ABTs).  They are a tool for describing syntax, much like abstract syntax trees (ASTs).  They simply allow you to describe syntax that includes binders in a way that generic tooling can be applied.  Capture-avoiding substitution, for example, works basically the same way for first-order logic as it does for the untyped lambda calculus, so it would be nice to implement it once and then "instantiate" it to these particular languages.  This is what ABTs accomplish.

Just like ASTs, ABTs have little to no semantics on their own, even when instantiated to a particular syntax.  An ABT describing the syntax for the untyped lambda calculus is doing just that, describing syntax.  Until you add the beta rule, it's not the lambda calculus.  Similarly, if I make an ABT for the the syntax of the simply typed lambda calculus, the ABT won't stop me from making ill-typed nonsense.  A type checker still needs to be implemented.  Indeed, the exact same ABT could be used for very different type systems or semantics.  For example, the difference between the linear lambda calculus and the typed lambda calculus is not a matter of syntax. Similarly, the difference between the call-by-value untyped lambda calculus and the call-by-name lambda calculus is entirely in when the beta rule can be applied, syntactically they are identical.


1) The automaton "halts" after it reads the input, whether or not it reaches a final state.  It accepts the input if, when it halts, it's in a final state.

2) Inputs are always finite strings.  There are generalizations of finite automata ($\omega$-automata of various kinds  [Buchi, Rabin, Muller]) that accept $\omega$-words (countably infinite strings) as inputs.


Do "inductively" and "recursively" have very similar meanings?

No, but not for the reasons other people have given. The difference between recursion and induction is not that recursion is "top-down" and induction is "bottom-up." Induction is isomorphic to something called "primitve recursion," but, in general, recursion is strictly more powerful than induction.

The distinction between top-down and bottom up is trivial -- any "top-down" primitive recursive program can be mechanically converted into something "bottom-up." In fact, any proof by induction can be turned into a recursive program. In the framework of the calculus of inductive constructions, if you want to prove that every natural number is froopulous, you'd write it as a function that constructs a proof that n is froopulous by making a recursive call to construct a proof that n-1 is froopulous.

The key factor of induction is that things are defined in terms of smaller things, and they "bottom out" after finitely many steps. Natural numbers are inductive because every natural is either 0, or the successor of a smaller natural. Lists are inductive because every list is either empty, or can be broken down ("unfolded") into an element and a smaller list.

Sometimes recursive programs aren't written in terms of smaller things though. For example, take this Collatz funtion:

fun collatz(n)
   if n <= 1
      return 0;
   else if n % 2 == 0
     return 1 + collatz(n / 2)
   else
     return 1 + collatz(3 * n + 1)
end

This function goes neither top-down nor bottom-up, and is thus not inductive over the natural numbers.

There might be an ordering to treat that inductively, but for most things there's simply no way. Functions over infinite streams are a great example. In fact, streams are the prototypical example of a "coinductive" type.

Bob Harper's "Practical Foundations for Programming Languages," available free online, has a nice introduction to inductive, coinductive, and recursive types.


Max number of configurations of a Turing Machine

Yes, that's right.  If there are $k$ possible configurations, then any such Turing machine either runs in time at most $k$, or it loops forever.  That's because if it runs for at least $k+1$ time steps, some configuration must be repeated; and if a configuration is repeated, it will continue repeating forever.

Let $|\Gamma|=2^c$, i.e., $c = \lg |\Gamma|$.  Then $|\Gamma|^{f(n)} = (2^c)^{f(n)} = 2^{c f(n)} = 2^{O(f(n)}$.  For similar reasons, $\vert Q \vert \cdot f(n) \cdot \vert \Gamma \vert ^{f(n)} = 2^{O(f(n)}$.  So, the number of possible configurations of a $f(n)$-space-bounded Turing machine is $2^{O(f(n)}$, and thus any such machine must either halt in time at most $2^{O(f(n)}$ or loop forever.


Yes.  Any known pattern can be used for camera calibration, if you know the ground-truth shape.  You just need to have a number of points where you know (a) their location in the image and (b) their location in the physical world.  The procedure is simplest with a grid, so if you're choosing a pattern, might as well stick to that standard (why not?).

Questions about implementation and OpenCV are off-topic here, though.


Is there a simple way of calculating perceptron weights based on a classification graph?

think that you may be somewhat misinterpreting the point of the question. the intent of the exam question seems to be, "what good perceptron weights would result for this classification problem". the reason for this is that one cannot go through all the steps of a long-running algorithm during an exam or even homework.

so going back to perceptron theory [which is several decades old] the point is that its a classifier based on linearly separable functions, ie linear inequalities. for the 2d case this results in simple algebraic geometry. in other words the perceptron can implement some number of linear inequalities to attempt to create the classification. here it is given as $n=2$. so the question probably intended is, "what are two linear inequalities that a good perceptron algorithm would converge to for this problem".

so it seems to reduce to find the coefficients of:

$y < m_1 x + b_2$

$y > m_2 x + b_2$

so then use basic geometric algebra to determine the coefficients $m_1, m_2, b_1, b_2$ that work for the above diagram. based on the diagram there is not a perfect solution, but a "good" one. (also note that the equations only need to work within $[0,1]^2$.)

intuitively, its also somewhat implied from this analysis why perceptrons are so limited. because its easy even in 2d to draw classification problems for which there is no linearly separable solution (concave shapes, shapes with holes in them, etcetera— some hint of this is seen in noting the above shape is slightly concave). this observation, fleshed out in a more sophisticated/formal/mathematical/rigorous way in [1], caused a lot of controversy at the time & was an important debate in the history of AI, and even apparently discouraged some scientists from investigating more sophisticated simulated neural network models for some time, although Minsky emphatically denied that was his intent and said his work was misinterpreted.

[1] Perceptrons, by Minsky & Papert


I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }

Yup, I can see why that would be confusing.  The typesetting is probably making this harder to follow.  I'm guessing what's written is $\{w \mid |w| \text{ is odd}, \ldots\}$.   This is the set of all $w$ such that $|w|$ is odd etc.  Here $|w|$ typically represents the length of the word $w$.

It might have been clearer if the author had used a colon instead of a vertical line in our set builder notation: then it would have been written $\{w : |w| \text{ is odd}, \ldots\}$, and maybe it would be easier to see what is going on..


Building probability distribution functions from observation

i am not sure i understand correctly what the question is or rather what are the observations from which the (experimental) distributions are going to be estimated.

The problem of a distribution estimation is related more to statistics than computer science althougn it can be relevant in this area as well.

There are various methods using 2 main approaches:

Parametrized models of a probability distribution, where one (assuming prior knowledge) uses a pre-defined model (or form or function) of the distribution (e.g a Gaussian) with some free parameters depending on data (observations) and estimates these parameters (eg through Maximum Likelihood or EM algorithm or Maximum Entropy etc..). Even if the form of the prob distribution is not known this method can still be used on approximations like Gauusian Mixture Models. This method produces smooth (and usually robust) estimated distributions assuming the prior form is close to the underlying prob. distribution.
Un-parametrized models, estimate the whole PD (including its form) directly from the data. methods in this category are Parzen windows and kernel estimation. This method can be better from parametrized estimation provided the form of the underlying pdf is completely unknown or non-trivial or irregular in some sense.

All the previous methods are computationally efficient (although not necessarily polynomial). This is like the way the Simplex algorithm works, although it is not polynomial-time, it is efficient in many practical situations.


Call $(0+11^*0)$ as A and $(1+01^*0)$ as B. Then what you have on left-hand side is just: $$ R = A + AB^*B$$
Using Arden's Theorem we know that in this case: $$R = AB^*$$

Then what we have simplified is: $$(11^*0+0)(1+01^*0)^*$$
Another simplification using Arden's Theorem would give us:
$$(11^*+ \epsilon)0(1+01^*0)^*$$
Which is finally equivalent to: $$1^*0(1+01^*0)^*$$


Addition of 3 bits using Full Adder when the initial carry bit is 0

A full adder adds three bits and outputs a sum and a carry. If you want to add three bits, you just connect them to the inputs x, y, and carry of the full adder.

If for some reason there is a requirement that the carry input of the first full adder must be zero, then you leave that first full adder totally unconnected and connect to the three inputs of the second full adder.


Zero-padding is used to compute longer FFT, in your case the signal is padded to be power of 2. In fact, there is no need to do so, there are FFT available using different lengths (also prime ones).

The zero-padding does not introduce new data, does not change sampling frequency of the original signal, it just interpolates the values. In your example there are 5 points, padding them to 8 introduces additional result bins that are closer to each other - this makes particular frequency bin shift, which is stored in the phase component of the result.

So the most probably your FFT is fine, just the test changes the distance between frequency bins, but this step is not included in reading phase, so the test is faulty.


Questions from Dijkstra's EWD 1300: "The notational conventions I adopted, and why"

Conjunction and disjunction are dual, but if conjunction has higher precedence than disjunction, then dual to p ∧ q ∨ r is (p ∨ q) ∧ r != p ∨ q ∧ r.
As you can see exc is dif with its arguments flipped: exc(x, y) = y - x. min is probably short for "minus", not "minimum".


Find all pairs (i, j), such that i + (i+1) + (i+2) + ... + j = n

Another algorithm:

Find all factorizations of $2n$ into a product of two integers, say $2n=r \times s$ with $r \le s$.  Then find $i,j$ such that $j-i+1=r$ and $i+j=s$, i.e., $i=(s-r+1)/2$ and $j=(s+r-1)/2$.  Check whether $i,j$ are positive.  If they are, output this pair $i,j$.  Do this for each way of expressing $2n$ as the product $2n=r \times s$.

How do you find all factorizations of $2n$ into two integers?  First factor $2n$ into a product of prime powers, say

$$2n = \prod p_i^{e_i}.$$

Next, for each $c_i$ with $0 \le c_i \le e_i$, you can let $r = \prod p_i^{c_i}$ and $s = \prod p_i^{e_i-c_i}$.  So in this way you can enumerate all such factorizations.  There will be $\prod (1+e_i)$ of them.

The running time for this is significantly faster than $O(n)$.  In the worst case the number of such factorizations can be no larger than $O(n^{1/2})$, so the worst-case running time of this method is $O(n^{1/2})$ -- already a significant speedup over Hendrik Jan's elegant answer.  Even better, in the average case, the number of such factorizations is far smaller than $n$, exponentially smaller, making this much faster.  Often, the dominant cost will be the cost to factor $2n$, which can be done in subexponential time using standard algorithms.


The constraint expresses the following fact:

  Let $T$ be a spanning tree, and suppose that we partition the vertex set into $r$ parts. There are exactly $r-1$ edges of $T$ which connect different parts.

For example, if $T$ is a tree and $C,\overline{C}$ is a cut, then exactly one edge of $T$ crosses the cut, that is, connects $C$ and $\overline{C}$.


Troubles understanding this Interval Scheduling question

You'll want to start by answering the question in the hint, and then make another argument to obtain the final result.

The hint is saying that for any job $j \in A$, there is a fixed upper bound on the number of intervals in $B$ with which $j$ overlaps. Think about what happens if $j$ intersects with three or more intervals in $B$. Would this be possible using the Shortest-Job-First algorithm?

Let the upper bound you obtain from the hint be $k$. Then, you can make the following argument (presented informally, as it is just a hint). Using our result above, we can state that in the worst case, we have each $j \in A$ overlapping with a subset of $k$ distinct jobs of $B$, where these subsets of $k$ jobs are pairwise disjoint. This gives you an upper bound on $|B|$ in terms of $|A|$.

Can you take it from here?


How to handle dfa with countless states?

You seem to have missed the last sentence of the question:

  What is the problem with this DFA?

The problem with this DFA is that it isn't finite (so it's not really a DFA).

A DFA is a static object — the only way it interacts with the environment is by switching states.


Does converting algorithms into elementary recursive form preserve runtime bounds?

This depends highly on the encoding.  If you consider bounded summation, the number of summations done is the value of the first argument of the function.

If the "encoding" (whatever that means) of the input is unary, this takes linear time, otherwise it takes exponential time in the size of the input. It is not obvious that it makes sense to assume input to be unary.

Elementary recursive functions are over natural numbers and do not speak of their encoding: is $s(0)$ encoded as $1$ or as $s0$?


Karger's min cut and tips on bounding nonlinear recurrences

First of all, let me explain why your estimate is lossy: when $P_i$ becomes small, $P_{i-1} - P_{i-1}^2/4$ is very close to $P_{i-1}$, and in particular, it doesn't decrease exponentially.
Since the function $x - x^2/4$ is monotone in the range $[0,1]$, if you solve the corresponding recurrence $Q_i = Q_{i-1} - Q_{i-1}^2/4$ (with base case $Q_0 = 1$), then $P_i \geq Q_i$.
Let us write the recurrence relation as $Q_i - Q_{i-1} = -Q_{i-1}^2/4$. This is a difference equation which can be approximated by a differential equation $q' = -q^2/4$, with $q(0) = 1$. Using standard techniques, you can determine the solution, which is $q(i) = 4/(4+i)$. This suggests that $Q_i \approx 4/(4+i)$, and so hints that $4/Q_i$ is a useful quantity to look at.
Here is another way to estimate the recurrence. Write the recurrence as $$ Q_i = (1-Q_{i-1}/4) Q_{i-1}. $$
In a range of $i$ where $Q_i \approx \theta$, it takes $\Theta(1/\theta)$ steps to reduce $Q_i$ by a factor of $1/2$. In particular, after
$$
\Theta(1+2+\cdots+2^{\ell-1}) = \Theta(2^\ell)
$$
steps, we reach $Q_i \approx 2^{-\ell}$. This suggests that $Q_i$ scales like $\Theta(1/i)$. With a little bit of work, this argument can be made completely formal, though it is hard to get a hold on the exact constant factor in this way.


Question about set-associative cache mapping

You're absolutely right: the question is unanswerable as stated because you don't know what's in the cache at the start of the sequence of memory accesses. You're probably expected to assume that the cache is initially empty but, if this is an exercise you've been set, you should ask your instructor to clarify.


Can maximal number in poset be more than one?

Consider for example the poset of all subsets of $\{1,2,3\}$ of size at most $2$ ordered according to inclusion. The maximal elements in this poset are $\{1,2\},\{1,3\},\{2,3\}$.

For an even more striking example, every antichain (set in which no two elements are comparable) is a poset in which all elements are maximal and minimal. For example, consider the poset of all subsets of $\{1,2,3\}$ of size exactly $2$ ordered according to inclusion. There are three elements $\{1,2\},\{1,3\},\{2,3\}$, and all are maximal and minimal.

It is always possible to add a maximal element to a poset so that it contains a unique maximal element. See if you can figure out how.


There are functions with f (n) = f (2n) which can't be calculated

Cook up some encoding of Turing machines so that if $n$ codes a machine, $2 n$ codes "the same" (perhaps use binary numbers ending in 1 as starting points, and 0s at the end are disregarded, thus making that odd $n$ and $n \cdot 2^k$ represent the same machine). Then use that e.g. $\operatorname{HALT}(M)$ (does $M$ halt if started on an empty tape?) isn't computable.


How do I explain that a polynomial time reduction is in fact polynomial time?

Your reduction indeed shows that $QuadSAT\in NP$, since you showed a reduction to a problem in NP.
Perhaps an easier way to have done this, is to simply show that there is a "short witness" for the membership of a formula in $QuadSAT$.
In order to show NP-hardness, you must show a reduction from an NP-hard problem. A good candidate for that is $SAT$ (or $3SAT$).


Not really.

Polling requires CPU cycles to poll a device and respond if needed. Detecting interrupts takes up no extra CPU cycles and is almost always done in parallel with instructions being executed. CPU cycles are only used up in servicing the interrupt.

Also, with polling, you have a control over how and when you poll devices whereas interrupts are generally out of sync with the program (or at least, you cannot exert too much control over when they arrive).

The mindset behind polling driven and interrupt driven code/architecture is entirely different.


Proof that the regular languages are closed under string homomorphism

First of all, homomorphism is a special case of substitution. Now define the homomorphism as a substitution $h$ that replaces each symbol $a$ in an alphabet $\Sigma$ for a string $h(a) \in \Gamma^*$, where $\Gamma$ can be another alphabet (they can perfectly be the same). Formally the homomorphism $h(\epsilon) = \epsilon$ and for all strings in $ \Sigma^*$, $$h(a_1a_2\ldots a_n) = h(a_1)h(a_2)\ldots h(a_n)$$

Then you are near to proving the closure. Try induction over the number of operands (unions, concatenations, stars) in the regular expression that represents the language $L$. Base step: $h(\epsilon)=\epsilon$ for all $a \in \Sigma^*$, $h(a)$ is a string over $\Gamma^*$ and $h(\emptyset) = \emptyset$. The induction hyphotesis says that if $L$ is regular, then $h(L)$ is regular. The inductive step has three cases: $L$ as a union of $A$ and $B$ ($A \cup B$), $L$ as the concatenation of $A$ and $B$ ($L=AB$) or $L = A^*$. Then you should be able to finish the proof.


How can a quadratic algorithm be faster than a linearithmic one?

All you know is that an $O(n\log n)$ algorithm is eventually (a lot) faster than an $O(n^2)$ algorithm, but for any specific value of $n$, you can't say anything. Indeed, the asymptotic growth of the function doesn't depend on its value on $n < 100$. This means that if $f(n) = O(n^2)$ then for all $c_1,\ldots,c_{99}$, the following function is also $O(n^2)$:
$$
f'(n) = \begin{cases} c_n & \text{if } n < 100, \\ f(n) & \text{if } n \geq 100. \end{cases}
$$
So asymptotic notation is completely uninformative regarding the performance of algorithms on specific values of $n$.

You could say that functions such as $f'(n)$ are artificial and never really occur in practice. This is not quite true (you can hard-code some auxiliary information for small $n$, for example), but even if you consider "natural" functions, asymptotic notation doesn't help you to determine anything other than asymptotics: consider for example $n^2$ against $10^{100} n\log n$ (such examples definitely happen in practice, for example in fast matrix multiplication).


How to prove properties about a specific modular arithmetic equivalence

You can prove it by calculating the value of $a^3 \bmod 7$ for $a=0,1,2,3,4,5,6$; if none of those yield 5, then you have proven the claim.

Why is this sufficient?  Well, if $a \equiv b \pmod 7$, then $a^3 \equiv b^3 \pmod 7$.  So, if there was any solution to $a^3 \equiv 5 \pmod 7$, then you could take $b = a \bmod 7$, and that would be another solution.  Now $b$ is one of $0,1,2,3,4,5,6$, so we've proven that if there is any solution, then one of $0,1,2,3,4,5,6$ must be a solution.  Conversely, if none of $0,1,2,3,4,5,6$ is a solution, then there is no solution whatsoever.

For the special case of squaring (rather than cubing), you might be interested in quadratic reciprocity, which is a more advanced technique that allows to check for the existence of solutions to such an equation.  There is also cubic reciprocity, though I'm not sure whether it leads to an efficient algorithm to check for solutions when you have a cube instead of a square.


What is the fastest addition algorithm on a turing machine?

(This should be a comment but I can't comment yet)

Just to clarify, when you have an integer $n$, it's represented on $\operatorname{size}(n)=\log_2 n$ bits.

So here, you are given $n_1$ and $n_2$ and you want to compute $n_1+n_2$. Let $f(n_1, n_2)$ be the number of steps needed to compute that. You seem to be claiming that $f(n_1, n_2)=O\left((n_2)^2\right)=O\left(\left(2^{\operatorname{size}(n_2)}\right)^2\right)$, which is obviously false. Now if you change it to $f(n_1, n_2)=O\left((\operatorname{size}(n_2))^2\right)=O\left((\log_2 n_2)^2\right)$, it becomes a little bit more plausible.

But that still can't be the complexity because if you have $n_1=2^{k}-1$ and $n_2=2^0$, your algorithm will at least read $n_1$, which takes $O\left(\operatorname{size}(n_1)\right)=O\left(\log_2 n_1\right)=O(k)$ while $O\left((\log_2 n_2)^2\right)=O(1)$ in these cases. The complexity should depend on the size of $n_1$ one way or another.


Why are there multiple computer languages instead of multiple libraries?

There are many features that cannot be simulated by a library (or rather - are very hard to simulate by a library), for example garbage collection, or exception handling. And even features which can, say object-oriented programming, are much easier to use when they're part of the core language.

You can certainly have a library in C implementing an interactive python interpreter, and then you can just put python code in quotes as input. There are several problems with this: it will be hard to debug, and syntax highlighting could be a nightmare. However, the real issue here is that if you've gone that far, you actually have a python interpreter.

Simulating python in any other way seems difficult: how would you implement control structures, for example? How would you implement message passing, operator overloading and so on? You will need to replace the usual operators by named functions like add and so on, which aren't going to be very easy to use. And to implement message passing you will need to use variadic functions with string parameters, taking care to handle somehow named parameters. You will do all that, and still lack the interactive python interpreter.

You can say the same regarding any other language - even if you could simulate language features, it would be awkward. This even goes to object-oriented programming in the C++ tradition. You will need to have a special calling mechanism which wouldn't be able to do static type-checking, for example. And how about templates? This sounds even harder. You will need to have void* pointers, and to instantiate the code yourself.

Summarizing, modern languages are more than just syntactic sugar above C, and even if they were just that, it would still be very awkward to program them directly in C.


Getting O-bounds by applying regression methods to execution time measurements

It's impossible. No finite set of measurements can prove asymptotic bounds.

Proof sketch: Assume you had such a method. Apply it to any algorithm $A$. If your largest measurement is for input size $n_0$, construct a new algorithm $B$ that branches into $A$ for all $n \leq n_0$, and one with a different $\Theta$-runtime class for $n > n_0$. The method fails for $B$.

That said, there are ways to perform reasonable experiments (for average-case performance). I recommend the book "A Guide to Experimental Algorithmics" by C. McGeoch.


Is my algorithm a $O(nm \lg m)$ solution for sorting a row and columnwise sorted $2D$ array?

You should be careful using standard big-O analysis with more than one variable, I read a paper recently pointing out that this analysis can fail if certain assumptions are not met. In any case, let's assume for simplicity that $m$ is a power of 2. If it is not, the analysis will be very similar, just with some extra floors and other ugly stuff. In this case, we merge last two $n\times m/2$ arrays in time $2\cdot c\cdot (m/2)\cdot n$. Before that, we merged four (2x2) $n\times m/4$ arrays in time $4\cdot c\cdot (m/4)\cdot n$. Seeing the pattern, we add all of these times to get
$$\sum_{k=1}^{\log_2m}2^k\cdot c\cdot (m/2^k)\cdot n=\sum_{k=1}^{\log_2m}c\,m\,n=c\,m\,n\log_2m=O(n\,m\log m)$$
As a formality for the curious, I now cover the case where $m$ is not a power of 2. Then instead of two $n\times m/2$ arrays, we will have an array of size $n\times\lfloor m/2\rfloor$ and an array of size $n\times\lceil m/2\rceil$. Similarly, in the next step we get four arrays of sizes $n\times\left\lfloor\frac{\lfloor m/2\rfloor}{2}\right\rfloor$, $n\times\left\lceil\frac{\lfloor m/2\rfloor}{2}\right\rceil$, $n\times\left\lfloor\frac{\lceil m/2\rceil}{2}\right\rfloor$, and $n\times\left\lceil\frac{\lceil m/2\rceil}{2}\right\rceil$. Recursively, we have a runtime of
$$T(n,\,m)=T(n,\,\lfloor m/2\rfloor)+T(n,\,\lceil m/2\rceil)+c\,m\,n$$
Nobody wants to solve that, so I simply show that the complexity is still $O(n\,m\,\log m)$ if we take $m$ to be the next largest power of 2, call it $m'$. So I want to show that
$$\frac{n\,m'\,\log m'}{n\,m\,\log m}=O(1)$$
Say $m'=2^k$ and $m=f\cdot2^k$ for some $0.5\leq f<1$ ($f$ as in fractional coefficient). We can write $m$ this way, since it is between $2^{k-1}$ and $2^k$ by construction of $m'$. This means that $m'=f^{-1}m$. Then we have
$$\frac{n\,m'\,\log m'}{n\,m\,\log m}=\frac{n\,f^{-1}m\,\log(f^{-1}m)}{n\,m\,\log m}=\frac{n\,f^{-1}m(\log m+\log f^{-1})}{n\,m\,\log m}=f^{-1}+\frac{f^{-1}\log f^{-1}}{\log m}=O(f^{-1}+f^{-1}\log f^{-1})=O(1)$$
Then the case when $m$ is a power of 2 can be applied in general.


How fast can we compute the size of maximum matching in an unweighted bipartite graph?

I believe the best algorithm known is Hopcroft and Karp, "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs", SIAM Journal of Computing 2:4 (1973), pp 225-231.


If $B$ is in $SPACE(n^2)$ and $A \leq_p B$ then so $A$ will be in $SPACE(n^2)$?

$A$ may or may not be in $\mathrm{SPACE}(n^2)$.

Any language $A\in\mathrm{P}$ can be reduced be reduced to any nontrivial language $B\in \mathrm{SPACE}(n^2)$ in polynomial time.  Fix your favourite strings $x_\mathrm{yes}\in B$ and $x_{\mathrm{no}}\notin B$ ("nontrivial" means that $B$ is neither $\emptyset$ nor $\Sigma^*$, so both of these strings exist). The reduction is to determine if the input is in $A$; if so, map it to $x_\mathrm{yes}$; if not, map it to $x_\mathrm{no}$.

This is true regardless of whether $A\in\mathrm{P}\cap\mathrm{SPACE}(n^2)$ or $A\in\mathrm{P}\setminus\mathrm{SPACE}(n^2)$.

To get some intuition, it might help to look at it in another way. To show that $A\in\mathrm{SPACE}(n^2)$, you'd want to show that the algorithm "Reduce to $B$, then decide $B$" runs in quadratic space. However, the reduction from $A$ to $B$ might blow up the length of the instance by any polynomial amount.  For example, It could map a instances of length $n$ to ones of length $n^2$. So, now, if you try to decide $A$ by first reducing to $B$, you'll need space $(n^2)^2 = n^4$ to solve  the instance of $B$. Or the reduction itself might take more than $n^2$ space.


Myhill–Nerode equivalence classes of $\{0^n1^n \mid n \in \mathbb{N}\}$

Here is how to think of this question. The equivalence relation is determined by which extensions of the current word belong to the language. There are three cases:

The current word is not a prefix of any word in the language. This happens if either the word is not in $0^*1^*$ at all, or if it is of the form $0^n1^m$ but $m > n$.
There is a unique extension of the current word which is in the language. This happens if the word is of the form $0^n1^m$ with $m \neq 0$ (and, to exclude the case above, $m \leq n$).
There are multiple extensions of the current word which are in the language. This happens for words in $0^*$.

Let us now get into more detail:

If $w = 0^n$, then we can extend $w$ to a word in the language by adding $0^m 1^{n+m}$ for arbitrary $m \in \mathbb{N}$. Note that this set of extensions is different for every $n$.
If $w = 0^n1^m$ where $0 < m \leq n$ then there is a unique way to extend $w$ to a word in the language, namely by adding $1^{n-m}$.
Otherwise, $w$ cannot be extended to a word in the language.

Accordingly, the equivalence classes are:

$\{0^n\}$ for every $n \in \mathbb{N}$.
$\{0^{n+m} 1^m : m \in \mathbb{N}\}$ for every $n \in \mathbb{N}$.
Everything else.


Is Supervised Learning Better than Unsupervised Learning (For Recommendation Systems)

It doesn't make sense to ask if supervised learning is better or worse than unsupervised since they are used in different contexts.

In the most simple terms, supervised learning is used when you have a dependent variable, so you're investigating the relationship between this dependent variable and one or more independent variables.  Often you're trying to predict something about the dependent variable using the independent variable(s).

In unsupervised learning, you are essentially looking for certain kinds of structure in the data or trying to find various kinds of relationships between variables, but none are considered special in the sense of being a dependent variable.


What approaches are most useful when proving uncomputability of a given function?

There are unfortunately as many techniques to prove functions uncomputable as there are to prove things in general, so there's no comprehensive doctrine for how you should approach this.

Note that the proof by reduction is just a special case of a proof by contradiction; assuming that the function is computable leads to a proof that some other problem is computable, which is a contradiction if there's already a proof that the other problem is not computable.

Your first problem can immediately be shown to be uncomputable due to Rice's Theorem. Briefly, Rice's Theorem states that for any non-trivial semantic property of TMs, detecting whether a given TM has the property is undecidable. Semantic means the property depends only on the language accepted by the TM (all TM's accepting the same language have the property, or all do not have the property, regardless of the specific implementation). Non-trivial simply means that there do exist languages that have the property, and languages that don't. So one way to solve this problem is to simply recognise that "for all strings w accepted by M, the reverse of w is also accepted by M" is a non-trivial semantic property and invoke Rice's Theorem. That may not be the most satisfying way to solve your problem if you're doing this to learn though (although the proof of Rice's Theorem is quite accessible; it's essentially a very generalised reduction from the Halting Problem).

For your reduction proofs, remember that you can "cheat". You are assuming the existence of a solver (call it P) for the problem you're trying to prove undecidable, and show that if you had that you could solve the Halting Problem. This means your reduction can presume that P "just works" by black-box magic, regardless of whether it seems possible. In particular, you do not need to care that the machines you construct to feed to P halt or do anything at all useful; only that they cause P to accept/reject in a way that can be used to solve the Halting Problem (or some other undecidable problem, but I found the Halting Problem to be very productive when I was doing these sorts of exercises at uni).

For example, one of my most enjoyable exercises in my undergraduate Theory of Computation course was proving that it as undecidable to detect whether a TM ever attempted to move the tape head left from the left-most cell of the tape (in the model we were using this would cause the tape head to simply remain in the left-most cell). I did this by showing that for an arbitrary TM M you could construct a machine that was in fact guaranteed not to halt on any input, but would attempt to move left from the left-most cell if-and-only-if M halted on the same input.

So what you need to do to prove $R$ uncomputable by reduction is find some undecidable problem P, such that you can transform an arbitrary instance of P's input into a TM that has the property R if-and-only-if the original input to P should be accepted (or rejected; the negative works too).

Similarly for problem 2, the obvious (to me) thing to do is to take an arbitrary TM M, and transform it into a machine M' that halts exactly when M writes something on the output tape, and is guaranteed not to halt if M never writes something on the output tape. Don't get hung up on whether M or M' halts; you're not planning to run either of them, only to run your hypothesized solver for problem 2 with M' as input.


computably defined function with non computable range

Your question is a bit unclear, but you're probably looking for this example:
$$
A(x,n) =
\begin{cases}
x & \text{ if program $x$ halts within $n$ steps}, \\
\bot & \text{ otherwise}.
\end{cases}
$$
This is a computable function whose image is the set of halting problems (together with $\bot$).


Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)

It is enough to pad a special delimiter (say a comma) and $(|x|^2-|x|-1)$ 1's. Suppose $L_\mathrm{pad}= \left\{\left\langle x,1^{|x|^2-|x|-1} \right\rangle : x \in L\right\}$. Since $L\in\mathsf{DTIME}(2^n)$, there is a TM that can determine whether $x\in L$ in $O(2^{|x|})$ time. We then construct a new TM: given a string $y$, it first checks whether $y$ has the form $\left\langle x,1^{|x|^2-|x|-1} \right\rangle$, then simulates $M$ on $x$. This new TM determines whether $y\in L_\mathrm{pad}$ in $O(2^{|x|})=O\left(2^{\sqrt{|y|}}\right)$ time, so we have $L_{\mathrm{pad}}\in \mathsf{DTIME}\left(2^{\sqrt{n}}\right)$, thus $L_{\mathrm{pad}}\in\mathsf{NP}$ by your assumption. This means there exists a non-deterministic TM $M'$ that decides $L_{\mathrm{pad}}$ in polynomial time. Hence, we can construct a new non-deterministic polynomial-time TM that decides $L$ by first padding a comma and $(|x|^2-|x|-1)$ 1's to the input then simulating $M'$, which means $L\in\mathsf{NP}$.


Fantasy premier league dream team algorithm?

You can formulate an integer program for this problem. For each player $i$ let $a_i$ be the number of points the player scored, $p_i$ is his price. Moreover, let $G, B, M, F$ be the set of goal keepers, backs, midfielders and forwards, respectively, $P := G \cup B \cup M \cup F$ the set of all players, and $C$ is the salary cap. We use binary variables $x_i \in \{0, 1\}$ for each player $i$, were $x_i = 1$ iff player $i$ is in the optimal roster, $0$ otherwise. The optimal roster is then induced by the solution of the following program:
$$\begin{aligned}
\text{maximize } & \sum_{i \in P} a_i x_i\\
\text{subject to } & \sum_{i \in P} p_i x_i \leq C\\
& \sum_{i \in G} x_i = 1\\
& \sum_{i \in B} x_i = 4\\
& \sum_{i \in M} x_i = 4\\
& \sum_{i \in F} x_i = 2\\
& x_i \in \{0, 1\} & i \in P
\end{aligned}
$$
Now you may have noticed that the objective function + capacity constraint is indeed a knapsack problem but you have additional constraints on the formation.

Although you can use a MIP solver of your choice, you might even exploit this knapsack structure as a subproblem by using a knapsack solver (I think there is some very popular dynamic programming approach).


Why $R\circ\emptyset$ is not always equal to $\emptyset$

Assuming by "$.$" you mean concatention ($\circ$ when made explicit by Sipser) and by $\phi$ you mean $\emptyset$, I'm not sure what the confusion is. Sipser is claiming that sometimes (in almost every case actually), $R\circ\emptyset \neq R$. You are correct in saying that $R\circ\emptyset = \emptyset$, so the only case where $R\circ\emptyset = R$ is when $L(R)=\emptyset$. For any regular expression that generates at least one string (including $\varepsilon$), $L(R) \neq \emptyset$ but $L(R\circ\emptyset) = \emptyset$, so $R\circ\emptyset \neq R$.


Dynamically Learning Haar Cascade (in OpenCV)

Sadly, I don't know of any simple way to achieve this, for Haar cascades.

The problem is that Haar cascades are trained using boosting.  A cascade is a multi-stage classifier: we use the first stage to quickly discard candidates: if the first stage says "no", we immediately reject, and only go on to process the input with the second stage if the first stage says "yes".  That means that the second stage is trained on only images that the first stage classifies "yes".  If you add some more training examples and want to update the first stage, then now this has cascading effects on all of the subsequent stages: naively, you need to re-train all subsequent stages, because the set of images they should be trained on has now changed.

There might be a clever way to do it, but it's not straightforward.


Compare the growth of $2^{n}$ to $n^{a}$ for all $a \in \mathbb{N}$?

As a hint, $n^\alpha = 2^{\alpha \log_2 n}$. Now, you can compute the ratio between these functions by subtracting the exponents. There's no need to use l'Hôpital's rule.


First, it is not known that 3-coloring takes exponential time. Even if P is different from NP, it could still be the case that 3-coloring can be solved in subexponential time, though the Exponential Time Hypothesis (ETH) precludes this possibility (if you assume the hypothesis).

Second, regarding your suggested solution. The black box only accepts graphs, it doesn't accept partially colored graphs. You need to give a reduction which only feeds the black box  actual graphs.

Third, if a graph is 3-colorable, then there is always a 3-coloring in which a particular vertex is red. So what you're really trying to do is ask whether there is a 3-coloring in which a given set of vertices has the same color, another set of the vertices has a different color, and yet another one has the remaining color. See if you can somehow encode some of these constraints using graphs rather than partial colorings.


What is the possible number of states in the DFA of intersection of two given FA?

The product construction shows that if $L_1$ is accepted by a DFA having $n_1$ states and $L_2$ is accepted by a DFA having $n_2$ states then $L_1 \cap L_2$ is accepted by a DFA having $n_1n_2$ states; browse back to the product construction to understand why. The resulting DFA need not be minimal even if the DFAs for $L_1$ and $L_2$ were (a trivial example is given by $L_1 = L_2$, assuming $n_1>1$). In your case, this means that if you can find a DFA for $\{w : 6\mid \#_a(w)\}$ having six states and one for $\{w : 8\mid \#_b(w)\}$ having eight states, then you can find a DFA for the intersection having 48 states.

Is this DFA minimal? You can use the Myhill–Nerode criterion to show that indeed it is: the 48 words $\{ a^i b^j : 0 \leq i < 6, \; 0 \leq j < 8 \}$ are pairwise incomparable.


Help with context free grammar excercise

I think you can do it in this way
$$\begin{align}
X&\to A\ |\ aXc\ |\ aAc\\
A&\to aA_t\\
A_t&\to aA_t\ |\ B\\
B&\to bB_t\\
B_t&\to bB_t\ |\ \epsilon\\
\end{align}$$
Here $X$ can choose to do the first transformation, if there are not going to be any $c$s. $X$ can do the second transformation many times to add an initial chunk of the same amount of $a$s and $c$s, or do the third transformation to put a last pair of an $a$ and a $c$.
In that third case, it goes to $A$ which puts one extra $a$ and goes to $A_t$, which can put even more $a$s or go to put $b$s.
Then $B$ puts one $b$ and goes to $B_t$, which puts as many more $b$s as wanted or terminates.
But check it. This is the first ever context free grammar rules that I write in my life.

Shorter rules by nir shahar
$$
\begin{align}
S&\to AB\ |\ aSc\\
A&\to aA\ |\ a\\
B&\to bB\ |\ b
\end{align}
$$


Maximization problem on finite collection of finite sets

This problem is NP-complete. Let's reformulate it first: we have a bipartite graph, where

The left side corresponds to elements
The right side corresponds to sets
The edge $(u,v)$ means that $u \in v$.

Our goal is to find the bipartite clique with the maximum number of edges. As stated in Rene Peeters, "The maximum edge biclique problem is NP-complete", the decision problem is NP-complete.


Complexity of recursive solution to coin change

A general method for solving recurrences of this form is generating functions. The exact solution also depends on the initial values. In your case, one possible solution is $T(n,k) = C 2^{n+k}$.