As it's explained in the comments, $M$ and $N$ are know as metavariables. More importantly, this kind of definition is known as an inductive definition, that is, you start with very basic elements (symbols belonging to the set $\mathcal{V}$) and build up more complex things from there.

For instance, let $\mathcal{V} = \{v_0, v_1, \ldots, v_{1001}, \ldots\}$. In the BNF definition:

$$ M,N ::= x \mid (M N) \mid (\lambda x.M) $$

$x$ can be any of the $\{v_0, v_1, v_2, \ldots \}$. That means any symbol from $\mathcal{V}$ can be considered a $\lambda$-term, a most basic of rules.
$M$, $N$ are structures already known to be $\lambda$-terms, so from the previous example we can build expressions like $(v_0 ~ v_1)$, $(v_{100} ~ (v_{0} ~ v_{1}))$, $((v_{100} ~ (v_{0} ~ v_{1})) ~ v_2) $ and so on.
With the previous two rules you can now build more complex expressions like $(\lambda v_{100}. (v_0 ~ v_1))$, since all previous terms made by combining the two previous rules are known to be $\lambda$-terms.
Now you can mix all three rules, like in $(v_0 ~ (\lambda v_9.(v_9 ~ v_{999})))$


Runtime analysis of sorting an array with known number of inversions

Hint: Make use of the following facts:

Each pair $i,j$ that forms an inversion for sorting in ascending order, does not form an inversion when sorting in descending order (and vice versa).
Reversing the complete list can be done in $\Theta(n)$.


To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$

You're headed in the right direction, but you need an intermediate step. Permit me to simplify things a bit by defining $\lg n = \log_2n$.

A Dead End

Your substitution method, where you want to establish that $T(n) \le cn^{\lg7}$ inductively, using the assumption $T(n/2)\le c(n/2)^{\lg 7}$ runs into problems, as you've already seen. Here's what happens:
$$\begin{align}
T(n) &= 7T\left(\frac{n}{2}\right)+n^2&\text{by definition}\\
 &\le 7\left[c\left(\frac{n}{2}\right)^{lg7}\right]+n^2&\text{by the inductive assumption}\\
 &=7\left[c\frac{n^{\lg7}}{7}\right]+n^2&\text{since $2^{lg 7}=7$}\\
 &=c\,n^{\lg7}+n^2
\end{align}$$
and you'll obviously never be able to find a $c$ for which $c\,n^{\lg7}+n^2\le c\,n^{\lg 7}$.

A Way Out

The problem is that the $n^2$ term is messing you up. If it weren't there, then substitution would work. Suppose, for instance, that we had the simpler recurrence $S(n)=7\,S(n/2)$. Now life would be easy, since then the proof above would go through nicely. Assume that $S(n)\le c\,n^{\lg7}$. Then we'd have
$$\begin{align}
S(n) &= 7S\left(\frac{n}{2}\right)&\text{by definition}\\
 &\le 7\left[c\left(\frac{n}{2}\right)^{lg7}\right]&\text{by the inductive assumption}\\
 &=7\left[c\frac{n^{\lg7}}{7}\right]\\
 &=c\,n^{\lg7}&\text{as required}
\end{align}$$
and if you do this again and again, driving $n$ down to $1$, you'll find that you can choose any $c\ge S(1)$.

Transforming the Dead End Into the Way Out

Let's make the $n^2$ term go away. Let $S(n) = T(n)+k\,n^2$. Then from
$$
T(n)=7\,T(n/2)+n^2
$$
we have, substituting and simplifying,
$$\begin{align}
S(n)-k\,n^2&=7\,[S(n/2)-k(n/2)^2]+n^2&\text{and so}\\
S(n) &= 7\,S(n/2)+n^2(k-7k/4+1)
\end{align}$$
and it's not hard to see that $k=4/3$ will make the $n^2$ term vanish, giving the $S$ recurrence we just solved above. Putting these together we have
$$
T(n)+\frac{4}{3}n^2=S(n)\le c\,n^{\lg7}
$$
and so
$$
T(n)\le c\,n^{\lg7}-\frac{4}{3}n^2<c\,n^{\lg7}
$$

Lessons Learned

Truth to tell, I'd attack this problem by iterative expansion, namely the way Yuval did it in his answer, but these "substitution method" questions come up often enough that I thought this cautionary tale was warranted. The lessons to be learned here are

The method of substitution often doesn't work when applied to a recurrence relation.
It always applies to recurrences of the form $S(n)=p\,S(n/q)$ as long as $q\ne0$
A useful tool to have in your kit is knowing that sometimes you can transform a complicated recurrence into a simple one by suitable addition (or, sometimes, multiplication).


A single rule can not be "unrestricted".

The whole set of rules is $(T \cup N)^+ \to (T \cup N)^*$. So the class of unrestricted grammars may use any rule from this set.

Restricted classes of grammars are only allowed to use a strict subset of all rles, e.g.

right-regular grammars are restricted to $N \to T^*N^{\{0,1\}}$, and
context-free grammars to $N \to (T \cup N)^*$.

By going through the Chomsky hierarchy, you will note that the rule

$\qquad zA \to xy$

is not admitted in any but the type-0 grammars; try to see why it's not a "context-sensitive rule". That does not mean it is only ever allowed in the unrestricted class -- just that it's not in any on this list. There are many more classes.


Proving that the average case complexity of binary search is O(log n)

I think most text book will provide you a good proof.

For me, I can show the average case complexity as follows.

Assuming a uniform distribution of the position of the value that one wants to find in an array of size $n$.

For the case of 1 read, the position should be in the middle so there is a probability of $\frac{1}{n}$ for this case
For the case of 2 reads, one will read the middle position and then 1 of the 2 other middle positions from the 2 sub-arrays. This probability is $\frac{2}{n}$
For the case of 3 reads, there are $2*2$ positions which result in this cost as you go into the 4 sub-arrays of the first 2 sub-arrays.  The probability for this cost is $\frac{2^2}{n}$

...
For the case of $x$ reads, the probability for this case is $\frac{2^{x-1}}{n}$

For the average case, the number of reads will be

$\sum\limits_{i=1}^{\log(n)} \frac{i2^{i-1}}{n} = \frac{1}{n} \sum\limits_{i=1}^{\log(n)} i2^{i-1}$

Now you can do integration on an approximation formula which will give you $O(n\log(n))$.
Note that $\int\limits_{1}^{\log(n)} x 2^x dx$ can be calculated and bounded into $\log(n)*2^{\log(n)} = n\log(n)$
This is a very good way to do that applies to many cases.

Another way to see it can also be $i2^{i-1} < \log(n) * 2^{i-1}$

Then the formula above is bounded by
$\frac{\log(n)}{n} \sum\limits_{i=1}^{\log(n)} 2^{i-1}$

The summation part is actually $\frac{1 - 2^{\log(n)}}{1 - 2} = 2^{\log(n)} - 1 = n - 1$
which is definitely less than $n$, multiplying this with $\frac{\log(n)}{n}$ gives you what you want $\log(n)$

So you will get the bound as you want $O(\log(n))$


How to sample random game input that looks similar to human control?

A Hidden Markov Model could be useful here. Basically you have a Markov Chain of internal states (e.g. "i just jumped", "i'm running", "i'm ready to jump again") and for each transition of the internal state it generates an action (e.g. "f" or "j") according to a distribution that is different for each internal state. You will need to figure out how many different internal states you need, and then you can learn the model from the data.

