Hash table where items can fall into multiple buckets. What's the name of the data scrtucture?

Whether it is a good approach or not entirely depends on the time/space requirements of your particular application. All data structures have trade-offs. Your primary alternatives for storing partitions of a multiset are:

Collection of containers/dictionaries: you can store each subset in a different container or dictionary (such as an array or a hash table). This will allow fast unions and intersections between specific subsets, but slow membership queries. This is probably the data structure that you are trying to implement.
Generalized bit vector: assuming that your universal set $U$ is not too big, you can define a two-dimensinal array. The $i$th element of this array will store the identifers of the subsets that contain $i$. Membership queries will be fast; however, unions/intersections take time proportional to $U$.
Dictionary with a subset attribute: you can store each distinct element of the multiset in a dictionary (e.g., a hash table); then, associate an attribute to each element. This attribute will record the identifiers of the subsets that contain the element. Membership queries can be performed in the time it takes to search in the dictionary; however, union/intersection operations are again slow.
Union-find: in this data structure, each subset is represented as a rooted tree that is made up of parent pointers. This idea is extremely useful since it enables membership queries and union of subsets in (nearly) constant time. It does not support, however, to split previously unioned subsets.

For more information about all of these choices, you can have a look at Section 12.5 of The Algorithm Design Manual [1].

[1] Steven S Skiena: The Algorithm Design Manual, Springer-Verlag London (2008).


Clarification on evenly dispersing modular hashing

The remark is quite cryptic. If $m = 2^r$, then only $r$ bits of the input affect the value of the hash. But it any other circumstance, all input bits affect the value of the hash.
By the way, your example ($7,17,27,37$ all get mapped to the same value modulo $10$) works for any value of $m$. For example, $7,18,29,50$ all map to the same value modulo the prime $11$.


Decidability of directed strongly connected graphs

Yes, the DFS is an algorithm, and hence has an equivalent turing machine. The definition of the decidability as you have said, is for the language to be exactly accepted by some turing machine.
The formal definition of the turing machine accepting the language of strongly connected graphs probably is waaaay too hard to explicitly write, so I guess your teacher meant for you to show an algorithm and state that an algorithm is equivalent to a turing machine.
Btw, as a side note, you can run DFS only twice in total instead of $n$ times - once per node. If you have free time, its a good exercise in algorithms :)


Minimum number of adjacent swaps needed to sort a circle of elements

Suppose we have two lists $L$ and $M$ of length $n$. They are identified as circular lists if and only if, when you write out $(L_1 \ldots L_n)$ and $(M_1 \ldots M_n)$, they give the same permutation, when considered as an element of $S_n$.

We can consider the graph $\Gamma$ with vertex set $(123\ldots n)^{S_n}$ (that is, the $n$-cycles in $S_n$). $\Gamma$ has an edge $(v, w)$ iff there is a transposition of adjacent elements (adjacent when we write $v$ down as $(v_1, \ldots, v_n)$) taking $v$ to $w$. This is well-defined since the only different way to write a cycle is by cyclically permuting it - the adjacent elements stay adjacent.

Given a circular list $L$, the problem is now finding the distance in $\Gamma$ from $L$ to $(1\ldots n)$.

To actually compute this, I used the GAP algebra system. We can take some steps to define the edges in a nicer way.

Let $G = S_n$. $G$ acts on the vertex set $V$:

$$\sigma \cdot (v_k)_{k=1}^n = (v_{\sigma(k)})_{k=1}^n$$

Also notice there is one vertex orbit, since any vertex can be relabelled to any other vertex.

Using this, we can define the group action in GAP:

G := SymmetricGroup(n);
ncycle := PermList(Concatenation([2..n], [1]));
all_ncycles := ncycle^G;
action := function(cycle, g)
    list := WritePermAsList(cycle);
    result := [1..n];
    for i in [1..n] do
        result[i] := list[i^g];
    od;
    return WriteListAsPerm(result);
end;

where WritePermAsList just writes e.g. the permutation (1,2) as the list [1,2] and so on.

Now we have the action, we can define a graph Gamma with vertex set $V$ with NullGraph and use AddEdgeOrbit to add all edges corresponding to the permutations we want to allow. In this case, we want to allow permutations of the form $(i\;i+1)$ and $(1 \; n)$. So we do AddEdgeOrbit(Gamma, [1, 1^Permutation(sigma, ncycles, action)]) for each sigma we want to allow.

Now computing the answer to the question I asked: "What is the minimal number of swaps required [to sort $L$]?" is just Distance(Gamma, 1, i) where i is the vertex representing our circular list $L$ since 1 represents $(1\ldots n)$ in our graph and we want to sort meaning get to $(1\ldots n)$.

I think this method isn't even that bad since I only really need this for small (length less than 10) lists. The simple structure of the graph means that we don't actually need to store all that much information about it (certainly we don't need to keep a huge list of vertices and edges in memory).

There are probably more insights about how to reduce this problem to something else, but this was good enough for me.


Why does the distribution of pseudorandom numbers change when operating like this?

rand() returns an integer uniformly distributed between 0 (inclusive) and RAND_MAX (exclusive).

When using modulo to partition those possibilities into 6 buckets you will end up with a few buckets that has 1 more possibility than the others. This means the random result ends up biased.

However the exact same thing happens if you use divide. The only difference lies in which buckets get biased.

This is due to pigeon stuffing. There is no way to divide a population of $2^n$ individuals into 6 groups perfectly evenly.

Instead you should check whether one of the biassing results is returned from rand() and generate a new number if so:

int bias = RAND_MAX % 6;
int divisor = (RAND_MAX - bias)/6;

while(true){
    int random = rand();
    if(random < RAND_MAX - bias)
        return random / divisor;
}

The difference between divide and modulo for partitioning the data has to do with which bits are more random. Many implementations of rand() use a simple linear congruential generator where the more significant bits have better randomness than the lesser significant bits. In a good RNG every bit is equally random and it does not matter whether you use modulo or divide.

Having said all that if you really cared about randomness you would use a proper high quality random number generator that doesn't have some of the well known issues you'll find in a LCG.


Algorithm to check the distance between integers

If you allow no missing elements, there is indeed an algorithm that does not
need to check all values:

Since the numbers are distinct and sorted, the algorithm

$\qquad\displaystyle
  [a_1, \dots, a_n] \mapsto \begin{cases}
                              \mathrm{true}, &a_n = a_1 + n - 1,\\
                              \mathrm{false}, &\text{else}
                            \end{cases}$

solves the problem.

If $a_n \geq a_1 + n$ there has to be a step larger than one.
On the other hand, $a_n < a_1 + n - 1$ can not happen without duplicates (pigeon-hole principle).

If you allow some missing elements but not too many in a row, this no longer works.
We will show this by an adversary argument.

Assume there was a deterministic, correct algorithm $A$ that reads $<n$ of
the input values.
Then, $A$ answers false for inputs with $n$ elements of the form

$\qquad\displaystyle I_1 = [1,3,\dots,2n-1]$.

By assumption, $A$ does not read at least one value; let's call that one $i$.
Without loss of generality, let $i \not\in \{1, 2n-1\}$; these cases can be dealt
with similarly. Then, $A$ also answers false on

$\qquad\displaystyle I_2 = [1,\dots,i-2,\mathbf{i+1},i+2,\dots,2n-1]$

because it is deterministic; if it does not read $i$ on $I_1$ it will also
not read $i+1$ on $I_2$ since the other elements are all the same.

But this result is wrong since there is a gap of $(i+1) - (i-2) = 3$ in $I_2$.
This contradicts our assumption that $A$ is correct; therefore, there can be no
such algorithm.


How to understand definition of $\Pi_k$ in arithmetical heirarchy

For $k$ even, a language $L$ is in $\Pi_k$ if there exists a recursive predicate $R$ such that
$$
x \in L \Longleftrightarrow \forall y_1 \exists y_2 \cdots \forall y_{k-1} \exists y_k \, R(x,y_1,\ldots,y_k)
$$
The quantifiers alternate between $\forall$ and $\exists$.

When $k$ is odd, the same definition works, but the last quantifier is $\forall$:
$$
x \in L \Longleftrightarrow \forall y_1 \exists y_2 \cdots \exists y_{k-1} \forall y_k \, R(x,y_1,\ldots,y_k)
$$

For example, the language of all total Turing machines is $\Pi_2$ since
$$
x \in \mathsf{TOT} \Longleftrightarrow \forall y \exists z \, \text{"Machine $x$ halts on input $y$ within $z$ steps"}
$$

The class $\Sigma_k$ is defined in the same way, with the first quantifier being $\exists$ rather than $\forall$.

If you complement a language in $\Sigma_k$ you get one in $\Pi_k$, and vice versa. This is due to de Morgan's laws for quantifiers, and the fact that the negation of a recursive predicate is also recursive.

For example, the language of non-total Turing machines is $\Sigma_2$ since
$$
x \in \mathsf{NTOT} \Longleftrightarrow x \notin \mathsf{TOT} \Longleftrightarrow \exists y \forall z \, \text{"Machine $x$ doesn't halt on input $y$ within $z$ steps"}
$$


name matching algorithms from partial input

A cheap but possibly low-precision, low-recall way is to compute something similar to Soundex or Metaphone codes for your product names and candidates. This only really accounts for misspellings, and even then not reliably or in a principled way. But it's cheap to compute.

Alternatively, for a language-independent approach, consider computing the edit distance between each candidate and all the database entries, and return the cheapest match that's under some threshold. There's worked examples of how the Levenshtein distance is computed on the Wiki page.


Removing epsilon transition from context-free grammar

As described in the algorithm to put a given CFG in Chomsky Normal Form:

To remove the $\varepsilon$-rules: Remove a rule $A \to \varepsilon$ if $A \neq S_0$ ($S_0$ being the start-variable). To 'repair' the CFG, add for every occurence of $A$ in the body of a rule, the same rule but with $A$ removed.
Example: if you have rules $A \to B | \varepsilon$ and $B \to BAAB$. To remove the $\varepsilon$ for $A$, add for each ocurrence of A a new rule with A removed. In this case:
$A\to B$ (remove $\varepsilon$) and $B \to BAAB|BAB|BB$.

Finally, for rules of the form $R \to A$, add $R\to \varepsilon$ if you did not remove $R \to \varepsilon$ in a previous iteration.


What is the name of the domain or theoretical problem of transmitting game states in an online game

I'm not sure there is a single "name" for this non-trivial situation -- not every situation you will run into will have a single "name" or terminology for that situation -- but there are multiple topics and concepts that seem relevant:

As Draconis mentions, serialization or pickling are relevant for how to convert a complex data structure in memory into a sequence of bits that can be sent to another party.
Data synchronization and file synchronization may also be relevant; there are techniques that may be useful if the data structure representing game state changes slowly, as then it may be more efficient to send only the changes to the other parties without having to repeatedly send the current state.  You might enjoy reading about rsync and mosh.
Video games may use various methods for lag compensation that are worth knowing about.

Stack Exchange has an entire site for game development.  I suggest spending some quality time there perusing questions that seem related, to get a taste of some of the methods, concepts, and techniques that are relevant.


Consider the construction of an NFA from a regular expression $r$. The construction is by induction over the generating sequence of $r$. If you examine the different operations (union, Kleene star, and concatenation), you will see that each operation increases the size of the NFA by a linear blowup.

For example, an NFA for $r_1\cup r_2$ is obtained by nondeterministically starting in an NFA for $r_1$ or an NFA for $r_2$, so the size of the NFA is (by induction) at most $|r_1|+|r_2|$.

Now, determinizing an NFA with $k$ states may involve a blowup of up to $2^k$ states. However, the NFA you obtained from the construction has $k=O(n)$ states, so the blowup is $2^{O(n)}$. The paper you read shows that the $O(n)$ factor is in fact $n\cdot O(\log|\Sigma|)$, thus making the total size $O(|\Sigma|^n)$.


What does "If P1 is reduced to P2, then P2 is at least as hard as P1" mean?

Interpretation (i) is correct: "$A$ is at least as hard as $B$" means that $A$ is as hard as or strictly harder than $B$. (Think about numbers: "$a$ is at least as big as $b$" means "$a=b$ or $a>b$.")
Note that not only does "$A$ is at least as hard as $B$" rule out $A$ being strictly weaker than $B$, it also rules out $A$ and $B$ being of incomparable complexity. Complexity isn't a linear order; we can find problems such that neither helps us solve the other.


How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals?

Well, consider the following "proof" (I'll explain afterwords why the quotation marks):

Let $w=a_1\cdots a_n$ be a word, then we have that

$w\in (L_1L_2)^{\mathrm{rev}}$ iff

$a_n\cdots a_1\in L_1L_2$, iff

there exists $0\le k\le n$ such that $a_n\cdots a_k\in L_1$ and $a_{k-1}\cdots a_1\in L_2$, iff

there exists $0\le k\le n$ such that $a_k\cdots a_n\in L_1^{\mathrm{rev}}$ and $a_{1}\cdots a_
{k-1}\in L_2^{\mathrm{rev}}$, iff

$a_1\cdots a_n\in L_2^{\mathrm{rev}}L_1^{\mathrm{rev}}$ iff

$w\in L_2^{\mathrm{rev}}L_1^{\mathrm{rev}}$

In my opinion, this proof is correct, formal, and would be accepted as a proof of the claim.

However, each "iff" along the way (apart from the last one) actually hides an inductive proof. The point is that each of these inductions is extremely trivial.
In fact, even writing $w=a_1\cdots a_n$ actually hides some induction. So you need to ask yourself how "deep" do you want to go into the technicalities.

If you want to prove this claim from basic principles, i.e. from the axioms of set theory, then you need to formalize everything. This would be very painful, but such things are actually useful when we use computer-assisted proofs.


Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?

The case you are describing is NP-complete, so the answer is no.

I don't know if still remains NP-complete if the graph is a Euclidean graph. Anyone knows?


Prove that every thin AVL tree may be converted to red-black tree

Just a remark.

Your "thin" trees are sometimes know as Fibonacci trees. A Fibonacci tree $T_h$ of height $h$ is recursively defined as root with two subtrees $T_{h-1}$ and $T_{h-2}$. Hence the name.

As the number of black nodes along each path from root to leaf must be equal, this means that the subtrees $T_{h-1}$ and $T_{h-2}$ must have the same black height  in $T_h$, although they differ in height.


shortest cycle passing through vertices a and b with changeable edge weights

This solution assumes all weights are non-negative.

  Lemma. There exists an optimal traverse with the following shape ($A, B,C$ may be the same vertex and may coincide with $S,M,T$), where each arrow represents a simple path, and paths represented by different arrows are edge-disjoint.

The strict proof of this lemma is somewhat tedious, so I omit it here. If I have time in the future, I'll add it into this answer.

Let $d_a(x,y), d_{a+b}(x,y)$ respectively denote the shortest distance between vertexes $x$ and $y$ when edges have weights $a_i$'s and when edges have weights $(a_i+b_i)$'s. Let $\mathrm{opt}$ denote the value of optimal solution, then by this lemma we have

$$
\begin{align*}
\mathrm{opt}\ge\ & d_a(A, B)+d_a(B,C)+d_a(C,A)\\
&+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S).
\end{align*}
$$

On the other hand, following the shortest path (with weights $a_i$'s or $(a_i+b_i)$'s accordingly) from $S$ to $A$, then from $A$ to $B$, and so on, constitutes a valid traverse. Easy to see the cost of this traverse is no more than

$$
\begin{align*}
d_a(A, B)+d_a(B,C)+d_a(C,A)+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S),
\end{align*}
$$

