Is a 2 address machine more likely to follow a RISC or CISC design?

The problem is that the terms RISC and CISC are marketing terms, not science or engineering terms.  The terms are supposedly acronyms for "Reduced Instruction Set Computing" and "Complex Instruction Set Computing."  Your assumption that 3 addresses is much more complicated than 0 addresses is logical, but there is no logic here, and typically 3-address instructions are associated with RISC and 2-address instructions are associated with CISC (and 1-address and 0-address instructions aren't very common any more, so aren't associated with either RISC or CISC).

The term RISC is generally associated with instruction sets that have the following characteristics:

Fixed width instructions.  Usually 32-bits or 16-bits.  This makes it easier for the instruction decoder to find the boundaries between instructions.  In CISC machines, by contrast, the different instructions can range in length from 8-bits to as much 64-bits.  This makes the job of the instruction decoder somewhat harder in CISC machines, but can result in programs consuming less memory.
Fewer operand addressing modes.  In a RISC machine typically each operator (add, sub, jmp, load) has only one available addressing mode for its operands (the a, b, c, d, and e in your picture.)  Typically for arithmetic type instructions (add, sub, xor, ...) the only available addressing mode is register direct.  The source operands are found in registers, and the result of the computation can only be placed in a register. Load and store type instructions typically have one operand that is register direct and the other operand is register indirect plus offset.  Jump and branch type instructions will typically have a target operand that is pc relative.   There will typically also be a few jump and branch type instructions with a register indirect target, and sometimes a jump instruction with an absolute target operand.  The smaller number of operand addressing modes is typically the only way in which "RISC" instruction sets are actually reduced (compared to "CISC" instruction sets).  The reasoning, again, has to do with trying to keep the instruction decoder as simple as possible in RISC machines.  The simple operand addressing modes are easier to implement in a simple pipeline, and so the decoder in modern CISC machines often has to do extra work to crack instructions with complex operand modes into sequences of micro-operations that are more like RISC instructions.
There is a tendency for RISC architectures to have more register names available.  Many RISC architectures have 32 registers, while many CISC architectures have only 8 or 16.  This again has to do with making it somewhat simpler to exploit instruction-level parallelism with a simple pipeline.  Having more available register names makes it possible for the compiler to use different register names for unrelated computations, without requiring the hardware to do register renaming.
RISC architectures tend to have "3-address" instructions, while CISC architectures tend to have mostly "2-address" instructions.  The notion of "3-address" vs. "2-address" is also somewhat fuzzy (and somewhat mis-named).  Every add instruction has 3 operands, 2 source operands and 1 destination operand.  The real distinction is whether those operands are explicit or implicit.  In a so-called "3-address" instruction you make all 3 operands explicit.  In a so-called "2-address" instruction you make the destination operand explicit and one of the source operands explicit.  The third source operand is implicit: it is always the same address as the destination operand.  In a so-called "1-address" instruction only one of the source operands is explicit.  The other source operand is implicitly either an accumulator register or the top of the stack, as is the destination operand.  Finally in a "0-address" instruction all the operands are implicit (usually the two source operands are the top two values on the stack and the destination goes back on the top of the stack.)

To sum up: these are all marketing terms, and don't really mean much.  The important concepts have to do with the relationship between different instruction-set design choices and how those choices make it easier or harder to implement hardware pipelines.


If i rightly assume that you are trying to convert the E-R diagrams to relations (tables), then the procedure to convert a many-to-many relationship into relations is to create one more table, apart from the 2 tables that you will create for the 2 entities (waiter-drinks and waiter-shirt). This new table created for the relationship will have its attributes (columns) as the PKey of the constituting entities. In your case, this table will contain 3 attributes; namely waiter_number, drink_number and shirt_number.

Had you been working on a one-to-one or one-to-many relationship, you would augment one more column to the table on many sides instead of creating another relation.


Is the following statement about turing machines true?

This is an interesting statement, but it is not true. I'll give a proof sketch and leave the construction of the actual machines to you (read as: I am too lazy :) ). For example, take two functions

$f : \mathbb{N} \setminus \{0\} \to \mathbb{N}, n \mapsto n^2$

$g : \mathbb{N}\setminus \{0\} \to \mathbb{N}, n \mapsto 2^n$

and two turing machines $M_f, M_g$ which compute $f$ and $g$, respectively. Without loss of generality, we may exclude $0$ because I think it might require special handling in $M_g$, but this depends on the actual construction of the turing machine - it does not matter this way.

It is safe to assume that minimal turing machines for $f$ and $g$ would need each of its transitions for any value bigger than $1$ since they both have to implement some kind of looping scheme. This comes from the fact that $f$ and $g$ can be defined primitive-recursively, where $0$ and/or $1$ are the recursion base cases (depending on your exact definition). Now if we look at the values of these two functions:

$\begin{align}
n&:& &1,& &2,& &3,& &4,& &5,& ... \\
f(n)&:& &1,& &\color{green}{4},& &9,& &\color{green}{16},& &25,& ... \\
g(n)&:& &2,& &\color{green}{4},& &8,& &\color{green}{16},& &32,& ... \\
\end{align}$

We see that for an input set $I = \{ 2, 4 \}$, then $M_f$ and $M_g$ compute the same value for all input values, and since $\forall n \in I : n > 1$, they would also need all of their transitions. Still for any input value $n \geq 1, n \notin I$, they would differ.

To generalize: Take any two sequences of numbers which are recursively defined and computable and also equal in at least two places, then the statement does not hold.

I overcame my laziness and did one turing machine for the calculation of $2^n$ in unary. The code can be executed on this turing machine simulator to check that for inputs $11$ and $1111$, every state transition is required.

; Compute 2^n in unary
; First go to the end of the input string and write a single 1.
; The tape content is then <input>01
 0 1 1 r 0 ; Move right until we are at the end of the input string.
0 _ 0 r 1 ; Write 0 separator
1 _ 1 l 2 ; Write an initial 1, since this is the value of 2^0.

; Then rewind to the beginning
2 1 1 l 2 ; Keep moving left without altering 1s
2 0 0 l 2 ; Keep moving left without altering 0s
2 _ _ r 3 ; We move back to the start.

; Now we double the string after the separating zero until
; there are no more 1s in the beginning (= decrement counter until 0)
3 1 _ r 4 ; Remove the first 1, this is equal to decrementing the counter
3 0 _ r halt ; if there are no more 1s, we are finished.
4 1 1 r 4
4 0 0 r 5 ; Move right till the separator is found
5 1 1 r 5 ; Move to the end of the result string
5 _ _ l 6
6 1 _ r 7 ; And replace the last 1 with a blank, the initial position marker.
7 _ 1 l 8

; Now comes the actual doubling
8 1 1 l 8 ; Move left until the blank marker is found
8 _ 1 l 9 ; Move left until the blank marker is found
9 1 _ r 10 ; Shift the blank marker to the left
10 1 1 r 10 ; Move to the end of the string...
10 _ 1 l 8 ; ... and write a 1.
9 0 0 l 11 ; Once we hit 0, we are finished doubling

; And again rewind to the beginning
11 1 1 l 11 ; Keep moving left without altering 1s
11 _ _ r 3 ; We move back to the start.

The computation of $n^2$ is similar, except that for doubling the output $n$ times, you add $n$ to $n$ exactly $n$ times.


Your solution is fine.  There are multiple ways to prove this fact, all of them valid/correct.  So your approach is valid, and it's possible that the solution from your class is also valid: that's not a contradiction.

Let me give you one piece of advice for structuring your proof in the future, though.  In the argument you sketched in the question, you are "working backwards": you start from the statement you wish were true (that $c_1 n^2 \le 2 n^2 -4n + 7 \le c_2 n^2$), and then you try to derive what needs to be true about $c_1,c_2$ for your wish to hold true.  Experience has proven that that kind of reasoning is error-prone, though: it's easy for you to make a mistake along the way.  It is also hard for others to check.

When you write up your proof, I suggest you do the reasoning in the opposite direction.  Start from what you know is true, and then derive the implications of that, ending with the conclusion that $c_1 n^2 \le 2 n^2 -4n + 7 \le c_2 n^2$.  This better matches how people think and makes it easier for the reader to understand what's going on.  And the purpose of a proof is to communicate an idea to the reader, so the proof should be structured to make the reader's life easier: to make it as easy as possible for the reader to verify that the proof's reasoning is correct and valid.  It's just like a good book; good writing is chosen to make life good for the reader.  Proofs are the same way.  And, ultimately, this will benefit you too: in my experience, if you follow this approach, then you're less likely to make a subtle mistake in your proof.

So, a better proof outline would be to show that $n^2 \le 2n^2 - 4n + 7$ holds for all $n\ge 2$ (because such-and-such), and show that $2n^2 - 4n + 7 \le 2n^2$ holds for all $n\ge 2$ (because blah-de-blah), and then conclude that $2n^2 - 4n + 7 \in \Theta(n^2)$.  I realize this kind of proof is harder to write, because you need to know the value of $c_1,c_2$ to use before you can start writing down this style of proof.  But you know what?  That's OK.  You can do a side calculation, on scratch paper, to figure out what value of $c_1,c_2$ to use.  Don't show us that side calculation; just figure out what value of $c_1,c_2$ would be good ones to do, and then start the proof with you pulling $c_1=1,c_2=2$ magically out of thin air, and demonstrate that your choice is valid.  This style of proof will be better for you, and better for the reader.


Comparing Selection, Insertion, and Bubble Sorts for database application

A "database" that isn't ashamed of calling itself "database" will have hundreds of thousands or millions of records. Any algorithm where the number of operations is quadratic except for special cases is totally unsuitable. So the answer is "none of the above".

You'd do some serious measuring to decide whether to just create an in-memory index (that means you don't sort anything at all, but you just record #1 = 7 at record 3, #2 = 10 at record 6, ...), or use merge sort or Quicksort. Quicksort only if you have a backup, in case there's a problem during the sort.


Complexity-theoretic difficulty of checking the value of $\pi(x)$?

This is very much an open problem. I'll sketch some classes that the problem could "naturally" fit in.

Your definition is somewhat awkward to work with, the problem is hard to fit in to any existing complexity class. The language you've defined is the intersection of the languages $\{(x,n)|\pi(x)\leq n\}$ and $\{(x,n)|\pi(x)\geq n\}$. So if for instance $\{(x,n)|\pi(x)\leq n\}$ was in class $K$ then $\{(x,n)|\pi(x)\geq n\}$ would be in $coK$. This makes giving a characterization of the language you've defined hard because one would have to state "the intersection of a language in $K$ with a language in $coK$" to give the tightest bound.

The problem "Compute $\pi(X)$" is a problem in $\#P$, where $\#P\subseteq FPSPACE$ is the class of problems of the form "Compute the number of accepting paths of a nondeterministic, polynomial TM". Clearly we can construct a nondeterministic TM that guesses a number $q \leq x$, and then (with AKS) tests whether $q$ is prime.

A decision variant of $\#P$ is $PP$, which is the class of languages that are of the form: "Given a nondeterministic polynomial TM, do at least half the computation paths accept?". Both $\{(x,n)|\pi(x)\leq n\}$ and $\{(x,n)|\pi(x)\geq n\}$ are probably reducible to a problem in $PP$ (by doing some fudging to the aforementioned TM to balance out the number of accepting paths).


Are there adversarial inputs for randomized quicksort?