If you want to model a bunch of different things inside the hidden state (running/not running, has weapon/doesn't have weapon, ...) you can switch to some kind of recurrent neural net (e.g. LSTM)


Finding pairs $a \in A$, $b \in B$ where $a \ge 3b$ in linear time

If you need to list all output pairs, as you say, then the problem can't be solved in any less than quadratic time, for the reason that the output may be of quadratic size. Imagine that $A$ and $B$ are both half the input (say, both length $n$), and
\begin{align*}
A &= [3n + 1, 3n+2, 3n+3, \ldots, 4n-1, 4n] \\
B &= [1, 2, 3, \ldots, n]
\end{align*}

Then the output to your problem is all pairs of an element in $A$ and an element in $B$, and there are $n^2$ such pairs.

Probably there is an additional fact you haven't mentioned, that you don't have to produce all pairs, but you just have to produce a more compact representation of the output (e.g. for each $a \in A$, you only need to produce the maximal $b \in B$ such that $a \ge 3b$).

A hint for this altered version, where you only need the maximal $(a,b)$ pairs:

Imagine you are iterating through both $A$ and $B$ at once, instead of just iterating through $A$ or $B$ separately. So, you are keeping two pointers, one into $A$ and one into $B$. Suppose you have found the maximal pair for $a$, so you know $(a, b)$, and the next element in $A$ after $a$ is $a'$. What should you do?


How to represent bottom element (integer domains) in SMT formula

First, you need to figure out the semantics of your language: does divide-by-zero cause the program to abort/halt/throw an exception, or does execution proceed and the divide-by-zero returns a NaN?
If it causes the program to halt, then you should not try to represent $\bot$ values.  Instead, treat division as a conditional statement, that first tests whether the divisor is zero, and if so, aborts/halts/etc.
If it returns a NaN, then one approach is to introduce an extra boolean variable associated with each program variable.  This boolean indicates whether the corresponding program variable holds a NaN.  You should be able to work out the appropriate constraints to ensure these boolean variables receive the appropriate values.


What is a "contradiction" in constructive logic?

It is immaterial whether we speak about constructive or classical logic in this situation. If you read your questions again, you will see that they apply to boths kinds. The only difference that we need to take notice of is the presentation of negation $\lnot A$. It can be presented in several ways classically, but intuitionistically it is best to use it as an abbreviation for $A \Rightarrow \bot$ (which is precisely what Bob Harper is hinting at in the quoted paragraph). But let us not confuse negations and contradictions.

In both cases, a contradiction is a situation in which we have managed to prove falsity $\bot$. How could we derive $\bot$ in a sensible way? Well, from an inconsistent set of hypotheses, that wold be a sensible way to do it.

You have no discretion to "declare" a contradiction. You must prove that a given set of hypotheses is contradictory by deriving $\bot$. For instance, if $a = b$ and $\lnot (a = b)$ then we may use the fact that $\lnot (a = b)$ is an abbreviation for $(a = b) \Rightarrow \bot$ and conclude $\bot$ by modus ponens.


5-state DFA that recognizes only the string 00001111

[If I understand the question correctly, this only relates to strings of length 8, i.e. for an automata $A$ we only look at $L(A) \cap \Sigma^8$]

There is a slight variance in interpretation of what a DFA is that plays a role here.

You can construct a DFA with 5 states that accepts $00001111$, but it is not complete, meaning not every state has an exiting transition for every symbol of the alphabet. This quesiton addresses this point in more details.

What this difference in notation allows you to do is skip the sink-node:

If the input string is of length 8, this automaton accepts only $00001111$.


Many research projects use something called "hard negative mining": instead of training on all of the positive instances (e.g., "text" or "object") and all of the negative instance (e.g., "not text" or "not object"), they train on all of the positive instances and a carefully chosen subset of the negative instances.  In particular, they omit many of the 'obvious' negative instances and try to bias towards choosing negative instances that are more difficult to handle correctly.  It's not clear to me whether this is truly necessary or beneficial with modern machine learning methods, but it is something you could try, if you don't want to use all of the negative instances.

Yes, to create negative instances, you would normally sample random patches of the image (at a random location), subject to the restriction that they not have too much overlap with the actual text/objects.

For learning more about how to recognize object vs objectness, read about "objectness" detection or saliency detection.  For learning more about detecting text, you might be interested in the stroke width transform and the segmentation step in OCR.


The fitting of a minimum area quadrilateral to a set of points is an uneasy problem, and I believe that simpler approaches are good enough.

Notice that the corners are rounded and cannot be used as such. So you'd better fit straight edges and intersect them to obtain the quadrilateral.

One approach is by the Hough transform. To make it maximally efficient, I would recommend to process four tight areas or interest around the edges of the axis-aligned bounding box. This will make processing much faster, avoid false positives and avoid any ambiguity on the correspondences.

You can also sample points on the four sides and fit a straight line by total-least squares, or by some robust line fitting method.

If you want to make sure that the fitted lines don't cross the shape at all, you can handle the four sides independently and consider a partition of the plane in the four quadrants delimited by the diagonals (even if they are approximate). In every quadrant, you will find the minimum area triangle formed by the line against an edge of the convex hull. Just try every edge of the convex hull in turn.

[Technically, it is possible that the minimum is achieved with a line through some vertex of the convex hull, with an intermediate angle, i.e. not in the direction of a hull side. We should also check if the area function is always unimodal in terms of the line angle. IMO these refined considerations can come later.]


Algorithm to check that one sum is less than another

I will assume your variables can take on arbitrarily real numbers.  Build a weighted directed graph that represents all known inequalities, with one vertex per element (i.e., $n+m$ vertices in total).  In particular, apply 'eq' and 'lt' to all ${n+m \choose 2}$ pairs of elements.  Then:

If $x < y$ (i.e., $\textsf{lt}(x,y)$ returns true), where $x,y$ are two elements, add a directed edge $x \to y$ with length $-1$.

If $x \le y$ (i.e., $\textsf{lt}(y,x)$ returns false), add a directed edge $x \to y$ with length 0.

If $x=y$ (i.e., $\textsf{eq}(x,y)$ returns true), then add directed edges $x \to y$ and $y \to x$ with length 0.

If $x\ne y$ (i.e., $\textsf{eq}(x,y)$ returns false), do nothing and add no edges.

Let $d(x,y)$ be the length of the shortest path from $x$ to $y$ in this graph.  If $d(x,y)=c$, then we will be guaranteed that $x \le y + c$, and this is the optimal $c$ for which this is true (i.e., it is the smallest $c$ for which this is true).
Compute a new bipartite graph $G$  with an edge $a_i\to b_j$ of length $d(a_i,b_j)$ for each $a_i,b_j$.  This can be computed with the Floyd-Warshall algorithm, for example.
Find the minimum-weight perfect matching in this bipartite graph.  This is an instance of the assignment problem, and hence can be solved in polynomial time with standard algorithms.  If the total weight of the matching is $w$, then we can conclude that
$$a_1+\dots+a_n \le b_1+\dots+b_m + w.$$
Consequently, if $w \le 0$, then we can conclude that $a_1+\dots+a_n \le b_1+\dots+b_m$ and we can return "true" to the original question.
Solve another assignment problem for the bipartite graph with edges $b_j \to a_i$ of length $d(a_i,b_j)$ for each $a_i,b_j$.  In this way, we obtain $w'$ such that
$$b_1+\dots+b_m \le a_1+\dots+a_n + w'.$$
If $w' \le 0$, return "false" to the original question.
Otherwise, return "unknown".
This takes $O(nm)$ calls to the binary operations and $O((nm)^{2.5} \log n)$ running time.
This works for this very specific problem.  A more general approach is to use linear programming: if you want to check whether $(I_1 \land \cdots \land I_k) \implies J$, where the $I$'s and $J$ are linear inequalities, then check whether the system of inequalities $I_1 \land \cdots \land I_k \land \neg J$ is satisfiable using linear programming.  This will let you support more general mathematical expressions and more general relationships between the variables, as long as they are all linear functions/inequalities of the variables.  In your problem, after you call 'lt' and 'eq' on all pairs of elements, each operation that returns something other than "unknown" gives you an inequality or equality $I_i$ on two variables.  Here $J$ is the inequality $a_1+\dots+a_n \le b_1+\dots+b_m$.  So, you could apply linear programming directly to your problem.  This approach also supports more general operations, as long as they are all linear.
My answer above essentially solved the linear programming problem for the special case where $I_1,\dots,I_k$ are all inequalities with a difference of two variables, and $J$ has the form $a_1+\dots+a_n \le b_1+\dots+b_m$.  I used a standard data structure for representing differences of two variables (the graph), and then combined it with an algorithm for the assignment problem to capture the one additional inequality with multiple variables.


Are Test and set primitives as powerful as semaphores?

Your hunch is correct, they aren't equivalent. Test-and-set has a consensus number of 2, which means, roughly speaking, that it is only able to efficiently synchronize between 2 processes. See Why is the consensus number for test-and-set, 2?. Semaphores allow synchronization between an arbitrary number of processes (assuming no bound on the number of processes waiting on a semaphore).

It isn't really a “fair” comparison, since test-and-set is a hardware primitive while semaphores are a software interface. But if does show that test-and-set isn't sufficient to implement (wait-free) semaphores.


Is the DPLL algorithm complexity in terms of # of clauses or # of variables?

In the papers I've read the time complexity of DPLL is expressed in terms of the number of variables in the CNF formula.  Using the number of clauses is inappropriate in general because it is known that random k-SAT instances go through an easy-hard-easy transition if you fix the number of variables and increase the number of clauses.  The solution space goes from underconstrained to overconstrained as the number of clauses increases with the hard instances clustering between those extremes.


Forward must problem explanation in compiler design

I typically think of must as meaning logical and.

In the case of available expressions, when you reach a join point, the expression in question is available at the join point if and only if the expression is available on all of the input edges to the join point.  That is: if the expression is available on the first input edge, and it is available on the second input edge, and it is available on the third input edge, etc.

There are other properties, such as "could be a null pointer" which are may properties instead of must properties.  May I think of as meaning logical or.


Why do admissible functions allow $A^*$ to retain correct shortest path computations?

Look at it this way:

The heuristic function lets us avoid exploring subpaths that we know are too long.

Suppose we're trying to get from $u$ to $t$. We're running our search, and the best path from $u$ to $t$ so far has length $UB$. We know it takes at most $UB$ to get to $t$.

Now, we see a vertex $v$. If we've found $v$, then we know the exact shortest path from $u$ to $v$. Call this $k$.

We want to know if we should bother looking at the shortest path from $v$ to $t$. So we ask, can it possibly be better than our best so far? So, we check our heuristic. We know that the distance from $v$ to $t$ is at least $h(v,t)$.
So if $k + h(v,t) > UB$, then we don't need to even bother expanding $v$, since there's no way it will be better than existing paths to the goal.

This is only safe if $h$ is admissible. But note also that, the larger $h$ is, the more paths we will be able to eliminate. So we have "Price is Right" rules: our goal is always to get $h$ as close to the actual distance function as we can, but we are never allowed to go over.

Dijkstra's is just A* with the heruistic of $h(x,y) = 0$: we ignore vertices if the distance to them from the start is farther than the best distance to the end so far. But we can do a lot better than this if we have a lower-bound on the distance between two vertices, since we can eliminate even more paths.

A common heuristic in a path-finding graph is to use euclidean distance: the shortest road between two points is never shorter than the distance between those two points.
Then, our heuristic lets our algorithm eliminate nodes which are close to the initial node if they take us too far away from the final node.

If you're trying to get from Seattle to New York, Dijkstra's might try to go through Portland, because it's close to Seattle. But A* with a Euclidean heuristic sees that this takes you out of your way too much, and can avoid this path.


Should you post basic computer science homework to your github?

No, solutions to homework assignments are not likely to impress potential future employers.
Many professors would prefer that you not post solutions to homework assignments to public Github repositories. Why? If they ever reuse those problems in a future semester, then by making the solutions publicly available you are creating a temptation to cheat for other students, and that can be detrimental. So it would be a kindness to avoid publicly posting solutions.
If you are a student, you can get free unlimited private repositories on Github that you could use for homework assignments. Just make sure not to let them revert to public when you graduate.


First take the case when you don’t have any key repeated: you can use an ordinary Binary Search Tree (BST) and perform an inorder traversal for searching the required key. Since inorder traversal gives you the keys in sorted order, so you can simply maintain a counter which you increase every time you visit a new node.

Since, you want to allow multiple occurrences of keys, you need need to modify the node to have a integer to hold the number of times that key has been added.

It’s quite easy to fill the details.


Yes:
$n+m \le n+n=2n$ which is $O(n)$, and thus $O(n+m)=O(n)$

For clarity, this is true only under the assumption that $m\le n$. Without this assumption, $O(n)$ and $O(n+m)$ are two different things - so it would be important to write $O(n+m)$ instead of $O(n)$.


Question on Virtual memory and Physical memory

The page entry contains other things than the base of the physical page.  Typically:

a present or absent bit (to handle the case where the page is not present in the memory: is on disk or just does not exist)
access right: may the process read, write, execute the page
some kind of use count (to help the OS makes its choice when there is a need page out)

and obviously some bits may be unused or reserved for future usage.

Note that, although in 64-bit system we are in a phase where the virtual address space is bigger than the physical address space, historically on architectures which lived long enough that tends to be followed by a phase where the physical address space is bigger than the virtual one.  The additional memory may be visible only by the OS (which will put other processes there), or even made available to user processes with some kind of bank switching (see extended and expanded memory or more recently PAE in x86 world, some other architectures have had similar things)


Even if i don't really understand your point, i'm try to figure out an intuitive proof for building heap time complexity, starting from a simple recursive algorithm for building heap.

You have a collection of n unsorted element, called A,
you want from this collection build a heap(in your case a min-heap because you are mantaining the minimum of collection in the root).

So modelling the heap you want to create like a binary tree, it must shows some property like:

complete: the tree is "fullfilled" until second-last level and the leaves are "compatted" on the left.
logarithmic height: if the number in the heap is n then the height is O(logn) (you can proof this starting from the first property)
order relation between nodes: in particular, if v is father of w in the tree then $$ value(v)<= value(w) $$

Now think A as an unsorted binary tree you can recursively construct an heap follows this step:

Make recursive call on the left sub-tree
Make recursive call on the right sub-tree
Call heapify on the root of the current tree

heapify

Heapify on a node v simply compare v with it sons, and exchange v with the lowest son if it is less than v. Do this repeatedly until exists a son of v that have less value.

heapify complexity

So in heapify you make, at most, as many exchanges as high as the tree is, and since the only operation you perform is compare with the son(at most 2) for each level

=> time complexity is O(logn) for the 2nd property.

now for compute the overall complexity you can set a recursion function considering the worst case in wich A is a perfect binary tree (complete and with last level  fullfilled).

So let's assume A is a perfect binary tree,
the recursion function is:

$$ T(n) = T((n-1)/2) + O(log(n)) $$

because in each recursion step you consider half-part of the tree and exclude the root, and in each step with n as parameter you pay $$ O(log(n))$$ for heapify.

So by Master theorem (https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms))