so

$$
\begin{align*}
\mathrm{opt}\le\ & d_a(A, B)+d_a(B,C)+d_a(C,A)\\
&+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S).
\end{align*}
$$

As a result,

$$
\begin{align*}
\mathrm{opt}=\ & d_a(A, B)+d_a(B,C)+d_a(C,A)\\
&+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S).
\end{align*}
$$

So one can pre-compute the all-pair shortest paths using Floyd–Warshall algorithm, then exhaust all posible $(A,B,C)$'s to find $\mathrm{opt}$. This algorithm costs $O(N^3)$.


As we already know, the loop iteratively calculates the nth Fibonacci number, so it naturally follows that the loop invariant should contain $b = \mathsf{fib}(i)$ condition.
But that is not sufficient for us, because the computation depends on the variable a, and we don't need c, because it is initialized in the loop body.

The line b ← c + a actually gives us a hint as to what the condition on a should we impose: after this line $b$ must be equal to $\mathsf{fib}(i+1)$. Now, from the expression for c and the expression $\mathsf{fib}(i+1) = \mathsf{fib}(i) + \mathsf{fib}(i-1)$ we easily obtain the condition for a: $a = \mathsf{i + fib(i-1)}$.

If we rewrite the for loop into an equivalent while loop, we'll get a loop invariant:

$$a = i + \mathsf{fib}(i-1) \wedge b = \mathsf{fib}(i) \wedge i \le n.$$

Here is how we can prove that the loop actually does the job:

{a = i + fib(i-1) /\ b = fib(i) /\ i <= n}
while i < n do
  {a = i + fib(i-1) /\ b = fib(i) /\ i < n}
  {a = i + fib(i-1) /\ b = fib(i) /\ b − i = fib(i) - i /\ i < n}
  c ← b − i
  {a = i + fib(i-1) /\ b = fib(i) /\ c = fib(i) - i /\ i < n}
  {a = i + fib(i-1) /\ c + a = (fib(i) - i) + (i + fib(i-1)) /\ c = fib(i) - i /\ i < n}
  {a = i + fib(i-1) /\ c + a = fib(i+1) /\ c = fib(i) - i /\ i < n}
  b ← c + a
  {a = i + fib(i-1) /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  {c + 2*i + 1 = fib(i) - i + 2*i + 1 /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  {c + 2*i + 1 = fib(i) + (i+1) /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  a ← c + 2*i + 1
  {a = (i+1) + fib(i) /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  {a = (i+1) + fib((i+1)-1) /\ b = fib(i+1) /\ (i+1)-1 < n}
  i ← i + 1
  {a = i + fib(i-1) /\ b = fib(i) /\ i <= n}
{a = i + fib(i-1) /\ b = fib(i) /\ i <= n /\ i >= n}
{a = i + fib(i-1) /\ b = fib(i) /\ i = n}
{b = fib(n)}


Knapsack Greedy Approximation: Worst Case

The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been picked had it fit. Let $\alpha$ be the fraction of $p_k$ that does fit – so $\alpha < 1$. These lecture notes (Claim 2) show that
$$ p_1 + \cdots + p_{k-1} + \alpha p_k \geq OPT, $$
where $OPT$ is the optimal solution. In particular,
$$ p_1 + \cdots + p_{k-1} + p_k > OPT. $$
The algorithm picks either items $1,\ldots,k-1$ or only item $k$, and there is some choice that results in strictly more than $OPT/2$.


How can you iterate through a hash table in constant time?

What you said is true. You can't iterate through all the elements in a hash table in constant time. It would take $O(N)$. But the author is not actually talking about all the elements in the hash table, but to iterate though each single element (in which there is only one element, making it constant). It comes down to the assumption here:

"all the elements that are in your set happen to be placed into different entries in the table."

In this case for each element, there is a single node. If this was not true you need to form a link-list for the hash table table, that is when there is collision. Then for each element it's no longer a constant time. But whatever item in the hash table happens to have the longest list.

Again, the explanation isn't clear here. As it looks like the author is saying iterating through all the elements in a hash table, and not iterating through for each element.


Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.

Since you seem to want only a hint rather than a full solution, here is my attempt:

Undecidability of the Halting problem is one of the most famous impossibility results. It is not the most powerful one in the series (consider Rice's theorem) but it is a relatively simple in layman's terms and IMHO pretty impressive (in a bad way). The undecidability  of the halting problem means that no matter which algorithm you try for the halting problem, it will fail on some inputs. It does not say that you can't predict if the program will halt for each (program, input data) pair, for example there are some very predictable programs. But it says that for every deciding program there will be some bad pair (possibly different for different programs, but even if you "combine" many such deciding programs, there still will be some bad cases).

Reduction is a general concept in math with several overlapping meanings. Here is one related famous joke about mathematicians:

An engineer and a mathematician were shown into a kitchen, given an empty pan, and told to boil a pint of water. They both filled the pan with water, put it on the stove, and boiled it.
The next day they were shown into the kitchen again, but this time given a pan full of water, and told to boil a pint of water. The engineer took the pan, put it on the stove, and boiled it. The mathematician took the pan and emptied it, thereby reducing it to a previously solved problem.

On a more serious note, reduction to the Halting problem is an argument that shows that a perfect anti-virus is impossible: the virus potentially can do its harm at any time during its whole runtime. So if the antivirus can catch all the viruses, it has to be able to solve the halting problem because I can put my virus "at the end" of any other program which the antivirus has to analyze first.
If you want a similar but I bit more formal argument take a look at wiki reduction of the Rice's theorem to the Halting problem
Generally in the CS-world reduction is mostly used in two ways:

To prove that some problem is undecidable by reducing it to some other well-known undecidable problem (and the Halting problem is often used here). In other words, if we could solve the problem X, we also must be able to solve the problem A which is known to be undecidable so X must be undecidable as well.

To prove some boundaries on complexity of some problem. For example, problem X is NP-complete because here is how to transform (reduce) an arbitrary input for a known NP-complete problem A into an input of the problem X and then how to transform the answer back.


Maximize function over a set with a transitive and antisymmetric relation

You can compute the maximum weight of an antichain, or more generally the maximum weight of a union of $k$ antichains, by reducing to the maximum flow problem. See for example a technical report by Cong.


Algorithm for generating coprime number sequences?

Yes.  It's possible to satisfy all of your requirements, by combining some standard tools:

Let $F$ be a function that, given a sequence of random bits as input, outputs a random 1000-bit prime.  $F$ can be implemented by repeatedly picking a random 1000-bit number, then using a primality test to check if it is prime, and outputting the first prime number you see.
Let $G$ be a pseudorandom generator that expands a short random seed to a long sequence of pseudorandom numbers, e.g., AES-CTR mode.
Let $H$ be a cryptographic hash function, e.g., SHA256.
Let $s$ be a random seed.

Now define

$$f(i) = F(G(H(s,i))).$$

Then the sequence

$$f(1),f(2),f(3),f(4),f(5),\dots$$

satisfies all of your requirements:

Every number in the sequence is prime, and it is super-unlikely that any prime will repeat (this can be quantified using the birthday paradox), so all of the numbers in the sequence are co-prime.
It is super-unlikely that any number will be less than 50.  If you prefer an absolute guarantee, you can tweak the definition of $F$ to require that the number is both prime and at least your lower bound.
The sequence can be efficiently computed: each of the building blocks $F,G,H$ has efficient instantiations, so $f$ can be computed efficiently.  Moreover, this construction permits efficient random access into the sequence.


What is wrong with this proof that proves that 0*1* is not a regular language?

The pumping lemma states that if $L$ is regular then there exists a constant $p$ such that any word $w \in L$ of length at least $p$ can be decomposed as $w = xyz$ so that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, and (iii) $xy^iz \in L$ for all $i \geq 0$.
The pumping lemma does not state that any decomposition which satisfies properties (i),(ii) also satisfies property (iii).
The pumping lemma only guarantees that some decomposition which satisfies all three properties exists.
In your case, you can take $p = 1$. If $w = 0^n1^m$ for $n \geq 1$, then you can take the decomposition $x = \epsilon$, $y = 0$, $z = 0^{n-1} 1^m$. If $w = 1^m$ for $m \geq 1$, then you can take the decomposition $x = \epsilon$, $y = 1$, $z = 1^{m-1}$.


Lower bound on number of (different) circuits of given size?

Let $1000 \leq s \leq 2^n/n$.
Every function on $m$ bits can be computed by a circuit of size $O(2^m/m)$ (I believe that even the optimal constant is known). Choose a value of $m$ such that every function on $m$ bits can be computed by a circuit of size $s$, and furthermore $s = \Omega(2^m/m)$.
Since there are $2^{2^m} = s^{\Omega(s)}$ different functions on $m$ bits, we see that your upper bound is quite tight.


Chebyshev's inequality states that
$$
\Pr[|x_i - \mu| > c\sigma] < \frac{1}{c^2}.
$$
Choosing $c = \sqrt{n}$, we deduce that with positive probability,
$$
|x_i - \mu| \leq \sqrt{n} \cdot \sigma \text{ for all } i.
$$


Machine Learning method maps from $\mathbb{R}$ to $\mathbb{R}^2$

Sure.  You can use a neural network with fully connected layers; or a neural network with deconvolutional layers.  The latter is common in image segmentation tasks, so you may already be familiar with it.


Can I construct a Turing machine that accepts only its own encoding?

The answer is yes.

See Kleene's second recursion theorem: for any  partial recursive function $Q(x,y)$ there is an index $p$ such that $\varphi_p \simeq \lambda y.Q(p,y)$.

Suppose that $M$ is a Turing machine that on input $\langle x,y \rangle$ accepts if and only if $x=y$; then, by the above theorem, exists $M'$ such that $M'(\langle y \rangle) = M(\langle M' , y \rangle)$ and we have $L(M') = \{ \langle M' \rangle \}$.

P.S. you can find a very clear proof of the recursion theorem in Chapter 6 of the M. Sipser's book "Introduction to the theory of computation".


Can SSL be hacked if we know some of plain data?

No, it is not possible. Any modern encryption algorithm is designed so that even even if you have some ciphertext and part of the corresponding plaintext, it is unfeasible to find any information (other than the length) about the part of the plaintext that you don't know. This is true even if you get to choose all of the plaintext except one bit, and you get the corresponding ciphertext and you want to find the bit that you don't know. This property is called indistinguishability under chosen-plaintext attack (IND-CPA for short).

Unfeasible is a technical term, meaning that it requires an amount of computation that cannot be performed in practice. The theoretical definition is that the complexity of the attack is more than polynomial over the size of the key. In practice, key sizes are chosen so that it would take more than the total computational power available in the world for more than a lifetime to break the key (for example, it would take a billion PCs more than the age of the universe to break a 128-bit key).

Note that I simplified the definitions a bit; the actual definitions are fairly complex and subtle. If you want to understand them precisely, read a cryptography textbook.

In practice, this assumes that:

There is no flaw in the protocol, such as using the same key for different purposes or accepting invalid output, that could lead to the implementation acting as an oracle.
There is no flaw in the implementation, that could lead to secret information leaking directly or indirectly.
The algorithm genuinely has the IND-CPA property. It is in fact not known whether any encryption algorithm (apart from the very unwieldy one-time pad) has this property. In practice, people use algorithms that cryptographers have spent many years trying very hard to break, and failed.

In practice, most security flaws related to cryptography are due to implementation bugs. A minority are due to protocol weaknesses, and modern protocols tend to be designed with more attention than protocols designed 20 years ago. Flaws in modern encryption algorithms are extremely rare.


Bipartite Perfect Matching "Assignment Problem" - finding an assignment of a particular weight

The problem becomes NP - Complete when the weights are exponential in the number of variables. This can be shown by a reduction from the subset sum problem described in the paper "Planarizing gadgets for perfect matching do not exist" by Gurjar et al. (link)


Algorithm for grid with obstacles and movement restriction

You can depict states of the graph as following:
(grid_position,|consecutive_left|,|consecutive_up|)
if you are at state ([2,3],3,0) then you have no other option but to go
up to ([3,3],0,1)

so you have  n^2 * 4 * 4=16*n^2 states=O(n^2) states.
And you can also save some space by noticing that states such as ([x,y],2,1) are impossible.


You'll find plenty of literature on this widely-studied problem, which is called complete coverage path planning. Many techniques have been applied with more or less success (genetic algorithms, etc.) but in the end the only viable technique is some variant/improvement on the boustrophedon decomposition algorithm, which is in the class of Morse decompositions.

Choset's paper is the founding document, but I found Xin Yu's PHD dissertation to be the best practical description. The problem is that Boustrophedon decompositions find only a single 'best' ploughing angle for all trapezoids, when some may certainly be better ploughed at some other angle.

Bochkarev and Smith recently described a way to minimize turns by exploiting the minimum altitudes of the polygons, but I found it difficult to grasp with my limited high-school maths.

I am currrently trying out an alternative approach, by taking a Boustrophedon decomposition at all the angles of the polygon and then layering all the resultant trapezoids sorted by a score based on area and minimum altitude. If it works out I'll try and remember to come back here to post the results.

Citations

Choset, Howie. "Coverage of Known Spaces: The Boustrophedon Cellular Dercomposition" Autonomous Robots 9, 247-253, 2000.

Xin, Yu. "Optimization Approaches for a Dubins Vehicle in Coverage Planning problem and Traveling Salesman Problems" PhD Dissertation, Auburn, Alabama, 2015.

Bochkarev, Stanislav and Smith, Stephen L. "On Minimizing Turns in Robot Coverage Path Planning" Automation Science and Engineering, 2016


Does an algorithm exist that transforms any connected graph, cyclic or not, into tree form?

In a general graph, the number of edges can go up to $\mathcal{O}(n^2)$ (where n is the number of verticies). But in a tree, that number is always $n-1$.

Then, we understand that its impossible to convert a graph to a tree preserving syntax without increasing the memory for each node by a linear factor, or increasing the number of nodes significantly.

Let us define a unique number for every node (in any way you like).

The algorithm now will be:

Let $\mathcal{T}$ be the tree from the BFS algorithm on the graph (starting from node 1, for uniqueness)
For every edge $e=(i,j)$ in the graph, that is not in $\mathcal{T}$ already, w.l.o.g assume $i\le j$, and add a new node with value $j$ to $\mathcal{T}$, and a connection between it and the (original) node $i$ in the tree.

Note that in the new tree, there will be a lot of nodes that have the same number.

To reconstruct the original graph, we will do the following:

Create a node for every unique number in $\mathcal{T}$.
Add an edge $(i,j)$ if there is a node with number $i$ that has an edge to some node with value $j$


How to add two numbers in IEE754 half precision format?


Compute sums of all subsets of some words

If you think that there are much fewer than $2^{16} $ sums, you can try the following approach. Iteratively compute a sorted list of all partial sums of the first $k$ values.  Given this list for some $k$, add to all sums in the list $W_{k+1} $, and then merge the two lists like in Mergesort, removing duplicates. The total complexity should be asymptotic to the number of distinct partial sums.


Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

If $L_1,L_2$ are two disjoint context-free languages which are not inherently ambiguous, then $L_1 \cup L_2$ is also a context-free language which is not inherently ambiguous. The reason is simple: starting with context-free grammars for $L_1,L_2$ with start symbols $S_1,S_2$ (respectively) and otherwise disjoint non-terminals, you can construct an unambiguous grammar for $L_1 \cup L_2$ by adding a new start symbol $S$ and the productions $S\to S_1|S_2$. This takes care of 1) and 3), once you construct unambiguous grammars for the constituent languages.
As Palec mentions, 4) is regular, and so admits a regular grammar which corresponds to a DFA accepting it. This grammar has as non-terminals the states of the DFA, and productions $A \to aB$ if the DFA moves from $A$ to $B$ upon reading $a$. For each final state $F$ we add a production $F\to\epsilon$, and the start symbol is the start state. This description should make it clear that the grammar is unambiguous.
Intuitively, 2) could be inherently ambiguous since words of the form $a^n b^m c^p$ with $n \neq m \neq p$ could have two different parse trees, corresponding to the two constituent languages. Proving this formally could be tedious. The only method I know consists of coming up with two words $x,y$ that can be pumped to the same word $w$ in such a way that makes it clear that the corresponding parse trees are different. If you want to pursue this further, a good first step will be to read some examples of this method.


What sort of theoretical machine would be needed to solve the tiling problem?

According to Wikipedia, the halting problem reduces to the tiling problem. This means that one thing that prevents Turing machines from solving the tiling problem is their inability of deciding whether a given procedure ever halts. The tiling problem might be even more difficult that the halting problem, but unfortunately I wasn't able to confirm or disprove this.


What counts as automatic program analysis?

There is no sharp formal definition.

"Static" denotes "before running the program".

"Dynamic" denotes "while running the program".

"Automatic" stands for "without the intervention of the user". For instance, Hoare logic can be used to prove program properties, but (at least in its basic form) it requires user-provided invariants. Abstract interpretation, instead, often results in a totally automatic analysis. Type checking is usually regarded as automatic, since the type checker does not (usually) ask the user to provide hints about, e.g., why a given expression has the given type.

Parsing is static, but it's such a preliminary stage that probably most people wouldn't consider as program analysis at all. If a text file does not respect the syntactic rules, it is not part of the programming language (a language being a set of strings, after all!), hence it is not even a program, hence parsing is not program analysis. I would not be very interested in the syntax errors reported by cc kitten.jpeg, for instance.

Observing the program when it is being run is definitely a "dynamic" approach. Using a debugger, observing fired exceptions fall in this category.


Finding pairs of vertices which would disconnect a graph

Assume that $G=(V,E)$ does contain any articulation point (otherwise the answer is easy).

One simple approach that requires $O(|V| \cdot |E|)$ time is that of computing the articulation points of $G-v$ for each $v \in V$.

If you find any articulation point $u$ then removing the two of vertices $\{u,v\}$ disconnects the graph.

In practice this amounts to running the depth first search needed to compute the articulation points of $G-v$ on $G$, while ignoring the edges to $v$.


Request for examples to show various types of subproblems in dynamic programming

Everything you need could be found on Topcoder.com (TCC for short).
Start with Dumitru's tutorial.
Done that, you should be able to integrate the DP technique on various structures, like 2D grids, narrow ribbons, convex polygons, etc. to name just a few.
An archive of DP problem on TCC: https://www.topcoder.com/tc?module=ProblemArchive&sc=2&sd=desc&cat=Dynamic+Programming
And the match editorial is the best collection: https://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=archive
I have learnt so much from these. Unfortunately, this editorial series stopped since 2008. From that time on, the SRMs are only discussed in the forum like these more recent SRMs:
https://www.topcoder.com/blog/single-round-match-735-editorials/
A tagged search produces this: https://www.topcoder.com/blog/tag/srm-editorials/
So you may easily access all the recent SRMs.
SRM: Single Round Match (TCC is the arena of online competitive programming)

Please note that TCC has been gone through various reconstruction (since the integration with Data Science market). As a (unwanted) consequence, many links are broken but can be fixed by modifying some middle parts (as often the cases for decades-old websites)


Papadimitrou and standard landau notation

The two definitions are not equivalent. However, the case where they aren't equivalent is one that we aren't interested in for algorithm analysis.

The standard definition implies the Papadimitriou definition. The proof is fairly straightforward, by following the definitions carefully.

   Suppose that $\exists c, n_0 \in \mathbb{N}, \forall n \gt n_0, f(n) \le c \cdot g(n)$. Let $c$ and $n_0$ be such constants. We want to prove that there exist $c',d' \in \mathbb{N}^*$ such that $\forall n \in \mathbb{N}, f(n) \le c' \cdot g(n) + d'$. Take $c' = c$ and $d = \max\{f(x) \mid x \le n_0\}$. If $n \le n_0$ then $f(n) \le d'$; if $n \gt n_0$ then $f(n) \le c \cdot g(n)$. Either way, for any $n \in \mathbb{N}$, $f(n) \le c' \cdot g(n) + d'$.

The converse is not true. Again, unfolding the definition works up to a point, but then one little extra assumption is needed to make the proof go through.

   Suppose that we have $c', d'$ such that $\forall n \in \mathbb{N}, f(n) \le c' \cdot g(n) + d'$. We want to find $c$ and $n_0$ such that $\forall n \ge n_0, f(n) \le c \cdot g(n)$. If there is an $n_0$ such that $\forall n \ge n_0, g(n) \ge 1$, then we can factor $g(n)$: for any $n \ge n_0$, $f(n) \le (c' + d'/g(n)) g(n) \le (c' + d') g(n)$, so we can take $c = c' + d'$.

The case where this proof fails is when there is no $n_0$ such that $\forall n \ge n_0, g(n) \ge 1$, i.e. when there are infinitely many integers $x$ such that $g(x) = 0$. (More generally, for real-valued functions, the problem case is when there is a set of values $(x_k)_{k\in\mathbb{N}}$ such that $\lim_{k\to\infty} x_k = \infty$ and $\lim_{k\to\infty} g(x_k) = 0$. Equivalently, that means that $g$ has no positive infimum.) Under the Papadimitriou definition as quoted here, the order of such a function includes all constants, but under the standard definition, there has to be a cutoff point above which $f$ is zero when $g$ is zero. For example, take the function $g : \mathbb{N} \to \mathbb{N}$ defined by $g(x) = 1$ if $x$ is odd and $g(x) = 0$ if $x$ is even. The function $f(x) = 1$ does not satisfy $f \in O(g)$ under the standard definition, but it does under the Papadimitriou definition.

This corner case isn't important in algorithm analysis because complexity functions are never “really” zero. With space complexity, there's always a bit of stack space just for the function call. With time complexity, it takes a few instructions to call a function even if the function does nothing.


Why does the program counter increment before an instruction is completed?

The exact details of when (or even how) to increment the program counter are implementation specific details. There are however a few considerations that come into play across most computers.

After sending out the PC address, there is (almost) always a delay waiting for memory to respond. Thus there's often not a lot going on. One possible use of this "dead" time to do something useful, like incrementing the PC.
The next instruction is going to need the incremented value of the PC before it can proceed. If the processor does this at the end of the instruction, then the PC increment becomes part of the critical path for the next instruction.

The thing is, once this becomes part of the programming model for a processor, it is difficult to change the outward semantics of the PC increment. Consider processors with a PC relative addressing mode. If the value retrieved were to change from incremented to non-incremented, almost all the code would break. Thus the decisions made for early versions of a CPU must be honored in later (pipelined/overlapped/multi-way executing/multi-threaded/etc) versions of that CPU family.

Finally, and while silly sounding, most important; People are just used to having processors work that way. Some really great gains would be needed in order to ignore this bit of orthodoxy.


Formal notion of a call graph for Turing machines

Turing machines have no concept of "calling".

Tou can jump to another state and that can look quite a lot like a procedure call, especially if an author's description of the machine in English uses words that make it sound that way. But that's all you can do. In particular, there's no notion of "return" in a Turing machine. There's no way to say "OK, this procedure is finished – now go back to wherever we came from." All you can do is say "OK, this procedure is finished – now go to this specific point."

Of course, because Turing machines are Turing powerful, you can simulate these things. For example, you can write some notion of a return address on the tape as part of your simulation of a procedure call. But that's not intrinsic to Turing machines: it's just a property of the particular Turing machine you're writing at the moment. A coding convention, if you like.


I would like to try an intuitive explanation.
Assume your algorithm works in $2m$ time units on your current machine. If you run it on a machine twice as fast, then it takes $m$ times units. As we do not know (and do not care) on which machine(s) the algorithm will run, this makes the $2$ factor irrelevant. This is what the big-$O$ notation captures, in a sense.
(In addition, if we know that $n>m$ then we have $3n > n+2m$, and so anything below $n+2m$ also is below $3n$. As big-$O$ deals with upper bound, this means that $O(n+2m)$ complexity is, in this case, in $O(3n)$ complexity which, as explained above, is nothing but $O(n)$.)
Hope this helps.


How approximate are "approximate" nearest neighbor (ANN) search algorithms?

nanoflann is a library for building KD-trees.  For the best bin first (BBF) approximate nearest neighbor algorithm (which is based on KD-trees), the authors report the following performance results:

  In 12 dimensions, for example, BBF recovers the closest neighbor 94%
  of the time (versus 59% for restricted search) while on average
  examining only 200 of the 100,000 leaf nodes. For this same case, the
  “exact” search has to examine over 2400 leaves. [Even] when the method
  does not discover the exact nearest neighbor, it does not fail by
  much.  Even up to dimension 20, the average distance of recovered
  neighbors is only 2% greater than the true NN distances.

However, that paper does not contain a formal analysis of the error bounds in this particular $\varepsilon$-approximation.


This was proved NP-complete in "Optimal Packing and Covering in the Plane are NP-complete" (Fowler, Paterson and Tanimoto, Information Processing Letters 1981). I found a freely available version of the paper here. They give a neat reduction from 3SAT -- I'll summarise this below, but the paper is short and easy-to-read with several diagrams, and I recommend reading it!
For each variable they construct a "loop of wire" having an even number of points (1-cells in your formulation), and such that a single square can cover two adjacent points in the loop but no more. This means that there are two ways to cover all points in the loop using a minimal number of squares: Either use a square to cover points 1 and 2, another square to cover points 3 and 4, and so on, or use a square to cover points 2 and 3, another square to a cover points 4 and 5, and so on. Which minimal cover is used corresponds to whether the variable is assigned a value of true or false.
For each clause, they add a single extra point out to the right, and "extrude" the wire loops for the three relevant literals near this point. If any of them is in the right state, the extra point for this clause can be covered "for free" by a square in that loop. Negated literals are achieved simply by slightly compressing a few links in the loop, so that at a position to the right of the compression zone the "parity" of the wire is reversed.
In order to thread the loops through each clause they participate in, wires need to be able to cross over with their signals remaining independent. Interestingly, this "just works" without any additional gadgets.


Is there a defined set of steps or principles on how to reduce time complexity of algorithms?

Just something to remember: You said "could you make it faster (time complexity)". What counts in practice is the resources used for practical cases. Reducing the runtime by a factor ten may be extremely valuable, but doesn't reduce time complexity. It is in practice more valuable than reducing time complexity by a factor log log n.
Next thing to remember: In many cases "could you make it faster" has the valid response "Probably, but I wouldn't bother". Making it faster takes time in money. The first step is to figure out whether it's worth the effort. Especially in an interview.
One method that works very well is called "brute force and ignorance". It doesn't care about algorithms, but about making the identical code run faster. Removing all unneeded overhead. Check for cache usage and so on.
And the other method is finding better algorithms. O (n*n) can often be changed to O (n log n), which is massively better. And with really complicated algorithms, you may find some heuristics that improves it. For example, optimisation algorithms tend to work a lot better if you manage to start with a good solution that may be good enough to allow you showing that many other solutions cannot be optimal.
But general principles? No.


proving that if $\{w\$w^R | w \in L\}$ is context-free then $L$ is regular

Here is a proof sketch. The idea is to take a context-free grammar for $L'$ and come up with a regular grammar for $L$.

Start with a grammar for $L'$. Say that a language $M$ is symmetric if it is of the form $\{w \$ w^R : w \in P\}$ for some $P \subseteq \Sigma^*$. Prove that every non-terminal in $L'$ generates a language of one of the forms $w, wM, Mw$, where $w \in \Sigma^*$ and $M$ is symmetric. Consider two cases: the non-terminal generates a word without $\$$, or it generates a word with $\$$. In the first case, it's easy to see that it must generate a unique word. In the second case, every word it generates must contain $\$$, and the words need to be "compatible" in some sense, which implies that it generates a language of the form $wM$ or $Mw$.

For each non-terminal generating $wM$ or $Mw$, we can come up with a non-terminal generating the language $M$. This is because context-free languages are closed under this operation. So we can assume without loss of generality that each non-terminal either generates a unique word or a symmetric language.

Substitute all non-terminals generating unique words. All remaining productions must be of the form $A \to w B w^R$ or $A \to w \$ w^R$. We can come up with an equivalent grammar in which $w$ is always a symbol in the first case and empty in the second, so that all productions are now either $A \to a B a^R$ or $A \to \$$. If we replace these productions with $A \to a B$ and $A \to \epsilon$ then we get a right regular grammar for $L$.

For completeness, let me mention that the converse to the theorem also holds. You can see this by reversing the construction: from a right regular grammar for $L$, construct a context-free grammar for $L'$.


Algorithm for searching in BST with only <

If what you mean is that you want to build a BST and you only have the $<$ operation, and you only know the algorithms with the $\leq$ operation, you can notice that :
$$a \leq b \Leftrightarrow \neg (a > b)$$
$$\Leftrightarrow \neg(b < a )$$
Hence, using a negation in the right place, you can build your usual algorithm.


Proving that DFA equivalence is decidable

Here is a slightly different proof, along similar lines.

Lemma 1. Let $A$ be a DFA having $n$ states, and let $B$ be a DFA having $m$ states. There is a DFA $C$ having $nm$ states such that $L(C) = [L(A) \setminus L(B)] \cup [L(B) \setminus L(A)]$.

The proof uses the product construction (exercise).

Lemma 2. Let $C$ be a DFA having $p$ states. If $L(C) \neq \emptyset$ then $L(C)$ contains some word of length at most $p-1$.

Proof sketch. The language $L(C)$ is non-empty if some final state $q_f$ is reachable from the initial state $q_0$. The shortest path from $q_0$ to $q_f$ has length at most $p-1$, and this corresponds to a word of length at most $p-1$ in $L(C)$.

Theorem. Let $A$ be a DFA having $n$ states, and let $B$ be a DFA having $m$ states. Then $L(A) = L(B)$ iff for all words $w$ of length at most $nm-1$, either $w \in L(A),L(B)$ or $w \notin L(A),L(B)$.

Proof. If $L(A) = L(B)$ then the condition clearly holds. If $L(A) \neq L(B)$ then $\Delta := [L(A) \setminus L(B)] \cup [L(B) \setminus L(A)] \neq \emptyset$. According to Lemma 1, there is a DFA having $nm$ states whose language is $\Delta \neq \emptyset$. According to Lemma 2 (with $p = nm$), there exists a word $w \in \Delta$ of length at most $nm-1$. This is a word for which it doesn't hold that either $w \in L(A),L(B)$ or $w \notin L(A),L(B)$.


Partitioning a set so both parts have sum at least $c$ times the total sum

The problem is polynomial (even linear time) for any fixed $c < 1/2$.

Assume no there is no item of size $> (1-c)S$, otherwise it is a trivial no-instance.

If there is any item $w_i$ with size $\geq cS$ we are immediately done because we can take one half of the partition to be that item.

Otherwise, all items are $< cS$. Greedily taking items means we will exceed the target sum by less than $c S$, meaning the remaining items have weight at least $(1-2c)S$. If $c\leq 1/3$, the instance trivially is a yes-instance.

For $c>1/3$, note that for the items smaller than $(1-2c)S$, we can use a greedy algorithm to assign them after we have a correct(*) solution for the large items. The number of large items is at most $1/(1-2c)$, which, for fixed $c<1/2$, is a constant. Thus, we can guess (in constant time) a solution for the large items, then use a greedy algorithm to distribute the small items. Note that the constant tends to infinity as $c$ tends to $1/2$.

(*) Where correct means neither half of the partition exceeds $cS$ by more than $(1-2c)S$.


Can we improve internet speed by serializing timestamps?

If we restrict ourselves to the 52 letters from the Latin alphabet that are commonly used in English (i.e. we exclude letters like ï as seen in words like naïve), then we need 6 bits to encode each letter.
However, in 6 bits, we can encode 64 different numbers.
That means our encoding using letters is only 81.25% as dense as the encoding using numbers.
This is actually the best case scenario. Most protocols are octet-oriented, so we have to pad our representation to a full octet boundary. That means that a single letter will be encoded in 8 bits. A single letter can express 52 timestamps, but 8 bits can express 256 numbers.
We could try to find an alphabet with 64 letters (or even better 256 letters), then the representation using letters would be as good as the representation using numbers … but why go through all the trouble of representing timestamps (which, after all, are numbers) as letters, then at the other side of the transmission turn them back into numbers again when simply representing them as numbers is in the worst case just as efficient as when using letters and in the best and average case is significantly more efficient?
After all, computers and networks can only process and transport numbers, so whatever representation using letters you find, you will have to represent that representation using numbers again, and this representation cannot be more efficient than the original one.
Basically, you start off with a timestamp, which is a number, you need to end with a timestamp at the other end, which is a number, and the network can only transport numbers.
Your proposal looks like this:

Encode the number as letters
Encode the letters as a number
Transmit the number
Decode the number as letters
Decode the letter as a number

Whereas what we are doing today is:

Transmit the number

Which is more efficient.


Big Oh Time Complexity Involving 'for i in range(n)'

So you have the right logic, if you have a loop of $O(n)$ iterations, the complexity of the entire loop will be $O(n*\text{complexity of loop operations})$. In this case, you again are correct that your loop's complexity is $O(n)$ for each iteration.

Your last bullet point shows that you understand this as well, as the total loop complexity is then $O(n^2)$. However, this trivially results in an overall time complexity of $O(n^2)$, not $O(n)$ as you concluded.

I imagine what you were really asking about is the complexity of range(n). While it is true that the initial call to range is $O(1)$, that is because it produces a generator which takes $O(1)$ to return the next successive value i.e. it doesn't produce the entire range right away, but instead on demand. However, keep in mind that the generator will be advanced $O(n)$ times (once for every iteration of the loop).


Existence of a route following one-way streets

First, it definitely won't result in a DAG, just a digraph. You need to get from A to B and B to A in order to satisfy your condition for nodes A and B, but that itself is a cycle.

Lots of time BFS and DFS are equivalent in relation to a problem, so it doesn't matter which one you choose. Here, the real trick is not choosing between DFS and BFS, but dealing with the fact that the graph is directed.

If you don't want a direct answer, here's the strategy I would use: first find a representation for the streets in terms of a digraph. What corresponds to edges? What corresponds to nodes?

Then, you need to find a graph algorithm that will work for this problem. What information do BFS and DFS give you about the graph? How can they be adapted to a directed graph?

To give you a little hint, I'd recommend you Google Eulerian chains.


Writing a factorial function in ARM assembly language

we were required to do something similar. We were given a number to calculate, which was 7!.r0 will hold the final value. I ended up doing the following:

MOV r1, #7
MOV r1, #6
MOV r1, #5
MOV r1, #4
MOV r1, #3
MOV r1, #2
MOV r1, #1

MUL r0, r1, r2
MUL r0, r0, r3
MUL r0, r0, r4
MUL r0, r0, r5
MUL r0, r0, r6
MUL r0, r0, r7


In their most basic form, computers use electrical signals that are represented as 1's or 0's. A 1 meaning that there is an electrical signal and a zero meaning that there isn't an electrical signal.

A computer keeps track of time using a vibrating crystal oscillator. This crystal oscillator gives off a constant and precise frequency. The oscillator is powered by a small and weak CMOS battery on your motherboard that provides a constant electrical signal for up to three years.

So how can a computer use this oscillator along with binary (1s and 0s) to keep track of timers?

When an interval is set, a value of zero is given to the computer along with a threshold based on the length of the interval and the frequency of the oscillator.

threshold = length of interval in ms / 1000 * frequency of crystal in MHz

When the oscillator vibrates, it puts off an electrical signal (1) and triggers a binary calculation that adds 1 to to the initial binary number (the one that started at 0). Once the initial value passes the threshold, the binary function puts off a 1 indicating that the interval has been fulfilled. Depending on the operations that are done after the threshold is met, the interval may be reset, saved, altered, or deleted.

Helpful links:

https://www.youtube.com/watch?v=1gyCZIBk_88

https://www.computerhope.com/jargon/q/quartz.htm


How to find whether a grammar's language is finite or infinite?

A language is infinite if it can generate infinitely many words. In order to prove that a language generated by a grammar is infinite, you need come up with some infinite list of words generated by the grammar. Proving that the language is finite is slightly more messy—you need to make a list of all possible derivations, and show that all of the terminate.

In your case, you have the derivation $S\to^*SSSS$, which suggests that the language is infinite. Can you come up with an infinite list of words generated by this grammar?


What is this problem? Largest set of contiguous x values for which the same y value can be held

Here is a slightly different algorithm. Start by sorting the list according to the $y$ value. Iterating through all different $y$ values, maintain a list of all rectangles which intersect the given $y$ value, as well as the $x$-intervals that they span. When you lose an interval, you need to split a range. When you add an interval, you need to find which intervals, if any, it is adjacent to, and then enlarge the interval and possible merge two intervals. Some kind of search tree containing all endpoints of the current intervals can be useful for locating the intervals adjacent to a new segment (if they exist). Maintaining the intervals (shortening, splitting, enlarging, joining) should be possible with a Union-Split-Find data structure.

If you use the correct data structures, this algorithm should run in time $O(n\log n)$, where $n$ is the number of intervals. (That's an informed guess.)


First of all, note that your quest for "rules in place" is probably doomed. This looks pretty much like an exercise problem you would pose in class; there is not necessarily an intuitive rule or semantics. It's just a playground for developing your skills. Therefore, it may be more helpful to strap on theory glasses and just look at the formal object given to you.

Now, for your problem. In order to get to a context-free grammar, it can be useful to identify "phases" a grammar can work through. A good first step is to identify which parts of the word are "connected" by the restrictions in place and which are independent of each other. If you find intersecting dependency arcs, you either have a non-context-free language (which you can check) or you need to represent your language differently (sometimes restrictions are redundant or seem to imply dependencies that are not really there¹).

   Here, note that your words have the form

 $\qquad a^n b^m \dots b^{n-m}$.

 Why can I remove a part for an intuitive look? Because I cut away $b^p c^p$ which can clearly by generated by a standard grammar and independently of the rest. Now, the above is just

 $\qquad a^n b^n$

 if you remember to insert $b^p c^p$ at some point in $b^n$.

  Try to come up with a grammar along these lines. Take care about corner cases and the exact restrictions on $m,n,p$! And, of course, prove correctness.

Another strategy that can sometimes work better is to build a PDA and convert it into a(n ugly) grammar by the standard construction.

A simple example: $a^nb^nc^n$ is not context-free, so $a^na^na^n$ is not. Right? Wrong: $a^na^na^n = a^{3n}$ is clearly regular.


What does "fast-forwarding" mean in the context of CPU simulation?

Fast forwarding is used to warm-up microarchitectural state (caches, branch predictors, etc.) in preparation for more accurate simulation of a particular section of interest within an application. Since microarchitectural state can depend on operation ordering (e.g., cache replacement for data accesses and interactions between threads), speculation (e.g., instruction caching behavior), and even timing (e.g., thermal behavior), this is not a perfectly accurate warm-up, but "all models are wrong".


Find the closest point in a point cloud in a near equivalent point cloud

This problem is known as Euclidean minimum cost perfect matching, I have linked a survey by Sayan Bhattacharya that contains various references to algorithms, both exact and approximations.
If you wish to solve this problem for $n \approx 50000$, I would skip the exact solutions entirely and go straight to the approximations.


A very nice question!

You just ventured into a large body of knowledge and research in computational theory around the concept of relative primitive recursiveness and hierarchy of total recursive functions such as fast growing hierarchy, which are full of interesting and mind-boggling facts.

  What function class $\cal F$ do we get by adding the Ackermann function as basic function?

Well, that is one of its own kind.

  Do we get all $\mu$-recursive functions?

No. What we get are far far from all $\mu$-recursive functions since all functions we get are still total recursive functions as primitive recursion preserves totality. Recall that $\mu$-recursive functions means partially recursive functions or, what is equivalent, all functions that can be computed by Turing machines.

You might ask, then, do we get all total recursive functions?

The answer is still no. What we get are far from all total recursive functions. For example, a "Ackermann modification of Ackermann function" is not included. Here is a version of that "doubly Ackermann" function.

Let us start from the usual two-argument Ackermann–Péter function.
$$A(m, n) =
\begin{cases}
n+1 & \mbox{if } m = 0 \\
A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\
A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0.
\end{cases}$$
Let $f(n)=A(n,n)$ be the Ackermann–Péter function of a single-argument. Now let us define
$$D(m, n) =
\begin{cases}
f(n) & \mbox{if } m = 0 \\
D(m-1,1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\
D(m-1, D(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0.
\end{cases}$$

Then $D(m,n)$ is a doubly Ackermann function, which cannot be obtained from composition and primitive recursion of Ackermann functions and all primitive recursive functions. This is not surprising, since a single Ackermann modification accelerates the growth of a strictly increasing function faster than arbitrarily finitely many compositions and primitive recursions.

You may continue to ask, what if we add that doubly Ackermann function? Then we are missing the "triply Ackermann functions". If you keep asking, then you will be building a growing hierarchy by Ackermann modification. Even if you have asked $\omega$ times this way, where $\omega$ is the first infinite ordinal, the growth rate of any function thus obtained is still dwarfed by most of functions in the fast growing hierarchy.

  or do we get some strange sub-class?

You may call it some strange sub-class as you like. However, as you might have expected, it is not unusual at all in the field of computation theory. Here is an excerpt from paper The Ackermann functions are not optimal, but by how much? by H. Simmons, slighted edited.

  5.1 DEFINITION. For each set $\Theta$ of functions, let
  $PR(\Theta)$ be the clone of those functions that can be obtained from members of $\Theta$ by primitive recursion. $PR(\Theta)$ is also called a primitive recursive degree. The primitive recursive degrees measure the complexity of functions up to primitive recursive equivalence.

The "strange sub-class" of yours is just $PR(\alpha)$, where $\alpha$ is the set of primitive recursive functions and the particular versions of Ackermann function you have in mind. In that paper, "by taking a closer look at the construction of an Ackermann function we see that between any primitive recursive degree and its Ackermann modification there is a dense chain of primitive recursive degrees."

Hopefully, I have shown you a glimpse of the fascinating theory around recursiveness and growth of total recursive functions. You may want to read some of the following articles as well as raise more interesting questions like this one.

Mind blown: the fast growing hierarchy for laymen — aka enormous numbers
Ackermann function
Higher-Order Recursion, How to Make Ackermann, Knuth and Conway Look Like a Bunch of Primitives, Figuratively Speaking


Select K columns from matrix and one element from each row that has maximum sum

There is trivial reduction from set cover. Consider 0-1 matrix where columns are subsets, rows are set elements and 1 means that subset contains element. Algorithm for your problem then can find K subsets to cover (sum max elements to n) set.

So your problem is NP-hard, no chances.


Note that this language excludes all strings of length divisible by 3 but not by 2, i.e., of length $3, 9, 15, 21,\dots$.

Consider languages
$$L_1 = \{w\mid |w|=2k, k\geq 0\}$$ and $$L_2 = \{w\mid |w|=3k, k\geq 0\}$$
They are regular, since it is very easy to design DFA for both languages; the first has three states, the second has four states. The complement of the language $L$ is equal to $L_2-L_1$, and by the closure properties of regular languages $L=\overline{L_2-L_1}$ is also regular.


Creating an K-nary tree that is balanced in both width and depth for N nodes. N known a priori

This sounds as follows.

The answer is that the optimal number of children in a tree is $e$. What was "optimal" in the question?

One such question is as follows.

Let us construct a tree of $N$ nodes.
Imagine we arrange them into a perfect $K$-ary tree with $L$ levels of internal vertices.
When we search over such tree, assume that the worst case is that we visit $K$ vertices in each of the $L$ internal levels, making the search $O (K \cdot L)$.
What is the optimal $K$ as $N$ tends to infinity?

Here, we select $K$, and then $L$ is computed as $log_K N$.

When we think about it a bit, here is an arithmetic rephrase.

We have a number $N$.
We want to express some integer $M \ge N$ as a product of integers $S_1 \cdot S_2 \cdots S_L$ so that the sum $S_1 + S_2 + \ldots + S_L$ is minimal possible.
When $N$ tends to infinity, what will be the sequence $\{S\}$?

The values $S_1, S_2, \ldots, S_L$ are the number of children at levels $1, 2, \ldots, L$, respectively.
If we had a perfect $K$-ary tree, all our $S_i$ would be equal to $K$, but we lifted the restriction that they are all equal: the essence of the solution remains the same.

When we don't insist that $N$ and $S_i$ are integers, after performing some basic calculus, we can see that the optimal answer is to pick all $S_i$ close to $e$.
Note that the closest integer to $e$ is $3$.
So for the integer version, the optimal answers turn out to be of the following forms:
$$(3 \cdot 3 \cdots 3)$$
$$(3 \cdot 3 \cdots 3) \cdot 2$$
$$(3 \cdot 3 \cdots 3) \cdot 2 \cdot 2$$


How to prove $c = a + b$ using Program Verification Techniques

We can prove the Hoare triple

\begin{align}
  \{{\sf true}\}\\
  c = a + b\\
  \{c = a + b\}
\end{align}

using the assignment rule. We take the postcondition $c = a + b$ and we substitute backwards $\{(a+b)/c\}$, so we get $(c = a + b)\{(a+b)/c\} = (a+b=a+b)$. That's the weakest precondition. Hence, we proved

\begin{align}
  \{a+b = a+b\}\\
  c = a + b\\
  \{c = a + b\}
\end{align}

We can then use the weakening/strengthening/pre-post rule to rewrite $a+b=a+b$ as $\sf true$, since they are equivalent logical formulae.


Where's the flaw in my algorithm? (Linear program to solve NP-hard problem)

In your program specification, "$\forall e\in E: x_e \ge 0$" should be "$\forall e\in E: x_e=0\text{ or } 1$".

"Each LP-program runs in polynomial time". However, your instance is an instance of integer linear programming (ILP), which is NP-hard, even when all variables are restricted to be either 0 or 1. In particular, this answer shows that the instances of ILP as given in this question is NP-complete.


You cannot make a DFA for this language because its not a Regular language
in fact its not even a context free language so you can't even make a PDA for it

to prove its not regular and not  context free you should use pumping lemma

but you can make a linear bounded automata for this language so therefore its a context sensitive language

hint for the linear bounded automata: put both of the w's in the tape and separate  them with 0, then compare them.

also here's some examples for some of the strings in the language :

00 , 11 , 0101 , 1010 , 110110 ...


Prove that the upper bound in the Noiseless-coding theorem is strict

Take the probability distribution that you consider: there are two symbols, one with probability $\delta$, the other with probability $1-\delta$.

Any minimum redundancy code for this distribution has average codeword length $1$. Therefore the redundancy is $1 - h(\delta)$. Since $h(1/2) = 1$, $\lim_{\delta\to0} h(\delta)=0$ and $h$ is continuous, for every $0 < \gamma \leq 1$ you can find $\delta > 0$ such that $h(\delta) = \gamma$. Choosing $\gamma = 1 - \epsilon$, we get a distribution whose redundancy is $1-\gamma = \epsilon$.

It is natural to "outlaw" such distributions by requiring all probabilities to be smaller than some $\kappa$. For small $\kappa$, we can no longer find distributions whose redundancy is close to 1. It is natural to conjecture that as $\kappa$ goes to zero, the maximum redundancy also goes to zero. However, this is not the case: for arbitrarily small $\kappa$, there are distributions whose redundancy is roughly 0.086. See Gallager's Variations on a theme by Huffman, which establishes that the limiting value of the maximum redundancy is (roughly) 0.086.


You are trying to find an Euleran path in a graph.

Observe, that if each node has equal number of incoming and outcoming edges, every time you enter a node using an edge you have not used before, there is an unused outgoing edge. The only vertex that does not have this property is the starting vertex. Therefore, any path that starts in vertex $v$ can either be easily extended or end in $v$, resulting in a cycle.

The only problem we now have to take care about is covering all the edges. After you finish a cycle and can't proceed, take any vertex $t$, which is in your cycle and has some unused edges. Start a new cycle from $t$, obviously using only unused edges. Connect the new cycle with the old one. Iterate until finished.


Example of typed lambda term with recomputed argument

In the simply typed $\lambda$-calculus with pairs, a simple example is

$$(\lambda x :T. (x,x))a$$

where $a$ is a term of type $T$.


Which NP-Complete problem has the fastest known algorithm?

Vertex Cover has an algorithm running in time $1.2738^k + nk$, and is thus faster than $2^n n^2$, even with $k=n$.  You can check out Table of FPT races for a short list of FPT running times of different problems. Here, $n$ is the number of vertices and $k$ is the solution size.

Also, the question Are there subexponential-time algorithms for NP-complete problems? addresses similar questions.


Are two terms where one is without a $\lambda\beta$ normal form unconvertible in $\lambda\beta$?

It is trivially the case that two terms can be $\beta$-convertible even though they do not have a normal form.

Consider:

$$((\lambda x.x)\ (\lambda x.x\ x))\ (\lambda x.x\ x)$$

and

$$(\lambda x.x\ x)\ (\lambda x.x\ x).$$

In one step we have
$$((\lambda x.x)\ (\lambda x.x\ x))\ (\lambda x.x\ x)\to (\lambda x.x\ x)\ (\lambda x.x\ x)$$


Hint: is the language $L' = \{a^n b^n c^{2n} \mid n \ge 0\}$ context-free?


The signed digit representation of Real Numbers seems like an efficient approach for:

Defining the arithmetic operations and proving their algebraic properties. This was done already in a Master's thesis by Michael Herrmann.
Proving Cantor's theorem on the uncountability of the real numbers.
Developing the notions of continuous and uniformly continuous functions.
Proving the Extreme Value Theorem in the form that every function on $[0,1]$ has a finite supremum.
Developing the Riemann integral.

This has the nice property of being constructive.

As demonstrated by Michael Hermann, the operations listed above can be defined using colagebraic coinduction and then reasoned about using set-theoretic coinduction.

This also suggests the possibility of proving analogues of the above in $p$-adic analysis. Here, a purely coalgebraic approach might actually work.

It's possible that vast swathes of General Topology (over separable spaces) can be developed using coinduction over $\mathbb N^\mathbb N$. Here, continuous functions would be defined by corecursion over $\mathbb N ^ \mathbb N$ and then reasoned about using set-theoretic coinduction. This appears to be the approach taken in Frank'a Waaldijk's Natural Topology (I'm not sure if it uses coinduction though).

The caveat of all the above is that I've never seen a full development of the above. But the possibility certainly exists if anyone has the time or motivation.


Suffix array and counting distinct substrings of specific length

The geeksforgeeks solution gives an efficient algorithm that accomplishes the following:

Sorts the suffixes of the input string in lexicographic order.
For every two adjacent suffixes in this order, finds the longest common prefix.

If you are after the number of distinct substrings of length $\ell$, you should proceed as follows:

If the first suffix has length at least $\ell$, initialize your counter with 1, otherwise with 0.
Now go over all the suffixes in lexicographic order. If the new suffix has length at least $\ell$ and the lcp with the preceding suffix has length smaller than $\ell$, then increment the counter.

For example, suppose that the string is ababa, and you're after substrings of length $\ell = 3$. The ordered suffixes are a, aba, ababa, ba, baba. The algorithm proceeds as follows:

The first suffix a is shorter than $\ell$, so the counter starts at 0.
The second suffix aba has length at least $\ell$, and the lcp with the preceding suffix has length less than $\ell$, so increment the counter. (We have discovered aba.)
The third suffix ababa has length at least $\ell$, but the lcp with the preceding suffix also has length at least $\ell$.
The fourth suffix ba has length less than $\ell$.
The fifth suffix baba has length at least $\ell$, and the lcp with the preceding suffix has length less than $\ell$, so increment the counter. (We have discovered bab.)


What is the difference between E-Science Infrastructures and Distributed Computing Infrastructures?

Both eScience infrastructures and grid computing are based on distributed computing, which is related to loosely-coupled applications. There are several models including client-server, peer-to-peer etc. The issues arising in distributed computing, such as security, failures, network partition etc must be taken into account at design time, since in this context failures are the rule and not the exception. Many large-scale scientific endeavors rely on distributed computing, such as for instance SETI@HOME, the projects using the BOINC middleware etc. However, these projects are not examples of grid computing.

Grid computing refers to the coordinated sharing of resources installed at different administrative domains, usually HPC resources. Each domain is called a Virtual Organization.
In contrast, the resources shared in projects such as SETI@HOME are usually common PC and laptops.

The grid computing paradigm emerged as a new field distinguished from traditional distributed computing because of its focus on large-scale resource sharing and innovative high-performance applications such as:

distributed supercomputing;
on demand computing;
high throughput computing;
data-intensive computing;

Distributed supercomputing applications require multiple supercomputers to solve problems otherwise too large or whose execution is divided on different components that can benefit from execution on different architectures. This class of applications present a number of challenges to be faced, like resource discovery and scheduling, coordinated startup, configuration at multiple sites, wide area message passing and fault tolerance. An example of such application is SF-Express, a distributed interactive simulation of a military battle. On demand computing refers to the possibility of dynamically acquiring online instruments (e.g. microscopes, satellite sensors and telescopes) connected by high-speed networks to gather and process the data generated. An experiment of microtomography at photon sources in 1999 demonstrated the feasibility of on demand computing. The aim of high throughput computing (HTC) is to schedule many independent jobs for parametric studies or data analysis; in this case a measure of efficiency is the number of jobs processed per unit of time. The two most important tools for HTC, namely Condor and Nimrod are now grid-aware. Data-intensive applications extract new knowledge from geographically distributed data archives or digital libraries; issues related to this class of applications include scheduling and configuration of multiple data flows through several hierarchy levels.

In the past, eScience infrastructures were almost always based on grid computing. Right now, cloud computing is also emerging as a viable alternative in some cases.


Convergence of recursive formula in TextRank

Your process is a Markov chain, so I suggest you try applying the theory of Markov chains. There's a rich and powerful theory that has been built up over time, which might be applicable here.

In particular, if we let $S$ denote the column vector $S = (S(V_1),S(V_2),\dots,S(V_n))$, then there is a matrix $n\times n$ $M$ such that each iteration maps $S$ to $MS$.  If the underlying graph is strongly connected, it looks like this Markov chain is irreducible, ergodic, aperiodic, and all its states are recurrent.  From this you should be able to deduce that it has a stationary distribution $\pi$ and that the stationary distribution is the unique limiting distribution of the chain, hence the algorithm eventually converges.  You should check all of this yourself carefully; I haven't checked any of this.

The rate of convergence will be dependent on the magnitude of the second-largest eigenvalue of the Markov chain.

Look at the analysis of PageRank for a detailed, worked example applying these concepts to a similar algorithm.  This analysis can be found in many textbooks and algorithms courses.


How can I make sense of amortized accounting method?

Amortized analysis is a strategy for analyzing a sequence of operations irrespective of the input to show that the average cost per operation is small, even though a single operation within the sequence might be expensive.

As it is shown in the above quote, amortized analysis is applicable particularly to a sequence of operations in which cheap operations occur frequently and expensive ones occur rarely. Moreover, in an operation sequence, the expensive operation is often related to (OR caused by) the cheap ones before it. For example, in your "Multi-Pop Stack", the cost of the expensive operation multi-pop(S,k) depends on the number of elements in the stack and thus on the earlier push(S,x) operations.

If we focus on a single multi-pop(S,k), we may be disappointed by its expensive cost. Worse still, its cost varies, depending on the current state of the stack when it is issued: if it has popped $t$ elements, then its cost is $t$. By accounting method, we turn to a sequence of operations and attribute (average) the varying cost $t$ of multi-pop(S,k) to the $t$ Push(S,x).

  Even if I get pass the "why 2 but not 100 credits" stage, $\ldots$

Yes, you can use 100 credits. However, 2 is tighter in terms of worst-case time complexity.

  $\ldots$ how can I rationalize the fact that the object somehow stores a credit?

"Credit" is only an analogy. We are charging the cost of some (expensive) operations to earlier (cheap) ones. From a different perspective, the earlier (cheap) operations had better save credits for further use of some (expensive) ones.

  How can we just arbitrarily assign these costs to these operations?

They are of course not arbitrarily assigned. Instead they are well chosen.


An algorithm for comparing a DFA and a regular expression

This technique I am going to describe works to compare two NFAs. Fortunately, you have mentioned that you know how to convert your regular expression into an NFA and it is trivial to convert your DFA into an NFA. (just treat the DFA as though it were an NFA)

Once you have your two NFAs, add two new symbols to your alphabet: $\$_1$ and $\$_2$. We're going to construct a larger NFA by combining the two NFAs that we have. Add a node (call it $\omega$), and add edges from every accepting node in the first NFA to node $\omega$ labeled with $\$_1$. Now add edges from every accepting node in the second NFA to node $\omega$ labeled with $\$_2$.

Now add another node (call it $\alpha$) and add epsilon-transition edges from $\alpha$ to the initial node in each NFA. (so $\alpha$ has only two edges leaving it). (alternatively, since some people don't like epsilon transitions, you can instead add to $\alpha$ all the outgoing edges of the initial nodes in each original NFA)

Now take this combined graph with the two extra nodes as an NFA: the initial node is $\alpha$, and the only accepting node in the combined graph is $\omega$.

Turn this NFA into a DFA. One side-effect of how we constructed edges into $\omega$ is that the DFA will have only a single accepting state. The two original languages will be identical if and only if in the DFA every edge going to this accepting node is labeled with both $\$_1$ and $\$_2$.

Essentially, what we did was form the languages:
\begin{align}
L_1 &= \{ w \ \$_1 \  | \ w \in L(M)\} \\
L_2 &= \{ v \ \$_2 \  | \ v \in L(r)\}
\end{align}
and then our combined NFA was the NFA for the language $L_1 \cup L_2$. The statement about the edges of the DFA says that there exists some set $A$ such that the language of our DFA is
$$\{a \ x \ | \ a \in A, x \in \{\$_1, \$_2\} \}$$
But this implies that if you stripped the $\$_i$ symbols off the end of the strings in $L_1$ and $L_2$ you'd have the same language.

Incidentally, you can use this DFA for $L_1 \cup L_2$ to easily construct DFAs for $L(M) \cap L(r)$, for $L(M) \cup L(r)$, for $L(M) \setminus L(r)$, for $L(r) \setminus L(M)$, and for the symmetric difference of $L(M)$ and $L(r)$. The exact details are left as an exercise for the reader, but it involves examining nodes with outgoing edges labeled with one of the $\$_i$ symbols, labeling some of those nodes as accepting nodes, and then erasing all edges labeled with the $\$_i$ symbols.

(These won't necessarily be minimal DFAs, even if you minimized the DFA before erasing the $\$_i$ edges. You'll need to apply standard DFA minimization algorithms if you want that.)


You said you could see lines, so I assume you could see their intersections. If you could assume to have at least 4 fixed points of the court which are always visible (corners might be a good choice), this problem is similar to the 3D pose estimation problem, since you are essentially looking for a pose (position and orientation) of a known 3D object in a 2D image.

You might find it useful to read about POSIT, an iterative algorithm published in 1992 and there is also this algorithm from 1999. Both algorithm solve the 3D pose estimation problem.


Are results after performing operations on AVL trees ambiguous?

In standard way the order of operations determines the tree shape - there are no ambiguous choices during insertion / deletion or rebalancing so it is unique.

There are more possible trees if you consider some additional operations that do not violate AVL properties like introducing stricter balance or rotating -1 to +1, please remember that this operations are non-standard and changing -1 to +1 serves only one purpose - to show different existing trees with AVL properties.


Find small superset of at least k of n given sets

The problem is NP-complete. Here is a reduction from 3SAT-5, an NP-complete version of 3SAT in which every variable appears exactly 5 times (and so the number of variables and number of clauses are linearly related).

We start by constructing two set systems. The first system $\mathcal{S}$ consists of 6 sets $A_0,A_1,B_0,B_1,C_0,C_1$ and 15 elements $D = \{0,1\}^4 \setminus (1,1,1,1)$, and has the following property:
$$ |A_i \cup B_j \cup C_k| = \begin{cases} 14 & \text{if } i=j=k=0, \\ 13 & \text{otherwise}. \end{cases} $$
The set system is given by
$$\begin{align*}
A_i &= \{(a,b,c,d) \in D : a = i\}, \\
B_i &= \{(a,b,c,d) \in D : b = i\}, \\
C_i &= \{(a,b,c,d) \in D : c = i\}.
\end{align*}$$
The only elements not covered by $A_i \cup B_j \cup C_k$ are those of the form $(1-i,1-j,1-k,d)$. If $i = j = k = 0$ then there is one such element, otherwise there are two.

The second system $\mathcal{T}$ consists of $2n$ sets $X_1,Y_1,\ldots,X_n,Y_n$ and $O(n^2)$ elements, and has the following property. Call a family of $n$ sets out of $\mathcal{T}$ proper if it contains exactly one of each $X_i,Y_i$. All proper families of $n$ sets cover the same number of elements $M$, and each improper family of $n$ sets covers at least $M+1$ elements.

The set of elements consists of all unordered pairs of sets $\{S,T\}$ other than those of the form $\{X_i,Y_i\}$. Each set $S \in \mathcal{T}$ consists of all $2n-2$ pairs containing it. Let $\mathcal{F}$ be a family of $n$ sets, with complement $\overline{\mathcal{F}}$. The only elements not covered by $\mathcal{F}$ are those of the form $\{S,T\}$ where $S,T \in \overline{\mathcal{F}}$. If $\mathcal{F}$ is proper then so is $\overline{\mathcal{F}}$, and so there are $\binom{n}{2}$ elements not covered. If $\mathcal{F}$ is improper then so is $\overline{\mathcal{F}}$, and so there are fewer than $\binom{n}{2}$ elements not covered.

The reduction. Let $\phi$ be an instance of 3SAT-5 with $n$ variables and $m=5n/3$ clauses. For each clause $\phi_j$ there is a copy $\mathcal{S}_j$ of system $\mathcal{S}$. There is also a copy $\tilde{\mathcal{T}}$ of $\mathcal{T}$ in which each element is replaced by $N = 13m+1$ elements. The total number of elements is polynomial in $n$.

For each variable $x_i$ there are two sets $X_i^0$ and $X_i^1$. The set $X_i^0$ is the union of the following six sets:

the set $X_i$ of $\tilde{\mathcal{T}}$
for each clause $\phi_j$ containing $x_i$ at the first position, if $x_i$ appears positively, then the set $A_0$ of $\mathcal{S}_j$, otherwise the set $A_1$ of $\mathcal{S}_j$
for each clause $\phi_j$ containing $x_i$ at the second position, either $B_0$ or $B_1$ (as above)
for each clause $\phi_j$ containing $x_i$ at the third position, either $C_0$ or $C_1$ (as above)

The set $X_i^1$ is defined similarly as the union of the following six sets:

the set $Y_i$ of $\tilde{\mathcal{T}}$
for each clause $\phi_j$ containing $x_i$ at the first position, if $x_i$ appears negatively, then the set $A_0$ of $\mathcal{S}_j$, otherwise the set $A_1$ of $\mathcal{S}_j$
for each clause $\phi_j$ containing $x_i$ at the second position, either $B_0$ or $B_1$ (as above)
for each clause $\phi_j$ containing $x_i$ at the third position, either $C_0$ or $C_1$ (as above)

The problem is to decide whether there are $n$ sets which together cover $13m+NM$ elements (or less).

If $\phi$ is satisfiable, say with truth assignment $x_i$, then $\{X_i^{x_i} : 1 \leq i \leq n\}$ covers exactly $13m+NM$ elements. Conversely, suppose there is a way to cover at most $13m+NM$ elements. If the solution is improper then it covers at least $N(M+1) > 13m+NM$ elements (considering only $\tilde{\mathcal{T}}$). If it is proper then it corresponds to some truth assignment $x_i$, and it is easy to check that the number of elements covered is $13m+NM+Z$, where $Z$ is the number of falsified clauses. Hence $Z = 0$ and we conclude that $x_i$ is a satisfying assignment.


How to create an LR($k$) grammar for a given language?

You question is very strangely stated. The answer is however very
trivial. Your language $L$ is a regular language, hence recognizable
by a DFA. It does not even need a pushdown stack. Hence it has to be
LR(k). Indeed, the lookahead is necessary only to make the recognition
deterministic, but in this case, it is deterministic to start with if
you use the DFA (this is a bit tautological, since building the LR
parser involve in general building a DFA, if my memory does not fail me)

You can get the LR grammar (if one dares calling it that, trivial as it is) just by taking the right-linear grammar
corresponding to the transitions of the DFA.

BTW, it is not easy to decide whether a given grammar is LR(k) for some unknown k, it is undecidable. But it is decidable when k is given, you just try to build the tables.

To answer your question about a procedure to build a LR(k) grammar for a given CF language, the answer is "sorry: not in this universe".

The reason is that it is undecidable whether a given CF language is deterministic or not. Since any deterministic CF language has a LR(k) grammar, if a procedure existed to produce a LR(k) grammar for a language, when possible, that would be a procedure to decide whether the language is deterministic. Since no such procedure can exist, we have no systematic way of obtaining an LR(k) grammar for the language.


What's the name of this sorting(?) algorithm?

If we can assume that there is a total order on all colors: to find the largest element, there is a straightforward $O(n)$-time algorithm to find it: you scan through all colors, keep tracking of the largest element seen so far:

Set $m$ to the first color.
For each other color $c$:

Set $m := \max(m,c)$.

(Here $\max$ refers to the larger of the two colors, i.e., whichever is more preferred.) There is no need to "sort" all of the colors to find the largest (most favorite) color.
Alternative, suppose we cannot assume the colors are totally ordered, and the order is a partial order.  Then you'd need to specify what is meant by "most favorite" color.  One possible definition is a maximal color, i.e., one where no other color is more preferred.  (Note that there may be multiple such colors.)  If so, you can again find it via the same linear scan (if two elements are incomparable, you stick with the current element).


How to intuitively come up with an example for an ambiguous grammar and how to make that grammar unambiguous?

The simple way of seeing this class of ambiguities is to observe that if two right-hand sides for the same non-terminal overlap, then they could be applied in either order:

 D ::=     "*" D
    |          D "[" number "]"

The overlap is pretty clear:

 "*" D "[" number "]"

Another example, where a right-hand side can overlap with itself:

E ::= E "+" E

Overlap:

      E "*" E
            E "*" E
      -------------
      E "*" E "*" E

The solution is to remove the overlap by introducing a new non-terminal for one of the overlapping uses. Here's my solution to the ambiguity in your grammar:

Declaration ::= Type D ;
Type ::= "int" | "char"
D ::= "*" D
   E
E ::= E "[" number "]
   |  E "(" Type ")"
   |  "(" D ")"
   |  name

Which productions you decide to shift to the new non-terminal is not arbitrary; it will define which of the competing parses is correct for the language you are designing. There is no universal answer to that question, so it cannot be done algorithmically.

Note: The clumsy solution you have been provided with is probably because your lesson is being mixed with a discussion of top-down parsing. My grammar, though unambiguous, is not suitable for top-down parsing because it is left-recursive. However, the resulting parse tree reflects the syntactic structure of the declaration.


Can we say DFA is more efficient than NFA?

There are two answers, depending on how you define efficient.

Compactness of representation

Telling more with less: NFAs are more efficient.

Converting a DFA to an NFA is straightforward and does not increase the size of the representation.

However, there are regular languages for which the smallest DFA is exponentially bigger than the smallest NFA. A typical example is $(a|b)^*b(a|b)^k$ for $k$ fixed.

Computation

Running it fast: DFAs are more efficient.

The computers we use today are deterministic in nature. That makes them bad at dealing with non-determinism. There are two common ways of dealing deterministically with NFAs: backtracking on one side, which is rather costly, or keeping track of the active states, which means each transition will take up to $N$ times longer (where $N$ is the size of the NFA).


The problem of creating a parse tree given a grammar and a word generated by it is known as parsing. The CYK algorithm parses all context-free grammars, but is slow. In practice, only restricted types of context-free grammars are used, and these can be parsed in linear time. The common example is LALR parsing. Perhaps you will learn more about this topic in due time.


Zero-knowledge proof of $\beta\eta$ equality

I doubt that a zero-knowledge proof is possible, because it seems likely that any finite proof will leak at least partial information about the length of the path that converts $t_1$ to $t_2$, and hence won't be zero-knowledge.  In particular, suppose Alice and Bob's interaction takes $T$ time steps.  Then in any reasonable proof I can imagine, Bob would be able to infer that $t_1$ can be converted to $t_2$ using a path of length at most $T$.  This is partial knowledge, because there exists a pair $t_1,t_2$ of terms that take strictly more than $T$ time steps to convert.

I suspect that we might need an additional condition, such that there is a fixed and known upper bound $B$ on the length of the path converting $t_1$ to $t_2$.  If you have such a bound, there is a zero-knowledge proof protocol whose complexity is polynomial in $B$, as the statement you are proving becomes a NP-statement, and it is known that there are zero-knowledge protocols for every language in NP.


Polynomial time problems with provably high degree time complexity?

The time hierarchy theorem, proved by diagonalization, shows that for every reasonable function $f$ there exists a problem solvable in $O(f(n))$ but not in $o(f(n)/\log f(n))$. One such problem is, given a Turing machine and in input $x$, to determine whether the machine halts in $x$ within $f(|x|)$ steps. In your case, you can choose $f(n) = n^k \log n$ to obtain a problem solvable in $O(n^k \log n)$ but not in $o(n^k)$.


Question about how can i determine if counting sort is the right option over other sorting algorithms

I wouldn’t be too happy with your professor’s solution. You noticed that it will refuse to do a very fast counting sort if all item are either nk+1 or nk+2. That’s bad. What is fatal is that it will always do a counting sort if the array elements are all negative. (Please don’t tell me that a sorting algorithm which can only handle positive numbers would ever be considered).