There are implementations of Quicksort (the partitioning algorithm, specifically) which deal badly with duplicates. No matter how much you randomize -- shuffling the input, random choice of the pivot, random choice of the pivot with sampling, ... -- if all entries are the same (or there are only constantly many distinct values), these bad implementations will result in worst-case behaviour, always.

You can find details e.g. here and in the literature.

Note bene: The reason why many TCSists would claim the opposite with a passion it that they forget that most classical analyses are performed under permutation models. That does not give the whole truth, though, particularly if you use sorting in practice. Duplicates are relevant, for instance if you sort lists of binary values.


Why precondition strengtening is sound in Hoare logic

The triple $\{Q\}C\{X\}$ states that if $Q$ holds, then after executing $C$, the condition $X$ holds. Now suppose that $\{Q\}C\{X\}$ and that $P \Longrightarrow Q$. We will prove that $\{P\}C\{X\}$. Indeed, suppose that $P$ holds. Since $P \Longrightarrow Q$, also $Q$ holds. Hence if we execute $C$, then $X$ will hold. Altogether, we see that $\{P\}C\{X\}$ is valid.

An example can also be helpful. If we know that $\{x=1\}x\gets x+1\{x=2\}$ then we certainly know that $\{x=y=1\}x\gets x+1\{x=2\}$.


What does "order of growth decreases exponentially" mean?

I think it just wants a recurrence for a sequence where the even-numbered terms increase exponentially and the odd-numbered terms decrease exponentially. Talking about the order of growth changing sounds like some kind of second-derivative property but I think it’s just poor phrasing.

To be absolutely sure, you’d have to ask the person who wrote the exercise.


Based on your description, I take it that an element product is taking one element from each array and multiplying?

You don't really need to multiply or use prime numbers which might overflow (but not too much for your constrains I suppose, and is a cute solution :-)).