$$T(n) = O(n) $$

so you can deduce that building an heap from an unsorted collection of value is linear in the number of element in the collection.

Know this maybe don't answer your question but i hope can help!


Clearly, an algorithm that runs on bipartite graphs only can't be slower than an algorithm that works on any graph. Therefore, the bipartite-shortest-path problem is in P.

In the opposite direction, consider a transformation that splits every edge into a pair of edges. It results in a bipartite graph and it preserves shortest paths. Therefore, any algorithm that can find the shortest path in a bipartite graph with v+e vertices and 2e edges can also find the shortest path in an arbitrary graph with v vertices and e edges.

Time complexity of Dijkstra's algorithm is O(e + v log v),  so any performance improvement gained by a bipartite-shortest-path algorithm over a regular algorithm is limited to the constant factor of 2. Any faster, and it supersedes the regular algorithm entirely.

The Wikipedia page on the shortest path problem lists several special cases but never mentions bipartite graphs even in passing. It does include an algorithm from 2004 which reduces the time complexity to just O(e + v log log v).

Conclusion: There most likely is no known algorithm for bipartite path search that improves upon the best known algorithm for path search on arbitrary graphs. There is also no room for such improvement in terms of algorithmic complexity, and for only a factor of two in terms of runtime (treating log(log v) as a constant).


What to consider while proving NP-completeness?

However, if one of the coordinates has exponentially many bits with respect to the input, then is this considered as a exponential-time checking? Or it is still polynomial-time with respect to the length of the solution?

The length of the solution/certificate must be polynomial in the size of the original instance. Therefore, if the certificate/solution can be exponential in the size of the input (due to the numbers needing exponential representation) then you do not have a valid proof of membership in $NP$. The problem might be $\exists \mathbb{R}$-hard.


Will the machine ever reach on any other state other than start state?

Say $M$ has start state $s$ and transition function $\delta$. Construct a new Turing machine $M'$ with $Q = \{s, HALT\}$ (where s != HALT) and $\delta'$ as it's transistion function, defined by the following. $s$ is again the start state and $HALT$ is the accept state.

$$ \delta'(s, x) = \begin{cases}
      s & \delta(s, x) = s \\
      HALT & \mbox{otherwise} \\
   \end{cases} $$

$M'$ will halt IFF $M$ ever transitions out of the start state.

If you know what the maximum shifts function is for two states and your symbols then you can simulate $M'$ for that many steps to determine if $M'$ halts or not. Non constructively even if we can't compute the busy beaver function for your number of symbols it has some value and therefore our argument still goes through.

This shows that, at least classically speaking, this problem is decidable. It also constructively shows that it's decidable for any number of symbols that we can constructively prove an upper bound on the maximum step function for. This algorithm runs in constant time...where the constant might be very large. So asymptotically it's ideal. I'm not sure if there's an algorithm that does this with a smaller constant but I'm betting it's not possible.


What is the name two mutually idempotent functions?

These are known as inverse functions. For example, the mappings $x \mapsto 2x$ and $x \mapsto x/2$ are inverses of each other, as are $\exp$ and $\log$ (restricted to positive numbers), or $\sin$ (restricted to the interval $[-\pi/2,\pi/2]$) and $\arcsin$.


Term for a matching which is perfect on one side only

Such a matching is said to saturate one of the sides.  More specifically, if $M$ is a matching of a graph $G$ and $v$ is incident to one of the edges of $M$, we say that $M$ saturates $v$.  If $A$ is a set of vertices, then we say that $M$ saturates $A$ if every vertex in $A$ is saturated by $M$.

Specifically for your case, the matching saturates the smaller of the two sides of the bipartition.


How come this turing machine running time is $O(n^{1+\log_2 2006}\cdot \log_2n)$

This bound comes from the number of possible configurations. If you do more steps than you have configurations, you are in a cycle.

So let us quickly get a bound for the number of configurations. You have $100+\log n$ possible positions for the head on the work tape and $n$ positions for the head on the input tape. The work tape can contain $2006^{100+\log n}$ different words. Furthermore there are 27 states. Combining everything gives
$$
\begin{align}
27n \cdot (100+\log n) \cdot 2006^{100+\log n}&=27\cdot2006^{100}(100n+n\log n) n^{\log 2006}\\
&=O((100n+ n\log n)  n^{\log 2006})\\
&=O(\log n\cdot  n^{1+\log 2006})\\
\end{align}$$


Ironically, the title is on point but not in the way you seem to mean it which is "is the lambda calculus just a notational convention" which is not accurate.

Lambda terms are not functions1. They are pieces of syntax, i.e. collections of symbols on a page. We have rules for manipulating these collections of symbols, most significantly beta reduction. You can have multiple distinct lambda terms that correspond to the same function.2

I'll address your points directly.

First, lambda is not a name that is being reused. Not only would that be extremely confusing, but we don't write $\lambda(x)$ (or $(\lambda\ x)$) which is what we'd do if $\lambda$ was a name for a function, just like we write $f(x)$. In $f(x)$ we could replace $f$ (if it were defined by a lambda term) with the lambda term producing something like $(\lambda y.y)(x)$ meaning $(\lambda y.y)$ is an expression that can represent a function, not a declaration declaring a function (named $\lambda$ or anything else). At any rate, when we overload terminology/notation, it is (one hopes) done in a manner where it can be disambiguated via context, that certainly can't be the case for lambda terms.

Your next point is fine but somewhat irrelevant. This is not a competition where there's Team Lambda Terms and Team Functions, and only one can win. A major application of lambda terms is studying and understanding certain kinds of functions. A polynomial is not a function though we often sloppily identify them. Studying polynomials doesn't mean one thinks that all functions should be polynomials, nor is it the case that polynomials have to "do" something "new" to be worth studying.

Set theoretic functions are not black boxes, though they are entirely defined by their input-output relation. (They literally are their input-output relation.) Lambda terms are also not black boxes and they are not defined by their input-output relation. As I've mentioned before, you can have distinct lambda terms that produce the same input-output relation. This also underscores the fact that lambda terms can't be functions, though they can induce functions.2

In fact, the analogy between polynomials and lambda terms is very close, and I suspect you may not appreciate the distinction between a polynomial and the function it represents, so I'll elaborate a bit.3 Typically when polynomials are introduced, usually with real coefficients, they are treated as real functions of a particular type. Now consider the theory of linear-feedback shift registers (LFSRs). It is largely the theory of (uni-variate) polynomials over $\mathbb F_2$, but if we think of that as a function $\mathbb F_2\to\mathbb F_2$, then there are at most $4$ such functions. There are, however, an infinite number of polynomials over $\mathbb F_2$.4 One way to see this is that we can interpret these polynomials as something other than $\mathbb F_2\to\mathbb F_2$ functions, indeed any $\mathbb F_2$-algebra will do. For LFSRs, we commonly interpret the polynomials as operations on bitstreams, which, if we wanted could be represented as functions $\mathbf{2}^{\mathbb N}\to\mathbf{2}^{\mathbb N}$, though the vast majority of such functions would not be in the image of the interpretation of an LFSR.

This applies to lambda terms as well, we can interpret both of them as things other than functions. They are also both much more tractable objects to work with than the typically uncountably infinite sets of functions. They are both much more computational than arbitrary functions. I can write a program to manipulate polynomials (with coefficients that are computably representable at least) and lambda terms. Indeed, untyped lambda terms are one of the original models of computable functions. This more symbolic/syntactic, calculational/computational perspective is usually more emphasized, especially for the untyped lambda calculus, than the more semantic interpretations of the lambda calculus. Typed lambda terms are far more manageable things and can usually (but not always) easily be interpreted as set theoretic functions, but can also usually be interpreted into an even broader class of things besides functions than the untyped lambda calculus. They also have a rich syntactic theory of their own and a very deep connection to logic.

1 It's possible the issue might go the other way. Maybe you have a misapprehension about what a function is.

2 This is actually not so straightforward. For the untyped lambda calculus, it doesn't really make sense to naively interpret arbitrary lambda terms as set-theoretic functions. You can start to see this when you try to articulate what the domain of the interpretation should be. If I interpret a lambda term as an element of a set $D$, I also want to be able to interpret it as a function on $D$ and into $D$ since I want to interpret application as function application. You end up with $D^D\subseteq D$ (or a weakening of this) which is true only of the singleton set. What we need for the untyped lambda calculus is a reflexive object, and for the category of sets there are no non-trivial reflexive objects. The story is quite a bit different for typed lambda terms, but can still be non-trivial.

3 If you are clear on this distinction, then the analogy should be pretty informative.

4 This issue doesn't occur with fields of characteristic 0, like the complex numbers, reals, rationals, or integers, so the distinction isn't as sharp, though it still exists.


Is the capacity achieving input of a discrete memoryless channel unique?

I believe the answer is "yes", when $Q$ is square and nonsingular, and "not necessarily", otherwise. See "On the Capacity of a Discrete Channel. I", by Saburo Muroga, Journal of the Physical Society of Japan, Vol. 8, No. 4, July - August 1953, pp 484-494.

You might also be interested in my note on Muroga's paper, in which I attempt to provide an alternate proof of the feasibility of the optimal input probability distribution, in the special case of a binary channel, and to correct what I think is a trivial error in Muroga's paper (although this might simply have been Muroga being too polite to point out a trivial mistake by Shannon), and I also try to simplify a part of Muroga's argument:

"On the Computation of the Shannon Capacity of a Discrete Channel with Noise", S. Cowell, arXiv:1701.08731v2 [cs.IT] [here]1


Prove that there always exists a line bisecting each of two point sets

We can prove this using the geometric dual of $P$ and $Q$.

Take the line arrangement of $P^*$ and $Q^*$ in the plane and let us look at the median levels $\Lambda_p$ and $\Lambda_q$. Their intersection is definitely a possible solution because $\Lambda_p$ is the point set describing the dual of all bisecting lines for $P$, and vice-versa for $Q$.

Note the following: Since $|P|$ and $|Q|$ are odd, both median line arrangements have the same slope (and since all slopes are unique by assumption, they must correspond to the same lines) in the beginning and the end of the arrangement. Let us denote $p^*$ and $q^*$ as the respective lines. Then at the beginning (i.e. the largest x-value where no intersections occured yet), one must be above the other and at the end (i.e. the smallest x-value such that no intersections happen from now on forward), they must have switched places.

Since the levels $\Lambda_p$ and $\Lambda_q$ are piecewise continuous (actually even continuously extensible), by the intermediate value theorem they must intersect in at least one point $c^*$, which is the dual of a possible simultaneously bisecting line $c$.


