Looking for a succinct dynamic sorted dictionary

If you can tolerate $O(\sqrt{n})$ time complexity, I'd go for bi-parental heaps by Munro and Suwanda. This seems like an elegant implementation that should have $O(\sqrt{n})$ memory overhead in practice.

If your sets are too large for that, I'd try this data structure by Frederickson. You'll need a Hashed Array Tree to make it work with malloc.

Theoretically, a solution with $O(\log n)$ time per operation is possible. See this extended abstract by Franceshini and Grossi, and my bachelor's thesis that goes into greater detail and fixes some of the bugs.

Note that, apart from the bi-parental heap, I am not aware of any implementations. The asymptotically optimal solution probably has excessive multiplicative constants and I still need to complete it (which shall be my master's thesis).


Multiple neural networks or multiple outputs?

You can do either.

If the learning tasks are related at all (i.e., the meaning of the columns of B are related), it's probably better to have one neural network with multiple outputs.  This is often more effective, because the first few stages of that neural network might do some processing that is relevant to all of the outputs -- e.g., it might look for some local patterns or properties of the input that can then be useful for predicting all of the outputs.  The network might take a bit longer to train if you use one big network rather than many smaller networks, but usually this is worth it if it leads to better accuracy.

But if you're not sure, you can always try both approaches and see which works better.


Trying to simplify a particular regular expression

Assume the notations used in the question is the ones as described in the Wikipedia entry on regular expression for formal language theory. More specifically, it is the variant where "+" is used for alternation. (If you want to interpret the question in the notation used in common programming languages, please check the first version of this answer. Also note this updated answer renders the some comments below outdated. Thanks to the commenters!)

Suppose the task is to determine whether the following equality of regular expressions is correct,
$$(a^* (ba)^* )^* (b\text{+}\epsilon) = (a\text{+}b)^* (b\text{+}\epsilon)$$
then the answer is NO.

Why? Let us consider word $bb$. The right side is, in fact, the set of all words over the alphabet $\{a,b\}$. In particular, the right side contains $bb$. Can the left side contains $bb$? If the first $b$ in $bb$ comes from the part $(b\text{+}\epsilon)$, then it must be the end of the word, but there is another $b$ following the first $b$. If the first $b$ comes from the part $(ba)$, then it must be followed by an $a$, which is not the case.
Since the right side contains $bb$ but the left side does not, the equality cannot hold.

Now suppose the task is to simplify the left side of that incorrect equality,
$$(a^* (ba)^* )^* (b\text{+}\epsilon)$$
then a likely answer is, as given and proved by OP correctly,
$$(a\text{+}ba)^*(b+\epsilon)$$
The equality of these two regular expressions can also be understood easily by observing that the language is the set of all words over the alphabet $\{a,b\}$ that have no two consecutive $b$'s.


Does closure against countable union survive union of classes?

The answer to (3) is yes. Suppose that $S \subseteq \mathcal{C} \cup \mathcal{C}'$. Then $S$ is countable, because $\mathcal{C}\cup\mathcal{C'}$ contains only decidable languages of which there are only countable many. Now let $T = S \cap \mathcal{C}$, $T' = S \cap \mathcal{C}'$. By assumption $L = \bigcup T \in \mathcal{C}$, $L' = \bigcup T' \in \mathcal{C}'$. Since $L,L'$ are decidable, $L \cup L'$ is decidable.


Which language is used to construct a type system?

OCaml and Scala are popular choices for types systems, but they are by no means the only languages you can write a compiler, interpreter, typechecker, or type system in.
Type-checking involves traversing syntax trees representing terms and types. Languages with some form of algebraic data type make this easy, since these traversals can be defined using pattern-matching . In an object oriented language, these traversals have to be done using a Vistor pattern, which ends up using much more boilerplate. Languages like Haskell can use techniques like monads or  datatype-generic programming to abstract away even more of the boilerplate of these traversals.
Also, functional programming languages tend to be closer to the lambda calculus and the other formalizations of programming languages. Since programming language researchers are often the ones developing both these formalizations and the implementations, so it makes sense that they'll be more comfortable in languages like these.
It's worth mentioning that a some work has been put into developing other ways to declaratively specify type systems for languages. For example:

Turnstile is a Racket DSL that lets you develop type systems in a form that looks a lot like formal inference rules.
Spoofax is a toolkit for writing programming languages, that can generate a typechecker with IDE integration from a specification.

A related question, is a type system for a language always written in the native language itself?

Certainly not! It's popular for writers to implement a language in the language  itself, (often called "self hosting"). If you're writing a programming language, then there's a good chance that it's  been designed to solve problems that whoever was writing the language had. So whoever is designing the language probably finds it a pleasant language to use.
But for performance reasons, often languages are implemented lower-level languages like C or Rust. This is particularly important for interpreted languages: if you write your interpreted language in another interpreted language, then interpreting code involves running your interpreter in yet another interpreter, which is a lot of indirection that hurts performance.


What do we mean by polynomially upper bounded and lower bounded

Now a polynomial is of the form,$n^{c}$ where $c$ is constant.

Now let $f(n)$ be a constant function. Now it being a constant function we have,

$f(n) \in O(lg (n))$