Suppose the arrays were of fixed size $k$ (You can pad the arrays to achieve this, and based on your constraints, won't be too much of a problem).

Then you want to map all possible tuples $(x_1, x_2, \dots x_n)$ where $0 \le x_i \lt k$ to unique integers.

The mapping you need: Interpret the tuple as an integer in base-$k$.

If arrays are shuffled you can still change the $ind$ function and remap the digits according to that.

(or did you try that and didn't work for some reason?)


Everything becomes much simpler if when $n$ is odd we stop the sum at $\lfloor n/2 \rfloor$, and when $k$ is even we discount the term corresponding to $k/2$ by a half. In that case you can write
$$ 2T(k) = \sum_{i=1}^{k-1} \binom{k}{i} T(i) T(k-i) $$
and so, putting $T(0) = 0$, we get that for $k \geq 2$,
$$ 2T(k) = \sum_{i=0}^k \binom{k}{i} T(i) T(k-i). \tag{1}$$
(When $k = 1$ this reads $2T(1) = 0$.)

Now define the exponential generating function
$$ P = \sum_{n \geq 0} T(n) \frac{x^n}{n!}. $$
Put $T(1) = c$. The identity (1) implies the equation
$$ 2(P-cx) = P^2. $$
Solving the quadratic, we obtain
$$ P = 1 - \sqrt{1 - 2cx} = 1 - \sum_{n \geq 0} \frac{(2n)!}{(1-2n)(n!)^24^n} (2cx)^n = \sum_{n \geq 1} \frac{(2n)!(c/2)^n}{(2n-1)n!} \frac{x^n}{n!}. $$
We conclude that for $n \geq 1$,
$$
T(n) = \frac{(2n)!(c/2)^n}{(2n-1)n!} \sim \frac{1}{\sqrt{2} n} \left( \frac{2c}{e} n \right)^n.
$$
The first few terms (starting with $T(1)$) are
$$
c,c^2,3c^3,15c^4,105c^5,\ldots
$$


Creating a temp array vs passing one in Mergesort

Memory management would be the only reason. In the second approach, you need to create $2n$ arrays total size of about $2n\log{n}$. If it is happening with a large $n$ or very small computing unit, you will face serious performance issues.
Finally, you have to be careful with memory when you work with recursive functions. It easily cause memory overflow.


Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?

The idea is to implement the following regular expression:
$$
\sum_{\sigma \in \Sigma} \Sigma^* \sigma \Sigma^* \sigma.
$$
Details left to you. Number of states is $|\Sigma| + 2$.

Let us show that $|\Sigma| + 2$ is the optimal number of states, using the fooling set method. We have to give $|\Sigma|+2$ pairs $(x_i,y_i)$ such that $x_iy_i \in L$ (here $L$ is your language), but for each $i \neq j$, either $x_iy_j \notin L$ or $x_jy_i \notin L$. For each $\sigma$, we have the pair $x_\sigma = y_\sigma = \sigma$. For some arbitrary $\tau \in \Sigma$, we have the two pairs $x_\gets = \tau\tau, y_\gets = \epsilon$ and $x_\to = \epsilon,y_\to = \tau\tau$. You can check that indeed $x_iy_i \in L$ for all $i$. In the other direction:

If $\sigma_1 \neq \sigma_2 \in \Sigma$ then $x_{\sigma_1} y_{\sigma_2} \notin L$.
If $\sigma \in \Sigma$ then $x_\sigma y_\gets, x_\to y_\sigma \notin L$.
Similarly, $x_\to y_\gets \notin L$.


Algorithm to compute sum of cost of all path between pair of unique vertices of a tree

Let's build some recursive function. We start picking any vertex of the tree $T$ and call it $R$ as root. If $R$ was removed, you would get a forest of several sub-trees. Every subtree $T_k$ has a vertex $k$ connected to $R$ in $T$.

Now there are 3 types of paths contributing to the sum of cost of paths $N(R)$:

$I(R)$, the cost of all inner paths of the sub-trees (computed with recursion),
$S(R)$, the cost of all paths starting on $R$: $(R, i)$ for any $i \ne R$,
$C(R)$, the paths between the different sub-trees.

Once you recursively have computed the 3 components for each of these vertex $k$ in its own sub-tree $T_k$. Let's call $E(k, R)$ the cost of the edge $(k, R)$ and $n_k$, the number of vertices in $T_k$.

You can compute $N(R)$:

$I(R) = \sum_k N(k)$
$S(R) = \sum_k S(k)+n_k E(k, R)$,
$C(R) = \sum_{k1, k2, k1 \ne k2}(S(k1)+n_{k1}E(k1, R))(S(k2)+n_{k2}E(k2, R))$

Note that if $R$ is connected to only one other vertex, $C(R) = 0$. You also can track $n$ with $n_R = \sum_k n_k + 1$.

This has a linear time and space complexity.


Algorithm to determine a set given the size of its intersection with sets you choose

You are asking two questions. I will only answer the first, ignoring the fact that $|T|$ is much smaller than $|U|$. Your problem is very similar to the one tackled in this question. The same lower bound of $\Omega(n/\log n)$ holds here as well, where $n = |U|$. The same (apparently) matching upper bound also holds, since you can simulate a Hamming distance query using your kind of query.


Show how a sentence can be produced from a grammar (Dragon book 2.1)

$$\begin{align*}
S \Rightarrow & SS* \\
  \Rightarrow & SS+S* & \text{(leftmost derivation )} \\
  \Rightarrow & aS+S* \\
  \Rightarrow & aa+S* \\
  \Rightarrow & aa+a* \\
\end{align*}$$


Computer Organization and Assembly Language Programming

Learning assembly language will be helpful for you in understanding computer architecture, because the CPU is designed to run the instructions that are part of its assembly language.  So, to understand what the CPU is doing and why it was designed that way, you need to know what operations it is designed to support.


difference between minus and subtract microoperation

Suppose we're working with unsigned bytes, e.g. modulo 256.

Let's say R1 = 100 and R2 = 70. Direct subtraction should give us 100 - 70 = 30:

01100100
01000110 -
========
00011110

Modulo 256, subtracting 70 is the same as adding 256 - 70 = 186, because -70 is +186. The complement of 70 is 255 - 70 = 185, which is just one less. Therefore, the following sum produces 100 + 185 + 1 = 286 which is the same as 30 (modulo 256). Of course, the ninth bit 'falls off' when doing 8-bit arithmetic, so we get 30 as a result.

 01100100
 10111001
 00000001 +
 ========
100011110

So both methods give the same result, just in a different way.


Increasing every starting edge by a constant, then the shortest path tree remains the same?

I think you can prove it by counter-example.

Assume your SPT (shortest path tree) from the original graph is no longer a valid SPT in the new graph.  That means there's a node $f$ s.t. the path $(s, n_1, n_2, ..., f)$ in your SPT is no longer a shortest path, meaning some other path $(s, v_1, v_2, ..., f)$ (whose length wasn't shorter before) now has a shorter length.

Now show that's impossible by calculating how much the lengths of those two paths have increased.


What is the best algorithm known to learn the regular expression from a set of positive examples?

I have wondered something similar and failed to find much in the way of satisfying answers in the literature.  Here is what I tentatively came up with.

It seems perhaps what we need is some kind of regularization.  If $\theta$ is a model (say, a regular expression), let $c(\theta)$ denote some measure of the complexity of the model (say, the size of the regular expression).  Also, let $\ell$ be a loss function, so that $\ell(\theta(x),y)$ denotes the loss incurred based on the model's prediction on string $x$, given that the ground-truth label is $y$.  Given a training set $(x_1,y_1),\dots,(x_n,y_n)$, define the total loss as

$$L(\theta) = \sum_i \ell(\theta(x_i),y_i) + \lambda c(\theta),$$

for some hyperparameter $\lambda>0$.

Then we could frame the learning task as finding a model $\theta$ that minimizes $L(\theta)$.

In your case, $\theta$ is a regexp, $c(\theta)$ is the length of the regexp, $x_i$ is a string, $\theta(x_i)$ is true or false according to whether $\theta$ matches $x_i$ or not, and you have only positive examples so all of your $y_i$'s are true.  You could also consider other models as well, such as a finite-state automaton (whose complexity is given by the number of states) or a neural network (e.g., a CNN or RNN).

The term $\lambda c(\theta)$ is a regularization term that penalizes model complexity, and thereby combats overfitting.  Basically, we're applying Occam's razor, that simpler explanations are more likely to be true.  If we omitted this term (or equivalently, set $\lambda=0$), we would indeed overfit and obtain poor generalization: e.g., we might learn the regexp $x_1|x_2|\cdots|x_n$.  If we over-regularize (and set $\lambda=+\infty$, say), then we underfit and might learn the regexp $.*$, which also is not good.  The hope is that the regularization term will find a happy medium between these two extremes.

So now the problem reduces to, how can we solve the optimization problem above?  Unfortunately, I don't know of any good ways to do this, for the case of regexps.

One approach would be to set an upper bound on the size of the regexp, i.e., choose some hyperparameter $s$, and limit consideration to regexps of length $\le s$; then try to find a regexp $\theta$ that minimizes $\sum_i \ell(\theta(x_i),y_i)$ subject to $c(\theta) \le s$.  (This formulation is closely connected to the formulation at the top of the question; the theory of Lagrange multipliers tells us that there is a one-to-one correspondence between $\lambda \leftrightarrow s$ that yields equivalent solutions to the optimization problems.)    Unfortunately, I don't know of any good algorithms for solving this optimization problem, i.e., for finding such a regexp $\theta$ that minimizes this loss.  Perhaps you could use a SAT solver to solve it; I don't know.

Another possibility is to choose a different model.  With CNNs or RNNs, it is easier to fix the size of the neural network architecture (thus implicitly fixing an upper bound on the complexity of the model), and then use gradient descent to find weights $\theta$ that minimize $\sum_i \ell(\theta(x_i),y_i)$.    Or, you could use a DFA instead of a regexp as your model, and then I think there are methods you could use to solve this optimization problem.  In particular, there are known algorithms for using a SAT solver to find whether there exists a DFA with $\le s$ states that matches every string in a given set of strings; and to minimize $\sum_i \ell(\theta(x_i),y_i)$, you culd plausibly repeatedly choose random subsets of $x_1,\dots,x_n$, find a DFA that matches every string in the subset, and check its total loss on the entire training set.

It seems hard to imagine that these are the best one can do, but I haven't been able to find better methods in the literature yet; this is the best I've been able to come up with so far.

Related: https://datascience.stackexchange.com/q/16115/8560.


Non-trivial bin-packing instance with 5 objects

Let's look at two algorithms: Best Fit Ordered, and First Fit Ordered. Both take the items in descending order and put them into a non-empty bin if possible, or into a new empty bin if they don't fit into any existing bin. Best Fit Ordered puts an item into the filled bin with least available space, First Fit Ordered puts an item into the first filled bin with enough space.

Question: Are there five items A ≥ B ≥ C ≥ D ≥ E such that BFO or FFO are not optimal?

If all items fit into one bin then BFO and FFO will fit them into one bin, because both will just put items in the first bin. Both are optimal.

If five bins are optimal then BFO and FFO cannot be non-optimal, since they can't use more than five bins.

If four bins are optimal then there are two items fitting into one bin, therefore D and E fit into one bin, therefore when BFO and FFO finally try to find a bin for E, either four bins are filled and E fits into the bin with D, or there are only three bins filled and E goes into the fourth bin.

So the only cases to consider are those where two or three bins are optimal. I'll consider cases systematically:

A, B and another fit -> 2 bins, BFO and FFO are optimal
A, B fit, C, D, E fit -> 2 bins, BFO and FFO are optimal
A, B fit, C, D, E don’t fit -> 3 bins required, BFO and FFO are optimal.

We now assume A and B don't fit into a bin, so A goes in the first and B in the second:

A, C and another fit -> 2 bins, BFO and FFO are optimal
A, C fit, B, D, E fit -> 2 bins, BFO and FFO are optimal
A, C fit, B, D, E don’t fit: A, D, E don’t fit, A, D or A, E doesn’t help -> 3 bins required -> BFO and FFO are optimal.

We now assume neither A and B, nor A and C, fit into one bin. If B and C don't fit, then A, B, C go in three different bins. 3 bins are optimal, so D and E can be made to fit, and BFO and FFO will both find a way.

So we assume B and C fit in one bin. Both BFO and FFO will fit them in one bin. D  E must also fit into one bin, so if three bins are optimal, then BFO and FFO will find a solution.

If two bins are optimal, then one bin must contain A, one must contain B and C. D and E fit, so BFO and FFO will fit them.


Enumerate the terms resulting from decomposing a number by repeated divisions by 2

Denote the total number of terms by $m = 2^{\lfloor \log n \rfloor}$. Suppose that $m_1$ terms are equal to $1$, and $m_2$ terms are equal to $2$. Thus
$$
n = m_1 + 2m_2 = m + m_2,
$$
from which we find that $m_2 = n-m$ and $m_1 = 2m-n$. So if you arrange the terms in nondecreasing order, the first $2m-n$ would be $1$, and the remaining $n-m$ would be $2$.


Count elements in the real world in constant time by weighing them

Weighing elements works faster than counting them, because the scale is a fully parallel computing device. It sums the weighs of all elements in constant time. Of course you need an infinitely large scale if you want to talk about asymptotic runtimes. In practice your scale can only weigh a constant number of items at once, so your speedup is only a constant factor.

A related algorithm is Spaghetti sort.


General start rule question for a context free grammar

Yes you can apply the second rule you have written if you'd like. Since $S$ is your start symbol, you can apply any of its productions when you begin. It might be clearer if you wrote it as follows (where $|$ denotes or):

  $S \rightarrow 0SS1 \; |\; 1 \; | \; \epsilon$


The language of machines that accepts all palindromes is not Turing recognizable

Let $M_p$ be a TM that decides palindromes with runtime on $x$ at least $|x|$. Given $\langle M \rangle$ construct $\langle M' \rangle$ where $M'$ on $x$ behaves as follows:

Run $M$ on $\langle M \rangle$ and $M_p$ on $x$ in "parallel" (i.e. step by step, on separate cells, e.g. $M$ only uses odd cells, and $M_p$ uses only even cells of the tape).
If $M$ on $\langle M \rangle$ terminates, $M'$ rejects unconditionally.
If $M_p$ on $x$ terminates and $M$ on $\langle M \rangle$ is still continuing the computation at this step, $M'$ terminates the simulation of $M$ and outputs according to $M_p$ on $x$.

Note that $M$ on $\langle M \rangle$ does not halt if and only if $M'$ decides the language of palindromes. (Why?)


If $L$ is a regular language, then $s(L)$ is also regular

First thing you must understand  is that regular expression are closed under union(+), closure(*) and concatenation (.)  . reason being every regex denotes a regular language and regular languages are closed under union, closure and concatenation.

Second thing you should know that if r1 and r2 are regex then the following regex are also regular

r1 + r2
r1.r2
r1* ,r2*

so if you are substituting a regex by another regex it should fall among the above three categories or in simple words you will be able to form the regex(after substitution) with use of above relation. coming to you question the language generated after substitution can be formed using above closed properties over regex. let say r1 = a , r2 =b  then we have

( ((r1.r2) * ) . r2* )  making it regular

one more thing the only operation defined to regex are the above three  and if so any substitution of regex by regex will have
either of the three operation associated with it thus making it regular again


Find all the special graphs which can reduced to the shortest paths graph

Nearest neighbor, nearest insertion, farthest insertion, and cheapest insertion are just some heuristics to get you started. You can also model the problem as a maximum flow integer program.

http://www.ida.liu.se/~TDDB19/reports_2003/htsp.pdf


Predicate Logic - negating the conclusion to prove logical consequence?

The method works in the same way as proofs by contradiction. Suppose you have a set of assumptions $A$ and you want to prove that formula $\phi$ is a logical consequence of the formulas in $A$. One of the ways to do this is as follows.

Put the negation of $\phi$ in your assumptions. So, now $A' = A\cup\{\neg\phi\}$
Show that $A'$ is inconsistent. Here, this means to consecutively apply the resolution step on (appropriately chosen) formulas of $A'$, until a contradiction $(T\to F)$ is reached.

Classical logic tells you that, if (a) the initial set of assumptions $A$ is consistent and (b) $A\cup\{\neg\phi\}$ is inconsistent, then $A\cup\{\phi\}$ is consistent and you can say that $\phi$ is a logical consequence of $A$. So, if steps (1) and (2) succeed, then $\phi$ is a logical consequence of $A$.

If you don't negate the goal when you put it in the set of assumptions and  if you manage to show that $A\cup\{\phi\}$ is inconsistent, then $A\cup\{\neg\phi\}$ is consistent and therefore $\neg\phi$ is a logical consequence of $A$.


Question concerning subset sum problem: split into 3 equal subsets

I don't think the proposed algorithm is correct. It may happen that the first solve for $A/3$ picks a set of numbers that makes it impossible to split the remainder into equal halves. Consider this example:

Given the set of numbers $\{1,1,3,3,3,4,8,10\}$, which sum to $A=3*11$
Assume that the first DP picks $||\{1,1,3,3,3\}||_1=11$
It is impossible to split the remaining set $\{4,8,10\}$ into equal halves.

Here's a recursive function in pseudocode instead which computes what you need in a single step:
bool CanBuild3EqualSums(int sumA, int sumB, int sumC, int[] numbers)
{
    if(numbers is empty)
        return sumA == sumB && sumB == sumC;
    else
        return CanBuild3EqualSums(sumA + numbers[0], sumB, sumC, numbers.WithoutFirst())
            || CanBuild3EqualSums(sumA, sumB + numbers[0], sumC, numbers.WithoutFirst())
            || CanBuild3EqualSums(sumA, sumB, sumC + numbers[0], numbers.WithoutFirst())
}

This is a pure function (without side-effects). Add memoization and you'll end up with a DP algorithm. Of course, there are many other ways to formulate this. There is some potential for a more efficient, practical implementation:

You could pass the index of the next number, instead of the whole array.
You could get rid of sumC, and compute when needed, based on sumA and sumB
If you have small values, a bottom-up formulation might be more efficient.


Is call stack compile time or runtime detail?

The architecture of a computer is where concepts like "heap" and "call stack" originate from.  If you take a look at the C standard (http://www.iso-9899.info/wiki/The_Standard) you won't find anything about the stack or heap.

Compilers for a language like C can implement the specification in a number of ways in order to target specific architectures; even ones where memory is not organized in a stack, such as a "LISP cpu" (for example Sussman and Steele's: https://dspace.mit.edu/bitstream/handle/1721.1/5731/AIM-514.pdf?sequence=2) where memory is organized as linked lists.

Of course a language specification could define these things, but I am not aware of any language which goes so far.  (The closest I can think of is forth.)

Operating systems and libraries can abstract away some of the details of the underlying architecture via system calls and apis.


Number of path with given length within an unrooted Tree

Hint: divide-and-conquer.  How many paths are there of length C in the left subtree of the root?  How many in the right subtree?  How many others not covered by either of those two cases?


What is the minimal number of states for the DFA?

Your $\Sigma=\{a,b,c,d\}$ so you have to add at least one dead state. The DFA is:


Thue language is based on string rewriting and it's just 179 lines of c code.

Pure is an LGPL'd functional language based on term rewriting.

Not an example, but a course with really complete slides on the theory of term rewriting systems.


Why unsafe state not always cause deadlock?

Deadlock means something specific: there are two (or more) processes that are currently blocked waiting for each other.

In an unsafe state you can also be in a situation where there might be a deadlock sometime in the future, but it hasn't happened yet because one or both of the processes haven't actually started waiting.

Consider the following example:

Process A                  Process B
lock X                     lock Y           # state is "unsafe"
                           unlock Y
lock Y                                      # state is back to "safe" (no deadlock this time.  We got lucky.)

There's a more interesting example in Section 7.5.1 of the link you gave:

  Consider a system with 12 tape drives with:

Process       Max Need       Current
P0:             10              5
P2:              9              3

This is an unsafe state.  But we're not in a deadlock. There's only 4 free drives, so, for example, if P0 does request an additional 5, and P2 does request an additional 1, we will deadlock, but it hasn't happened yet.  And P0 might not request any more drives, but might instead free up the drives it already has.  The Max need is over all possible executions of the program, and this might not be one of the executions where we need all 10 drives in P0.


In a Turing machine, what is the difference between the instruction table and the algorithm?

The Turing machine instruction table is a concrete implementation of the abstract algorithm. Usually, in one's everyday life as a computer scientist, there's not much to be gained by distinguishing these two concepts. Indeed, one can take the position that the Turing machine is the definition of "algorithm".


Estimating time cost for sorting algorithm given the average time for sorting of 1000 elements

It is in general impossible to interpolate the running time of algorithms even if you know their asymptotic running time. There are many reasons for this – here are two:

The running time of an algorithm is usually composed of many different terms. For example, it could be of the form $An\log n + Bn$. This running time doesn't scale like $n\log n$, since for small $n$ the $Bn$ term might be important, whereas for large $n$ it might be negligible.
Resource access times do not scale in $n$, but rather jump. When $n$ is small, everything fits into the smallest cache, so data access is very quick. When $n$ gets larger, you need to use a larger cache, so all at once data access becomes slower. When $n$ gets even larger, you need to use main memory (or even beyond), and data access becomes even slower.

In some cases these reasons do not apply. For example, you might be interested in values of $n$ for which one part of the algorithm clearly takes almost all the time, and you can easily estimate how it scales in $n$; and furthermore, memory consumption is minimal so increasing $n$ doesn't result in reduced data access behavior. In such cases it is possible to extrapolate the running time.

An extreme example is when you are estimating some quantity empirically, and $n$ is the number of samples. The running time of such a program scales linearly with $n$.


Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$

Hint: Use the time hierarchy theorem.

The first step, naturally, is understanding the question, that is, the definitions involved. The class $\mathsf{QP}_k$ consists of all problems solvable in time $2^{O(\log^k n)}$. We could similarly define $\mathsf{P}_k$ to consist of all problems solvable in time $O(n^k)$, and $\mathsf{P}$ to be a union over all $\mathsf{P}_k$:
$$ \mathsf{P}_k = \bigcup_{c>0} \mathsf{Time}(cn^k), \quad \mathsf{P} = \bigcup_{k>0} \mathsf{P}_k = \bigcup_{c,k>0} \mathsf{Time}(cn^k). $$
The class $\mathsf{QP} = \bigcup_{k>0} \mathsf{QP}_k$ is known as quasi-polynomial time. The question asks you to show that the corresponding hierarchy $\mathsf{QP}_2 \subseteq \mathsf{QP}_3 \subseteq \cdots$ is strict, that is $\mathsf{QP}_2 \subsetneq \mathsf{QP}_3 \subsetneq \cdots$. The same happens with the hierarchy corresponding to $\mathsf{P}$, again using the time hierarchy theorem: $\mathsf{P}_1 \subsetneq \mathsf{P}_2 \subsetneq \cdots$.

Why can't the same approach be used to prove $\mathsf{P} \subsetneq \mathsf{NP}$? Because here we're comparing deterministic computation to non-deterministic computation with the same time bounds, and there is no counterpart of the time hierarchy theorem which helps us here. Moreover, the time hierarchy theorems, in both the deterministic and non-deterministic case, are proved using diagonalization, a technique which is known to be unable to separate $\mathsf{P}$ from $\mathsf{NP}$ (in its vanilla form).


Hoeven et al. studied the problem of digital preservation through emulation:

... Digital preservation does not end with the careful storage of digital objects. In order
to keep these objects accessible, a continuous effort towards the development of
strategies for permanent access is required ....

They ended up with a modular emulation model and the need of an Universal Virtual Machine (UVM):

... The basis of the modular emulation model is founded on the Universal Virtual
Machine (UVM). The UVM is a platform- and time-independent layer on top of the
underlying future host platform. As a result, programs that are developed for the
UVM will continue to work even if the host platform changes. It not only consists of a general purpose processor and memory, but also offers additional functionality for input and output (I/O) communication with peripheral devices (like keyboard, storage, graphics,
networking) between host and target platform. This will be provided by the interface
layer.

.. and started the "Dioscuri project": a modular emulator for digital preservation. Not surprisingly, they chose Java to implement it:

... Java has been chosen as programming language. The main reason is its possibility to run Java code on a large variety of computer platforms using the Java Virtual Machine (JVM) without the need to recompile the source code. Recompilation is a risk factor since program code is adapted to a specific underlying computer platform. Although today’s compilers are very advanced, it can still result in different functionality of the same emulator compiled for different platforms. By avoiding this step, the emulator will be more stable and portable. Using the JVM instead provides similar results to the use of a UVM as discussed above....

The papers:

"Modular emulation as a long-term preservation strategy for digital objects" (2005)
"Emulation for Digital Preservation in Practice: The Results" (2007)

EDIT: the last changelog  of the Dioscuri project is dated: 19-Jan-2011
... so - perhaps - a new project/research should be started: "How to preserve the digital preservation tools?" :-D :-D

EDIT 2: just my personal opinion: if the Java program does useful things, humanity will preserve it without the need of any efforts by its author :-)


Do system calls always means a context switch?

A system call does not necessarily require a context switch in general, but rather a privilege switch. This is because the kernel memory is mapped in each process memory. The user process cannot access the kernel's memory because the memory mapping indicates which part are for the user and which parts are for the system. Thus a system call is really just a change of privilege, not of process. On some systems, like micro-kernels, a system call may involve a context switch because drivers are in a different process. But on monolithic systems like Linux this is not necessary. Linux also supports what is called the vDSO to implement some system calls entirely in userspace.

EDIT: attached a picture


How can $\Theta$ and $O$ complexities be different?

If the $O$-complexity given is true, then $f(x)\leq c_2n\log n$ will not always be true. So in this case, how is $\Theta$-complexity different from $O$-complexity?

Yuval has covered the quicksort aspects of your question but you have a couple of fundamental misunderstandings about asymptotics.

There is no such thing as "$\Theta$-complexity" or "$O$-complexity". Asymptotic notations such as $\Theta$ and $O$ are simply ways of describing the growth rate of functions. Those functions could be used to measure anything at all (including nothing at all). The complexity is the function (or, rather, the running time is measured by the function); the asymptotic notation is just a way of describing that function's behaviour.  As an analogy, suppose that I tell you that my height is "less than two metres": you wouldn't say that my "less-than height is two metres". Likewise, if I say that I weigh about 70kg, you wouldn't say that my "about weight is 70kg." "Less than" and "about" are just ways of describing the numbers that measure those physical properties.

The second misconception is that, for a given function $f$ there is some unique function $g$ such that it's correct to write $f=O(g)$. Remember that $f=O(g)$ means (in a way that's more precise than the following description) "$f$ is kinda less than $g$."  To continue the analogy of the previous paragraph, it's completely true to say that my height is less than 2m and that my height is less than 102m.  Indeed, there's also no contradiction in saying "My height is about 1.8m and less than 2m", which is directly analogous to "The running time is $\Theta(n\log n)$ and $O(n^2)$."


The Algorithm Design Manual - Working with the Big Oh

It is difficult to avoid what is repeating what is in the text, but you have exactly:
$T(n) = (n-1)+(n-2)+\ldots+1+0 =n\tfrac{n-1}{2} = \tfrac12n^2 -\tfrac12n$
and as an upper bound taking each value up to $n-1$:
$T(n) \le (n-1)+(n-1)+\ldots+(n-1)+(n-1) =n(n-1) = n^2-n$
and as an lower bound taking values of at least $\tfrac n2$ down to $\tfrac n2$ and other down to $0$ $($assuming $n$ is even; the odd case gives $\tfrac14n^2+\tfrac14 n)$:
$T(n) \ge \tfrac n2 +\ldots +\tfrac n2 +0+\ldots +0 = \tfrac n2 \times \tfrac n2 +\tfrac n2 \times 0 = \tfrac14n^2$
Since all three are essentially of the order of $n^2$ up to a constant, you can conclude $T(n)$ is $O(n^2)$ and $\Omega(n^2)$ and so $\Theta(n^2)$


Do most bitstrings expand if they halt when executed by a Universal Turing machine?

Both can happen.

The counting argument applies to all TMs that always halt.

In the partial world, you can construct Turing machines for both extreme cases (and everything in between) like so. Assume $T$ is a Turing machine. Construct

T<(x) = if |T(x)| < |x| then return T(x) else loop

and

T>(x) = if |T(x)| > |x| then return T(x) else loop

Note that if T(x) loops, both T<(x) and T>(x) loop; that's not a problem.
It's easy so see that for T<, all halting inputs contract, and for T> all expand.

Rice's theorem immediately shows that these expansion/contraction properties (and related ones) are undecidable, by the way.


Finding the connected subgraph of a given size with maximum number of edges, that includes a given vertex

It's NP-hard (by reduction from clique problem).
Let $G$ be an arbitrary graph, and we want to check if there exists a clique of size $m-1$ in this graph. This problem is NP-hard. By adding $v_1$ to the graph and connecting it to all vertices in $G$, we reduce the clique problem to your problem (since clique, when exists, has the maximum number of edges).


context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$

When $n=1$, the language $L_1$ consists of all words of the form $ywz$, where $|y|=|z|$ and $w$ is a non-empty palindrome. We can generate all non-empty palindromes as follows:
$$
P \to 0P0 \mid 1P1 \mid 0 \mid 1 \mid 00 \mid 11
$$
Given that, we can generate $L_1$ by capturing also the outer part:
$$
S \to 0S0 \mid 0S1 \mid 1S0 \mid 1S1 \mid P
$$
For larger $n$, all we need to change is the "base cases" for $P$.

Further observation reveals that we can actually assume that $|w| \leq 2$ (for $n = 1$), and so we can use alternatively the following productions for $P$:
$$
P \to 0 \mid 1 \mid 00 \mid 11
$$
This allows us to eliminate $P$ from the grammar, reaching the following grammar:
$$
S \to 0S0 \mid 0S1 \mid 1S0 \mid 1S1 \mid 0 \mid 1 \mid 00 \mid 11
$$
These steps can also be extended to larger $n$.


maximizing inner product of vectors in an ellipsoid and a given vector

There must be something wrong if you look at the dimensions. Actually the constraint should be
$$(\theta_a-\hat{\theta}_{t,a})^TA_{t,a}(\theta_a-\hat{\theta}_{t,a})\leq c_t^2.$$

The inner product takes its maximum on the boundary of the ellipsoid so we can make the constraint a equation. The gradient of Lagrange function has to be zero at the maximum:
$$\left\{\begin{array}{rcl}
x+2\lambda A(\theta-\hat{\theta}) &=&\vec{0} \\
(\theta-\hat{\theta})^TA(\theta-\hat{\theta})-c^2&=&0
\end{array}\right.$$

So
$$x^T(\theta-\hat{\theta})=2\lambda(\theta-\hat{\theta})^TA(\theta-\hat{\theta})=2\lambda c^2,$$
$$x^TA^{-1}x=4\lambda^2(\theta-\hat{\theta})^TAA^{-1}A(\theta-\hat{\theta})=4\lambda^2c^2,$$
which implies $x^T\theta=x^T\hat{\theta}\pm c\sqrt{x^TA^{-1}x}$. Since it's the maximum we take the positive sign here, so we have the LHS you wanted.


Is there any recursive function f whose code is unique?

No. The Padding Lemma states that there is a primitive recursive function $\sf pad$ such that, if $n$ is a code for $f$, then ${\sf pad}(n)$ is another code for $f$ which is larger than $n$.

Therefore, if $f$ has a code, it has infinitely many.

The intuition is: if you have a TM $M$ computing $f$, you can modify the TM so that it starts with some useless steps (e.g. move right, then left), and then behaves as $M$. The modified TM has a few more states, and under the "usual encoding" it will have a larger code than $M$.


Would an optimization version of the 3-partition problem also be strongly np-complete / np-hard?

The objective function $f$ (to minimize) is not completely formalized in the question. It is written that the groups should "sum to as close to a target as possible", so it seems natural to assume that $f$ is $0$ if the sum of the elements in each group is equal to the target, and greater than $0$ otherwise.

Two examples of such functions are the maximum and the sum of the absolute differences between the sum of the elements in each group and the target.

Under this assumptions, the above optimization problem is strongly NP-hard since the answer to the decision problem is "yes" if and only if an optimal solution $S$ to the optimization problem satisfies $f(S)=0$.

It would not be NP-complete since it does not belong to NP (which only contains decision problems).


Is it NP complete to decide whether a graph has bigger clique or bigger independence number?

Note that there is a slight technicality with regards to whether you consider the graph where the clique is larger a "yes"-instance, or a graph where the independent set is larger a "yes"-instance (i.e. the complement problem) and what you do in the event of a tie. I have picked one particular way of settling ties, but this proof can easily be adapted to the other way of settling ties (i.e. by fudging with a $\pm 1$).

If $NP\not = coNP$ then neither this problem nor its complement is in $NP$, so neither problem is likely to be $NP$-complete.

It is $NP$-complete to decide whether a graph has an independent set of size $k$. We show that, if there exist polynomial certificates for your problem then there exist polynomial certificates for the complement of the independent set problem. We note that IS remains $NP$-complete even when restricted to maximum degree $3$ graphs and $k>4$.

Given a graph $G$ that does not have an independent set of size $k$, we create a new graph $G'$ as the union of $G$ and a clique of size $k$ (note that this increases the independence number by one).

$G'$ is a "yes"-instance of the problem "Is the Clique greater or equal to the IS?". A polynomial certificate for this fact would give a polynomial certificate testifying to the fact that $G$ does not have an IS of size $k$, which is impossible unless $NP=coNP$. (The largest clique in $G$ is of size $4$ since $G$ has maximum degree $3$, so the largest clique in $G'$ is of size $k$. The certificate for $G'$ thus has to certify that $G'$ has no IS of size $k+1$ and equivalently, that $G$ has no IS of size $k$).

If we instead consider the complement problem "Is the Clique strictly smaller than the IS?", we create $G'$ by adding a clique of size $k+1$ and then taking the complement graph $\bar{G'}$. Since a Clique becomes an IS in the complement graph and vice-versa, the largest IS in $\bar{G'}$ is of size $k+1$ while the largest Clique is of size at most $k$. $\bar{G'}$ is thus a "yes"-instance of the complement problem, but a certificate for this fact would give a certificate for $G$ not having an IS of size $k$ which is impossible unless $NP=coNP$.