Reduction is not symmetric. Intuitively, if $A$ reduces to $B$, then $B$ is at least as hard as $A$. Just as the usual comparison is not symmetric — for example $3 > 2$ but $2 \not> 3$ — reduction, which is a (partial) order of hardness, isn't symmetric.
For example, SAT reduces to the halting problem, but the halting problem doesn't reduce to SAT.


You made a small mistake by thinking that the Voronoi diagram is a planar graph. Remember that it has those rays that go to infinity. you can make a planar graph out of the Voronoi diagram by adding a new vertex and making all rays incident to this "apex". Plugging this into Euler's formula yields

$$ 2n-4 - e + n = 2 \quad \Rightarrow \quad  e= 3n - 6.$$

A planar graph has $3n-6$ edges if it is a triangulation (this can als be obtained via Euler's formula – just set $3f=2e$). As a consequence the dual graph to your Voronoi diagram (the Delaunay tessellation) is a triangulation. Or phrased differently, every vertex of your Voronoi diagram  has degree~3 and there are three rays.


Concatenation of language to itself zero times

$L^0$ is defined to be $\{\varepsilon\}$. (Since a string formed by concatenating zero strings together is the empty string).

This gives the answer to the first question - which is correct.

Now, $\{\varepsilon\}$ contains exactly one string - which is the empty string. Therefore: $|\{\varepsilon\}|=1$. (The given answer is wrong).

Note that $|\{\varepsilon\}|=1\ne0=|\varepsilon|$. Also, note that $\{\varepsilon\} \ne \emptyset$.


Does 'subexponential algorithm' refer to input or number of bits used to represent input?

It refers to the number of bits to represent N.  More generally, the complexity of a problem is normally taken to be a function of the length of the input (the number of bits needed to represent the input).

Trial division is exponential: its running time is $O(N^{1/2})$, i.e., $O(2^{B/2})$ where $B=\lg N$ is the length of the input in bits.  That's an exponential function (of $B$).  See Are there subexponential-time algorithms for NP-complete problems?.


Is there a formal term for functions that have static state across executions?

Not that I know of, but "stateful function" is reasonably descriptive.  In informal conversation, that's what I'd use, as long as I suspect the audience will understand what I mean.  In formal writing, I might still use the same phrase but also provide a careful definition of what I meant by that phrase.  Really, that's a large part of what "formal" writing is about: it's about being precise about what you mean.


Perhaps the problem is still NP-complete; this reduction should work: given a planar graph $G$ and two nodes $s$ and $t$ (start and end), expand it to a new graph $G'$ in this way: for every node $u$ of $G$ add two nodes $u_1,u_2$ and two edges: $(u,u_1),(u_1,u_2)$ (informally add a tail made with two new nodes).

There are only two ways to traverse the three node gadget with a valid Hamiltonian path (i.e. cover the three nodes):

a) $out \rightarrow u \rightarrow u_2 \rightarrow u_1 \rightarrow out$ and its reverse

b) $out \rightarrow u_1 \rightarrow u_2 \rightarrow u \rightarrow out$

In both cases the node $u$ must be traversed and cannot be reused in another part of the path.

Now, in order to force one of the two traversals in every node, add two tails to $s$: $(s,s_1), (s_1,s_2)$ and $(s,s_3), (s_3,s_4)$ and pick as starting node of $G'$ the node $s_1$. The only way to traverse and leave $s$ is $s_1 \rightarrow s_2 \rightarrow s \rightarrow s4 \rightarrow s3 \rightarrow out$. This forces traversal (a) on all remaining nodes (gadgets) of $G'$. Pick $t_2$ as the ending node in $G'$.

So the original graph $G$ has an Hamiltonian path from $s$ to $t$ if and only if $G'$ has a "modified" (one node jumps allowed) Hamiltonian path from $s_2$ to $t_2$.

EDIT:

If $deg(v_i) \leq 4$ the above reduction still works because Hamiltonian path is NP-complete even in planar cubic graphs. In a planr cubic graph $deg(v_i) = 3$, so nodes can be extended with the tails as described above. If the starting node has degree 3, just add another node $s'$, an edge $(s,s')$ and add two tails to $s'$.
But, if $deg(v_i) \leq 3$ then the problem falls in $\mathsf{P}$, the following algorithm should work (but I didn't think about it too much):

calculate the shortest path from $s$ to $t$: $s \rightarrow u_1 \rightarrow ... \rightarrow u_m \rightarrow t$, then expand the path using a depth first search from every node; this will lead to a spanning tree having the shortest path as a "backbone". For each $u_i$ of the shortest path there is only one branch $u_i,b_1,b_2,...,b_k$(because the degree of $v_i$ is $\leq 3$) and it can be covered using jumps:

$u_i > b_2 > b_4 > ... > b_k > b_{k-1} > ... > b_3 > b_1 > u_{i+1}$ if $k$ is even
$u_i > b_2 > b_4 > ... > b_{k-1} > b_k > b_{k-2}... > b_3 > b_1 > u_{i+1}$ if $k$ is odd

The only problem is if $s$ and/or $t$ have degree 3. In that case the above procedure must be repeated several times using only one incident edge of $s$ (and eventually only one incident edge of $t$).

In order to formally prove that the algorithm is correct one must prove that every Hamiltonian path (with jumps) from $s$ to $t$ in a $deg(v_i) \leq 3, deg(s)=1, deg(t)=1$ graph can be transformed to an Hamiltonian path (with jumps) of the above form (a spanning tree from the shortest path). It is not immediate but it seems intuitive (but perhaps I'm just wandering :).


Computing losing positions in modified Wythoff's game efficiently

There is no closed form for $n=3$ piles. But one can solve the question efficiently using dynamic programming.


Complexity of / best algorithm for finding the dichotomy that maximizes information gain?

The information gain in that case depends only on the mass of $A$, and is maximized when $P(A)=\frac{1}{2}$. This probably shows why this definition of information gain is not very interesting.

Suppose $X=\left\{x_1,...,x_n\right\}$ and $P=\left(p_1,...,p_n\right)$.

The information gain is defined as

$IG(A)=H(X)-\left(P(A)H(A)+\left(1-P(A)\right)H\left(X\setminus A\right)\right)$

Where $H(A)$ is the entropy of the random variable which takes values in $A$ with probabilities $q_x = \mathbb{1}_{x\in A}\frac{p_x}{p(A)}$.

Now lets write explicitly what is $IG(A)$:

$$\begin{align*}
IG(A)&=
H(X)+P(A)\sum\limits_{x\in A} \frac{p_x}{P(A)}\log \frac{p_x}{P(A)}+
\left(1-P(A)\right)\sum\limits_{x\in X\setminus A} \frac{p_x}{1-P(A)}\log\frac{p_x}{1-P(A)} \\ &=
H(x)+\sum\limits_{x\in A} p_x\log \frac{p_x}{P(A)}+
\sum\limits_{x\in X\setminus A} p_x\log\frac{p_x}{1-P(A)} \\ &=
H(A)+\sum\limits_{x\in A} p_x\log p_x -\sum\limits_{x\in A} p_x \log P(A) +
\sum\limits_{x\in X\setminus A}p_x\log p_x - \sum\limits_{x\in X\setminus A}p_x\log \left(1-P(A)\right) \\ &=
-P(A)\log P(A) - \left(1- P(A)\right)\log(1-P(A)).
\end{align*}$$

So setting $y=P(A)$, you seek to maximize $f(y)=-y\log y-(1-y)\log(1-y)$ in $y\in[0,1]$. Maximum is achieved at $y=\frac{1}{2}$.

The optimization problem (or corresponding decision problem) is NP-hard, meaning that unless $P=NP$, you can't find a subset $A$ which minimizes $\left| P(A)-\frac{1}{2}\right|$ in polynomial time. This problem is called the partition problem (special case of subset sum), only that now you have the constraint that the elements sum to 1. See this question for some information about the hardness of partition problem.


A Query regarding Quadratic Residuocity Problem

It can be solved in randomized polynomial time, so it's not NP-complete (unless RP=NP, which is considered unlikely).

If $n=p_1p_2p_3$ is composite, where $p_1,p_2,p_3$ are three distinct prime factors, and $p_1,p_2,p_3$ are given, then the problem can be solved in polynomial time.  In particular, in this case, there are only 8 square roots of $q$ (modulo $n$), and you can enumerate them all and check whether any of them are in the range $[0,c)$.

Details and justification: you can use the Chinese remainder theorem.  Let $x_1$ be one of the two square roots of $q$ modulo $p_1$, i.e., it satisfies $x_1^2 \equiv q \pmod{p_1}$.  (Then the other square root is $-x_1$.)  Similarly, let $x_2$ be a square root modulo $p_2$ and $x_3$ a square root modulo $p_3$.  Then you can find a square root modulo $n$ by using the Chinese remainder theorem to find the unique solution to $x \equiv x_1 \pmod{p_1}$, $x \equiv x_2 \pmod{p_2}$, $x \equiv x_3 \pmod{p_3}$.  In general, you can look for $x$ to be $x_1$ or $-x_1$ mod $p_1$, and $x_2$ or $-x_2$ mod $p_2$, and $x_3$ or $-x_3$ mod $p_3$; each of those $2 \times 2 \times 2 = 8$ combinations gives a different square root of $q$ modulo $n$.  You can find $x_1,x_2,x_3$ in randomized polynomial time, and the CRT computation can be done in polynomial time, so you can enumerate all square roots modulo $n$ in polynomial time.

This same argument generalizes to any case where the number of prime factors of $n$ is constant, and where those prime factors are given in advance.  However, when the number of prime factors is unlimited, this line of argument doesn't work, so this won't work for general $n$.


Reduce ATM to the language of TM encodings where if the TM accepts w then the TM accepts ww

First of all, assume the TM $S$ receives a (correctly encoded) instance $\langle M, w \rangle$ of $A_{\text{TM}}$. $N = N_{M,w}$ must be constructed in terms of $M$ and $w$, that is, its description depends on the problem instance $\langle M, w \rangle$. (It is sloppy to just describe $N$ without having fixed this instance first.)

Your overall proof structure is correct, only you made a couple of mistakes in the constructions of $N = N_{M,w}$ and $S$. Instead you should have for $N$:

  On input $x$:

  If $x$ is of the form $w'w'$ for some $w' \in \{0,1\}^\ast$, reject;
  Otherwise, simulate $M$ on input $w$ and do what $M$ does.

Why this? Consider the following:
$$\begin{align*}
\langle N \rangle \in L
&\iff \forall w' \in \{0,1\}^\ast: (w' \in L(N) \implies w'w' \in L(N)) \\
&\iff \forall w' \in \{0,1\}^\ast: w' \not\in L(N) \lor w'w' \in L(N) \\
&\iff \forall w' \in \{0,1\}^\ast: w' \not\in L(N) \\
&\iff \not \exists w' \in \{0,1\}^\ast: w' \in L(N) \\
&\iff \lnot (\text{$M$ accepts input $w$})
\end{align*}$$

The third equivalence is the reason behind constructing $N$ so as to reject inputs of the form $w'w'$. The last equivalence holds because not all strings are of the form $w'w'$ for some $w' \in \{0,1\}^\ast$.

To complete the construction of $S$, have it feed $\langle N \rangle$ to $R$ and accept if $R$ rejects and reject otherwise (i.e., $S$ returns the opposite of what $R$ returns). By the equivalences above, $S$ reduces $A_{\text{TM}}$ to $L$, so $L$ must be undecidable.

As to your more general question regarding reductions: Unfortunately, I am afraid these kind of problems are rather tricky in of themselves. (I suppose that, at the core of it, the problem is that we are dealing with paradoxes, which are, of course, very nasty little things.) Nevertheless, Rice's theorem generalizes a great deal of these questions and makes it much simpler to prove something reduces to $A_{\text{TM}}$ or the halting problem.


Calculating DFT of a specific polynomial

You haven't explained what you mean by the DFT of a polynomial, so I'm assuming you mean the polynomial evaluated at all $n$th roots of unity, that is,
$$ v_i = P(\omega^i), $$
where $\omega = e^{2\pi i/n}$ is a primitive $n$th root of unity. Let now $Q(x) = P(x^2)$, and let $\varpi = e^{\pi i/n}$ be a primitive $2n$th root of unity, $\varpi^2 = \omega$. Let us examine its DFT $w_1,\ldots,w_{2n}$:
$$
w_k = Q(\varpi^k) = P(\varpi^{2k}) = P(\omega^k) = v_{k \mod{n}}.
$$
We conclude that the DFT of $Q$ is
$$ v_1,\ldots,v_n,v_1,\ldots,v_n. $$


The order of dimensions usually depends on the library you are using
Tensorflow : (Height,Width,Channel) : HWC
PyTorch: (Channel,Height,Width) : CHW
In your case the image seems to go with CHW , since you cant apply 5x5 filters on a 1x128 image
As for the final shape , we follow the rule :
for input length N, and k-size filter , output-length = N-k+1
so each of the 10 filters produces output length = 28-5+1 = 24
so output length = (10,24,24) in the CHW format
Here is a simple Tensorflow code to test it if you want :
from tensorflow.keras.layers import Input,Conv2D
x = Input(shape=(28,28,1))
x = Conv2D(filters = 10, kernel_size = 5, padding='valid')(x)
print(x.shape)


How did each class of languages receive their name?

Regular Languages:

There's some good discussion of this here: https://ell.stackexchange.com/questions/83917/how-did-regex-get-its-name

Context-Free vs Context-Sensitive Grammars:

For CFGs and CSGs, the "context" part is the idea that certain rules can be extended  to apply based on relative positions of symbols rather than on single specific symbols.

Context-free grammars have substitutions that only allow you to replace single non-terminal characters at a time and does not consider the symbols around it. Since the context of where in a string the symbol occurs does not matter, we call the rule context-free.

Examples:

$S \rightarrow foo$ is a context-free rule
$aSb \rightarrow a foo b$ is not context-free due to it only contextually applying when $S$ is surrounded by both an $a$ on the left and $b$ on the right. It is instead, context-sensitive.

Context-sensitive grammars allow you to construct rules that operate on these situations where the relative locations of symbols matter. Since the rules can be specific respective to relative positions of terminal and non-terminal symbols, the rules are said to be context-sensitive.

Recursively Enumerable:

A set (language) is recursive if a Turing machine can tell you if a particular element is a member of that set or not in finite time. The name comes from a field called recursion theory, where recursion is a mathematically formal way to derive what computability is.

For example, the set of even binary numbers ($2\mathbb{Z}$) is a recursive set because I can take any number and test whether or not it is even in finite time on a Turing machine.

A set (language) is recursively enumerable if a Turing machine can enumerate over all the elements of that set. If an element you are testing for is in the set, you will eventually encounter it while enumerating through elements of the set. However, since the set can be infinitely large, you potentially will never be able to look at them all. If your element you are searching for is not actually in the set, you will neither be able to encounter it or know for certain that it is not in there.

Recursive languages are not part of the Chomsky hierarchy because the hierarchy is specific to grammars. It is not known if there is a natural grammar that captures recursive languages. See Decidable languages and unrestricted grammars?

Side Note: Typically we say that Turing machines recognize languages (not construct).


Possibility of using loops instead of traps

Your first DFA is minimal. To see this, for each pair of states $q_i \neq q_j$ we need to come up with a word $w$ such that $\delta(q_i,w) \in F$ and $\delta(q_j,w) \notin F$, or vice versa, where $F$ is the set of accepting states.
Here is such a list of words:

$q_0,q_1$: $\delta(q_0,b) \notin F$ and $\delta(q_1,b) \in F$.
$q_0,q_2$: $\delta(q_0,\epsilon) \notin F$ and $\delta(q_2,\epsilon) \in F$.
$q_0,q_3$: $\delta(q_0,ab) \in F$ and $\delta(q_3,ab) \notin F$.
$q_1,q_2$: $\delta(q_1,\epsilon) \notin F$ and $\delta(q_2,\epsilon) \in F$.
$q_1,q_3$: $\delta(q_1,b) \in F$ and $\delta(q_3,b) \notin F$.
$q_2,q_3$: $\delta(q_2,\epsilon) \in F$ and $\delta(q_3,\epsilon) \notin F$.


Minimize Manhattan distance travel algorithm

You could always try the A* algorithm.  It might not be optimal but it is something you could try, and depending on how big the matrix is it might be good enough.  You'll need to design an appropriate heuristic (e.g., maybe the number of elements that are non-zero, divided by two?).


Given a randomised algorithm for a problem, is there a corresponding deterministic algorithm?

If the running time of the algorithm is bounded, in the sense that for every input $x$ there is a number $T(x)$ such that whatever the coin tosses are, the algorithm always terminates within $T(x)$ steps, then you can always "try all possibilities" and convert your randomized algorithm to a deterministic one, albeit with a possibly much larger running time.

For polynomial time algorithms in particular, it is conjectured that you can derandomize any algorithm with at most a polynomial blow-up in time, a conjecture usually stated as $\mathsf{P}=\mathsf{BPP}$.


Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguities

Intuitively, the reason the claim is true is that if a grammar $G$ had only finitely many ambiguous strings, then you could somehow resolve the ambiguity and come up with an equivalent unambiguous grammar $G'$, thus contradicting the inherent ambiguity. The way you would resolve the ambiguity is something like this: you would generate all small strings (say at most $\ell$, the length of the maximal ambiguous word in $G$) explicitly (and unambiguously), and modify the grammar so that all other strings that it generates are longer; for example, you could have a different subgrammar for every prefix of length $\ell+1$ which simulates $G$.

Of course, this is only one argument, there might be completely different ones.


Prove correctness of this (context-free) grammar

Now how can you justify the correctness of this grammar?

In order to prove that some grammar $G$ generates a language $L$, i.e. $L= L(G)$, you need to prove two things:

for any string $w \in L$, $G$ yields/generates $w$, i.e., $S \Rightarrow^* w  $, and
for any string $w$ (consisiting of only terminal symbols), if $G$ yields/generates $w$, then $w \in L$

In your particular example, you first need to prove that if $w$ has twice as many $a$s than $b$s then your grammar $G$ yields $w$, and if $G$ yields some string $w$ then $w$ has twice as many $a$s than $b$s. Induction on the length of $w$ or the number of steps of application of derivation rule might be helpful.

This is our reference question which may be helpful to prove that a language is context free.


Is closed form of summation less costly?

I cannot imagine there exists an internal representation of multiplication on any machine that does not involve repeated addition.

Try being more imaginative.  I'm pretty sure that you were taught at school how to calculate, say, $38\times 144$ without adding $144$ thirty-seven times.


Changing Rabin-Karp without modulo to Rabin-Karp with modulo

Don't wait to do the modular reduction at the end.  Every time you do an addition or multiplication, immediately reduce modulo the modulus.  This keeps all intermediate results small.


DFA, lower bound on number of states, language with primes and remainders

For a binary string $x$, let $N(x)$ be the value of the number when read LSB first. Then $N(xy) = N(x) + 2^{|x|} N(y)$.

Now consider any $P \subseteq \mathbb{Z}_p$. For any $x$, $N(xy) \bmod p \in P$ iff $N(x) + 2^{|x|} N(y) \bmod p \in P$. This condition depends only on $N(x) \bmod p$ and $2^{|x|} \bmod p$, i.e. on $N(x) \bmod p$ and $|x| \bmod \operatorname{ord}_p(2)$ (here $\operatorname{ord}_p(2)$ is the smallest exponent such that $2^o \equiv 1 \pmod{p}$).

As $x$ goes over all binary strings, $(N(x) \bmod{p}, |x| \bmod\operatorname{ord}_p(2))$ goes over all possible $p \cdot \operatorname{ord}_p(2)$ values. One way to see this is to take zero paddings of strings representing $0,\ldots,p-1$.

Let us now consider the particular $P$ stated in the question. Since $p \geq 5$, $2^2 \not\equiv 1 \pmod{p}$, and so to prove the claim, it suffices to show that the equivalence classes $\{(a,1),(a,2) : a \in \mathbb{Z}_p\}$ are all different.

Consider any two equivalence classes $(a_1,b_1),(a_2,b_2)$. If exactly one of $a_1,a_2$ is in $P$, then there is nothing to do. Suppose first that $a_1,a_2 \in \{1,\ldots,\frac{p-1}{2}\}$. If $b_1 = b_2$ then $a_1 \neq a_2$. Without loss of generality, $a_1 < a_2$. Therefore we can find $n$ such that $a_1 + nb_1 = \frac{p-1}{2}$ while $a_2 + nb_2 \notin P$. If $b_1 = 1$ and $b_2 = 2$ then there is a range of $\frac{p-1}{2}$ consecutive values of $n$ such that $a_1 + nb_1$ goes over all of $1,\ldots,\frac{p-1}{2}$. For the same values of $n$, the expression $a_2 + nb_2$ goes over $\frac{p-1}{2}$ values in jumps of $2$; it is not hard to check that not all of them can belong to $P$.

We leave the case $a_1,a_2 \notin P$ to the reader.


The solution which I provide below is very similar to Example 2.37 in classical Sipser's book "Introduction to the theory of computation"

  Let $p,r>0$ be the pumping length given by the lemma.

I think you have a little abuse of notation. Look carefully at definition. It states that if $L$ is $CFL$ then, there exists some constant $p$ (pumping length) that for every string $s \in L$ such that $|s| \ge p$, $s$ can be divided on five parts such that the following properites hold:

  $|vx|≥1$ $|vwx|≤n$ and for every $i≥0, uv^iwx^iy∈L$

So, let us take $s = a^nb^nc^{2n}$, where $n+n+2n > p$. Then the conditions for lemma are hold, and it follows that $s = uvwxy$ with all those properties. From the first property we get that at least one of $v$ or $x$ is non-empty string. Now, we should consider several cases:

1) At least one of $v$ or $x$ contains diffent letters of the alphabet (for example, $v$ = $zabt$, $|z|, |t| \ge 0$). Then $uv^2wx^2y$ doesn't has the form $a^nb^nc^m$ (problems with order, in my example $v^2 = zabtzabt$), so we get a contradiction.