$\implies lg(f(n)) \in O(lg(lg(n))$

Now $lg(f(n))$ is yet another constant function and let it be $g(n)$

So we have from the previous implication,

$ g(n) \in O(lg(lg(n))$

$\implies n^{g(n)} \in O(n^{lg(lg(n)})$

$\implies n^{lg(lg(n))} \in \Omega(n^{g(n)})$

But $g(n)$ is after all a constant so let it be $c$ then we have from the previous implication,

$n^{lg(lg(n))} \in \Omega(n^{c})$

Now $n^{c}$ is a polynomial and hence $n^{lg(lg(n))}$ is polynomially lower- bounded.

We cannot have the other way around i.e. $n^{lg(lg(n))}$ is upper bounded by a polynomial simply because of the observation, $n^{c} \in O(n^{lg(lg(n)})$ as clearly $lg(lg(n)$ shoots up faster(no doubt) than $c$ a constant.


Uniformly sampling from cycles of a graph

Exponential-time algorithm

One (slow) approach is to rejection sampling.

Let $c_1,\dots,c_k$ be the cycle basis.  Then we obtain an isomorphism $\varphi : (\mathbb{Z}/2\mathbb{Z})^k \to \mathcal{E}$, where $\mathcal{E}$ is the set of Eulerian subgraphs of $G$, given by

$$\varphi(\alpha_1,\dots,\alpha_k) = \alpha_1 \cdot c_1 + \cdots + \alpha_k \cdot c_k.$$

This gives us a way to sample uniformly at random from the set of Eulerian subgraphs.

Note that the set $\mathcal{C}$ of simple cycles of $G$.  Note that every simple cycle is an Eulerian subgraph, i.e., $\mathcal{C} \subseteq \mathcal{S}$.  Thus, a simple procedure to sample uniformly at random from $\mathcal{C}$ is:

Sample uniformly at random from $\mathcal{E}$, to get a subgraph $e$.  (Namely, pick $\alpha_1,\dots,\alpha_k$ uniformly at random and set $e = \varphi(\alpha_1,\dots,\alpha_k)$.)
If $e$ is a simple cycle, output it.  Otherwise, go back to step 1.

This samples a simple cycle uniformly at random from the set of all simple cycles of $G$.

The (expected) running time is proportional to $|\mathcal{E}|/|\mathcal{C}|$.  It is known that $|\mathcal{E}|=2^{|V|+|E|-1}$ if $G$ is connected.  Thus, if $G$ has $C$ different cycles, this gives an algorithm whose running time is proportional to $2^{|V|+|E|-1}/C$.  Depending on the number of cycles in $G$, this might be extremely slow.

I don't know if there is a polynomial-time algorithm or not.

Counting the number of simple cycles

Counting the exact number of simple cycles in a graph is NP-hard, by reduction from the Hamiltonian cycle problem.  Jonathan Katz has some lecture notes that provide a proof.

I don't know whether it is hard to approximate the number of simple cycles in $G$. If it is, then this might imply hardness results for uniform sampling from among the set of simple cycles.

See also https://cstheory.stackexchange.com/q/20246/5038.


Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?


Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

A* expands the search tree by expanding the node for which the past cost ($d(n)$; cost of path from the start point to the node) plus the heuristic value ($h(n)$) is minimum. Because the heuristic $h(n)$ is admissible, $d(n)+h(n)$ is a lower bound on the cost of the path to the goal that may be obtained by expanding the node $n$.

If we have found a path of cost $L$, we can (only) conclude that path is shortest when there are no more nodes for which $d(n)+h(n)<L$. If there were such nodes then expanding them could possibly give a path of cost $<L$.

Assume the shortest path has cost $L$. Consider the graph, but restricted to the nodes for which $d(n)+h(n)<L$. Then the nodes that A* expands are exactly the nodes in the connected component of the start point in this restricted graph.

If we have an alternative heuristic function $h'(n)$ such that for all nodes $n$, $h'(n)\leq h(n)$ then clearly the size of the connected component containing the start point in the graph restricted to nodes where $d(n)+h'(n)<L$ is greater (or equal to) the size of the same connected component in the graph restricted to nodes where $d(n)+h(n)<L$ because $d(n)+h'(n)\leq d(n)+h(n)$ for all nodes $n$.

This analysis assumes that there are no other nodes (other than the goal node) for which $d(n)+h(n)=L$, if not this is the case then how many nodes are expanded depends on the tie-breaking order (and we can not say anything useful about that).


Difference between assignment, binding, and substitution?

All three notions are related to variables. You can think of variables as named placeholders for some expression.

When introducing/declaring a new variable, you create a placeholder for an abstract expression (abstract in the sense that the variable does not represent a particular expression). Every variable declaration creates also a scope for that variable. A variable's scope is the part of the program that can refer to that variable. For example, in the line below (written in pseudocode)

add(a, b) = a + b;

variables a and b are being declared and their scope is the body of the add function. This means that any reference to a and b from within the body of add will refer to add's parameters. And any reference to a and b from outside the body of add will be meaningless (so you get a compilation error) or will refer to some other variables (which happen to have the same name, but have been declared outside of the function's body).

Altogether, this behavior is summarized in the sentence "Once a variable is declared, it becomes bound within its scope". Or, specific to this example, add binds the two variables a and b.

There's a third variable being declared in the pseudocode above and that is the add variable. So add is another placeholder, but this time the expression that add represents is not abstract, but a concrete value: it is the function that takes two expressions and returns their sum. Thus,

Assigning a value to a variable means that, while retaining the functionality of a placeholder, the variable does not represent some abstract expression any more, but an actual concrete expression.

The action of assigning an expression to a variable is closely related to substituting an expression for a variable. One difference is that variable assignment happens explicitly by the programmer at design time, while substitution is an internal mechanism of the language and happens at runtime.
Another difference is that, while variable assignment is itself an expression (it is part of the syntax of a language) and keeps the variable in scope, substitution is an action over expressions (it transforms expressions) and it entirely wipes away all occurrences of a variable from that expression. In other words, it eliminates the variable.

The relation between assigned variables and substitution is that all variables that have been assigned a value are internally substituted by their assigned values. This does not mean that substitution is triggered only through variable assignment. Another way is through function application (look up "beta-reduction" for more details).


Minimum Subsequence Sum Algorithm Verification

The fact that your algorithm is in Java or the source itself are not really relevant. That said, your algorithm requires time $\Theta(n \cdot k)$, where $n$ is the length of the input sequence, and $k$ is the length of the desired subsequence. This can be as bad as $\Theta(n^2)$, when $k=\Theta(n)$.

You can improve the time complexity of your algorithm to $O(n)$ by first finding the $k$-th smallest element $x$ in $O(n)$ time, and then selecting all elements smaller than $x$, plus the necessary number of copies of $x$ (there might be multiple copies of $x$ in the input sequence and not necessarily all of them belong to the output).

An easy selection algorithm is quickselect with randomized pivot selection. This algorithm has complexity $O(n)$ with high probability. If you want a $O(n)$ worst-case complexity you'll have to be a bit more careful with the pivot selection.
You can start by reading the Wikipedia pages on selection, quickselect, and median of medians.

If you want to be lazy and you don't care about losing a $O(\log n)$-factor over the optimal time complexity, then you can simply sort the input sequence in time $O(n \log n)$ (e.g., using Mergesort) and then return the first $k$ elements.

Another solution that is easy to implement if you have access to priority queues and has complexity $O(n \log k)$ is iterating over the input sequence while maintaining a max-Heap $H$ of the smallest $k$ elements encountered so far.
Initially $H$ is empty and, for each element $x$ of the input you: (i) push $x$ into $H$, (ii) if $H$ contains $k+1$ elements, you extract one element from $H$.
After examining all elements, $H$ contains exactly the $k$ smallest elements of the whole input sequence.


Is it a tautology or not? According to my truth table its not

The question is not phrased clearly.  Perhaps the question can be rephrased as follows: Let $p,q$ and $s$ be propositions whose truth values belong to some subset $A \subseteq \{T,F\}^3$.  Suppose $A$ is such that $(q \leftrightarrow p) \leftrightarrow s$ evaluates to true for each assignment from $A$ and $p \rightarrow s$ can take both possible truth values over assignments from $A$. Can $q \rightarrow s$ take both possible truth values over assignments from $A$?

But there are many $A$'s which satisfy the given two conditions, and different $A$'s will give different answers- it can be a contingency, or it can be tautology.


Hint: If $T(n/2) \leq M \frac{n}{2} \log \frac{n}{2}$ then
$$ T(n) = 2T(n/2) + cn \leq Mn\log \frac{n}{2} + cn \leq Mn\log n +n (c-M\log 2). $$
The lower bound should be similar.


What solution to apply for finding the optimal parameters?

It appears that you have a function $f:\mathbb{R}^4 \to \mathbb{R}$ and you want to find $x$ that maximizes $f(x)$, but you cannot compute $f$ directly; you can only obtain a noisy estimate of its value.

Many optimization methods can be adapted to this setting.  A simple thing you could try would be an iterative method like gradient ascent or Newton's method, but with more iterations to account for the noise; the idea is that the noise will average out given enough iterations.

For instance, gradient ascent requires that you be able to compute the gradient $\nabla f (x)$ for any point of your choosing.  In your case, this can be done by estimating

$$\nabla f(x) = ((f(x+e_1)-f(x-e_1))/2, \dots, (f(x+e_4)-f(x-e_4))/2),$$

where $e_1=(1,0,0,0)$, $e_2=(0,1,0,0)$, and so on.  Now given the ability to compute $f$ on a point of your choice, by computing $f$ on 8 inputs, you can estimate $\nabla f(x)$ and then take a single step of gradient ascent; and repeat until convergence.

A more sophisticated approach would be to try using Bayesian optimization, such as Google Vizier.


What is a good example to illustrate the difference between isomorphic and homomorphic representations?

You are probably talking about homomorphisms from logic, i.e. homomorphisms that just preserve your functions and relations: https://en.wikipedia.org/wiki/Structure_(mathematical_logic)

I'm a bit suspicious about why your instructor bothered to give you these concepts in the intro course. I also suspect you just need to understand a difference between injective and bijective functions (for this is what the difference between a homomorphism and isomorphism is in the logic world, ignoring all the stuff that deals with preserving structures).

Injective function. You have a set of shirts. You represent the shirts by their colours. Many shirts have the same colour. Some colours don't have any shirts mapped into them. If you are given just a colour, you cannot recover the knowledge of what shirt it was.
Bijective function. You have a set of books. You represent them by the ISBN number. Every book gets and ISBN number. Every ISBN number is associated with some unique book. You can go back and forth between these representations.


Finding an unambiguous grammar of a language provided by a CFG

First, let us show that the original grammar generates the language $L$ of all words in which in every prefix, there are at least as many $a$s as $b$.

A simple induction shows that every word generated by the grammar satisfies the property. In the other direction, let $w$ be a non-empty word in $L$. We consider two cases:

Some prefix of $w$ has exactly as many $a$s as $b$s. Write $w = axby$, where $axb$ is the shortest prefix with this property. This choice guarantees that $x \in L$. Also, $y \in L$. Hence we can generate $w$ using the rule $S \to aSbS$.
In every prefix of $w$, the number of $a$s exceeds the number of $b$s. Hence $w = az$, where $z \in L$, and we can generate $w$ using the rule $S \to aS$.

Every word $w \in L$ can be written (uniquely) as $w_0 a w_1 a \cdots a w_\ell$, where $w_i$ is a word in $L$ in which the number of $a$s is the same as the number of $b$s. Indeed, $w_0$ is the longest prefix of $w$ in which the number of $a$s is the same as the number of $b$s; $w_0 a w_1$ is the longest prefix of $w$ in which the number of $a$s exceeds the number of $b$s by 1; and so on.

Suppose that $T$ generates unambiguously the language $L'$ of all words in $L$ in which the number of $a$s is the same as the number of $b$s. Then we can generate $L$ itself unambiguously using the productions $S \to T a S \mid T$. The language $L'$ can be generated unambiguously using $T \to aTbT \mid \epsilon$.


How should we interpret a transition rule $\epsilon,b\to c$ in a Pushdown Automata as Sipser defined in his book?

Suppose that your PDA is reading $011$.

At the beginning, the PDA is at state $q_1$, and the stack is empty. The only move the PDA can make is to put $\$$ on the stack and to transition to state $q_2$.

Since the next symbol to be read is $0$, the only move the PDA can make now is the self-loop on $q_2$ which puts $0$ on the stack. The input is now $11$, and the stack is $0\$$ (top of stack first).

Since the next symbol to be read is $1$, the only move the PDA can make is to transition to $q_3$, erasing $0$ from the top of the stack. The input is now $1$, and the stack is $\$$.

Since the next symbol to be read is $1$, the PDA must move to $q_4$, erasing $\$$ from the stack. The input is still $1$, and the stack is empty.

At this point, the PDA is stuck. It cannot make any move. However, it hasn't read all the input yet. We conclude that there is no accepting computation for this input, and so the PDA doesn't accept $011$.


Maximal Minimum Spanning Tree by Removing $k$ Edges

This is known as the $k$ most vital edges for the minimum spanning tree problem. It has been proved as NP-hard [1].

For fixed $k$, Weifa Liang proposed an $O\left(n^k\alpha((k+1)(n-1),n)\right)$ algorithm where $\alpha$ is a functional inverse of Ackermann’s function [2], and can be improved to $O\left(n^k\log\alpha((k+1)(n-1),n)\right)$ using Seth Pettie's sensitivity analysis [3].

[1] Frederickson, G. N., & Solis-Oba, R. (1999). Increasing the weight of minimum spanning trees. Journal of Algorithms, 33(2), 244-266.

[2] Liang, W. (2001). Finding the k most vital edges with respect to minimum spanning trees for fixed k. Discrete Applied Mathematics, 113(2-3), 319-327.

[3] Pettie, S. (2005, December). Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. In International Symposium on Algorithms and Computation (pp. 964-973). Springer, Berlin, Heidelberg.


There is a standard construction to do this, discussed in all formal languages/automata courses. It results in gigantic grammars, often with lots of useless productions and nonterminals.

Added, as requested by Nehorai:

Take a PDA $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \varnothing)$ that accepts $L = \mathcal{N}(M)$ by empty stack (if you have a PDA accepting by final state, first convert to empty stack). We define a CFG that accepts $L$.
The nonterminals are symbols of the form $[p, A, q]$ with $p, q \in Q$, $A \in \Gamma$, and a start symbol $S$. The idea is that if $[p, A, q] \Rightarrow^* \sigma$, then if $M$ starts in state $p$ with $A$ on its stack, after consuming $\sigma$ it might be in state $q$ and the stack is shorter by one symbol for the first time. Consider an $A$ on the (eventually empty) stack as commitment to get rid of it.

If there is a move $(p, A_1 A_2 \dots A_n) \in \delta(q, x, A)$ with $x = \epsilon$ or $x \in \Sigma$, this adds productions:

$\begin{align}
  [q, A, q_n]
    \rightarrow x [p A_1 q_1] [q_1 A_2 q_2] \dots [q_{n - 1} A_n q_n]
\end{align}$

I.e., we consume $x$ from the input (generate it in the grammar), going to state $p$, from which we now are committed to get rid of $A_1 \dots A_N$. We don't know what states $q_1, \dotsc, q_n$ are involved, we just know that after consuming e.g. $A_i$ we will be in some state $q_i$, from which we have to consume $A_{i + 1}$. So we will have to consider all possible collections of states for them.

In the special case $(p, \epsilon) \in \delta(q, x, A)$, the above simplifies to:

$\begin{align}
[q, A, p] \rightarrow x
\end{align}$

If $x = \epsilon$, the above formally doesn't give a context free grammar, but with the standard construction $\epsilon$ productions can be eliminated.

To start the ball rolling, the stack initially contains just $Z_0$, we are in state $q_0$, and end up in any state:

$\begin{align}
S \rightarrow [q_0, Z_0, q]
\end{align}$

for any state $q \in Q$.

This should convince you the above construction is correct. It is far from a proof...


Pac learnable when changing distribution

I think the definitions in that book are unclear. If you note, the realisability assumption is not stated as an assumption on anything, nor as a standalone definition, so that already is a bit confusing. I have struggled to find one anywhere that is clear actually.

It appears to me that The Realisability Assumption is also dependent on the distribution  $D$ and the labelling function $f$. That is the trio ($H, D, f$) can be realisable. $H$ in and of itself cannot be realisable.

It took me some sleuthing to come to this conclusion, and I hope it is the right one. I think you are nearly on the right lines of thinking. Here is my thinking:

As you say, if we choose a distribution that causes problems then perhaps we can prove that $L(h) = Err(h) > 0$. If you assume $H$ is finite, and $f$ is not in $H$, then we can find problematic points $x$s and put positive probabilities on them. Then for every $h$ in $H$, $L(h) > 0$; i.e. $H$ is not actually realisable with respect to any distribution.

We have made an assumption that $H$ is finite, but given that the book later on goes on demonstrate results with realisability, and finite $H$, I think we should assume that realisability and finite $H$ together are a valid consideration, and therefore, we cannot assume that realisability holds across any distribution over the domain set $X$. I think therefore we should assume that that is what they meant when defining realisability.

Similarly for the labelling function $f$. If $H$ and $D$ are realisable, independently of $f$, then in the case where $H$ is finite and contains only one hypothesis $h$, we can choose an $f$ that is different to h on the whole domain, which would result in $Err(h) = 1$.

So here's how I would state the Realisability Assumption:

  Definition (The Realisability Assumption) Given a learning problem with distribution $D$ over the domain set, and labelling function $f$, then a set of hypotheses, $H$, is Realisable if there exists $h* \in H$ s.t.
  $L_{(D,f)}(h*) = 0$.

Note that you do not need to know what $D$ and $f$ are to assume that $H$ is realisable with respect to them. We can just assume that $H$ is realisable with respect to them, whatever they may be.

So, assuming realisability in PAC Learnability also restricts $D$ and $f$ to be those which are realisable w.r.t. $H$.


Is this the correct time complexity of my algorithm?

For each of the n people in the list you do $|E|\cdot log(n)$ plus the time of getting it from the list, which is $log(n)$. So the time you start with is complexity: $O(n(log(n)+(log(n)|\cdot|E|)))=O(n\cdot|E|\cdot log(n))$

Assuming E could be as big as n, you could simply say the time complexity is $O(log(n)\cdot n^2)$.


Parallel or efficient computation of value with momentum

I have noted that the above expression can be rewritten as:

$$
A'_{i,j} = \alpha^j A'_{i,0} + \sum_{1 \leq k \leq N} (1 - \alpha) \alpha^{j-k}A_{i,k}
$$

Which makes me think I can define a $M \times N$ matrix $P$ as:

$$
P_{i,j} = \alpha^j A'_{i,0}
$$

And a $N \times N$ matrix $R$ as:

$$
R_{i,j} =
\begin{cases}
\alpha^{j-i} & \text{if}~i \leq j \\
0 & \text{otherwise}
\end{cases}
$$

And so I think that I would have:

$$
A' = P + (1 - \alpha) A R
$$

Which would be a more parallelizable computation. The only challenges would be to efficiently construct $P$ and $R$ (which is probably not that hard) and, more importantly, the memory usage if $N$ is big (which unfortunately in my case it kinda is).


Here is a big hint to help you solve the problem:

 Can you give an example of a language that is in this class?  Can you give an example of a language that is not in this class?


No, there are no other possibilities as far as I can see.

The ambiguity comes from the production rule $expr \rightarrow expr - expr$. This rule allows you to derive the expression in two different ways:

Derive $1$ from the left $expr$ and the rest from the right $expr$
Derive $1-2$ from the left $expr$ and the rest from the right $expr$

Some ideas that might help.

The precedences look ok to me; the lower the precedence the closer the operator should be to the root (in this case $expr$).
- has the lowest (derived from $expr$), * has a higher precedence (derived from a production after $expr$).
And the parentheses (...) have the highest (derived from a production after $term$).

The $term$ production rule is left associative, which helps avoid the ambiguity of associativity.

The $expr$ production rule is the problem as mentioned above. A solution to that would be similar to what you see for the $term$ production rule. Make it left associative.


Repeated addition and comparisons of floating point numbers

The reason you are seeing these results are not due to the memory limits of your computer, but rather of the limits of the encoding of "floating point" numbers.  Python uses 64 bit floats (aka double precision floating point numbers), which are well described on wikipedia: https://en.wikipedia.org/wiki/Double-precision_floating-point_format

In short, there are only 52 bits for the significand and 11 bits for the exponent.  $2^{1023}$ is the highest exponent that can be represented.


Shortest Path Variant (constrained max hop)

The "best" way to solve your problem is by dynamic programming. This will give you a running time of O(knMaxDegree).

The program is almost identical to the one for the knapsack. The basic idea is that you create a space (node, remaining hops), start at the destination (s,k) and then visit the neighbours of s, and so on.

For a deeper explanation, this problem is known as Constrained Shortest Path.


Average time complexity of linear search

The right way to prove this is to use the notion of expected value.
Given an array $[x_1, …, x_n]$, an index $1\leqslant k \leqslant n$ and a value searched $1\leqslant i \leqslant d$, the probability that $x_k = i$ is $\frac{1}{d}$.
Now what we want to calculate is the expected value of the first index $k$ such that $x_k = i$. For that, we need to know the probability, for each index $k$, that $x_k$ is the first value equal to $i$. This probability is $p_k = \frac{1}{d}\left(1-\frac{1}{d}\right)^{k-1}$ (meaning that we did not encounter $i$ within indices $1…k-1$ but in index $k$).
The expected value is then $\sum\limits_{k=1}^{n}kp_k = \frac{1}{d}\sum\limits_{k=1}^nk\left(\frac{d-1}{d}\right)^{k-1}\leq \frac{1}{d}\sum\limits_{k=1}^{\infty}k\left(\frac{d-1}{d}\right)^{k-1}$.
We can show that this last quantity is equal to $\frac{1}{d}\frac{1}{\left(\frac{1}{d}\right)^2} = d$.
This indeed means that the average time complexity is $O(d)$.


You must subtract a lower order term in order to strengthen your inductive hypothesis: try

$T(n) \leq c_1 n^2 \lg n- c_2 n$ and you will be able to show by substitution that $T(n) = O(n^2 \lg n)$ for appropriate values of the constants ($c_2 > 1$ and $c_1$ big enough to correctly handle the initial conditions).


I think you are asking about how to implement a set difference operation. Specifically, if user 1's recipe for salad 1 is viewed as a set of ingredients A, and user 2's recipe for salad 1 is viewed as a set of ingredients B, then the the set difference A \ B is exactly the set of ingredients that are in A but not in B.
One well-known and particularly simple algorithm goes like this:

Sort each list of ingredients (let's say in ascending order).
At the start, the first element of each list is the current element.
Repeatedly compare the current elements of the lists. Calling the current elements of A and B by the names a and b, respectively, there are three cases:

a < b Ingredient a is in A and not in B, so make a note of it. Advance the current element for A, but keep the same current element in B.
a = b Ingredient a is in both, so nothing special need be done. Advance both current elements.
a > b Ingredient b is in B and not in A. We don't need to do anything special to rectify this situation. Advance the current element in B.

When you reach the end of both sorted lists, you will have a record of the ingredients that must be added to B's recipe.
There are more complicated algorithms that exploit the fact that strings support more interesting observations than just comparison, or which can take advantage of situations where there's only a small collection of possible ingredients, but I recommend you start here until you're confident that this algorithm doesn't meet your performance needs.


Does the Working Set Paging Algorithm use a separate page table?

Denning provides a rough definition for a working set in Section 2:

  Roughly  speaking,  a  working  set  of  pages  is  the  minimum
  collection  of  pages  that  must  be  loaded  in  main  memory  for
  a  process  to  operate  efficiently,  without  "unnecessary"  page
  faults.

And provides the precise definition in Section 3:

  We define  the  working  set  of  information  W(t,  r)  of  a
  process  at  time  t  to  be  the  collection  of  information  referenced by  the  process  during  the  process  time  interval  (t - r,  t).

  Thus,  the  information  a  process  has  referenced  during
  the  last  r  seconds  of  its  execution  constitutes  its  working
  set  (Figure  2).

The term "page" in these definitions refers to physical pages, not virtual pages. That's because only those physical pages that have resided in main memory at least once during that period of time are part of the working set of a process.

  is the Working Set a completely different, separate list derived from
  the page table entries, or is it defined in the page table entries?

The working set is not defined by the page table entries. These entries define the whole virtual address space of the process. Also, by only looking at the page table entires, it's not possible to determine or derive the working set. The pages that are resident in main memory in a particular period of time and that have been accessed by the process in that period constitute the working set for that period.

Even if a page table entry includes an accessed bit (like the x86 page table entries) and even if the OS supports the accessed bits, it's still not possible to determine the working set just by looking at the page table entries. That's because the same page table entry may point to multiple physical pages during a period of time. At the end of that period, there is no way to determine all of the physical pages that any page table entry has defined during that period. So some additional data structures need to be used.


Cut costly functions in inter-procedural abstract interpretation

Sure.  "Cut off and return Top" is sound.  It's valid.  It seems like a reasonable thing to do.

I don't know if it has been studied or used before in the literature.  I wouldn't be surprised if it has.  It feels to me like a variant on widening, even though it's not identical to the usual widening operator.   I've seen similar methods applied before (if you get stuck, give up and return Top) in other situations.

I don't think there's a single standard approach to this problem.  My impression is that there are multiple techniques. You can memoize analysis of a function (so you lazily generate a transfer function that summarizes the effect of the function, in terms of its arguments, and then reuse that information when you need it again in the future).  You can use widening operators.  You can use counter-example guided refinement to start with a coarse abstraction (which is efficient for static analysis), and then make the abstraction more precise as needed.  I imagine you could also do the converse: start with a fine-grained abstraction, and if it is taking too long, switch to a more coarse abstraction and restart the analysis with that coarser abstraction.  There are probably many other possible techniques, and the best one might depend on the specifics of your particular analysis.


Explanation for the proof "Every 2-thread consensus protocol has a bivalent initial state"

I don't understand why it can only output the input it has seen already.

The reason is simple. Just too simple. Because it cannot output any input that it has not seen deterministically, where the input could take one of two (or more) values randomly.

Let me use an example. Suppose you and I are two travellers (threads) travelling together. Each of us will be given one of two kind of maps to be used for travel, map 0 and map 1 separately. We two might be given the same kind of map. Or each of us might be given a different kind of map. Initially, each of us do not know what kind of map is given to the other one, since we are two separate travellers that have not communicated yet. Now suppose you have to decide which map should be used before you can make a move to know which map is given to me. What can you do deterministically? Since you do not know which map is given to me, the only deterministic decision you can make is to use whichever map given to you.

Had you have a chance to know which map was given to me, you could make a different decision deterministically. However, that is not the current situation.

  for A why "it cannot decide 1 because it has no way of distinguishing this state from the one in which B has input 0)".

That is because A does not know whether 1 or 0 is given to B. Even though the collective state of A and B might be observable/known to a third party, it is not known to A since, at the initial state, by definition, A has not made a move to access any shared object, i.e., A does not know the input to B since it might be 0 and it might be 1.

You will realize, sooner or later, wow, this is just too easy and too simple to understand. It might be fair to say that the lemma 5.1.1 is just too obvious or intuitive to use more than one sentence to explain.

On the other hand, there are lot of pitfalls and counterintuitive phenomenons in multiprocessor programming. Be careful and vigilant.


Let me first repeat my remark: in the application you have in mind (finding the maximal LCM of a partition of $n$), you can assume that the elements of $S$ come factored, and so can represent them as vectors of non-zero integers corresponding to the powers of the various primes. The problem of computing all maxima in this setting has been considered by Kung, Luccio and Preparata, but they only give efficient algorithms in the case when the dimension (number of different primes) is constant, which is not your case. They also give a lower bound of $\Omega(n\log n)$. The problem has took up in the database literature under the name of Skyline - perhaps these people have practical algorithms which could be useful here.


Computing binomial coefficients and factorials modulo a composite number

If $p$ is prime and $n = n_\ell \ldots n_0$, $x = x_\ell \ldots x_0$ in base $p$, then (Lucas' theorem)
$$ \binom{n}{x} \equiv \binom{n_\ell}{x_\ell} \cdots \binom{n_0}{x_0} \pmod{p}. $$

For a product of distinct primes, you can apply the Chinese remainder theorem. So it remains to deal with prime powers. Such a method is described in this paper of Andrew Granville, though it's not as nice as the formula above.


A function that either takes a function as argument or returns a function as result is called a High Order Function in functional programming. Your function make_adder is doing the latter.


Suppose we could always compress a string of length $n$ bits to a string of length $n/2$ bits. Apply this compression algorithm $\log_2 n + 1$ times, and we have reduced a string of length $n$ bits into the empty string. But does the empty string really contain within itself all the information needed to reconstruct the original $n$ bit string?

More generally, a simple counting argument shows that arbitrary strings cannot be compressed. For any compression algorithm $C$:

For every $n$ we can find a string $x$ of length $n$ such that $|C(x)| \geq n$.
For every $n$, at least half the strings of length $n$ satisfy $|C(x)| \geq n-1$.
For every $n$, at least $1-1/n$ of the strings of length $n$ satisfy $|C(x)| \geq n-\log n$.

In particular, an "arbitrary" string cannot be compressed appreciably.

What are compression algorithms good for, then?

Many compression algorithms are lossy, that is, they actually throw away some of the information. This is the case with JPEG, MP3 and MPEG, for example. The compressed picture doesn't look quite the same, but it does look very similar. This property of pictures, that a picture can look similar while differing at the bit level, is exploited by lossy compression algorithms. These algorithms isolate the important parts of the data which are enough to cause in the viewer the same sensation as the original.
Some compression algorithms are lossless but are still able to compress their input. This is because the inputs are often not random and have structure which can be exploited. For example, HTML documents are extremely non-random: for one, they don't use the entire range of characters, but only alphanumeric characters and punctuation. Even raw sound files and pictures can be compressed appreciably, since music and images one would like to compress are not arbitrary white noise, but are smooth in various ways.

After you have compressed a file once, you don't expect it to be compressible again. The aim of a good compression algorithm is to achieve a random looking output, which in particular usually cannot be compressed, as we've seen above.

There are many lossy and lossless compression algorithms out there. If you're looking for lossless compression, you can try some of them out. Many are implemented as standalone tools such as ZIP and BZIP2. Lossy compression strongly depends on the type of medium you are trying to compress. Again, standalone tools are usually available for your perusal.


Optimal solution for Weighted points problem

This problem is a variation of the Maximal Independent Set (MIS) problem in graph theory. To understand that you need to convert your point set $N$ into a graph $G=(N,E)$, where any two vertices $N_1,N_2 \in N$ are connected by an edge if and only if the distance between $N_1$ and $N_2$ is less than the threshold $D$. So the set $X$ you are looking for will be one of independent sets in the graph $G$. However your case is different, because here:

Each vertex in $G$ has a numerical weight, and you are trying to maximize the total weight of the independent set instead of its size - this problem is called Maximal Weighted Independent Set (MWIS) problem.
You are looking for an optimal independent set with exactly $k$ vertices.

There is a number of approaches to this class of problems, for example - this one. You can try to adapt their approach to your case with fixed size of the optimal independent set (which might not exist).

Another approach to this problem uses the fact, that the graph $G$ belongs to a class of Unit Disk Graphs. There is a number of approximation algorithms, developed for the MWIS, which use geometric specifics of such graphs - for example, this one. Again, they don't limit a number of vertices in the solution set. General discussion of heuristics for problems on unit disk graphs can be found here.

As for the straightforward heuristic algorithm for MWIS with predefined size of the solution - your approach is correct. I'll describe it in more details here. At first a definition:

An anti-neighborhood $A(N_i)$ of any point $N_i \in N$ is a subset of $N$, such that for any point $N_j \in A(N_i)$ the distance between $N_i$ and $N_j$ is greater or equal than $D$.

We'll assume that each anti-neighborhood is represented by a tree-like data structure, which can perform three operations:

Build a set from a list of points in $O(n\log n)$ time.
Find a point (in the set) with maximal weight in $O(1)$ time.
Compute intersection of two sets in $O(n\log n)$ time.

So, the algorithm:

Step 1. Find point $X_1$ with maximal weight and build its anti-neighborhood $A(X_1)$.

Step 2. Find point $X_2 \in A(X_1)$ with maximal weight and build the intersection $A(X_1) \cap A(X_2)$.

...

Step $m$. Find point $X_m \in \bigcap_{i=1}^{m-1}A(X_i)$ with maximal weight and build the intersection $\bigcap_{i=1}^{m}A(X_i)$.

...

The intersection of anti-neighborhoods may become empty at some step - in this case the problem doesn't have a solution.

The total time of this algorithm will be $O(kn\log n)$. It's unclear how close this heuristic solution will be to the optimal one.


Proving Turing Completeness by creating a compiler to a Turing Complete language

No. It's usually relatively easy to compile a language (Turing complete or otherwise). At a very simplistic level, a compiler flattens an abstract syntax tree into a list of instructions. This can usually be done by a simple structural induction over the syntax tree. Optimization passes often do data flow or control flow analyses that would be harder to represent as a simple structural induction.

You can make a practical demonstration by programming a compiler for the untyped lambda calculus into some simple Turing complete stack-based machine in Agda or some other non-Turing complete language.

However, just as an extreme example, the "compiler" could be the identity function. If you meant that you could write a compiler for any Turing complete language, then that wouldn't be possible simply because the semantics of the language may require executing arbitrary code (e.g. Common Lisp macros) to elaborate the syntax or otherwise to produce a correct compiler.


As Chi say to you, if you have in a program two operations, one $\mathcal{O}(log{}n)$ and another $\mathcal{O}(n) $ you must take a superior bound, and your result will be $\mathcal{O}(n)$ in this case.

you can see here the complexity graph.
If you say, that one operation take time $\mathcal{O}(n) $ , and nobody other operations take more of this, you can be at least $\mathcal{O}(n) $ time complexity.
If just one operation are over $\mathcal{O}(n) $, the complexity will be change in new bound (and so on).

P.s Sum two bound, will maintain the most higher, multiply  increse time complexity, like two neasted loop of $\mathcal{O}(n)$ will give you $\mathcal{O}(n^2)$ complexity.

I hope that this will help you.


Is the output of a Mealy/Moore automaton a regular language?

By discarding the input-letters you only consider the output language of the respective Mealy automaton. Effectively you obtain a finite state automaton that recognizes the output language and because it is a finite state automaton, which may be non-deterministic, the language it accepts is regular.

The length of the output of a Mealy-transition is irrelevant as you may have for example$aa\in\Gamma$, where $\Gamma$ denotes the output alphabet of a Mealy automaton.


When is the output of shortest path $\subset$ MST?

A basic observation first: in any unweighted graph with a cycle, there is an MST that is not a shortest path tree for some source node. Proof: the tree must omit some edge on the cycle, and for either endpoint of that edge, the shortest path tree contains the edge. So if we fix the source node for the SSSP tree, then it'll be difficult to say more than that the SSSP tree and the MST are equal for graphs that are trees themselves.

Raphael mentions in a comment that the same argument holds for weighted graphs with triangle inequality; to adapt the argument, we only need to consider the lightest edge on that cycle.

Generalizing in a different direction, whenever you have a weighted graph with weight function $w > 0$ that doesn't have a unique MST, then for every MST there is some node for which the MST is not a shortest path tree. The proof will assume that all edge weights are positive; I originally thought that since the set of MSTs is invariant under adding the same value to all edge weights, this would show the result for general graphs, but it doesn't since the set of shortest path trees is not invariant under that operation. Thus, the result will only be proven for graphs with positive weights. Regarding notation, $w > 0$ means that $w$ is positive everywhere.

Proof: Take two different MSTs $S = (V, E_S)$ and $T = (V, E_T)$ of some graph $G = (V,E)$. Consider a lightest edge that is in $S$ but not $T$, that is $ \{u,v\} = e \in \arg \min \{w(f): f \in E_S \setminus E_T\}$. Take the unique $u-v-$path $p_{u,v}^T \subseteq E_T$ in $T$. We know $e \not \in p_{u,v}^T$. Note also that $|p_{u,v}^T| \geq 2$.

Any two MSTs have the same multiset of edge weights, see e.g. Raphael's proof here; due to this, the weight of the lightest edge in $E_S \setminus E_T$ is the same as that of the lightest edge in $E_T \setminus E_S$. Now take all edges on $p_{u,v}^T$ that are not in $S$, that is $\Delta = (p_{u,v}^T \setminus E_S) \subseteq (E_T \setminus E_S)$. We know that $\Delta \neq \emptyset$ since otherwise, $\{e\} \cup p_{u,v}^T$ would be a cycle in $S$. Any lightest edge in this difference, $e' \in \arg \min \{w(f): f \in \Delta\}$, satisfies $w(e) \leq w(e')$ due to the choice of $e \in \arg \min \{w(f): f \in E_S \setminus E_T\}$. Since all edge weights are positive and $|p_{u,v}^T| \geq 2$, we know that $w(e) \leq w(e') < w(p_{u,v}^T)$. Thus, $T$ is not a shortest path tree for $u$. $\square$


Shortest path between any origin to any destination through some way stations

Unless I'm misunderstanding the problem, you can't solve this with any simple modification to Dijkstra's because it's NP-complete.

Given an arbitrary graph, call every node a "waystation", then add start/finish nodes that are fully connected. Now running the solver for your problem will solve TSP on the original graph.


The expected solution is wrong.

Pick $h=0$. The only ternary heap with height $0$ has only one node. Nevertheless the expected solution says that it needs to have at least $3^0 + 1 = 2$ nodes.

In case you meant to write $3^h \le n \le 3^{h+1}$ instead of $3^h < n < 3^{h+1}$, the expected solution is still wrong.
Consider a ternary heap with $n=2$ nodes. This heap has height $1$ but according the expected solution it should have at least $3^h = 3$ nodes.


What are 'Butterfly Combinations' and why are they called this way?

So, a summary of the Wikipedia page on Butterfly Diagrams:

In Computing Science, a Butterfly is the portion of a computation that combines the results of (two) smaller computations into the larger one.
This is common in Discrete Fourier Transformation algorithms, as well as in the otherwise unrelated Viterbi Algorithm for finding the most likely sequence of hidden states.
It is called 'Butterfly' because of how it works in the base case where you combine two single-point results: (Image courtesy of Wikipedia)
The earliest occurrence in print of the term 'Butterfly' is thought to be in a 1969 MIT technical report: C. J. Weinstein (1969-11-21). Quantization Effects in Digital Filters.


A syntax of aggregate operation in relational-algebra (according to [1]) is as follows :

  $G_1,G_2,...,G_n \hspace{2 mm}\textbf{g}\hspace{2 mm}
  F_1(A_1),F_2(A_2),...,F_m(A_m)(E)$

  where $E$ is any relational-algebra expression; $G_1,G_2,...,G_n$
  constitute a list of attributes on which to group; each $F_i$ is an
  aggregate function; and each $A_i$ is an attribute name.

Thus your query would look like :
$\pi_{name}(\sigma_{phone>1}(name\hspace{2 mm}\textbf{g}\hspace{2 mm} count (phone)( Person)\hspace{2 mm}))$

[1] A. Silberschatz, H. Korth, S. Sudarshan, Database System Concepts, 5th Edition


Does a language stay regular if you re-encode the input?

The answer is yes. This is generally called homomorphism, and regular languages are closed under homomorphism. Moreover, regular languages are closed under inverse homomorphism also. More precisely,
if $\tau$ is a homomorphism from alphabet $\Sigma$ to alphabet $\Delta$ and $L$ is a regular language over $\Delta$, then $\tau^{-1}(L)$ is also a regular language.

You can take a look here for more details, or the best is to take a look at this book, which contains proofs about basic properties of regular languages.


The maximum number of nodes in a heap tree of degree d and depth k

A complete $d$-ary tree of depth $k$ has $d^\ell$ on level $\ell$ (where $0 \leq \ell \leq k$), so its total number of nodes is
$$
\sum_{\ell=0}^k d^\ell = \frac{d^{k+1}-1}{d-1}.
$$


matrix multiplication speedup when the matrix elements are 0, 1 and -1

Per row of A you would perform 9 multiplication and six additions, which you could perform with 3 multiplications and 6 fused multiply-add instructions. Like
ResultX = ax * c00 + bx * c01 + cx * c02
ResultY = ax * c10 + bx * c11 + cx * c12
ResultZ = ax * c20 + bx * c21 + cx * c22

Use a switch for the 27 possible values of c00, c10 and c20. Then we need just the fma’s and even replace one of them with a plain multiplication in case one of these numbers is zero.


Calculate how much segements the system can handle

I think neither of those is a good solution, but yours is better than the one you were given.

Here's how I'd reason through it: there are 3 hex digits to represent the segment identifier.  That's 12 bits for the segment identifier.  12 bits can identify up to $2^{12}$ possibilities.  So the system can have at most $2^{12}$ possible segments.  The rest of the information is irrelevant.


Find the maximum number of contiguous occurrences of smaller string s in a larger string l

You algorithm as described doesn't work.
Consider $s=baab$ and $I=\textrm{baabaabbaab}$. Your algorithm would match $s$ with the first $4$ characters of $I$, and since the next $4$ characters don't match $s$, it would then continue with searching $s$ in $I' = aabbaab$.
There is only one occurrence of $s$ in $I'$ causing your algorithm to return $1$ (while the correct answer is $2$).
Here is a solution for your problem that runs in $O(|I|)$ worst-case time.
We can safely assume $|s| \le |I|$, as otherwise the answer is trivially $0$.
Step 1. Construct a DFA $D$ for the language of all words that end with $s$.
This DFA is essentially a path labelled with the characters in $s$ where the last state is a final state. Additionally, each state has "back-edges" that handle characters different from the (at most one) "forward" edge in the path. These "back-edges" point to the state representing the larger prefix of $s$ that is also a suffix of the string read so far.
This sounds more complicated than it really is, and can be computed in linear time (for any constant-size alphabet). Here is an example for $s=\textrm{abba}$ on the alphabet $\{a,b\}$.

Step 2. Now now create an array $A[1, \dots, |I|]$, and feed each character of $I$ to $D$. Whenever $D$ is in the final state after reading the $i$-th character of $I$ set $A[i]$ to $1$, otherwise set $A[i]$ to $0$.
Step 3. Compute the maximum number of consecutive occurrences of $s$ in $I$ using dynamic programming and the array $A$.
Define $B[i]$ as the maximum number of contiguous occurrences of $s$ in the prefix $I_i$ consisting of the first $i$ character of $I$, with the additional constraint that the last occurrence in the contiguous sequence must end with the last character of $I_i$.
For $i = 0, 1, \dots, |s|-1$ we have $B[i]=0$, while for $i = |s|, \dots, |I|$ we can write:
$$
B[i] = \begin{cases}
0 & \mbox{if $A[i]=0$} \\
1 + B[i-|s|] &  \mbox{if $A[i]=1$}
\end{cases}
= A[i](1+B[i-|s|]).
$$
Then the solution to your problem is then $\ell = \max_{i=0, \dots, |I|} B[i]$ and the $\ell$ consecutive occurrences of $s$ start at character number $\arg \max_{i=0, \dots, |I|} B[i] - \ell |s|$  in $I$.
A naive implementation of the dynamic programming algorithm requires time $O(|I|)$ and space $O(|I|)$.
However, one can observe that the value stored in $B[i]$ is useless after $B[i+|s|]$ has been computed (except for finding $\ell$).
Then, we can replace $B$ with a circular array of length $|s|$ (so that each access to $B[i]$ becomes an access to $B[i \bmod |s|]$) and compute $\ell$ by keeping track of the maximum values of $B[i]$ encountered so far.
Moreover, the array $A$ is not needed as we can run Step 2 and Step 3 in parallel: we feed the $i$-th character of $I$ to $D$ and immediately compute $B[i \bmod |s|]$ depending on whether $D$ is in the final state or not.
With these modifications the algorithm requires $O(|I|)$ time and $O(|s|)$ space.
Finally, notice that we don't really need to explicitly represent $D$: knowing, for each prefix $s'$ of $s$ and each character $c$ of the alphabet, the length of the longest prefix of $s$ that is a suffix of $s \circ c$ is enough (where $\circ$ denotes concatenation). See this chapter from Jeff Erickson's book Algorithms for a way to efficiently compute these quantities.


How to find percentage of CPU time consumed during DMA operation?

1 word=64 bit=8 B

64 B=8 word

machine cycle time=2 microseconds => 1 word is transferred from io buffer to memory by cpu in 2 microseconds =>  data preparation time by cpu
64 B data and io bandwidth is 1MBps

so 64/10^6 seconds = 64 microseconds = transfer time by io device = time to dump data from io device to io buffer

now in cycle stealing mode generally data is transferred byte wise..but here word size is given so we assume data is transferred word wise..

64B data in 64 microseconds

=> 8 word data in 64 microseconds

=> 1 word data in 8 microseconds = this is word transfer time by io to buffer

so % cpu blocked= % cpu time consumed = % time CPU is actually transferring data from io buffer to main memory= (2/8)*100%=25%

in burst mode its ( 2 / (2+8) )*100%=20%>>>>>>>

in burst mode all data is transferred once as a block...so we wait for io to dump all of 64 B data in its buffer which is 64 microseconds

now cpu will fully transfer this data from io buffer to main memory..64 B data meaning 8 word data meaning 8*2 microseconds meaning 16 microseconds..

so  16*100/(16+64) % = 2*100/(2+8) = 20%


How to obtain a trilateration ordering in a graph?

Focus on the right problem

I suspect you will find that the most important challenge is not finding a trilateration ordering, but rather choosing a strategy that minimizes the localization error.

It is easy to find a trilateration ordering, as I will describe below.  In contrast, minimizing the error is more challenging.  Trilateration might actually not be the best way to minimize the error.  For instance, when trying to localize a node, it is possible that you might get better accuracy by using four neighbors (e.g., doing multiple trilaterations) and averaging.  Also, the order in which you do the localization might matter.  If you choose a bad order, errors might accumulate.

So, I suspect you might not be focusing on the right problem.

Answering your question as posed

I'm going to answer your problem as posed, even though I'm not sure it is the right problem.

There is a trivial, straightforward algorithm to solve your problem.  You simply enumerate all possibilities.  That can be done as follows:

Let $S$ denote the set of nodes that are currently localized.  Initially, $S$ includes just the three seed nodes.
Repeat the following, until $S$ includes all nodes (i.e., until $S=V$):

For each node $v \in V\setminus S$, for all triples $s,t,u \in S$ of three nodes in $S$:

If $s,t,u$ are all adjacent to $v$, then append $v \to s,t,u$ to your
trilateration order.  Assuming localization of $v$ doesn't fail, add
$v$ to $S$, and continue to the next iteration of the outermost loop.

The running time is $O(n^5)$, i.e., polynomial in the size of the graph.

With standard optimizations, the running time can be reduced significantly.  For instance, you can use a worklist $W$ of nodes that are adjacent to some element of $S$ but not in $S$ themselves (i.e., $W= \{w \in V \setminus S : \exists s \in S . w \in N(s)\}$).  You can update this worklist efficiently.  You can also use a priority queue to sort the elements of $W$ by their "degree" (i.e., the number of nodes in $S$ they are adjacent to), and you can update this ordering efficiently.

But since you didn't list any specific running time requirements, this should be sufficient.

A better approach

I suspect that a better approach is to try to use statistical methods to estimate a global best-fit for the location of all sensors, simultaneously.  For instance, you might use least-squares methods.

Let me illustrate what I mean.  Suppose that you perform a bunch of measurements of the distances between pairs of sensors; create a graph $G=(V,E)$, where there is an edge $(v,w)$ if you have measured the distance between sensor $v$ and sensor $w$.  Let $m(v,w)$ be the measured distance between $v$ and $w$.

Now our goal is locations of all the sensors that best fit these measurements.  In particular, we are looking for a map $L : V \to \mathbb{R}^2$, where $L(v)$ represents the location of sensor $v$.  We are given the locations of three seed nodes, say $v_1,v_2,v_3$.  Also, we are given approximate distance measures between pairs of nodes that are connected by an edge in $G$.  We want to find a location map $L$ that minimizes the total error of the measurements.  Thus, the cost of a location map $L$ might be given by the total squared error:

$$\text{cost}(L) = \sum_{(v,w) \in E} (d(L(v),L(w)) - m(v,w))^2.$$

Here $d(p,q)$ represents the Euclidean distance between the two points $p,q \in \mathbb{R}^2$.

Now we want to find the location map $L$ that minimizes $\text{cost}(L)$, subject to the requirement that $L(v_1),L(v_2),L(v_3)$ have their given values (the locations of the three seed nodes).

This is an optimization problem that can be readily solved using standard methods, e.g., least-squares fitting.

Your problem then decomposes into two parts:

Select a set of measurements to perform.
Solve the optimization problem, e.g., using least-squares best fit, to find the location of all sensors.

A simple approach to decide on a set of measurements might be: each sensor looks at the set of other sensors that are within in its range, and selects 5 of them at random (and ensures that each sensor has its distance measured against at least 3 other sensors, to ensure its location can be uniquely determined; hopefully most will be measured against more than 3 other sensors).  Of course, you could adjust the parameter 5 based upon empirical accuracy/performance tradeoffs.

You could also imagine more sophisticated methods, e.g., where you perform a series of measurements, solve the optimization, look at the average error for each sensor (as a crude measure of how accurate its location might be), then perform a few additional measurements (e.g., only for sensors who average error in its location is too high), and solve the optimization problem again with the additional data.

I think you might find that this is a more effective and robust way to solve your localization problem.

I also encourage you to look at the literature on localization in sensor networks.  There is lots of prior work on this problem.  You know the saying: a month in the field can save you a week in the library.  So, spend the week in the library, and first inform yourself about what has already been tried in the literature.


Finite Automata: Final vs Accepting States

Those are two words that mean exactly the same thing.


Which is faster operations on register operands or immediate operands?

It depends.

Like AProgrammer said, it depends on the processor.

We are in an age where there are many limiting factors based on physics in CPU construction. This means that distance traveled for an instruction and heat generated by a gate cause latency. In theory, this means that for a pipeline where the bottleneck is the decoding stage, this matters. With immediate operands, you would not need to travel to the register to grab the values, which is additional clock cycles and distance traveled. This would decrease latency, and thus increase speed.

However, in real world applications, this is very likely NOT the bottleneck, and so there will be little to no increase (if mandatory register access stages exist) in speed.


Language of words whose run lengths are all distinct

The definition of your language is not completely clear, but whatever it is, if you consider
$$ L \cap 1^* 0^* = \{ 1^a 0^b \mid a \neq b \} $$
then you immediately see that $L$ is not regular.

If you have to prove it using the pumping lemma, then simply take a proof that works for the above language; it will work for $L$ as well.


If the number of citizens is large enough, such that the effect of one citizen changing his/her selection is negligible, then an envy-free division is equal to a Nash equilibrium in a congestion game.

Specifically, Igal Milchtaich's papers are relevant to this problem.

Additionally, Yonatan Aumann and Yair Dombb define several quantitative measures of unfairness: alpha-unproportionality, alpha-envy and alpha-inequitability, which may also be relevant.


You seem to be under the impression that we need to measure a qubit in order to copy it. That is not the case because the copy operation is performed by the mapping $|a,b\rangle \mapsto |a,a \oplus b\rangle$ which, when $b = 0$, can be realized by a CNOT gate. There is no measurement involved at all. You only need to know how many ancilla bits (i.e., initialized to zero) you need beforehand so as to have an adequate quantum circuit size.


Idea: Construct a Grammar fragment for $a^nb^(2n)$. Complement it with rules that break the symmetry.

1: L -> aaaX

2: X -> aXbb   // So far, the subsequence of terminals does not belong to L.
               // The next two rules break the symmetry.
3: X -> aP
4: X -> Qbb

5: P -> aP  | epsilon
6: Q -> Qbb | epsilon

Proof sketch

The grammar is clearly context-free.

The correctness can be proven eg. by induction over possible derivations. The intuition is simple:

Each derivation starts with applying rule 1 followed by an arbitrary number of. applications of rule 2. At each step of this derivation, the current item matches a^3a^nXb^(2n); n >= 0. In particular, n=min the nomenclature of the problem statement.
After application of any one of the rules 3 and 4, non-terminals will only ever expand into sequences of either a or b.
At least on application of rule 3 or 4 is necessary to complete a derivation.

The very first application of 3/4 introduces the imbalance between a and bb in the terminal string. After passing that 'trapdoor', this imbalance will never be offset, since only the 'right' terminals will be produced henceforth.


If-Then with disjunctions (OR) in Integer Linear Programming (ILP)

You have the following condition:

IF ((y1 <= y3) AND (y3 <= y2)) OR ((y1 <= y4) AND (y4 <= y2))
THEN (x1 >= x4) OR (x2 >= x3)

For each logical term, you'll need a new binary variable. At each "level" of the logical statements, you'll use the binary variables from the previous level. So:

z1 = 1 iff y1 <= y3
z2 = 1 iff y3 <= y2
z3 = 1 iff z1 = 1 AND z2 = 1
z4 = 1 iff y1 <= y4
z5 = 1 iff y4 <= y2
z6 = 1 iff z3 = 1 AND z4 = 1
z7 = 1 iff x1 >= x4
z8 = 1 iff x2 >= x3

Then you'll have a constraint that says:

if z3 = 1 OR z6 = 1 then z7 = 1 OR z8 = 1

Let's take one type of constraint at a time.

z1 = 1 iff y1 <= y3:

y3 - y1 + 1 <= Mz1
y1 - y3 <= M(1 - z1)

The logic is: If y3 > y1 - 1, i.e., y3 >= y1, then z1 must equal 1. If y1 > y3 + 1, i.e., y1 > y3, then z1 must equal 0.

Note that if the y variables are continuous, not integer, then replace the 1s with some small number. This isn't ideal from a numerical perspective though.

Constraints 2, 4, 5, 7, and 8 are similar.

z3 = 1 iff z1 = 1 AND z2 = 1:

z1 + z2 <= 2z3
z3 <= z1
z3 <= z2

The logic is: If z1 and z2 both equal 1, then z3 must equal 1. If either of them equals 0, then z3 must equal 0.

Constraint 6 is similar.

if z3 = 1 OR z6 = 1 then z7 = 1 OR z8 = 1:

z3 + z6 <= 2(z7 + z8)

The logic is: If z3 = 1 or z6 = 1, then z7 or z8 must equal 1.


Is there an algorithm for a number line from $0$ to $n$

For $a,b \in \{0,\ldots,n\}$, subtraction is given by
$$
a - b = [a + (n+1-b)] \bmod{(n+1)}.
$$


Check whether all elements are different

This sounds like an assignment, so I'll just give you a few things to think about:

Using a hash table/hash map allows you to access elements in near $O(1)$ time. The only reason it's not exactly $O(1)$ is because of the collisions, $m$.
Given two elements $a_i$ and $a_j$, if $h(a_i) = h(a_j)$, the two elements may or may not be equal. The hash table has to handle this collision in some way; you may then have to go back and check for actual duplicates.
On the other hand, if $h(a_i) \neq h(a_j)$, it's necessarily true that the elements are NOT equal. $a_i$ and $a_j$ are stored in separate locations in the hash table.
Think about the worst case test case; what would happen as you build up the hash table?


Decidability of checking an antiderivative?

The short answer to your question is "no". Richardson's theorem and its later extensions basically state that as soon as you include the elementary trigonometric functions, the problem of deciding if $f(x) = 0$ (and hence if $f(x) = g(x)$, since this is the same as $f(x) - g(x) = 0$) is unsolvable.

What's interesting about this is that the first-order theory of real closed fields is decidable. Intuitively, the reason why adding trigonometric functions makes the first-order system undecidable is because you can construct the integers via $\{ x \in R : \sin(\pi x) = 0 \}$, and the theory of the integers is undecidable.

Whether or not the theory of real closed fields with $e^x$ is decidable is a fairly famous open problem.

Even more interesting that this is that if you had an oracle which "solved" the constant problem (i.e. an oracle which can tell you if $f(x) = 0$ or not), then integration of elementary functions in finite terms is decidable, and a practical algorithm is known. So given $G(x)$, we could find $F(x)$ or know that there is no elementary integral of $G$ in finite terms.


NP-Completeness and commutative property

Your property holds for, for example 3-SAT and 3-COLOURABILITY so it's certainly not required that $X=Y$.

The fact that $Y\leq_p X$ and $X\in\mathrm{NP}$ tells you that $Y\in\mathrm{NP}$; the fact that $X$ is $\mathrm{NP}$-complete and $X\leq_p Y$ tells you that $Y$ is $\mathrm{NP}$-hard.  Therefore, $Y$ is $\mathrm{NP}$-complete.


Loop variant for a while loop that occasionally doesn't decrease?

Just a hint for now, since this is a practice problem: consider a lexicographic combination of orders.

In some more detail: Suppose you have two maps $f_1:S\to D_1$ and $f_2:S\to D_2$ from your program states $S$ into well-founded ordered domains $(D_1,\le_1)$ and  $(D_2,\le_2)$. The lexicographic combination of $\le_1$ and $\le_2$ is the order $\le$ on $D_1\times D_2$ given by $(x_1,y_1)\le(x_2,y_2)$ iff either $x_1\le_1x_2$, or $x_1=x_2,y_1\le_2y_2$. It is also well-founded.

So if $f_1,f_2$ are such that

$f_1$ never increases, and
whenever $f_1$ does not decrease, $f_2$ does,

then the map $(f_1,f_2):S\to D_1\times D_2$ is a variant proving termination.


Turing reducibility implies mapping reducibility

The statement is false.

Say B is the Halting problem and $A = \overline B$. Then, given oracle to the halting problem we can easily decide its complement.

However it is not true that $A \le_m B$ since $B\in RE$ and $A\in coRE$ but both are undecidable (i.e., if $A \le_m B$ was true, then $B=HP$ is both in $RE$ and $coRE$, that is,  $B\in R$ which is a contradiction).


Questions on shortest path and minimum spanning tree

You are wrong on the first one and right on the second one (but for the wrong reason).

To see that (1) is false, just observe that there exists a constant $c$ such that adding $c$ to all weights turns the weighted minimum distance problem into the unweighted one.

On the other hand, (2) is true because every spanning tree contains has exactly $|V|-1$ edges, therefore adding $c$ to all weights adds $c(|V|-1)$ to the total cost of each spanning tree.


Optimization in multivalued logic. Optimal strings with given patterns

As stated, it looks like the solution is trivial: if $\omega$ is the largest value in the underlying domain of values, then $\omega \omega \cdots \omega$ is the optimal value for the tuple.

Let's take your example, templates $AAAAB$, $AAABB$, and $AAABC$.  Suppose the underlying domain of allowable values is $\{0,1,\dots,9\}$.  Then $99999$ is the optimal tuple.  It satisfies $AAAAB$ by the assignment $A_1A_2A_3A_4B_5$.  It satisfies $AAABB$ by the assignment $A_1A_2A_3B_4B_5$.  In fact it satisfies every template.  For any template, there exists an assignment of values to each $X_i$ that makes the tuple $99999$ match that template: just assign the value $9$ to every $X_i$, for all levels $X$ and all variable indices $i$.

Perhaps you meant to provide both the templates and the assignment of values (all $m^2$ values for all the $X_i$'s, where $X$ and $i$ range over all possibilities) as input.


How do garbage collectors avoid stack overflow?

Note that I am not a garbage collection expert. This answer only gives examples of techniques. I do not claim that it is a representative overview of garbage collection techniques.

An unscanned queue is a common choice. The queue can get large — potentially as large as the deepest data structure. The queue is typically stored explicitly, not on the stack of the garbage collection thread.

Once all but one of the children of a node have been scanned, the node can be removed from the unscanned queue. This is basically a tail call optimization. Garbage collectors can include heuristics to attempt to scan the deepest child of a node last; for example a GC for Lisp should scan the car of a cons before the cdr.

One way to avoid keeping an unscanned queue is to modify pointers in place, making the child temporarily point to the parent. This is a constant-memory tree traversal technique that's used in contexts other than garbage collectors. The downside of this technique is that while the GC is traversing a data structure, the data structure is invalid, so the GC has to stop the world. This isn't a deal breaker: many garbage collectors do include a phase that stops the world, in addition to phases that don't but can miss garbage as a result.


Normally, in asymptotic analysis, it's most typical to analyze the worst-case running time.  It is correct to say that the worst-case running time of comparing two $N$-vectors is $\Theta(N)$; and not any less.

However there's nothing saying you have to focus on worst-case running time.  For instance, perhaps you are interested in the average-case running time (also known as expected running time).  In this case the answer will be $\Theta(1)$ if we assume that the vectors are uniformly distributed, as you predicted.

However average-case running time is tricky.  The expected running time depends on the distribution of values, so you must specify a distribution before you can begin the analysis.  If the distribution isn't uniform, then the expected running time might be very different.

Also the expected-running time doesn't add up like you might think.  What happens if you run Quicksort on a list of vectors?  Can we say that Quicksort does $\Theta(n \log n)$ comparisons on average, and each comparison takes $\Theta(1)$ expected time, so Quicksort on a list of vectors will take $\Theta(n \log n)$ time?  No, that doesn't follow.  Quicksort will tend to move similar vectors closer to each other, so as you get to later stages in the algorithm, it's possible that you might be mostly comparing vectors that are similar to each other.  In particular, the two vectors you're comparing won't be uniformly distributed; they'll come from some joint distribution which tends to make similar vectors more likely.  Of course similar vectors are (on average) slower to compare than independently uniformly-random vectors, so there's no longer any guarantee that every comparison takes $\Theta(1)$ time on average.

So, average-case running time analysis can be a lot trickier to get right than worst-case running time.  Beware!


Clarification sought for definition of a cut that respects a set A of edges in Graph Theory

One mistake you're making with the statement:

  In every example in the text, the set A is coincident with one of the partitions of the cut but I cannot see why this must be.

$A$ is a set of edges, while a cut is a partition of vertices: $(S, V - S)$.

Suppose, as you say, that $A$ is a subset of the set $\{(u,v): u,v \in S\}$, then $A$ respects the cut $(S,V-S)$ because none of the edges with both ends in $S$ will cross the cut.

If you add a new vertex $v'$ into $S$, and some other edges from $v'$ to other vertices $x$ in $S$, then $A$ can include ALL of these edges and still respect the cut $(S,V-S)$ because both $v'$ and the other edges from $v'$ are in $S$.


Grover's algorithm on probabilistic classical machines

Let $F$ be a function that maps integers from $0 \dots N-1$ to $\{0, 1\}$. We want to find $x$ (which is promised to be unique) such that:

$$F(x) = 1$$

Now let's take two random integers $a$ and $b$ from $0 \dots N-1$ and output:

$b$, if $F(a) = 0$
$a$, if $F(a) = 1$

For any fixed $x$ and $y$ we have:

$$P_{a=x} = P_{b=x} = P_{a=y} = P_{b=y} = \frac{1}{N}\\
P_{a \ne x} = P_{b \ne x} = P_{a \ne y} = P_{b \ne y} = \frac{N-1}{N}$$

Knowing that $a$ and $b$ are independent random variables, the probability that we output $x$ is

$$P_{a = x \lor a \ne x \land b = x} =
P_{a = x} + P_{a \ne x} P_{b = x} =
\frac{1}{N} + \frac{N - 1}{N^2}$$

and the probability that we output some other value $y \ne x$ is

$$P_{a \ne x \land b = y} = P_{a \ne x} P_{b = y} =
\frac{N - 1}{N^2} < \frac{1}{N}$$


(Nontrivial) Algorithms for finding the third largest element of a set

For $n>5$, this paper proves that the number of comparisons
deterministic algorithms need is $n  +  \big(2 \cdot \lfloor \log_{2}(n)\rfloor \big) - \big(\text{an element of } \{1,2,3\}\big)$,
where that element depends on $n$'s position relative to the nearby powers of $2$.

Furthermore, for $n>7$, that paper gives a
deterministic algorithm which achieves those values.

By pages 330 and 331, the average number of comparisons needed is  $n + \Theta(\ln\ln n)$.

Theorem 5 is that the average number of comparisons used by that
paper's algorithm is at most $n + 5 \cdot ( 11 + \ln\ln n)$.
I have currently not located anything else regarding non-worst-case
algorithms for your problem, although I've kept finding more as I go along.


The function $cut(v)$ is only defined for cutting $v$ from its parent for a reason, because this is the only possibility. The represented tree is first and foremost a Tree. By definition, edges will only exist from a parent to a child. Therefore, the only edge you would ever need to cut is from parent to child.


Issue understanding the reduction of SAT to 3-SAT in poly time

The clauses are not intended to be equivalent, so you shouldn't call it an "equivalent representation in 3-literal clauses."

All the reduction requires is that the original formula has at least one satisfying assignment if, and only if, the new formula does. In this case, we have this property: if the original formula was satisfiable, we can choose at least one assignment to the variables $y_i$ that makes the new formula true and it doesn't matter that there are also choices for the $y_i$ that make it false. Conversely, if the original formula was unsatisfiable, no choice of the $y_i$ will make the new formula true.

Formally, there doesn't even have to be any relationship between the values of the variables in the two assignments. In theory, you could map all satisfiable formulas to "$x$" and all unsatisfiable formulas to "$x\wedge \neg x$".  (But we don't know of an efficient way to do that.)


TM for $0^{5^n}$. Describing a turing machine that decides the language consisting of all strings of zeroes whose length is a power of 5

I'm gonna guess you're in s.datta's class?
I am not sure if this is correct but I tried to cross off 4 0's each time instead of 1.
It's like multiplying by 0.2 or the inverse operation of *5)

1*5 = 5
5*5 = 25
25*5 = 125

125*0.2 = 25
25*0.2 = 5
5*0.2 = 1

Edit: formatting


Prove a statement about searching in binary search tree

Let $h$ be longest path from root $T$ to leaves. We must read $h+1$ nodes. So searching for root of $T$ we have cost $1$, for child of root we have cost $2$ , and etc. it's sufficient to sum over cost at each nodes on $h$. As a result we have
\begin{gather*}
1+2+3...+h=O(h^2).
\end{gather*}
Now as mentioned in question,
$O(h^2)$ must be $O(n\log n)$. More formally, $O(h^2)=O(n\log n)$ that we can conclude that $h=O(\sqrt{n\log n})$.
For example consider a binary search tree with $n$ nodes such that root have sub tree with height $\sqrt{n\log n}$, and right sub tree of root have height $\log (n-\sqrt{n\log n}).$


Remember that a language is defined as a set of strings. The complement of a language is thus the complement of that set, defined in the usual way: everything not in the set.

In practice, when talking about the complement of a language, there's usually a particular alphabet you're interested in (which you can infer from context). If all else fails, assume $\{0,1\}$.

So in this case, the complement of that language is:

  The set of all binary strings $s$, such that either $s$ isn't a valid encoded Turing machine, or the machine encoded by $s$ accepts $1010$.

Hint: the problem of whether a string $s$ is a valid encoded Turing machine or not is known to be decidable. So you only need to worry about the second clause.


Deadlock vs "Progress" requirement of the solution to the critical section problem

and this selection cannot be postponed indefinitely

In case of deadlock, deciding which process will enter next will be postponed indefinitely. So progress won't happen.


If you can access the meta-data you could apply a number of heuristics:

Check the white-balance setting, the camera has chosen for the photo. Basically it indicates the color temperature of the light at the time the photo was taken. Usually sunlight is around 5500 Kelvin. Indoor lighting or cloudy days, usually have different temperatures.
Check the exposure settings. Usually when the sun shines, there is more light available, so this influences the following settings:

A lower shutter speed
A lower ISO setting
A higher f-value

In the old days of photography, the Sunny 16 rule was used to estimate exposure. And you could use it, together with the information in the list above, to check if the photo was taken during the day.
Check if a flash fired or not.
Check the time the photo was taken. Assuming the user has configured the clock, you might immediately remove photos shot at night.

If however you want to approach this problem simply from an image-processing point of view. I can say that sunlight has usually higher contrast, and harsher edges. Therefore histogram analysis and finding harsh edges might give a good indication.

Assuming the photos you are processing are in a Raw Image Format you could apply the same white-balance trick described above. This however does not work for standard images like jpeg or png. This because the image processor on the camera already compensates for the shift in color temperature, and bakes the result into the final image, merely recording the wb-setting it in the metadata.


Can a DFA just have one state that is both the initial state and the final state?

A DFA is defined as a tuple $\langle \Sigma,Q,\delta,q_0,F \rangle$, with $\Sigma$ a finite alphabet, $Q$ a set of states, $\delta$ a transition function, $q_0$ an initial state, and $F\subseteq Q$ a set of accepting states.

Take $Q=F=\{q_0\}$ with $\delta(q_0,\sigma)=q_0$ for every $\sigma$. This DFA accepts every string, since it's run is always of the form $q_0,q_0,q_0,...,q_0$, and $q_0\in F$.


Reducing 3-coloring problem to trio representatives

Let $G = (V,E)$ be an instance of $3$ coloring. Construct an instance $\phi$ of 3-SAT as follows.

For each vertex $v \in V$ create $3$ variables $v_a, v_b, v_c$ representing the $3$ possible ways to color of $v$.
For each vertex $v \in V$ create the clauses $(v_a \vee v_b \vee v_c) \wedge (\overline{v_a} \vee \overline {v_b}) \wedge (\overline{v_b} \vee \overline {v_c}) \wedge (\overline{v_c} \vee \overline {v_a})$. This encodes the fact that $v$ must be colored by exactly one color.
For each edge $(u,v) \in E$ create the clauses $( \overline{v_a} \vee \overline{u_a} ) \wedge ( \overline{v_b} \vee \overline{u_b} ) \wedge ( \overline{v_c} \vee \overline{u_c} )$. This ensures that $u$ and $v$ cannot be given the same color.

Clearly the above reduction can be performed in poylnomial-time and ensures that there is a satisfying assignment to $\phi$ iff there is a 3-Coloring for $G$.

Now transform the instance $\phi$ of 3-SAT into an equivalent of instance $\phi'$ of 1-in-3 SAT  (see here for the definition of 1-in-3 sat and the reduction from 3-SAT).

We have hence shown that 3-Coloring is polynomial-time reducible to 1-in-3 SAT.
It turns out that 1-in-3 SAT is exactly your problem: the set of students is the set of variables and, for each clause $\{x_i, x_j, x_k\}$ you create a group containing students $x_i$, $x_j$, and $x_k$. Setting a variable to true corresponds to selecting the corresponding student as a leader.


To show it's decidable, you just need to give some effective procedure to decide the language. While giving a TM is a pretty straightforward way to do this, it's not the only way. A much easier way to show this language is decidable is to give plain-old pseudocode for an algorithm to decide the language. Consider this:

AcceptsPermutation(
    word : string,
    Accepts : string -> Boolean)
1. permutations = GenerateAllPermutations(word)
2. result = false
3. for each permutation in permutations do
4.     if Accepts(permutation) then result = true
5. return result

In the above pseudocode, Accepts is a function that accepts the target language. Since the target language is decidable, this function is guaranteed to exist; in fact, you have a TM that computes it (or at least, you have something close).

If you can produce pseudocode to generate all permutations of a word, then you're already done. Consider the following:

GenerateAllPermutations(word : string)
1. if length(word) <= 1 then return {word}
2. else then
3.     result = {}
4.     for n = 1 to length(word) do
5.         first = word[n]
6.         rest = GenerateAllPermutations(word[1...n-1] + word[n+1...length(word)])
7.         for each permutation in rest do
8.             result.add(first + permutation)
9.     return result

Apologies if that isn't quite right... with luck, it's enough to convey the idea.

Suppose you really, really want to stick to Turing Machines. We can still make this problem a lot easier by relaxing the restrictions. Consider a multi-tape, multi-TM scenario: one TM reads the input tape, and begins writing permutations to an auxiliary tape. Once a permutation is written, the TM stops, activates a second TM on the new tape, and waits for the answer. If the TM accepts, so do we; otherwise, write the next permutation to the tape. If we run out of permutations to write, reject.

The TM on the second tape is the TM we assume exists since the language $L$ is decidable. All you need now is a $TM$ that can write permutations to a second tape. We might imagine a single-tape TM that works like the above algorithm... it might make the tape look something like this:

Someword_Omeword_Meword_Eword_Word_Ord_Rd_D_
Someword_Omeword_Meword_Eword_Word_Ord_rD_R_
...
someworD_somewoR_somewO_someW_somE_soM_So_O
someworD_somewoR_somewO_someW_somE_soM_sO_S_

Very roughly, the way to get the tapes to look like this is to:

Write out the initial one by capitalizing the first letter, scanning to the end, adding a blank, copy all the lower-case letters between the last two blanks, and repeat until nothing is copied.
Scan to the front; then, scan right, copying each upper-case letter to the second tape as a lower-case letter, until you see two blanks in a row.
Run the second TM on the second tape, to see if that's an accepted permutation.
Clear the second tape.
From the end of the first tape, scan backwards until you see a lower-case letter preceding a blank, erasing anything you see. When you do see a lower-case letter right before a blank, scan left until you see an upper-case letter; change it to lower-case, move right, and change that letter to upper case. Move to the second blank space to the right. Then, proceed to recreate the permutation string as in (1).
Continue in this way until, while scanning left, you see two blanks in a row. This means you've erased the entire tape without finding a matching permutation; since this procedure tries all permutations, you're done.

To make sure you've got it, try to work out the 3rd and 4th permutation strings generated by the above method, as well as the 3rd and 4th from last strings. They should be those given below:

...
Someword_Omeword_Meword_Eword_Word_oRd_Od_D
Someword_Omeword_Meword_Eword_Word_oRd_oD_O
...
someworD_somewoR_somewO_someW_somE_sOm_Sm_M
someworD_somewoR_somewO_someW_somE_sOm_sM_S
...


Is L={|M is a TM and L(M) is uncountable} decidable?

This is somewhat of a trick question. What you are missing is that there are no uncountable languages over a finite (or even countable) alphabet. This should be enough information to answer it.

(I initially gave the entire answer away, but edited it out after considering a bit.)


Short and slick proof of the strong duality theorem for linear programming

Probably not. Here is a conceptual argument based on

Farkas Lemma:
Exactly one of the following alternatives has a solution:

  $Ax \le b$ and $x \ge 0$
  $y^TA\ge 0$ and $y^Tb < 0$

Now let $\delta$ be the optimal objective value of the primal.
Let $\epsilon > 0$ be arbitrary.
Let  $A'$ to be $A$ with an additional $-c^T$ as the last row.
Let $b'$ to be $b$ with an additional $-\delta - \epsilon$ as the last value.

The system $A'x'\le b'$ has no solution.
By Farkas, there is a $y' = (y,\alpha)$ such that:

  $y^TA\ge \alpha c$ and
  $y^Tb < \alpha (\delta + \epsilon)$.

Note that if $\epsilon  = 0$ we are in the other alternative of Farkas.  Therefore $\alpha > 0$.

Scale $y'$ so that $\alpha = 1$.
$y$ is dual feasible.
The weak duality implies $\delta \le y^Tb < \delta + \epsilon$.


Is the punctuation part of the alphabet?

Yes, for a couple of reasons.

In natural language, punctuation changes the parsing and meaning of sentences. The classic example is "The panda eats shoots and leaves" (describing its diet) has a different meaning than "The panda eats, shoots, and leaves" (describing its violence before it departs). A parser should, in theory, generate different parse trees for these two sentences.
In formal languages, punctuation doesn't really exist as an entity separate from other symbols. So unless adding and removing punctuation from a word NEVER changes its membership in a language, you want to consider it, since any decision procedures will need to know about this.

For formal languages, we can't ignore that sometimes, what you call punctuation, might change the properties of the language.

For instance, it's easy to accept the set $\{ w.w^R \mid w \in \Sigma^* \}$ with a deterministic pushdown automaton. But remove the $.$ character as a delimiter, and we need non-determinism to guess where the end of the first string is, and where its reversal starts.


Detect if a sentence is in passive voice

I recommend you look at methods in the NLP literature for parsing a sentence and identifying its structure, classifying the tense of the sentence and the words present in it, and identifying the subject and object of the sentence.  That should help you build a more accurate classifier.  If you extract suitable features, given the parse tree, and then apply a suitable machine learning algorithm, you might get a more effective classifier.


Matrix for modular exponentiation in Shor's algorithm

Note that Shor's algorithm doesn't require modular exponentiation. All you need is (controlled) modular multiplication.

There are two steps to getting the matrix for modular multiplication:

Write a function to turn any permutation into a matrix.
Apply it to the permutation $a \rightarrow a \cdot k \pmod{r}$.
(Optional) Instead of making that matrix and multiplying by it, save massive execution time by just applying the permutation directly.

For step 1, just have a function like this:

import numpy as np

def make_permutation_matrix(n, permutation):
    r = np.zeros((n, n))
    for i in range(n):
        r[permutation(i), i] = 1
    return r

Then for step 2, use it:

import math
k = pow(base, exponent, modulus)
n = math.ceil(math.log(modulus, 2))
mul_matrix = make_permutation_matrix(
    2**n,
    permutation=lambda x: x*k % modulus)


Do all recursive problems have optimal substructure?

I think there is some confusion in terminology here. Part of the problem is what we mean by problem and algorithm. But there is more to it:

Textbooks like CLRS introduce the notion of optimal substructure as a property of problems (and not algorithms directly). That's because an algorithm often transforms a problem statement into other problem/s and, as a result, an algorithm may establish a link between problem solutions with subproblem solutions. Indeed, CLRS defines optimal substructure as follows: "A problem exhibits optimal substructure if a solution to the problem contains solutions to its sub-problems". While it doesn't say this directly, the term "contains" implies through an algorithm.
Just because a problem (and actually all problems) may accept a recursive formulation or algorithm, it doesn't of course mean of course that every algorithm to solve it is indeed recursive (this is in relation to Yuval Filmus's answer). For a particular algorithm to be recursive, it must call itself recursively.
Similarly, just because an algorithm may involve some form of iteration or even recursion (e.g. in some of its subroutines), it doesn't mean that the algorithm is actually solving the original problem recursively.
Last but not least, just because an algorithm is recursive, it does not mean it solves a problem with optimal substructure where solutions to the original problem are the result of combining solutions to sub-problems of the same type. For example, if you write an algorithm to sort numbers, and this algorithm sorts the input and then once it's done sorting, it e.g. calls itself recursively with a NOP in each call for some depth of recursion, that does not mean that the algorithm is actually building the sorted sequence (the solution to the stated problem) from solutions to subproblems, and thus exploiting the optimal substructure of the problem.


Solving recurrence relation with minimum and factorial

Summary

It is not true that the minimum can always be obtained at $c=\lceil n/2\rceil,a=c!,b=(n-c)!$. Here is the smallest counterexample, $$T(5,49) = T(1,1) + T(4,1) + T(5,48) = 3 \not=5=T(3,6)+T(2,2)+T(5,12).$$ Instead, the minimum can always be obtained at $c=1$, $a=1$,  $b=2(n-2)!.$

The following neat formula conjectured in the question is correct.
$$T(n,m)=\begin{cases}
1 & n=1 \text{ or }f(n,m)\leq 0,\\
3+2\Big\lfloor\dfrac {f(n,m)-1}{g(n)}\Big\rfloor &\text{otherwise},
\end{cases}$$
where $f(n,m)=m-2(n-1)!$ and $g(n)=\begin{cases}1 &\text{if }n<3,\\ 2(n-2)! &\text{otherwise.}\end{cases}$

Observations

$T(n,m)=1,$ if $n=1$ or $m\le 2(n-1)!$.
$T(n,m)$ is nondecreasing with respect to $m$.
$T(n,m)\ge3$ if $m\gt 2(n-1)!$.
$T(2,m)=\begin{cases}
1 & m\le2,\\
2m-3 & \text{otherwise}.\end{cases}$
If $n=3,4,5$, then the conjectured formula is correct.
The following proposition $p(n,j)$ is true for all $n\ge3$ and $j\ge0$.
$$\text{If $n\ge3$ and $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor$ for some $j\ge0$ and $m$, then $T(n,m)=3+2j.$}$$

The conjectured formula is the same as the combination of observations 1, 4, and 6.

All observations above except observation 6 can be proved easily, although observation 5 might take a while to sort out case by case.

Let $S(n,m,a,b,c)=T(c,a)+T(n-c,b)+T(n, m-ab)$. Then for $m\gt 2(n-1)!$,
$T(n,m)=
\min\limits_{a,b,c\geq 1,\ c\le\frac n2\\a\leq c!,\ b\leq(n-c)!}S(n,m,a,b,c).$ The reason why we can replace the condition $c\le n-1$ by $c\le \frac n2$ is that $(n,m,a,b,c)=(n,m,b, a, n-c)$.

Proof of observation 6 by well-founded induction

Here are the steps. Steps 1 and 2 are the induction bases while step 3 is the induction step.

Suppose $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor=0$, i.e., $2(n-1)!\lt m\le2(n-1)!+2(n-2)!$. Since $m\gt 2(n-1)$, $$T(n,m)\ge3.$$ On the other hand, $$T(n,m)\le S(n,m,1,2(n-2)!,1)=1+1+1=3.$$ So $T(n,m)=3$, i.e., $p(n,j)$ is true when $j=0$.
Observation 5 says that $p(n,j)$ is true for $n=3,4,5$.
Let $n\ge6$ and $j\ge1$. As induction hypothesis, suppose $p(x,y)$ is true for all $x\le n$ or $x=n$ and $y\lt j$, i.e.,
$T(x,y)=3+2\lfloor\frac{f(x,y)-1}{2(x-2)!}\rfloor$, which implies, by the definition of $\lfloor\cdot\rfloor$, $$(x-2)!(T(x,y)+2x-5)<y\le (x-2)!(T(x,y)+2x-3).$$

We will prove that $p(n,j)$ is true, i.e., $T(n,j)\le 3+2j$.

Let $j=\lfloor\frac{f(n,m)-1}{2(n-1)!}\rfloor$ for some $m$.

Proof for $T(n,m)\le 3+2j$

By induction hypothesis, we know that $T(n, m-2(n-2)!)=3+2(j-1)$. Hence,
$$T(n,m)\le S(n,m,1,2(n-2)!,1)=1 + 1 + T(n, m-2(n-2)!)=3+2j.$$

Proof for $T(n,m)\ge 3+2j$

Because $T(n,m)$ is nondecreasing with respect to $m$ (observation 2), we will assume $m=2(n-1)!+2(n-2)!j+1$, the smallest value possible such that $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor.$

We will prove that $S(n,m,a,b,c)\ge 3+2j$ for all valid choices of $(a,b,c)$.
The case when $c=1$ or $c=2$ is relatively easy. From now on assume $3\le c\le \frac n2$.

Let $A=T(c,a)$ and $B=T(n-c,b)$. The case when $A=1$ or $B=1$ is much easier to prove. Now assume $A,B\ge2$.

Since $c<n$, we have $a\le(c-2)!(A+2c-3)$.
Since $n-c<n$, we have $b\le(n-c-2)!(B+2n-2c-3)$.
Since $ab\ge1$, we have $\lfloor\frac{f(n,m-ab)-1}{2(n-2)!}\rfloor<j$, so we can apply induction hypothesis to yield the first equality below.

Since $T(n,m)$ is nondecreasing w.r.t $m$,
$$\begin{aligned}
&S(n,m,a,b,c)\\
&\ge A+B+T(n,m-(c-2)!(A+2c-3)\,(n-c-2)!(B+2n-2c-3))\\
&= A+B+3+ 2\lfloor\frac{f(n,m-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))-1}{2(n-2)!}\rfloor\\
&= 3+2j+ A+B +2\lfloor\frac{-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))}{2(n-2)!}\rfloor\\
&\gt 3+2j+ \frac{(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3)}{(n-2)!}(h(c,A,B)-1) \\
\end{aligned}$$

where
$$h(n,A,B,c)=\frac{(A+B-2)(n-2)!} {(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3)}.$$
Since $n-c<n$, induction hypothesis yields the second equality below.
$$\begin{aligned}
B&=T(n-c,b)\le T(n-c, (n-c)!)\\
&=3+2(\frac{(n-c)(n-c-1)}2-(n-c-1)-1)\\
&=(n-c)(n-c-3)+3.
\end{aligned}$$
Since $n\ge6$ and $c\ge3$, $(n-2)!\ge (n-2)(n-3)(n-4)(c-2)!(n-c-2)!.$
Since $n\ge6$, $c\le \frac n2$ and $A,B\ge2$, $(n-2)(A+B-2)\gt A+2c-3.$

$$\begin{aligned}h(n,A,B,c)
&\ge\frac{(A+B-2)(n-2)(n-3)(n-4)}{(A+2c-3)(B+2n-2c-3)}\\
&\ge\frac{(n-3)(n-4)}{B+2n-2c-3}\frac{(n-2)(A+B-2)}{A+2c-3}\\
&\ge\frac{(n-3)(n-4)}{(n-c)(n-c-1)}\frac{(n-2)(A+B-2)}{A+2c-3}\\
&\gt1
\end{aligned}$$

So $S(n,m, a,b,c) \gt 3+2j.$

The proof is complete. By the way, the proof for $T(n,j)\le 3+2j$ shows that the minimum can always be obtained at $c=1,$ $a=1,$ $b=2(n-2)!.$

Exercises

Exercise 1. Prove the formula for $T(2,m)$.

Exercise 2. (Observation 5) Prove the formula for $T(3,m)$, $T(4,m)$, and $T(5,m)$. Hint, the proof of observation 6 above might be helpful.

Exercise 3. Let $T_1$ be defined over $\Bbb N_{+}\times\Bbb N_{+}$.
$$T_1(n,m)=\begin{cases}
1, & n=1\text{ or }m\leq (n-1)!\\
\min\limits_{a,b,c\geq 1,\ c\le n-1\\a\leq c!,\ b\leq(n-c)!}T_1(c,a)+T_1(n-c,b)+T_1(n,m-ab), & \text{else}
\end{cases}$$
Show that $$T_1(n,m)=\begin{cases}
1 & n=1 \text{ or }m\le (n-1)!,\\
3+2\Big\lfloor\dfrac {m-(n-1)!-1}{(n-2)!}\Big\rfloor & \text{otherwise}.\end{cases}$$