However, the problem "Is the Clique strictly smaller than the IS?" is $NP$-hard. We reduce from Independent Set on a maximum degree $3$ graphs $G$ where $k>4$. We create $G'$ by adding a clique of size $k$ to $G$. If $G$ has an IS of size $k$ then $G'$ has one of size $k+1$ (obtained by adding any of the clique's vertices to the IS). The largest clique in $G'$ has size $k$, so $G'$ is a "yes"-instance if and only if $G$ has an Independent Set of size $k$.


Problem that is only solvable in a given space

This kind of question is studied in the cryptography literature under the name "memory-bound computation" or "memory-hard function".  Such a function is one that can be computed efficiently using $K$ bytes of memory but takes much longer to compute if you have significantly less than $K$ bytes of memory.  So, I suggest that you take a look at cryptographic constructions for memory-hard functions.  It's an active area of research, and researchers focus more on practical complexity (concrete running time, not asymptotic running time) than on complexity theory, but you might find it useful.

See https://en.wikipedia.org/wiki/Memory_bound_function#Using_memory_bound_functions_to_prevent_spam for a high-level overview.


Consequences of the Time Hierarchy Theorem

Let $f(n) = n^{\log n}$. Then $\mathsf{P} \subseteq \mathsf{DTIME}(f(n))$ while $\mathsf{DTIME}(f(2n+1)^3) \subseteq \mathsf{EXP}$.

(Actually, whether this argument works depends on the exact definition of $\mathsf{DTIME}$. If it doesn't, take $f_C(n) = Cn^{\log n}$ and sum over all integer $C>0$.)


Subtracting an integer from an ASCII number

It depends how exactly you do the subtraction. Depending on the processor, the string 10 is either 0x3031 (little endian) or 0x3130 (big endian). Most modern processors are little endian. That's assuming you regard 10 as a 16-bit integer, i.e. a C short on modern computers. If you're regarding it as a C char, then only the first digit 1 will be affected.


Understanding definition of NP and co-NP

Nondeterministic machines are only allowed to behave nondeterministically in a limited way: very briefly, "Accept iff some branch has [property]" is permitted but "Accept iff no branch has [property]" is not. Unlike with deterministic machines, there's a fundamental element of asymmetry here. Your $N'$ is not, in fact, a nondeterministic Turing machine.

Rather, it's a "co-nondeterministic Turing machine" (if that were a term). Unsurprisingly, co-NP is exactly the set of languages accepted by some co-nondeterministic Turing machine, and the fact that NP=co-NP is open means exactly that it is not currently known whether nondeterministic and co-nondeterministic machines can compute the same things in polynomial time.


How to prove that this language is not regular?

Now if we have $UVVW$ that means $V$ is repeating some of the characters in $x$ and therefore it must repeat some $x_i$. Therefore we have reached a contradiction, which shows that $L$ is not a regular language.

This is not necessarily true. Suppose $x=[0^p, 0^{p-1}, \dots, 00, 0]$. If $V$ is of length $k<p$ and entirely in $0^p$, we get $UVVW = [0^{p+k}, 0^{p-1}, \dots, 00, 0]$ which is still in $L$.

Normally when doing a proof using pumping lemma, we try to use a more specific $x$ such that the pumping lemma fails. Like this:

Suppose $L$ is regular and let $p$ be its pumping length. We choose $x=[0^p, 0^{p-1}, \dots, 00, 0]\in L$. By the pumping lemma, we can split it into 3 parts $UVW$. Noticed that $V$ cannot include the symbol [ otherwise $UVVW$ contains two [ which is not in $L$. Then, the choices for $V$ is either $0, 00, \dots, 0^{p-1}$. Note that it cannot be $0^p$ because it is subject to the constraint $|UV|\leq p$. No matter what we choose for $V=0^k$, the string $UW=[0^{p-k}, 0^{p-1}, \dots, 0]$ is not in $L$ because $0^{p-k}$ must be one of $0, 00, \dots, 0^{p-1}$. Hence $L$ is not regular.


Efficiently partition tree into clusters of similar diameter

Your problem is equivalent to the following:

Input: a tree $T$, an integer $r$ (the radius)
Find: a set $S$ of $k$ vertices, such that every vertex in the tree is at distance $\le r$ from one of the vertices in $S$; or failure if no such set exists

Why is this equivalent?  Well, if you have such a set $S$, then you immediately can find $k$ clusters of diameter $\le 2r$ (for each $s \in S$, you get a cluster of nodes that are at distance $\le r$ from $s$).  Conversely, if you have $k$ clusters of diameter $\le 2r$, then you can find such a set $S$: given a cluster, pick a pair of nodes $x,y$ in the cluster that maximizes $d(x,y)$; then find a shortest path from $x$ to $y$, and let $s$ be a node halfway along that shortest path; then one can prove every node in the cluster is at distance $\le r$ from $s$.  So, if you can solve the above problem, then linear search or binary search on $r$ will find the smallest such diameter.

The best algorithm I can find for this problem is the trivial $O(n^{k+1})$ algorithm: enumerate all subsets of size $k$, and test each to see whether it satisfies all the requirements.  The number of sets you must enumerate is $C(n,k) = O(n^k)$, and given a candidate set you can test whether it is valid in $O(n)$ time.  Unfortunately, for modest or large values of $k$, this will be totally impractical.

As an optimization, you can let $S'$ be the set of vertices that are at height $\ge r$.  (The height of a vertex $v$ is the length of the longest downward path from $v$ to a leaf; in other words, the height of a leaf is $0$, and the height of an internal node is one more than the height of its highest child.)  Then, you only need to enumerate subsets of $S'$ of size $k$.  In practice, this might provide a significant improvement, even though asymptotically it might not make much of a difference to the worst-case running time.

I don't know whether it is possible to do better, or whether a polynomial-time algorithm exists.  I think the problem can be solved in polynomial time for binary trees using dynamic programming, but you want to handle arbitrary trees, and I don't know what happens in that case.


Counting solutions to system of linear equations modulo prime

The integers modulo a prime form a field, so all assumptions done applying Gaussian eliminations work exactly the same. Luckily, there are no numerical instability problems. The system can be inconsistent (no solutions), underdetermined (several solutions modulo $p$) or have a unique solution modulo $p$.


What does > mean in this TAOCP solution?

What does > denote here?

It's not stated explicitly, but a reasonable meaning can be inferred from context.

The authors assume that the data can be sorted so there has to be some (total) order relation $\leq$ (canonically) on the elements. We don't care what the elements are, so we do not fix the relation, either. In any given situation, we would know what to do and have a fixed relation.

For instance, if we wanted to sort natural numbers in increasing order, $>$ would mean the usual. I we wanted to sort them in decreasing order, you'd have to replace $>$ by $<$ in the solution.


is any faster algorithm to calculate this series? ∑∑ai/aj

Assuming that your numbers $a_i$ are small enough and $n$ is large enough, the following algorithm may work better in practice.
For each $a_i$, for all possible division results $d_j$, find minimum $v_j$ such that $\lfloor \frac {a_i} {v_j} \rfloor = d_j$. The idea is the following:

There can't be too many different $d_j$. E.g. for $a=10^9$ there are about $6 \cdot 10^4$ possible $d_j$. It's possible to show that there are $O(\sqrt{a})$ possible values of $d_j$ (about $2 \sqrt a$). Note that it's possible to iterate all possible $d_j$'s in time linear of their amount.

All numbers between neighboring $v_j$'s give the same result after division.

Therefore, the algorithm is the following:

Sort $a_1, \ldots, a_n$
For each $a_i$, find all possible $\{(d_j, v_j)\}$ as described above. Using binary search on array of $a_i$, for all $j$ find the number of $a_i$ lying between $v_j$ and $v_{j+1}$. Division by any of them results in $d_j$.

P.S.: This algorithm can take exponential time (since it's polynomial on the numbers themselves), but it can have a guaranteed $O(n^2 \log n)$ time when we ignore $d_j$ which can't be achieved: when we've found the last number $a_k$ which lies between $v_j$ and $v_{j+1}$, we select the next $d$ to consider based on $a_{k+1}$. Additional $\log n$ comes from the binary search.


The number of multiplications in the algorithm is $2n - 1$, but the number of multiplications in the Horner's method is $n$, which means this algorithm is not optimal.
As mentioned in the Wiki page, Horner's method in evaluating a polynomial is optimal, therefore we can change this algorithm so that it uses the Horner's method.
p = a[n]

for i = n-1 to 0:
   p = p.x + a[i]


Dijkstra complexity analysis using adjacency list and priority queue?

Dijkstra's algorithm visits every node once ($=O(V)$), and tries to relax all adjecent nodes via the edges. Therefore it iterates over each edge exactly twice ($=O(E)$), each time accessing the priority queue up to two times in $O(\log V)$.

Therefore the complexity is $O(E \log V + V)$.

For a proof of the correctness, just look it up at any basic algorithms book, like CLRS.


Existence of shortest path in a graph with no negative cycles?

If there is a path $P$ from $s$ to $v$, there is one where no vertex
occurs more than once, with a weight that is less or equal to $P$. Indeed, if a vertex $x$ occurs twice, there is necessarily a loop
from $x$ to itself. This loop cannot have a negative weight by
hypothesis. So by removing it, we get a path that is no heavier. This
can be repeated until we obtain a path where no vertex occurs more
than once. Hence there are at most $n$ vertices on such a path, which
means that the path has at most $n-1$ edges.

Thus we can consider only paths with at most $n-1$ edges, with each
edge occurring at most once, since any other path is no lighter than a
path in that set.

Since this set is finite, the number of edge conbinations to be used for a
path is necessarily finite too (further limited by the constraint or
forming a path from $s$ to $v$). Thus the set of weights has a minimum
corresponding to some path(s) wich is (are) the minimum /shortest path(s).


Algorithm to identify if a string of numbers is a lottery sequence


Finding values in a space that matches a relational query

One approach is to guess $a$ (i.e., iterate over all possibilities for it, and the following for each possibility).  Then, you can infer the value of $b$, namely, $b = a r_b/r_a$, so test whether $b \in B$.  Do the same for each of $c,\dots,z$.  If they all work, then you have found a solution; otherwise, proceed on to your next guess at $a$.  This should give you approximately a linear running time if you use the right data structures for storing the vectors (e.g., a hashtable).
A similar approach is to compute the vectors $A/r_a$, $B/r_b$, ..., $Z/r_z$, and then look for an item that occurs in all of those scaled vectors, e.g., using a hashtable or a counter or by sorting and merging the sorted lists.


Random forests on monotone training set yields a monotone classifier?

No, it's not guaranteed.  You can end up with a decision tree or classifier that is non-monotone.

Here is an explicit counterexample, i.e., a training set of 5 samples on 5 attributes:

$$\begin{align*}
&(01011, 0)\\
&(01101, 0)\\
&(00111, 1)\\
&(10110, 0)\\
&(11000, 1)
\end{align*}$$

This training set is monotone: it is consistent with the monotone function

$$f(x_0,x_1,x_2,x_3,x_4) = (x_0 \land x_1) \lor (x_2 \land x_3 \land x_4).$$

However, if you run the ID3 algorithm on this training set, you may end up with a decision tree that computes the function

$$g(x_0,x_1,x_2,x_3,x_4) = (\neg x_0 \land \neg x_1) \lor (x_0 \land x_1),$$

which is also consistent with the training set yet is not monotone.  In other words, ID3 might produce the following decision tree:

       x0
     /    \
    /      \
  x1        x1
 /  \      /  \
1    0    0    1

which is quite evidently non-monotone (there's an obvious violation of monotonicity in the lower-left part of the tree, where the tree says that the output should be the negation of $x_1$ -- clearly non-monotonic).

Why can ID3 produce this decision tree?  Starting with the entire training set, splitting on $x_0$ yields predictions (information gain) that is at least as good as splitting on any other attribute.  Then we recursively run ID3 on the subset of training samples where $x_0=0$ and recursively run ID3 on the subset of training samples where $x_0=1$, and on each recursive run we discover an attribute that provides perfect prediction.  Try running the ID3 algorithm by hand to see what I mean.

Now at this point perhaps you are going to object: the ID3 algorithm made a choice that is obviously stupid.  When the training set contained $(01011,0)$, $(01101,0)$, and $(00111,1)$, the algorithm noticed that $x_1$ provides perfect prediction of $y$, via the rule $y = \neg x_1$ -- but this is a stupid choice if we want to end up with a monotone classifier, since even without looking into the future we can immediately see that this is going to yield a non-monotonic result.

So it is natural to try to rescue the ID3 algorithm with a local pruning rule that, at each stage, only considers attributes that aren't obviously dumb -- that aren't obviously going to lead to a violation of monotonicity.  Here is one way we could try to operationalize that idea.  Let's adjust the ID3 algorithm to be locally monotone.  Normally, the ID3 algorithm chooses an attribute $x_i$ that reduces the information gain as much as possible.  We could adjust this to also require that we pick an $x_i$ that is locally monotone, i.e., the fraction of training set pairs with $x_i=0 \land y=1$ is at most the fraction of training set pairs with $x_i=1 \land y=1$.  (If $x_i$ is not locally monotone, then splitting on $x_i$ seems likely to yield a decision tree where we predict an output of 1 more often when $x_i=0$ than when $x_i=1$, which is a violation of monotonicity.)  Out of all locally monotone choices, we'll pick the attribute with the best information gain (or the lowest Gini impurity, if you prefer).

Unfortunately, even with this modification to enforce local monotonicity, ID3 can still fail to yield a monotonic decision tree.  When we run the ID3 algorithm on the above data set, we obtain a decision tree that computes the function

$$g'(x_0,x_1,x_2,x_3,x_4) = (\neg x_0 \land x_2 \land x_3) \lor (x_0 \land x_1),$$

which is consistent with the training set yet is not monotonic.  In particular, we might obtain the following decision tree:

       x0
     /    \
    /      \
  x2        x1
 /  \      /  \
0    x3   0    1
    /  \
   0    1

This decision tree achieves 100% accuracy on the training set, yet it isn't monotone, even though there exists another decision tree (of the same depth) that is monotone and also achieves 100% accuracy.

Why can ID3 produce this decision tree?  Starting with the entire training set, splitting on $x_0$ yields predictions (information gain) that is at least as good as splitting on any other attribute.  Then we recursively run ID3 on the subset of training samples where $x_0=0$ and recursively run ID3 on the subset of training samples where $x_0=1$, and similar comments apply at each stage of the algorithm.  I'll let you run ID3 by hand and see that there is a way to resolve ties at each step that yields the decision tree above.

In short, we can potentially lose either way, whether or not we apply the "locally monotone" constraint.  We might get lucky and end up with a monotone decision tree, but there is no guarantee of that -- we also might unlucky and end up with a non-monotone decision tree, even though there exists a monotone decision tree that would be at least as good.

Similar comments apply to the random forests algorithm, as it merely applies the ID3 algorithm multiple times.  (Each tree is learned on a different subset of the training set, and with different subsets of the features at each node of the tree, but the same kind of anomaly can still occur.)

This proves that it is at least possible to end up with a non-monotonic classifier, even when starting from a monotone data set.  I don't know how likely it is that this will happen in practice, though, when taking the probability over the random choices made in the ID3 algorithm (to resolve ties) and in the random forests algorithm (for bagging and feature subsetting).

In other words, this demonstrates that if our goal is to learn a monotonic classifier, it's not enough to simply apply the standard random forests or ID3 training procedure on a (monotone) training set; something more sophisticated is needed.


How to solve for a problem using a primitive function in toc

Hint:

You probably have:
$$add(0, n) = n$$
$$add(m+1, n) = S(add(m,n))$$

Now you know the base case for addition is adding zero. What's the base case for multiplication? Multiplying by zero.

$$mul(0,n) = 0 $$

I will not do the last part,because you must do your own homework,  look at your example and the addition definition, the $mul$ function must work like this:

$$mul(3,5) \longrightarrow 5 + 5 + 5 + 0 $$


What programming languages always learned in computer science B.Sc.?

There is no programming language that is taught in every computer science B.A. program. There is a lot of variation in what languages are used to teach material, in different programs.  For instance, when I took computer science classes, I learned only C and Standard ML.  There are other other programs where you might learn (for example) Python and Java.  If you choose any one programming language, I would imagine you can find some B.A. programs that teach that language and others that don't.

Learning a specific programming language is usually not the main point of a computer science education. The goal is to learn concepts and skills, and teaching any one programming language is just a way to support that goal.


As pointed out by @Pseudonym, this problem is identical to finding a round robin tournament schedule. A straightforward implementation would be the following:

def get_sets(a: list):
    # Simple implementation of
    # https://nrich.maths.org/1443
    center, *rest = a
    for _ in range(len(rest)):
        rest = rest[1:] + rest[:1] # put 1st element to back of list
        solution = [[center, rest[len(rest) // 2]]] # combine middle element with center
        for i in range(len(rest) // 2):
            solution.append([rest[i], rest[~i]]) # combine i-th element from front with i-th from back
        yield solution

for s in get_sets(list(range(50))):
    print(s)

Note that this implementation creates a new list for each "set" in the output.
This is not strictly necessary, as the same result could be achieved by using only the initial list (actually array) and use smart indexing.


Universal hashing (or near-universal) is a key ingredient in defending against algorithmic complexity attacks that engineer hash table collisions from user input.

See Scott A. Crosby and Dan S. Wallach's "Denial of Service via Algorithmic Complexity Attacks".


Finding a O(n) solution to: max difference of pairs array question

Create an array considering the minimum value seen so far in the array (in O(n)).

Ex. (9, 2, 2, 2)

Create an array containing the differences between the previous array and the original array (again, in O(n)).

Ex. (0, 0, 4, 5)

Find the maximum value in the array (O(n)). In this case, the answer is 5 as required.

This can be done in O(1) memory and only one pass if a few optimizations are made.


How can the local feature size become arbitrarily small?

As you have suspected, it is impossible for a simple smooth closed curve to contain the line segment from (−1,0) to (1,0) such that its local feature size at $(0,0)$ is arbitrarily small.
On other hand, it is easy to draw a self-intersecting smooth curve with that property. Here is an example.

In fact, for every smooth curve that contains the line segment from (−1,0) to (1,0) and intersects itself at $(0,0)$, its local feature size at $(0,0)$ will be arbitrarily small.


Your approach doesn't work.  Presumably, you want to define the probability of a path to be the product of the probabilities on its edges.  It sounds like you want to define the weight $w(e)$ on an edge $e$ to be $w(e)=1-p(e)$ (one minus its probability). However, doesn't work.  It doesn't do what you want: you want $w(e)+w(e')$ to correspond to $p(e) \times p(e')$, but it doesn't.

Instead, you should be taking logarithms.  In particular, you should define the weight on edge $e$ by $w(e) = -\log p(e)$.  Now addition of weights corresponds to multiplication of probabilities:

$$w(e) + w(e') = -(\log p(e) + \log p(e')) = - \log(p(e) \times p(e')),$$

as desired.  At this point all of the weights in $G'$ will be non-negative (do you see why?), so you can use Dijkstra's algorithm to find the shortest path in $G'$, and that will correspond to the path in $G$ with highest probability.  As you can see, this is not a longest-path problem at all; it is just a straightforward shortest-paths problem.

The trick of taking logs to turn multiplication into addition is a standard one, including in many applications of graphs, so this is worth knowing.


Dynamic programming to find the least possible balance of a full binary tree

You should think about how your binary tree can be arranged. For each tree you have some nodes $x_1,\dots,x_k$ to the left and some $x_{k+1}, \dots, x_n$ to the right of the root. Now, the best possible imbalance for that root will be the arrangement that gives you the smaller ratio. So, you have to figure out a way of doing this evaluation in every internal node of your tree (considering the subtree rooted there). Another tip is to consider growing your tree while preserving the minimum imbalance. The "matrix-chain" problem is quite similar to this one, so you should take a look at it too. Good luck.


Extended version of the theory of reals and its decidability

Turing machines, in the classical sense, decide languages of finite strings over finite alphabets. Your logical language has uncountably many constant symbols so you can't even write down all the formulas as strings, let alone ask a Turing machine to decide things about the collection of formulas.


Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?

A two-stack PDA is equivalent in computing power to a Turing machine. Since a Turing machine can accept that language (stated without proof), a two-stack PDA can as well. The actual definition of such a machine is left as an exercise :)


Note that your grammar is regular. Quoting from wikipedia:

A grammar is regular when no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side.
Every regular grammar corresponds directly to a nondeterministic finite automaton, so we know that this is a regular language.

In theory, every regular grammar generates a regular language. Also, its not hard to construct the relevant NFA for the generated language: for a specific example on how to do that, you can click here (this is actually what has been done in @Matthieu Latapy's answer). Once you have an NFA for the language, you can translate it into a regular expression (there are several ways to achieve this based on state removal methods which are a bit tedious: see here).
BTW, you already know that your language is all words with "odd length and odd number of b's". It is easy to build a DFA for it consisting of 4 states (hint: your language is an intersection of two languages, each having a DFA with two states).


Unifiers modulo commutativity in terms of syntactic unifiers and $\approx_{C}$-class

Note that for all $s, t \in T(\Sigma, V)$ we have:
$$s \approx_{C} t \iff \exists_{i, j}:  s_i = t_j \tag{*}$$
Using (*) for the terms $s \sigma$ and $t \sigma$ we obtain:
$$s \sigma \approx_{C} t \sigma \iff \exists_{i, j}: s_i \sigma = t_j \sigma, $$i.e,
$$\mathcal{U}_{C}(\{ s \approx_{C}^{?} t \}) = \bigcup\limits_{1 \leq i \leq m \\ 1 \leq j \leq n} \mathcal{U}_{\emptyset}(\{s_i =^{?} t_j \})$$


Natural deduction: understanding bottom elimination (¬e)

Usually in practice we weld the two steps together and just say that from $p$ and $\lnot p$ anything follows, but in formal logic this is a combination of two rules of inference:

$p$ and $\lnot p$ both together entail falsehood $\bot$,
from $\bot$ anything follows.

These are precisely lines 9 and 10 in your proof.

We often take $\lnot p$ to be an abbreviation for $p \Rightarrow \bot$, in which case the rule "from $p$ and $\lnot p$ follows $\bot$" is just a special case of modus ponens "from $p$ and $p \Rightarrow r$ follows $r$".


If we spoke in TM-computable English, what would it look like?

Under reasonable assumptions, there is a TM which can decide whether something is a valid piece of English legalese. We can safely assume that the length of a law is bounded by some finite number $k$, say the number of characters the fastest human reader can read in less than two hundred years. There is then only a finite number of possible strings that might or might not be valid laws. Hence there is a lookup table of finite size that contains for every string of length at most $k$ the correct answer.

It is not settled whether humans can in fact recognize languages that TM can't recognize, so it's unclear whether the length restriction is truly necessary. See for example this question, or this question.

This is of course a boring answer, because this TM is completely impractical to construct. In actual practice you probably want to restrict yourself to a subset of English that can be parsed by an LL(k) parser (real English is not context-free), or go for a language specifically designed to be easy to understand to both humans and computers. @LukasBarth mentioned Lojban in the comments, but there are a number of such languages (programming languages are another example).


Isomorphism problem on bounded degree digraphs

You can reduce graph isomorphism on directed graphs to graph isomorphism on undirected graphs.  I think it's possible to build a reduction that preserves the bounded-degree property.

For instance, I think the following should work.  Replace each directed edge u --> v with the following gadget:

u --- a --- c --- v
      |
      b

where a, b, and c are fresh new vertices (different ones for each edge).

Next, we'll add some edges to make sure that the isomorphism makes original vertices like u, v map to other original vertices (not to the new vertices).  Add a new vertex A (just one), and connect A to each of the a's; to do this in a way that preserves bounded edge degree, use a binary tree.  Finally, add a long path A --- A' --- A" --- A"' --- ... with n+3 new vertices, where n is the number of vertices in the original graph.  Add a new vertex B, connected to a path of n+2 new vertices, and connect it to the b-type vertices as above; and add a C, connected to a path of n+1 new vertices, connected to the c-type vertices.

Apply this transformation to both directed graphs, to get two undirected graphs.  Now I think any isomorphism of the resulting undirected graphs corresponds to an isomorphism of the original directed graphs.  In particular, the isomorphism must map the two n+1 paths to each other; so it must map the two A-type vertices to each other; so it must map a-type vertices to other a-type vertices; and similarly, b-type to b-type and c-type to c-type.  Thus vertices of the original directed graph must be mapped to vertices of the other original directed graph.  The mapping must preserve the direction of the edges, due to the asymmetry in the gadget above.


Consensus number of memory-to-memory swap

See Theorem 10 (Figure 13) of the paper "Wait-Free Synchronization
" by Herlihy, 1991.

  Theorem 10: An array of registers with memory-to-meory swap has infinite
  consensus number.

  Proof: The protocol is shown in Figure 13. The processes share an array of
  registers $a[1 \ldots n]$ whose elements are initialized to $0$ and a single register $r$, initialized to $1$. The first process to swap $1$ into $a$ wins.

Footnote 4 of this paper remarks that:

  The memory-to-memory swap should not be confused with the read-modify-write swap; the former exchanges the values of two public registers, while the latter exchanges the value of a public register with a processor’s private register.


Flaw in linear programming solution for multi-commodity flow problem?

The linear programming formulation from CLRS is fine.  There is no problem with it.

Your purported counterexample isn't a valid counterexample -- it  doesn't satisfy all of the inequalities.  Take a closer look at the specification of the second inequality.  For instance, when we are dealing with commodity $a$ ($i=a$) it says that we should have

$$\sum_{v \in V} f_{auv} - \sum_{v \in V} f_{avu} = 0$$

for all $u \in V \setminus \{s_a,t_a\}$.  In particular, consider the case $u = t_b$.  We have

$$\sum_{v \in V} f_{at_bv} - \sum_{v \in V} f_{avt_b} = 0 - 2 \ne 0,$$

so the inequality is violated.

To put it in English: the second inequality requires conservation of flow for each commodity, except at that commodity's source and sink.  For example, for commodity $a$, we must have conservation of flow at every vertex except $s_a$ and $t_a$.  In your proposed counterexample, conservation of flow for commodity $a$ is violated at vertices $s_b$ and $t_b$; that's not allowed.


I'm not sure what you mean by "the simple case is to consider the diagonal of the Jacobian".  Are you perhaps doing some unusual variation of gradient descent where you compute only the diagonal of the Jacobian, but not the other entries?  If you are, then don't be surprised if it performs poorly.  Don't do that.  I wouldn't expect that to work well.

Instead, I recommend you follow the standard approach: use backpropagation to compute the gradient and use gradient descent to update the weights.  There are many standard tutorials on how to do that.  Realistically, we never need to compute the Jacobian matrix for the softmax directly.  Instead, we look at the output of the loss function, and we compute the gradient of that with respect to the weights.  That doesn't require a Jacobian, because we are computing the gradient of a function that has a single output.  Then, we use the gradient to update the weights (that's the gradient descent part).

If you're implementing this yourself from scratch, there are many things that can go wrong.  I recommend implementing a gradient check to make sure you are computing the gradient properly.  But, more realistically, I recommend using some existing framework for training neural networks (e.g., Keras, Torch, etc.) rather than trying to implement it from scratch.  If you implement from scratch, there are many ways you can create some small implementation error that will lead to results that are subpar but hard to debug.


How can I find matchings in a Bipartite graph beginning with specific vertices?

To make this a minimum-cost perfect matching problem, split each node as you indicated (sending/receiving).  Add a high-cost edge from each node's sending node to its own receiving node.  This high-cost edge will only be used if that node does not receive a kidney.  Additionally, I assume Node 0 in the above graph is supposed to be an altruistic donor or a deceased organ donor that does not need to receive a kidney.  (Otherwise, your example has no cycles and no exchange can take place.)  Assuming Node 0 is a 1-way donor, add low cost edges from every sending node to Node 0's receiving node.

Then solve the minimum-cost perfect matching problem.  A perfect matching is obviously possible (every sending node can send to its own receiving node).  A minimum-cost perfect matching will use as few of the high-cost edges as possible.  Minimizing the number of high-cost edges (nodes that send to themselves) is the same as maximizing the number of nodes that receive a kidney.

This is also known as the assignment problem and can be solved in polynomial time.  Most kidney-exchange research adds the significant complication of requiring cycles to be at most length k.  That complication makes the problem NP-hard.  Altruistic donors could allow for longer cycles in practice.


what are the conditions for two NFAs to be equivalent?

As commented, they are equal when they accept the same language.

In practice:

Every NFA has one (1) minimized DFA, which is unique. If two minimized DFA are equal, the corresponding NFA's must also be equal.


Does the Rabin-Karp really need me to care about applying a mod Q operation on the rolling hashes?

Yes, in practice you can get by fine with just letting the computations overflow. You are effectively working modulo $2^{32}$. It also has the advantage of not requiring an (expensive) modulo computation. However, it lacks some of the theoretical performance guarantees. You need to be very careful with the choice of the base (in this case: $10$) with respect to the modulus.

In particular, your choice of $10$ is very poor. Note that $10^{32}=2^{32}\cdot 5^{32}$, so $10^{32} \textrm{ mod } 2^{32} = 0$. This means that only the last $32$ characters of the string are taken in to account in the hash, so one can construct an input on which your algorithm performs very poorly.

Let the haystack be a string of $m$ $1$'s, i.e. $1111111\ldots$ and the needle a string consisting of $n$ $1$'s, one $0$, and then $32$ $1$'s. Because the string ends with $32$ $1$'s every position will result in a spurious hit, and the algorithm will need to loop over $n$ $1$'s before encountering a zero, meaning you will get a $\Omega(nm)$ running time.

I tested your algorithm on an input where $n=3000,m=n^2=9\cdot 10^6$. It took $18$ seconds to run on an input that ended in $32$ 1's, but only $200ms$ for a string ending in $31$ $1$'s.

The problem is that $10$ is not relatively prime to the modulus. For instance, taking $9$ as the base makes your program perform much better, taking only $200ms$ for the case with $32$ $1$'s. Of course, taking a prime modulus will partially solve this problem since the base will automatically be relatively prime to it. However, this is not the only reason for preferring a prime modulus.

Now, even if the modulus $n$ and base $b$ are relatively prime, undesirable things can still happen. For instance, there is a $k$ for which $b^k=1\textrm{ mod } n$. It is undesirable for $k$ to be small, since the hash function can not distinguish every $i^\textrm{th}$ character from every $i+k^\textrm{th}$ character. In mathematical terms you want the order of $b$ mod $n$ to be as large as possible.

The order of $b$ mod $n$ is always at most the Euler-Phi function $\phi(n)$. For a prime $p$, $\phi(p)=p-1$ while for non-primes $n$ it will be smaller. So taking $n$ to be a prime will allow more of the values of $b^k$ to be "useful". Ideally, one should take $b$ to be a primitive root modulo $n$, making that $b^k=1 \textrm{ mod } n$ does not hold for any value of $0<k<\phi(n)$.

Note that you can always construct instances for which the performance is poor, and to protect against "attacks" from an adversary you need to take the base and modulus to be random values.


Regular Expression for even-odd language of string

Constructing a DFA (and thus an NFA), is quite trivial, so let's focus on the regular expression. (well, you can always convert a DFA into a regular expression, but this will not be very insightful, is it?)

Let's start simple. How do we construct an expression that describes only even length strings (over $\{a,b\}$)? Or even more simple, how to construct an expression for a language of only even length strings over $\{a\}$?

If there's only $\{a\}$ in the alphabet, we either have none, or they come in groups of two, so a possible answer is $(aa)^*$.
When we have both $a$ and $b$, things become a bit more difficult. For instance, $(ab)^*$ is incorrect, since it doesn't allow $aa$. On the other hand, any expression of the form $(a^*b^*)^*$ not going to work, since we can't control the number of each letter. However, as before, we know that the letters must come in groups of 2, thus we should expect the form to be something like $(xy)^*$ with $x,y$ describing only even length strings, but what should $x,y$ be in this case? Well, we can just write all possible options, getting:

$$ ( aa+ ab+ ba+ bb)^*$$
(can you make it shorter?)

Now let's ask how do we get odd-length strings. Again, if the alphabet has only $a$, this would be quite easy - we can construct an even string, and add another $a$, getting:
$$ (aa)^*a$$

A similar approach works for the case where the alphabet is of size two:
$$ ( aa+ ab+ ba+ bb)^*(a+b)$$

Now a sanity check: we add the "a" or "b" only at the end. Maybe it comes in the middle, and not in the end?! Convince yourself that adding at the end is equivalent, and gives the right answer.

Finally, try to use the above ideas to solve your question. There is still some leap left, so don't give up too fast. Some hints:

    Hint1: the length of the final string must be odd (if it contains both letters)

.

    Hint2: get rid of one letter, so the length is even, and furthermore, both letters appear an even number of times!

.

    Hint3: don't forget to put back the one letter you got rid of. Convince yourself you placed it in the correct place...


What is complexity class language $L$ such that $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$?

Define
$$A := \bigcap_{\varepsilon > 0} O(n^\varepsilon) = \bigcap_{i \in \mathbb{N}} O(n^\frac{1}{i}).$$
This complexity class is analogous to
$$B := \bigcap_{i \in \mathbb{N}} \Omega(n^i),$$
the class of super-polynomial functions, in the sense that if $f$ is strictly increasing, $f \in A \Leftrightarrow f^{-1} \in B$. There isn't a "nice" description of $B$ so you wouldn't expect a "nice" description of $A$.

Note that $e^\sqrt[i]{n} \in B$ so $\log^i n \in A$.


Expectation Maximization Algorithm for simple naive Bayesian network

I finally found the solution
Expectation step is as follows
Calculate new probabilities of data points as follows
P(A|B,C)
which we break down to

  (P(A,B,C)/P(B,C) =

  (P(B|C,A) * P(C|A)*P(A)) / (sum of all P(B,C) for all A) =

since A is known then B & C is independent
therefore

  (P(B|C,A) * P(C|A)*P(A)) / (sum of all P(B,C) for all A) =

which we need to consider 3 binary variables, gives us 8 cases (2^3)
lets say for A = 1, B = 0, C= 1

  (P(B=0|A=1) * P(C=1|A=1)*P(A=1)) /
  ( (P(B=0|A=1) * P(C=1|A=1)*P(A=1)) + ( (P(B=0|A=0) * P(C=1|A=0)*P(A=0)) )

  =  P(A=1| B=0, C=1) = lets call it value val101

we use this value (val101) to update probability of each unknown data point that has B= 0 and C = 1 and A = 1.
Then update probability of each unknown data point where A=0, B=0 and C=1 with the (1-val101)

we do that for possible combinations of A, B and C
000
001
010
011
100
101
110
111

(I think this is already an M step - Maximization, but here it goes)

To calculate parameter theta for P(A=0) we do the following
count (sum of all probabilities) of each data point where A = 0 and we divide it by the original amount of data points
we do the same for the A =1

then we update conditional parameters
to update parameter theta of P(B=1|A=0)
we take a sum all the probabilities of all data points where A = 0 and B=1
and we divide it by the count (sum all the probabilities) of probabilities of data points where A =0
so its as follows

#(A=0,B=1) / #(A=0)  = theta P(B=1|A=0)

and we do that for all the conditional probabilities which are as follows

P(B=1|A=0)
P(B=0|A=0)
P(C=1|A=0)
P(C=0|A=0)
P(B=1|A=1)
P(B=0|A=1)
P(C=1|A=1)
P(C=0|A=1)

then you are done


Do exponents have higher time complexity than factorials?

In fact $e^n$ is $o(n!)$. We could show it using the Stirling approximation by taking limit
$$\lim_{n\rightarrow \infty}{\frac{e^n}{(\sqrt{2\pi n})(\frac{n}{e})^n}} = \lim_{n\rightarrow \infty}{\frac{e^{2n}}{(\sqrt{2\pi n})n^n}} = \lim_{n\rightarrow \infty}{\frac{1}{\sqrt{2\pi n}}\frac{e^{2n}}{n^n}}$$
Since $\lim_{n\rightarrow \infty}{\frac{1}{\sqrt{2\pi n}}} = 0$ we only need to calculate
$$\lim_{n\rightarrow \infty}{\left(\frac{e^2}{n}\right)^n}$$
The function $\frac{e^2}{n}$ decreases faster than any function $c^n$ where $0 < c < 1$ for sufficiently large $n$s (as $n$ goes to infinity), and so $\lim_{n\rightarrow \infty}{\left(\frac{e^2}{n}\right)^n} = 0$.
Regarding Quazi Irfan's comments about Matlab graph
I am not a Matlab user, but these are plots for $e^x$ and Stirling approximations of $n!$ using Wolfram script: plot (1\sqrt(2*pi*x)*(x/e)^x) from 0 to 6, plot(e^x) from 0 to 6

As you see $n!$ overtakes $e^n$ when $n=6$.


Anomaly/outlier detection using fuzzy clustering

As far as I know there is no unique definition for what is an outlier/anomaly. Therefore you'll have to decide by yourself what the characteristics of outlying data points in your data set are. This could be for example: distance to the cluster center (threshold), local neighbourhood (a data point that has no/few data points in its neighgbourhood might be an outlier) or statistical characteristics (an outlier doesn't 'fit' to the distribution of a cluster, e.g. Grubbs' method). You can find a survey of outlier detection methods in A Survey of Outlier Detection Methodologies by Hodge and Austin (2004).


Trouble seeing the contradiction in diagonalization proof

There is no contradiction, and the proof does not hold water. You are right: 'accepts' should be changed to 'rejects', and $D$ should be defined as

$$D=\{\langle M, x\rangle \quad | \quad M \underline{\underline{\text{ rejects }}}\langle M, x \rangle \text{ within }n\log(n) \text{ steps} \} $$

with $n=|\langle M, x\rangle|$, the length of the input. This way, the proof goes according to plan:

Proof. Suppose a $an+b$-time machine $T$ solves $D$. Take a sufficiently long $x$. Does $T$ accept input $\langle T, x\rangle$?

Suppose yes. Then $T$ accepts its input $\langle T,x\rangle$ within $an+b$, so $T$ accepts within $n\log(n)$. That's a contradiction, because by definition of $D$, $\langle T,x\rangle \in D \implies T \text{ rejects } x$.

Suppose no. Then $T$ rejects its input $\langle T, x\rangle$ within $n\log(n)$ steps, so $\langle T, x\rangle$ should be an element of $D$, so $T$ should have accepted. Contradiction $\square$


When Turing Machine behaves like Finite state automaton

Yes, this is (kind of) correct, in the following sense:

The set of languages that can be recognized by Turing Machines with a fixed tape is equivalent to the set of regular languages (i.e. the set of languages recognizable by finite automata).

The reason behind this is that such Turing Machines have a finite number of configurations, which is independent from the input.

Note that crucially, for this to hold we need one tape for the input which is read-only, and a fixed-space working tape.

A bit more precisely, for such a TM, we can construct a 2-way DFA, by having a state for every possible configuration of the TM, as well as a 2-way read only input tape. The latter model is equivalent to DFAs, by a clever construction using "crossing sequences".

An important observation, however, is that these machines can be far more succinct than their equivalent DFAs (or even NFAs).


Translating the in-order index of a node in a complete, balanced binary tree into the level-order index

I think it is possible by rescaling the in-order index to what it would be in a complete and full (perfect) tree, i.e. $perfect\_index = index*\frac{ceil_2(size + 1)}{size}$ where $ceil_2(arg)$ computes the next power of two of $arg$.
Then, the level at which this perfect-tree in-order index sits is given as follows: $level = \left \lfloor{log_2(size)}\right \rfloor - nr\_divisible_2(perfect\_index + 1)$ where $nr\_divisible_2(arg)$ computes the number of times $arg$ is divisible by 2.
This works because it seems like in a perfect tree, the number of times the $index + 1$ of a node is divisible by 2 corresponds to the inverse zero-indexed level number of the level it is contained in. $1 + \left \lfloor{log_2(size)}\right \rfloor$ represents the total number of levels ($nr\_levels$) in a complete tree, so that minus the inverse level index minus 1 should give the zero-indexed level index in narrow-to-wide (top to bottom) tree orientation.
Then, the numerical spacing between in-order node indices in zero-indexed top-to-bottom level $L$ is 2 for the bottom level, 4 one up, 8 one up etc, in other words: $spacing = 2^{nr\_levels - L}$. For a 1-indexed in-order index, there is an additional spacing of $\frac{spacing}{2}$ at the beginning of the level. The horizontal offset of the node into the level is therefore given by $h\_offset = \frac{perfect\_index + 1 - \frac{spacing}{2}}{spacing}$.
Lastly, the amount of nodes preceeding the level this index is contained in is given by the size of a perfect tree of depth $nr\_levels - 1$, which is $base = 2^{nr\_levels}−1$.
The zero-indexed level-order index into the perfect tree should now be $base + h\_offset$. Since the level-order index of the first $size$ (counted in breadth-first traversal order) nodes is the same whether the tree is perfect or complete, I think this index will also be the level-order index into the complete tree.
Note that I have no proof of any of this, and have not tested it yet. Specifically, what worries me most is the rescaling at the beginning and if that is allowed/will work at all. The rest might contain errors but is not fundamentally flawed I think.


Worst simultaneous blowup when converting to CNF and DNF

You haven't explained how you measure the size of a CNF/DNF – two common options are number of clauses/terms and total size of the clauses/terms.

The worst example is parity. Any CNF/DNF for parity must contain $2^{n-1}$ terms of size $n$. In contrast, this answer on cstheory shows that every CNF/DNF contains at most $2^{n-1}$ terms.

In the monotone case, the worst example is Majority. Majority has $\binom{n}{\lfloor n/2 \rfloor}$ many minterms/maxterms (for odd $n$), each of size $\lceil n/2 \rceil$. Since the set of minterms/maxterms is an antichain, by Sperner's theorem it contains at most $\binom{n}{\lceil n/2 \rceil}$ many minterms/maxterms. Moreover, the LYM inequality easily implies that the maximum total size of sets in an antichain is $\lceil n/2 \rceil \binom{n}{\lceil n/2 \rceil}$, exactly matching the performance of Majority.


Is there any merging procedure for multiple scenes taking from RGB-D to avoid noise?

Yes, one technique is known as super-resolution imaging.  There's a rich literature on the subject, at least for RGB images.  You could check Google Scholar to see if there has been any research on super-resolution for RGB-D images (e.g., from 3D cameras such as Kinect, Intel RealSense, etc.).