2) Either $v$ or $x$ contains only one letter from alphabet. Here we get such cases:

2.1) $v$ and $x$ don't contain the letter $c$. By lemma the string $s_1 = uv^0wx^0y \in L$. But $s_1$ has less than $n$ letters $a$ or $b$, while it contains $2n$ letters $c$. So, the property $m \le 2n$ doesn't hold in this case and we get a contradiction.

2.2) $v$ or $x$ contain the letter $c$, so either $a$ or $b$ doesn't belong to $v$ and $x$. Then string $s_1 = uv^2wx^2y$ contains at least $2n + 1$ $c$'s, and only $n$ $a$'s or $b$'s. Again, we get a contradiction.


CSL is the same as $\mathsf{NSpace}(n)$ (non-deterministic linear space). Any language which is outside $\mathsf{NSpace}(n)$ is not CSL.

To get a feeling of the situation, remember that $SAT \in \mathsf{NSpace}(n)$ and even TQBF.

  What others problems exists that are decidable but yet non-context-sensitive?

The are many problems. Any problem that is complete for a complexity class larger than $\mathsf{PSpace}$ will do (we need $\mathsf{PSpace}$ because problems like TQBF in $\mathsf{NSpace}(n)$ that are complete for $\mathsf{PSpace}$ because a (polynomial time) reduction can blow up the size of an input by a polynomial). Giving an example will mean proving a lowerbound for the complexity class containing the problem and that is very very difficult task. The only major way we know so far to do this is diagonalization which intuitively means that the larger class should be able to simulate the smaller class.

So $\mathsf{ExpSpace\text{-}hard}$ seems a natural place to start to look for natural examples of language which are not CSL.

  Is this class of problems the same as decidable EXPSPACE-hard?

No. By the space hierarchy theorem, there are languages which are in $\mathsf{NSpace}(n^2)$ which are not in $\mathsf{NSpace}(n)$. If you are asking for nice examples, that is going to be difficult because the theorem works using diagonalization and therefore the language it proves to satisfy these conditions is very artificial.

I suggest that you ask a separate question for a natural problem that separates $\mathsf{NSpace}(n^2)$ from $\mathsf{NSpace}(n)$.


Sort binary matrix by swapping columns to make subrectangle of ones with maximum size

Yes, you can solve it faster than trying all possible permutations.

The biggest such rectangle must span consecutive rows.  So, for all $i,j$ with $i \le j$, check what is the biggest rectangle you can make that spans rows $i..j$.  You can do this check in $O(mn)$ time, by checking which columns have a 1 in all of those rows.  There are only $O(m^2)$ possible values of $i,j$.

So, the running time of this simple method is $O(m^3 n)$, which is faster than trying all permutations.  (Trying all permutations would take $\Omega(m \cdot n!)$ time, which is far slower -- it is exponential time, rather than polynomial time.)  I make no claim that this simple method is optimal -- rather, I merely claim that the answer to your question is "yes".


Why is Byzantine Generals Problem with traitors possible?

Quoting from the abstract of the original paper introducing the Byzantine Generals problem (with my emphasis):

  The problem is to find an algorithm to ensure that the loyal
  generals will reach agreement.

If you read further in the paper, they reduce the problem to agreeing on a single bit: "Attack" or "Retreat". The question is can the loyal generals reach consensus amongst themselves when they don't know who the traitors are.

So for your proposed scenario, as far as the Byzantine Generals problem is concerned, the only question is whether all the loyal generals can agree on the plan, not whether the plan is workable. At any rate, "all attack" either means "all [loyal generals] attack" which is essentially what would be produced by a Byzantine fault-tolerance algorithm, or it means "all [generals, loyal and traitorous alike,] attack" which would simply be silly. In this thought experiment the generals know that there are potentially traitors so they would presumably not propose a plan that only works if there are no traitors. What is actually being agreed upon, e.g. the "goal", is outside the scope of the Byzantine fault-tolerance algorithm, of course. The algorithm doesn't care whether the question is "should we attack or retreat?" or "should we choose pink or chartreuse for the new standard?"


Finding largest subset that matches moments

I tried formulating this as an integer linear program, but ran into problems, because the variance is not a linear function: it is quadratic.

Here was my attempt.

Introduce variables $x_b$ (one for each $b \in B$), such that $x_b=1$ if $b \in C$ and $x_b=0$ if $b \notin C$.  Thus, we have $|B|$ new zero-or-one variables.  We can force them to be zero or one by adding the constraints $0 \le x_b \le 1$ for each $b \in B$.

Next, we'll force the mean of $C$ to be in the accepted range.  Introduce a new unknown $\mu$ and add the constraint

$$\mu = (\sum_{b \in B} x_b b)/|B|.$$

This forces $\mu$ to be the mean of $C$.  Also, it is expressible in a linear equation, since everything except for $\mu$ and the $x$'s are constants.  Finally, add the two linear inequalities

$$\text{mean}(A)-\delta \le \mu \le \text{mean}(A)+\delta.$$

But it's not clear how to force the standard deviation of $C$ to be in the accepted range.  Let $\sigma = \text{std}(C)$, i.e., $\sigma$ denotes the standard deviation of $C$.  We could try to use the fact that

$$\sigma^2 =  \frac{1}{N} \sum_{c \in C} c^2 - \frac{1}{N^2} \left( \sum_{c \in C} c \right)^2,$$

but now when we substitute in with our definitions of $x_b$, we get something ugly:

$$\sigma^2 =  \frac{1}{N} \sum_{b \in B} b^2 x_b - \frac{1}{N^2} \left( \sum_{b \in B} b x_b \right)^2,$$

where the right-hand term has something quadratic.  Worse still, $N$ also depends upon the $x$'s, which takes this even further away from something linear:

$$S = \sum_{b \in B} x_b.$$

Alternatively, we could try to use the fact that

$$\sigma^2 = \frac{1}{N} \sum_{c \in C} (c - \mu)^2,$$

but when we substitute in, again we get something that's not linear:

$$\sigma^2 = \frac{1}{N} \sum_{b \in B} x_b (b - \mu)^2,$$

where the non-linearity comes from the fact that $N$ is itself a function of the $b$'s, as well as the fact that the right-hand side involves a product of two linear variables ($x_b$ and $\mu$).

We want

$$\text{std}(A) - \epsilon \le \sigma^2 \le \text{std}(A) + \epsilon.$$

Plugging in, we find that we need

$$(\text{std}(A) - \epsilon)N \le \sum_{b \in B} x_b (b - \mu)^2 \le (\text{std}(A) + \epsilon)N.$$

This is not linear, because $x_b (b - \mu)^2$ is not a linear function of $x_b,\mu$.

We could deal with the fact that $N$ is not a constant by enumerating all candidate values of $N$ and solving an ILP for each.  However, that still doesn't deal with the problem that $x_b (b - \mu)^2$ is non-linear.

So, I'm stuck.  I wasn't able to formulate this cleanly as an ILP.


NP-Hard problems that are not in NP but decidable

By the nondeterministic version of the time-hierarchy theorem, we have $\mathsf{NP} \subsetneq \mathsf{NEXP}$, where $\mathsf{NEXP}$ is the class of problems solvable in non-deterministic exponential-time. Thus it suffices to consider any problem which is $\mathsf{NP}$-hard and in $\mathsf{NEXP}$, but not in $\mathsf{NP}$. For instance, we may consider any $\mathsf{NEXP}$-complete problem, such as

3-colourability of graphs described by succinct circuits — or any other NP-complete problem on graphs — where a "succinct circuit" is a format for representing very large graphs at the input: instead of explicit representation of a graph e.g. by adjacency lists, we instead provide a circuit computing some function $f: \{0,1\}^{n} \times \{0,1\}^n \to \{0,1\}$ which computes the coefficients of a $2^n \times 2^n$ adjacency matrix.
(Non-)equivalence of two regular expressions, where the Kleene star is replaced by squaring (repeating a sub-pattern exactly twice, rather than zero or more times), and where we ask whether two such regular expressions represent different sets of strings.

Note that in the latter case, if we take regular expressions as we are used to considering, including the Kleene star, the resulting problem is $\mathsf{EXPSPACE}$-complete: because we have the containments $\mathsf{NP} \subset \mathsf{NEXP} \subseteq \mathsf{EXPSPACE}$, this is still a decidable problem which is $\mathsf{NP}$-hard, and not in $\mathsf{NP}$.


Your problem can't be any easier than DNF-TAUTOLOGIES since that problem is produced by setting $k$ equal to $2^n$.  Therefore your problem is NP-hard, just as DNF-TAUTOLOGIES is.


What is the need for "some constant" times $n$?

What is the running time of an algorithm? To answer this question, we need to specify an exact computation model with a cost for each operation. Whatever computation model you choose to use, it is highly unlikely that the running time of an algorithm on an input of size $n$ is exactly $n$. It is far more likely to be of the form $an+b$ for some constants $a,b$, and even more likely to vary a bit with the exact input, but to be bounded by some expression such as $an+b$.
As an example, consider the following algorithm for computing the maximum of an array $A[1],\ldots,A[n]$:
max = A[1]
for i = 2, ..., n:
  if A[i] > max:
    max = A[i]
return max

Let us convert it into "machine instructions":
      max = A[1]                 (1)
      i = 2                      (2)
LOOP: if i>n, jump END           (3)
      if A[i]≤max, jump CONT     (4)
      max = A[i]                 (5)
CONT: i = i + 1                  (6)
      jump LOOP                  (7)
END:  return max                 (8)

Let's assume that each line costs $1$ time unit (this is a quite arbitrary assumption). How much time does the algorithm take on an input $A$ of length $n \geq 1$?
Lines $1,2,8$ run once. Line $3$ runs $n$ times each. Lines $4,6,7$ run $n-1$ times each. Line $5$ runs once per "left-to-right record" of $A$ beyond $A[1]$, which can be any number of times between $0$ and $n-1$. In total, the running time is between $3+n+3(n-1)$ to $3+n+4(n-1)$, that is, between $4n$ and $5n-1$.
If we choose a different cost model, we will likely get a different running time. However, this running time will likely still be $O(n)$. This is why big O notation is so useful – it hides such details.


Are dictionaries and associative arrays the same thing?

As far as I can tell, associative array is a newer term, maybe emerging from popular use in dynamic programming languages. In algorithms as an academic field, it seems to denote a generalisation of the dictionary but one usually works with dictionaries (probably because most resource characteristics carry over so one does not need to complicate notation).

Citing from theory-leaning [1, p281] (bold emphasis mine):

  The dictionary, symbol table, or simply search problem is a fundamental one in computer science: a set of distinct keys is to be organized so that client queries whether or not a given key is in the set can be efficiently answered.
  More generally, with distinct keys, we can use binary search trees to implement an associative array, where we associate information with each key and can use the kry to store or retrieve such information.

CLRS [2, p229] make no mention of associative arrays but define dictionaries:

  We call a dynamic set that supports [insertion, deletion and membership test] a dictionary.

In the more practically inclined [3, p361 ff], the term symbol table is used as a synonym for dictionary but defined in a slightly different way:

  A symbol table is a data structure for key-value pairs that supports two operations: insert (put) a new pair into the table and search for (get) the value associated with a given key.

Later, they write:

  [The conventions "no duplicate keys" and "put on an existing key replaces the old value"] define the associative array abstraction, where you can think of a symbol table as being just like an array, where keys are indices and values are array entries.

Summarising this small literature research (which is not without contradictions) and from a theoretical viewpoint, I'd state the following:

A dictionary is a data structure that implements a (dynamic) set with insertion, deletion and membership test.

Mathematically speaking, a dictionary over universe $X$ represents an element of the power set $2^X$ of $X$.
An associative array is a data structure that implements a (dynamic) mapping with insertion/update, deletion and retrieval.

Mathematically speaking, an associative array over key universe $X$ and value universe $Y$ represents an element of the set of functions $X \to Y$.

One can thus view a dictionary over universe $X$ as associative array over $(X,\{0,1\})$; this closely resembles the indicator function of sets.

I think this fits programmers' reality quite well, but terms may be used differently over there.

Important: The usage of the term "array" may suggest $O(1)$ accesses. This can, in general, not be expected to be true; at least not in the worst-case and without amortisation arguments. Implementations using hash tables come closest; see here for a discussion about what to expect w.r.t. performance.

An Introduction to the Analysis of Algorithms by R. Sedgewick and P. Flajolet (2nd ed, 2013)
Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (3rd ed, 2009)
Algorithms by R. Sedgewick and K. Wayne (4th ed, 2011)


Calculating the kth largest distance among $n$ points on a number line in $O(n\log n)$?

Given some pivot $K$, you can count the pairs with differences above it in $O(n)$, whether you use a random pivot or binary search.

The pairs form a kind of uneven grid in the plane, and you can search diagonally along the line $y = K+x$ to find the border between $x_j - x_i \le K$ and $x_j - x_i \gt K$ in $O(n)$ as follows (Bresenham's Line Drawing Algorithm):

Start at the y axis and find minimum $j$ so that $x_j - x_0 > K$
$Count = n-j+1$
For $i = 1$ to $n-1$ do

While $x_j - x_i < K$, $j = j+1$

If $j=n$ break

$Count = Count + n - j + 1$

(There are some adjustments for when K is larger than the range, but the main idea is here.)

Basically you move right and then slide $j$ up until you cross the line, then add all the entries above that point to the count. As you continue right you're always at or above the $j$ you used in the previous column, so you do $O(n)$ pair tests for the whole scan.


Meaning of complexity of a computational problem

You are missing one thing, namely that the optimal algorithm and worst instance are not simply functions of the instance size. Also, I am not sure that minimising/maximising algorithm and instance independently of each other is doing the right thing.

The complexity of a problem is the complexity of an optimal algorithm solving the problem in the chosen machine model. It's as simple as that, but of course we have to define what "optimal algorithm solving the problem" means. Note that we have to fix the machine model (in particular what to count, see below), as complexities can differ between models.

First, "solving the problem" is clear: for all inputs (that are instances of the problem), the algorithm should give the correct answer, i.e. terminate and produce the correct result, or don't terminate. Let's denote the set of all algorithms that solve problem $P$ with $\newcommand{\Alg}[1]{\mathsf{Alg}_{#1}}\Alg{P}$.

Second, what is the "complexity" of an algorithm? There are many ways to investigate runtime; complexity theory has defaulted to worst-case time and Landau classes. Formally, we define the (worst-case) runtime function of some algorithm $A$ to be

$\qquad \displaystyle T_A(n) = \max \{ T_A(x) \mid x \in I_P, |x|= n \}$

where $I_P$ is the set of instances of the problem $P$ (which $A$ solves) and $T_A(x)$¹ is the runtime of $A$ on input $x$² (in clock cycles, state transitions, whatever fits your machine model). Now, the complexity of $A$ is the asymptotic growth of $T_A$. For example, if $T_A(n) = 17n^2 - 5n + 13$, we would say "The complexity of $A$ is $\Theta(n^2)$".

Finally, an optimal algorithm (for $P$) is an algorithm with minimal complexity (among all algorithms in $\Alg{P}$)³.

We abuse notation here: depending on its parameter, $T_A$ means different things. It is usually done this way, though, and we don't need the runtime on individual inputs later on.
Let's assume for the moment that we deal only with deterministic algorithms. Otherwise, there may be many different runtimes for a given input. In that case, we would choose the runtime of the longest computation; see here for reasons why.
Note that Landau-$O$ implies a partial order on functions: $f \leq g \iff \exists c \in \mathbb{N}.\,\limsup\limits_{n \to \infty} \frac{f(n)}{g(n)} \leq c$.


How to choose between UC and PL when using the DPLL algorithm?

If you use the original specification of the DPLL algorithm, in which the unit rule is applied to a fixed point and then the pure literal rule, then only the unit rule is needed to reach a satisfying assignment.  If the rule order is reversed then the pure literal rule is used to eliminate the final unsatisfied clause.

DPLL is a complete and sound algorithm for deciding Boolean satisfiability even if the pure literal rule is removed.  In practice, pure literals are typically removed only during the preprocessing of a SAT instance, where the formula is simplified as much as possible before beginning recursive search.  This is because detecting pure literals during search is computationally expensive enough to more than offset any expected runtime gains.


Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods

If you want to find the optimal combination, one approach would be to use dynamic programming.  Let $f(n,s)$ denote the length of compressing the first $n$ characters via some combination of compression methods, ending with the compression subsystem in state $s$.  Here $s$ represents both which compression method is currently being used (Ascii or C40) as well as its internal state (i.e., whether you are currently in set 0, set 1, set 2, or set 3).

Then you can compute $f$ recursively.  Applying memoization, we get a dynamic programming algorithm to compute $f$.  The resulting algorithm will take $O(n)$ time to compute the best compression.

How do you compute $f$ recursively?  Basically, when computing $f(n,s)$, you consider both possible cases for how to encode the $n$th character:

Case 1: Stick with the same compression method and state you had before, when encoding the $n$th character.  The cost of doing so is $f(n-1,s) +$ the number of bits to encode the $n$th character when in state $s$.
Case 2: Switch compression methods and/or state just before encoding the $n$th character.  The cost of doing this is $f(n-1,s') + $ the number of bits to switch from state $s'$ to state $s$ and then encode the $n$th character while in state $s$.

You should choose whichever of those provides a shorter encoding.  In other words, $f(n,s)$ is the smaller of these two quantities.  This gives a recursive algorithm for computing $f$, which can be memoized, yielding a solution that is essentially dynamic programming.

Since there are only 8 possible states (2 compression methods $\times$ 4 choices of the character set), the running time to compute $f(n,s)$ is $O(n)$.  This gives you a linear-time algorithm to find the best combination of compression algorithms for encoding any given string.


Is the kernel loaded into memory for every user simultaneously using a Multi-User O.S. system?

The shell (or window manager) which provides a visual interface is not part of the kernel. It's a simple user process and it runs in userspace without elevated privileges. In order for the user to "log in", which involves associating their terminal with the shell (or window manager), a login manager is needed. This program does run with elevated privileges, but it is also not part of the kernel. And there is only one instance of it.
Almost all user processes interact at some point with the kernel, usually by triggering a software interrupt which is caught by the kernel and triggers some kind of kernel request handler. There is only one copy of the executable image which contains kernel functions, but each handler needs to run independently and normally requires some transient storage. This would most naturally be stored on a stack, as with the transient storage for any ordinary procedure. However the "kernel stack" for a process is provided, it will by unique to the process. But it's usually not very big at all.


Does quantum computing convert any O(2^n) algorithm into a polynomial running time and how?

No it does not. I mean probably. Because no-one really knows.

What do I mean by we don't know? We're not even 100 % sure whether P=NP or not and if it does, sure a quantum computer can solve any NP problem in polynomial time, same as a deterministic Turing machine.

However we assume that is not the case and we also expect the classes of NP and BQP (bounded-error quantum polynomial-time) to overlap, but each may contain problems the other one does not (i.e. neither contains the other). If NP contains something BQP does not, it surely has to be at least all NP-complete problems, including the TSP you mentioned in one of your comments. With these assumptions quantum computer cannot solve TSP in polynomial time (even with a given probability).

What we do have right now is Grover's algorithm, which provides quadratic speedup for black-box problems. Which means if the best we can come up with is brute force in $O(2^n)$ steps, Grover can solve it in $O(2^{(n/2)})=O(\sqrt{2}^n)$ steps with a given probability. That is it gives a quadratic speed-up, not exponential.


Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative?

Mostly for convenience's sake.  Since big-theta notation specifically tends to be used mostly for algorithmics (as opposed to $O()$ and especially $o()$, which make occasional appearances in more 'traditional' mathematics for talking about goodness of estimates) and is generally used to measure 'usage' quantities of some sort (e.g. CPU cycles, memory, comparisons, etc) there's generally little lost by requiring the quantities involved to be non-negative, and it simplifies some of the definitions and results.

Note that unlike with $\Theta()$, the definitions of $O()$ and $o()$ are often phrased in terms of absolute value, making this point moot - can you see why that idea doesn't make sense for $\Theta()$?


The role of depth of a circuit in its hardware implementation

In the zeroth order sense, it is correct that the logic depth and the time to execute the logic would be the same.  There are nuances to this because you need to do something with the result.

What logic is a medium to do work.  In the simplest sense, you have a bounded function with inputs and outputs:

In most actual systems, you need a way to hold the data, which is why we have latches:

and with the latch, we introduce the clock.  I will now give you two examples of where logical depth, in a system context, is not representative of speed.

The first assumption that made is "0"s and "1"s are things.  Digital is a special case of analog; however, I personally never run anything at a "1" because it is inefficient for power.  After you are above threshold, you lose transistor gain.  If you are trying to have power performance, you might not make the same choices as for speed performance. You are doing the same electrical work at a high total cost.

The second assumption is that everything is clocked.  In a system context, I often add logic to make things go faster.  Asynchronous systems give you the average speed as a delay, instead of the worst case delay as a synchronous, clocked system.

Another assumption is that logic doesn't have physical space.   Wires are costly even though that they do not add to calculation value.  A good example of this is the S-Box used in AES.  If you look at the "logic", I have often seen hardware implementations that use a lookup table.  This is because it's easy.  If you look at the gate depth alone, without the wires, it also would look to be fast.  When I make the AES S-Box, the circuit implementation looks like:

This circuit has a much larger depth than the lookup table; however, it requires, less power, takes up less area, and is faster than the lookup table implementation even though the logic depth is deeper.


Bachmair and Ganzinger, ordering of equations

A short answer to your question is to use the definition of multiset extension of a partial ordering.

We have the following:

Let $M = \{s,\bot\}$ and $N=\{s\}$. We have  $M\succ M$ since $M(\bot) > N(\bot)$ and there does not exist $x$ such that $N(x)> M(x)$.
Let $M=\{\{s,\bot\},\{u,\bot\}\}$ and $N=\{\{s\},\{t\}\}$. We have $M(\{s,\bot\})>N(\{s,\bot\})$ and by (1) $\{s,\bot\}\succ\{s\}$. Therefore $M\succ N$.

It would be interesting to see examples where the two ways of extending an ordering on equations to clauses disagree and discuss how that might affect the properties or performance of a rewrite-based prover.


efficiently find connected components in undirected graph considering transitive equivalence

Using depth-first search, compute the connected components, by constructing a mapping that maps each node in a connected component to the first node you visited in that component. This is linear in the number of nodes and edges. Preserve that mapping. Two nodes are equivalent if and only if they map to the same node.


If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?

I. I was not able to parse the question, sorry.
II. There is an infinite number of NP-complete problems.
III/I. Each NP-complete problem can be reduced to any other NP-complete problem.
III/II. If you show that there exists a (Karp) reduction from a NP-complete $B$ problem to a problem in P, then you have proved that all problems that reduce to $B$ are also in P. In particular this implies NP $\subseteq$ P, and hence P=NP.
IV. If a NP-complete problem is in P, then P=NP.


If you solve Vertex Cover with the simple branching algorithm, you achieve an FPT running time of $2^k \text{poly}(n)$, where $k$ is an upper bound for the solution you are looking for.

Substituting $k$ for $\log n$ gives you the answer you are looking for.


Recursion for runtime of divide and conquer algorithms

The total work is given by the sum of a geometric progression. In particular, let $r = a/b^d$, then total work = $O(n^d)\times (1+r+r^2+\ldots+r^p)$, where $p$ is the maximum depth.

Let $S = (1+r+r^2+\ldots+r^p)$.

If $r>1$, then $S = \frac{r^p-1}{r-1}+r^p = O(r^p)$.

If $r<1$, then $S \leq 1+r+r^2+\ldots = \frac{1}{1-r} = O(1)$.


Smallest Circuit for Square of Sparse Symmetric Matrix

If it's really depth that you care about, I think you should be able to do it with a circuit of depth $O(\log^2 n)$ using sorting networks.  I'll assume we want to compute the product $AB$, and that $A$ is represented as an array of rows, where each row is a sorted list of non-zero entries; and $B$ is an array of columns, where each column is a sorted list of non-zero entries.  Then the $ik$ cell of the product $AB$ (namely, $(AB)_{ik}$) can be computed as follows: copy the entire row $A_{i\cdot}$; copy the entire column $B_{\cdot k}$; concatenate these two lists; sort them based on their indices, using a sorting network, to bring together entries with a common index; at each position where both matrices have an entry, multiply those entries; and sum up those products.  You can build a sorting network with depth $O(\log^2 n)$, and the multiply-and-sum step can be done with depth $O(\log n)$ using an addition tree.


Can the same machine word sometimes be data and sometimes be code?

If your question is "can one and the same sequence of bits sometimes represent a machine instruction and sometimes represent data" then the answer is definitely yes.

If your question is "can one and the same location in memory sometimes hold a machine instruction and sometimes hold data" then the answer is it depends on the machine architecture. The Harvard architecture strictly segregates instruction memory and data memory into physically separate parts of the computer memory, with separate data buses. However, the Von Neumann has a single common memory which can hold either instructions or data at any location.

If your question is "can one and the same location in memory be treated sometimes as an instruction and sometimes as data by one and the same program" then the answer in a Von Neumann architecture is yes, in principle. However, this leads to the possibility of writing self-modifying code, which is considered undesirable because such code is difficult to maintain and is a security risk. Therefore all modern operating systems make sure that the programs they are running have a strict segregation between data and instructions, and cannot modify their own code. This is usually implemented within the operating system itself rather than at the physcial memory level.

Note, however, that the distinction between data and code still depends on context - what is data to one program may be code for another program. For example, the output of an assembler, which the assembler treats as data, will be treated as machine instructions when the assembled program is actually being run.


Probabilistic poly-time machine always halts on all inputs?

We say that a probabilistic Turing machine M runs in time T(n) if for any input x M halts in less than T(|x|) steps independently of the random choices it makes during the computation (worst case over all possible computation paths).

For example, the most general definition of Probabilistic Polynomial-time, namely  PP, is:

  A language L is in PP if and only if there exists a probabilistic Turing machine M, such that

  M runs for polynomial time on all inputs
  For all x in L, M outputs 1 with probability strictly greater than 1/2
  For all x not in L, M outputs 1 with probability less than or equal to 1/2.

It always halts in polynomial time on all inputs.

Because the two probabilities can be made very close ($\frac{1}{2}+\frac{1}{2^n},\frac{1}{2}-\frac{1}{2^n}$), it would take potentially an exponential number of runs to distinguish accepting from rejecting with good confidence; so a more representative and efficient probabilistic class is BPP (Bounded-error Probabilistic Polynomial-time):

  A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that

  M runs for polynomial time on all inputs
  For all x in L, M outputs 1 with probability greater than or equal to 2/3
  For all x not in L, M outputs 1 with probability less than or equal to 1/3.

Again, M always halts in polynomial time on all inputs.

See also the complexity class RP (Randomized Polynomial time).

We have: $RP \subseteq BPP \subseteq PP$


is modulo of hash function is evenly distributed?

if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed?

It depends on the hash function. For a good hash function the output should be uniformly distributed.

  so if I have a histogram of values [0,N-1] will the histogram be evenly distributed ?

For any reasonable hash function, yes.

Keep in mind that real-world hash functions are sometimes terrible. Many programming languages will, as the hash of an integer (using the built-in hashing function), return the original value. This is not a problem if your input is truly random, but usually the reason to use a hash function is to take an input that has some structure, and produce hashes that (hopefully) don't.


How can i fill shelves with products so that I have the maximum amount of sales?

You'd need to give an exact specification of the problem, but we can do something. It sounds that every item can in principle be placed anywhere, but has a different value depending on where it is placed. It's not quite clear how "value" and "max sales possibility" interact, that's for you to figure out.

I'd try to find a "profit" per item, which will depend on its shelf location. What's even more important is "profit per meter". Since the profit changes by the same percentage for all items, you want to put all items with "high profit per meter" to positions where their profit isn't removed.

A "greedy" algorithm would start by sorting all items by profit per meter. Then you put the items sorted by profit per meter into the high-value places first. That gives you a decent solution.

You will have unused space left, so you will try to improve things by putting items there that fit better. Say you had a meter high value space and put a 60cm item there and don't have anything to use the leftover 40cm, then maybe placing a 100cm item would be better. That's reasonably similar to bin packing.

You can be pretty sure that the problem is NP-complete, which means in layman's terms that neither you nor anyone else will be able to find an optimal solution in reasonable time, so you try to find a good solution instead.


A similar question has been asked before, that may answer your question, here. Quoting the answer:

This is basically an instance of the line segment intersection problem.  One standard approach is to use a sweep line algorithm.  For instance, the Bentley-Ottman algorithm would be a reasonable choice, and is not too difficult to implement.
At each iteration of the algorithm, we have some value of $x$, and we calculate what is the next largest value of $x$ where something interesting happens.  Here, "something interesting" is either (1) two pieces intersect each other at a point, or (2) we reach the end of one of the current pieces.  Then we advance $x$ to this next value.
At each iteration, we keep track of which pieces are currently active (i.e., $x$ is within the domain of that piece) and the order of the pieces, ordered by their $y$-value for that particular value of $x$.  Store them in sorted order, sorted by $y$-value.

So, in some sense it is a matter of proper abstraction: you need to implement a function
 something_interesting_happens(real x, function f1, function f2)

the function should return, given an x-value x, the next x-value where either an intersection occurs or the start or end of a line segment occurs. With this functionality out of the way, to return your maximum function, you just iterate over all the interesting x-values, starting from 0 and repeatedly using something_interesting_happens to get the next interesting x-value. It is a bit simpler for you as you are looking to only maximize two functions, and in the above quote they consider maximizing $n$ functions.
The final issue is that you need to settle on a representation for your piecewise linear functions. As plop points out in the comments, your current representation has an issue: it can't represent discontinuous functions.
Here's one possibility, for simplicity:

Define a piece to be either an open line segment, represented by a pair of points $(x_1, y_1), (x_2, y_2)$, or a single point, represented by $(x_1, y_1)$. This gives you sufficient expressiveness to have both closed and open line segments, without worrying about representing open and closed line segments separately. In particular, a closed line segment will be an open line segment, plus points at both of the endpoints.

It will be probably useful to have some functions on pieces, such as:
intersect(piece p1, piece p2)

to indicate if two pieces intersect in the $x$-values they consider, and
less-than(piece p1, piece p2)

which means that p1 and p2 don't intersect, and p1 is before p2.

Represent a piecewise linear function by a (possibly empty) sequence of pieces. The pieces should be sorted, so that less-than(p1, p2) holds for all pieces in the list p1 and p2 where p1 occurs before than p1.


Find a graph for which Kruskal's algorithm achieves worst-case running time

Let the answer be a complete graph $G = (V,E)$ with $|V| = n$ and a weight function $W : E \to \mathbb{R}$

Let the vertices be denoted by $1,2,\dots n$ and edges between $i$ and $j$ as $(i,j)$.

Now define the weights of all the edges as follows:
$$W(i,j) = j-1, \forall \ 1 \le i < j$$

(Assuming you break ties for the edges on the basis of the value of the nodes $i,j$)

If you add a break statement once all $n$ nodes have been merged, then the algorithm will iterate on all the $\binom{n}{2}$ edges (except the last $n-1$) before finishing execution. This is because it will iterate all the edges in non decreasing order and it will find that except for the edge $(1,j)$ all other edges connect nodes belonging to the same disjoint set.

The running time will thus be $\mathcal{O}(\alpha(n + \binom{n}{2}))$


Monetary computations theory (manual/textbook)

Let me illustrate one problem which could happen, and one way to solve it. You want to distribute a given amount of cents $N$ into $k$ piles, in proportions $p_1,\ldots,p_k$, where $p_1,\ldots,p_k \geq 0$ and $p_1 + \cdots + p_k = 1$. The problem is that $Np_i$ need not be an integer. As a simple example, you might want to divide $20$ cents into $1/3:2/3$ proportions. The fractional solution is
$$ 6\frac{2}{3}:13\frac{1}{3}. $$
It seems fair to round this to $7:13$ since $2/3 > 1/3$. More generally, compute $m_i = \lfloor N p_i \rfloor$ and $r_i = Np_i - m_i$. Here $m_i$ is the initial allocation and $r_i$ is the fractional one that you want to round. You need to add up some amount $R = N - \sum_i m_i$ of cents to make the total exactly $N$. Sort the $r_i$ in non-increasing order, and give one cent to the first $R$ parts according to this order (break ties arbitrarily). This is just a generalization of the example above.