Minimum-average-cost subtree that is not necessarily spanning

Tried to add this to the comments thread but stack overflow won't let me (new account)

@j_random_hacker I was thinking along similar lines to DP (a recursive algorithm that ran through the subtrees out to the leaves) but I hit a problem - I don't think the problem has an optimal substructure.

If you consider the graph in the image below, if x=1 then the 30-weight-edge is not part of the optimal solution (100,1,1,1) whereas if x=40 then it is (100,1,1,30). Inclusion of a specific edge in the optimal solution depends upon the weight of edges in completely separate parts of the graph.

I'd actually started writing some code before I realised. My recursive function assumed that given a subtree & the path from root to subtree you could make a decision but this counterexample broke it :(


Solving the emptiness problem for a CFG in Chomsky normal form (linear)

Yup, it can be done.  For each nonterminal $A$, introduce a boolean variable $x_A$, with the intent that if $x_A$ is true, that means $L(A)$ is non-empty.  Then you can convert each production into a corresponding Horn clause:

$A \to BC$ becomes $(x_B \land x_C) \implies x_A$
$A \to a$ becomes $x_A$
$S \to \varepsilon$ becomes $x_S$

Let $\varphi$ denote the conjunction of these Horn clauses.  Find the minimal satisfying assignment for $\varphi$; that can be done in linear time.  If this assignment makes $x_S$ true, then the language is non-empty, otherwise it is empty.

Alternatively, if you prefer a more direct algorithm, here is a standard one that you might see in textbooks.

Start out with all nonterminals unmarked. If you see a rule $A \to a$, mark $A$.  If you see a rule $S \to \varepsilon$, mark $S$.  Whenever you mark a nonterminal, check all rules of the form $A \to BC$ where it appears on the right-hand side; if both $B$ and $C$ are marked, mark $A$.  Repeat until convergence.  At that point, all marked nonterminals correspond to nonterminals that generate a non-empty language, so the language is non-empty iff $S$ is marked.

This also runs in linear time.  It takes a little more work to see why, but it's true.  In particular, each nonterminal can only be marked once, and each rule of the form $A \to BC$ will only be checked at most twice (once when $B$ is marked, once when $C$ is marked), so the amount of work you do is $O(1)$ per nonterminal plus $O(1)$ per rule, which is linear in the size of the grammar.  It does require suitable data structures that map from each nonterminal to a list of all rules containing it on the right-hand side, but that can be built in advance in linear time as well.


Product Matching problem in pattern matching

Hint: Starting with the original text, form a sequence $s_1,\ldots,s_n$ by the rule $s_i = t_i/t_{t-1}$, and similarly from the original pattern form a sequence $q_1,\ldots,q_m$ by the rule $q_j = p_j/p_{j-1}$. Look for the pattern $q$ inside the text $s$.


Some people in the literature (very few actually) do not consider missing transitions as nondeterminism, and given a DFA, they allow themselves to remove all transitions that lead to states from which we cannot reach an accepting state. The reason for that is technical, as sometimes it may simplify proofs a bit. Or it could be a matter of taste.
Intuitively, allowing missing transitions is justified as nondeterminism, or guessing occurs only when we have a choice, that is, when we have at least two transitions $\langle q, \sigma, s_1 \rangle$ and $\langle q, \sigma, s_2 \rangle$, going out from the same state $q$, and are labeled with the same letter $\sigma$. So, DFAs with missing transitions, or more accurately NFAs such that for every state $q$, and letter $\sigma$, it holds that $|\delta(q, \sigma)|\leq 1$, are considered deterministic in the sense that they have at most one run on a given input word.
The most common formal definition of a DFA does not allow missing transitions. Please note that it does not really matter to which definition you stick as long as you're consistent with it.
Also, given a DFA, it is easy to remove all transitions leading to a state from which we cannot reach an accepting state (because detecting states that do not lead to an accepting state can be done in polynomial time), and this does not affect the automaton's language. Conversely, given an automaton with missing transitions, you can direct all missing transitions to a rejecting sink which is a rejecting state with a self loop labeled with every letter.


The reason you can't just take $G$ as an input to $A$ is that (strangely enough) $A$ only works on connected graphs.

You want to prove that if $A$ exists, then Independent Set is solvable in polynomial time.  The reason you can prove that is by using a polynomial time reduction.   You have proved that if $A$ exists, then $A$ can solve Independent Set on any graph by using your trick of adding a universal vertex.

You have also proved that Independent Set on non-connected graphs is not particularly much easier than on connected graphs.


I didn't really understand your problem description, but if you go by the timezone analogy, the only thing stopping you from using Djikstra's algorithm are the negative costs on some edges (ie.: some edges go back in time). If this is the problem, you can get around it by using an alternate algorithm that can handle negative edges, like Bellman-Ford


Why this greedy algorithm does not return the optimal solution to this NP-hard problem?

One thing (which has been pointed out in the comments) is that it is unclear what you mean when you say "union". It appears that what you're doing is simply excluding items assigned to previous bins (but perhaps I do not understand, because "union" is a strange word for this). For example, when you've assigned 1,2 to bin 1 and 2,3,4,5 to bin 2, in the first step, in the final output you only assign object 2 to bin 1, and not bin 2.

Under this assumption, here is a simple example that shows that your greedy algorithm is not optimal. Assume we have two bins, both with capacity 5. Assume we have four items, with weights w_1 = 1, w_2 = 2, w_3 = 3, w_4 = 4 (we'll assume each item has the same weight for both bins). Then if you start assigning from smallest weight upwards until the bins are filled, your assignment is:

bin 1: items 1 and 2
bin 2: items 1 and 2

and after you exclude previously assigned items you end up placing items 1 and 2 in bin 1 and nothing in bin 2 (which is clearly not optimal, since you can place either of the other items in bin 2).

Perhaps you mean a different greedy algorithm, where first you assign 1 and 2 to bin 1, and then (since 1 and 2) are already assigned, you skip those and start again from lightest to heaviest weight, assigning item 3 to bin 2 (upon which there is no space for item 4). This assigns items 1, 2, and 3, and gets a score of 3.

But of course, it is possible to assign all the items, by assigning 1 and 4 to bin 1, and 2 and 3 to bin 2. The greedy algorithms miss this assignment.

As you've mentioned, this problem is NP-hard; in fact, it is hard even for the version where there are only two bins and the item weights are the same for all bins, where it reduces to the Subset Sum problem.


Is there an efficient algorithm for determining the probability a large randomly chosen integer is not divisible by any integer of some set?

Let $\mathbf x$ be a random number in the range $1,\ldots,N$, and let $E_i$ denote the event that $\mathbf x$ is divisible by $a_i$. You are interested in the probability that none of the events $E_1,\ldots,E_m$ happen (in your case, $m = 10$). Using the inclusion-exclusion principle, this reduces to computing the probability of the events of the form $E_{i_1} \land \cdots \land E_{i_k}$, that is, $\mathbf x$ is divisible by all of $a_{i_1},\ldots,a_{i_k}$. Since a $\mathbf x$ is divisible by a bunch of numbers iff it is divisible by their LCM, it suffices to determine the probability that $\mathbf x$ is divisible by $a$.

Among $1,\ldots,N$, the numbers divisible by $a$ are
$$
a,2a,3a,\ldots,\lfloor N/a \rfloor a,
$$
in total $\lfloor N/a \rfloor$ numbers. Hence the probability that $\mathbf x$ is divisible by $a$ is exactly
$$
\frac{\lfloor N/a \rfloor}{N}.
$$


Different ways to generate a big number with some small numbers

This is a well-known problem called the subset sum problem. Essentially we are looking for a subset of the elements that sums up to a target value, P. The problem is NP-hard, meaning it does not admit a polynomial time solution unless P = NP.  Here is a link that explains how to solve this problem. There are multiple algorithms for the problem. The recursive one runs at in an exponential time of $O(2^n)$. This problem is mostly associated with a Dynamic Programming solution since its run-time is $O(P\cdot n)$, such a running time is called pseudo polynomial, since it is polynomial in the value of the input instead of its size (which is the log of the value).


Constructors are used to initialize the object’s state. Like methods of, a constructor also contains collection of statements(i.e. instructions) that are executed at time of Object creation.A constructor is invoked at the time of object or instance creation.


There are several reasons why your standard library implementation of exp is slower than you might hope:

It should to be accurate to 0.5ulp (or 1ulp at worst), no matter what number you give it. This means that special care may need to be taken, say, in the subnormal range.
It needs to work for all floating point numbers, and return a reasonable answer for all of them. Assuming that you're on an IEEE-754 platform, this includes NaN, Inf, etc. The standard explains what the "correct" answer is for all of those cases, and the library function needs to get it right.
It may not be specialised for your specific instruction set (i.e. your CPU may have some advanced floating-point instructions that libc doesn't use by default).

This is what it means to be general-purpose.
Chances are that your standard library has had a lot of effort put into it, and you cannot beat it and still be general-purpose. To get more performance, you need to relax some restrictions. So we're going to need some details. How much accuracy is enough? Can you assume anything about the range of inputs?
I've gone through a typical implementation elsewhere (see this previous answer), and that should help you get an idea of how these things can be implemented.


On submultisets of given cardinality and bound that sum to $0$

Assuming that $c$ is fixed, this can be solved using dynamic programming in quasipolynomial time. We compute inductively all possible sums of all submultisets of size $k$ for all $k \leq \lceil m^\alpha \rceil$. Since each such sum is at most $2^{\log^c m} \lceil m^\alpha \rceil$, this algorithm runs in $O(2^{O(\log^c m)} m^{O(1)})$, which is quasipolynomial. This suggests that the problem is not NP-hard.


Since you solved the first question, let me answer the second one. If you don't mind, I will use $h$ instead of $h'$ for simplicity. Let $L$ be a regular language and let $K = h^{-1}(L^*)$. Since regular languages are closed under inverses of homorphisms, $K$ is regular. Moreover, if $u, v \in h^{-1}(L^*)$, then $h(u), h(v) \in L^*$ and hence $h(uv) = h(u)h(v) \in L^*$. It follows that $uv \in h^{-1}(L^*)$ and thus $K = K^*$. Consequently, $h^{-1}(L^*) = K^*$, which answers your question.


Is the complement of the Turing machine equality language not recursively enumerable as well?

The language that determines if two Turing machines are equivalent is not recursively enumerable because you can reduce it to the emptiness problem (does a Turing machine take no input).

You have the reduction the wrong way around. You're saying "Telling if two Turing machines are equivalent is impossible because, if I could solve some impossible problem, I could solve this one." Well, that's like saying, "Lifting a can of beans is impossible because lifting a truck is impossible and, if I could lift a truck, I could lift a can of beans."

Rather, you want to reduce the known-hard problem to TM equivalence: "If I could solve this problem, I'd be able to solve this impossible problem." Specifically, if you could solve the TM equivalence problem, you could solve the TM emptiness problem by asking, "Is the machine I'm interested in equivalent to this machine that immediately rejects every input?"

  Then for the complement of this language (ie. if two Turing machines are not equivalent) would you be able to reduce that to the non-emptiness problem (a Turing machine takes some input)?

Again, you mean the reduction to be the other way around. So, we need to show that the non-equivalence problem being RE would make the non-emptiness problem RE.  But the non-emptiness problem is RE: just dovetail simulations of the machine on all inputs and accept if it accepts one of them.  So there's no contradiction available, here.

  However, I thought the Turing machine equality language is an example where both a language and its complement are not recursively enumerable.

Correct.  Intuitively, you can't enumerate the language of inequivalent TMs because to do that would require you to definitively say "This machine loops on some input that this other machine accepts." And, indeed, we can turn this intuition into a formal proof.

First, observe that the Turing machine non-halting problem (given a description of a Turing machine $M$ and an input $x$, does $M(x)$ loop?) is not RE. This is the complement of the halting problem so, if it were RE, then both the halting problem and its complement would be RE. But if a language and its complement are both RE, they're both recursive, and we know that the halting problem isn't recursive.

Now, observe that, if we could solve the TM inequivalence problem, we could solve the non-halting problem. To determine if $M$ loops on input $x$, just ask if it is inequivalent to the machine "If the input is $x$, halt; otherwise, do the same as $M$."


The role of three values $V_1, V_2$ and $V_3$ isn't clear for me, but anyway:

Step 1. Sort the original list in parallel by key $K$ - you'll get a list of records $(K, V_1, V_2, V_2)$, where all the records with the same key are stored together in "buckets".
Step 2. Process each bucket concurrently, calculating all the averages.

There are many parallel sorting algorithms, you can choose one depending on your computational model.


NP-completeness of a problem with pretty fast algorithm

Yes, such problems can be NP-complete.

Consider classical NP-complete graph problems like clique.

Clique has an $O(2^n)$ time algorithm, where $n$ is the number of vertices. However the input for clique is the adjacency matrix of the graph, which has $n^2$ bits. Therefore when the size of input is measured in bits, clique has an $O(2^\sqrt{n})$ time algorithm, which is $O(2^{\alpha n})$ for any positive $\alpha$.


What she actually describing is the following construction.
For an $\epsilon$-NFA  $ A = \langle Q, \Sigma, \delta, Q_0, F \rangle$, the intuitive idea is as follows. Consider a state $q$. If there is an $\epsilon$-transition from q to $s$, then whenever we reach q, we can also reach $s$. Yet, there may be $\epsilon$-transitions from $s$, so we also need to take them into account.
For every state $q\in Q$, let $EC(q) \in 2^Q$ be the $\epsilon$-closure of $q$ which is formally defined as
$EC(q) = \{s \in Q: \text{ $s$ is reachable from $q$ using only $\epsilon$-transitions}\}$. In particular, for every state $q\in Q$, $q\in EC(q)$ as a state is reachable from itself by a path of length
0.
Now Given the sets $EC(q)$ for every state $q \in Q$, we define the DFA B as follows.
$B = \langle 2^Q, \Sigma, \kappa, \bigcup\limits_{q\in Q_0} EC(q), \{S\in 2^Q: S\cap F \neq \emptyset\}\rangle$, where
$\kappa(T, \sigma) = \bigcup\limits_{q\in T} \bigcup\limits_{s\in \delta(q, \sigma)} EC(s)$, for every set of states $T\in 2^Q$, and letter $\sigma \in \Sigma$. That is, given a non-$\epsilon$ transition $\langle q, \sigma, s \rangle$, we move not only to $s$, but also to all the states that are reachable from $s$ via $\epsilon$-transitions.
So indeed, in the first attached image, the state $3$ has no outgoing transitions that are labeled with letters from $\Sigma$, and thus, for every set $T$ that contains state $3$, the state $3$ does not contribute any states in the set $\kappa(T, \sigma)$, for every letter $\sigma$. However, in the 2nd attached image, there is a 0-labeled transition going out from the state 3. So, in the DFA $B$, when you read the letter 0 from a set $T$ that contains the state $3$, then the state $3$ contributes the states $\kappa(\{3\}, 0)$ in $\kappa(T, 0)$. Now since $\delta(3, 0) = \{4\}$, we have that $\kappa(\{3\}, 0) = EC(4) = \{2, 4, 5, 6\}$, that is, you're right that the state $3$, upon reading the letter 0, contributes the states $2, 4, 5, $ and $6$.
Important note: she is doing $\epsilon$-transitions removal and the subset construction at the same time. I don't like that at all as it is confusing, also I don't see the formal construction itself in the video. I suggest that you try to do $\epsilon$-removal alone (without determinization). That may give you a better understanding as a start.


If I write code in machine language, then I have access to the CPU in both modes (user and kernel), since the OS is bypassed, correct?

No. The Operating System is going to use context switching and virtual memory to hide the fact that there are multiple processes running on the computer. Native code does not mean you have full control to the CPU registers, global physical memory. Your program, if not privileged, is still running in user mode. You need to use syscalls to do lower level tasks. The operating system provided a virtual and abstract environment for the program to make them convince themselves they are running on a dedicated machine.


In the recursive definition

$$ P(a,b) = \begin{cases} P(2a,\lfloor b/2 \rfloor) & b > 1, b \text{ even} \\
P(2a,\lfloor b/2 \rfloor) + a & \text{if } b > 1, b \text{ odd} \\
a & \text{if } b = 1
  \end{cases} $$

the value of $b$ always decreases in a recursive call. Therefore you should prove the property $P(a,b) = a \cdot b$ by induction in $b$. We use the strong induction principle.

Base case - $b=1$:   $P(a,1) = a$ and $a \cdot 1 = a$.

Inductive step - assume for all $k < n$, prove for $n$:

Suppose $b$ is even. We then have $P(a,b) = P(2a,\lfloor b/2 \rfloor)$. Since $b$ is even, we have $\lfloor b/2 \rfloor = b/2$. Since $\lfloor b/2 \rfloor < b$, we have by induction hypothesis that $P(2a,\lfloor b/2 \rfloor) = 2a \cdot \lfloor b/2 \rfloor = 2a \cdot b/2 = a \cdot b$.

Suppose $b$ is odd. Since $b$ is odd, we have $\lfloor b/2 \rfloor = (b-1)/2$. We now have $P(a,b) = P(2a,\lfloor b/2 \rfloor) + a = 2a \cdot (b-1)/2 +a = a(b-1) + a = a (b-1 + 1) = ab$.


Is List comprehension equivalent to composition of filter and map?

Basic difference

List comprehension and combination of filter and map may be equivalent
only in languages with lazy evaluation.

The reason is that, without lazy evaluation, filter and map will want
to evaluate the whole lists given as arguments, while comprehensions
are built from the start as structure that evaluate on a call by need
basis.

Hence, comprehensions can in principle include infinite lists, and
some languages allow that (e.g. Python)

Also, evaluating all elements of a list may lead to non terminating
programs, if the evaluation of one element (not really needed) does
not terminate, while the corresponding comprehension may never be
asked to produce that element, and will not prevent termination of the
program.

The semantics of the program may also be changed if the computation of a list element produces side-effects. The ccomprehension will produce the side-effects later, if at all, during the execution of the program.

My interpretation of the wikipedia text

From what I always understood, comprehension means the same as
intension, which is itself opposed to extension
(wikipedia).

An extensional definition of a set is an actual enumeration of its
elements (which works moderately well for infinite ones).

An intensional definition is the usual technique that defines the
elements by specifying some property they must have.

The computational counterpart is comprehension, that provides a way of
computing the elements, rather than enumerating them explicitly.

Comprehension is in a sense the Curry-Howard counterpart of intension.

The counterpart for extensional sets is a data structure that
enumerates the elements explicitly.

Now, one can always define a property by extensionally giving the set
of elements that have that property, so that extensional definitions
can always be seen as a special case of intensional ones. But that
does not seem to be the point of view of wikipedia.

The wikipedia text is not too clear, and could be more explicit (no pun
intended)

My feeling is that they do want to exclude lists that are extensional,
maybe for typing reasons. It is not supposed to be a specific data-structure,
but an object to be used as an iterator , or as a stream possibly
(it is very remindful of the literature on coroutines and generators).

Direct use of map and filter with produce extensional lists, data structures actually containing all values.

But similar constructions with the same predicates and functions in comprehensions will produce a non extensional version of the same lists.

Computationally, comprehensions will be naturally evaluated in a call by need mode, which may allow different program organizations. A comprehension need not be finite, depending on how it is used.

Analysis of the various languages that use the concept might confirm,
or not, this understanding.


If $C = \prod_i C_i$ is a prime factorization of $C$ then $N(C) = \prod_i N(C_i)$, where $N(\alpha + \beta i) = \alpha^2 + \beta^2$. Furthermore, $\pi$ is prime if either (i) $N(\pi) = 2$, (ii) $N(\pi) = 4a+1$ is prime, (iii) $N(\pi) = (4a+3)^2$ is the square of a prime. So factoring $C$ reduces to factoring $N(C)$.


Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time?

Asymptotically, you're right: for big-enough inputs, the $\Theta(n\log n)$ algorithm can be faster. However, this is only true for big enough $n$.  It might be that "big enough" means "far bigger than any actual computer can store" or even just "plenty bigger than any input I care about".

For a specific example of this, look at matrix multiplication algorithms.  For $n\times n$ matrices, the standard pencil-and-paper algorithm takes time $\Theta(n^3)$.  Strassen's algorithm essentially considers the matrix to be a matrix of smaller matrices and improves the running time to $O(n^{2.81})$ but the algorithm is more complicated, so the constants hidden by the big-$O$ mean that Strassen is only likely to be faster for about $n>100$.  Coppersmith–Winograd is $O(n^{2.37})$ but is even more complicated and, as far as I'm aware, isn't used in practice, because it only wins on matrices that are too big for people to want to multiply anyway.

Another aspect is that some algorithms might be better or worse than others on real computers.  If an algorithm's data access patterns play nicely with the cache, it can be thousands of times faster than code that sprays memory accesses all over the address space: algorithms based on hash tables are particularly bad at for that.  $n^2 < 1000n\log_2 n$ for all $n$ less than about $14\,000$.  Likewise, an algorithm with a simpler branching structure in the code might run faster because the CPU pipeline is full more of the time.


The algorithm to compute $G'$ is really easy: just return $G$.
Indeed, given any $G=(V,E)$ the only graph $G'=(V, E')$ such that $U \subseteq V$ is a vertex cover of $G$ iff $U$ is a vertex cover of $G'$ is $G$ itself.
To prove this you can show that we must simultaneously have $E \subseteq E'$  and $E' \subseteq E$.
Proof that $E \subseteq E'$: Suppose towards a contradiction that $E \nsubseteq E'$. Then $\exists (u,v) \in E \setminus E'$. The set
$U = V \setminus \{u,v\}$ is a vertex cover for $G'$ but not for $G$.
Proof that $E' \subseteq E$: Suppose towards a contradiction that $E' \nsubseteq E$. Then $\exists (u,v) \in E' \setminus E$. The set
$U = V \setminus \{u,v\}$ is a vertex cover for $G$ but not for $G'$.


Why do logic gates behave the way they do?

As stated by user120366, 16 possible 2-input logic gates exist, I've tabulated them for you here:

A|B||0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f
-+-++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
0|0||0|0|0|0|0|0|0|0|1|1|1|1|1|1|1|1
0|1||0|0|0|0|1|1|1|1|0|0|0|0|1|1|1|1
1|0||0|0|1|1|0|0|1|1|0|0|1|1|0|0|1|1
1|1||0|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1

A and B are the inputs, 0 through f are the possible permutations of outputs.

These gates have been named:

0 = FALSE
1 = AND
2 = A NIMPLY B (A AND NOT B)
3 = A
4 = B NIMPLY A (B AND NOT A)
5 = B
6 = XOR
7 = OR
8 = NOR
9 = XNOR
a = NOT B
b = B IMPLY A (A OR NOT B)
c = NOT A
d = A IMPLY B (B OR NOT A)
e = NAND
f = TRUE

6 of these (0,3,5,a,c,f) discard one or both inputs. The IMPLY and NIMPLY gates are rare, though they are certainly used in formal logic. AND, OR and XOR are easiest for humans to reason with, but for physical hardware, NOR and NAND are also used heavily, because they can be simpler to implement and make smaller circuits. The same probably holds for XNOR.

So, as stated earlier, it's not so much that we decided that the gates should behave this way, but that 16 possible gates can be defined, and we came up with descriptive names for them.


When is splitting a collection coins two ways NP-complete?

Problem 2 is the same as the NP-complete problem PARTITION. Problem 3 is also NP-complete, since we can always arrange all denominations to be multiples of 10 cents.

The most interesting case is Problem 1. If the jar contains in total $2S$ cents, then we are looking for a subset of the jar summing to $S$. If $S$ is odd then there is no solution unless the jar contains a 1 cent coin, in which case we take one such coin and put it aside (it forms part of the solution), and update the target sum to $S-1$. Is $S$ is even we do nothing. In both cases, the new target sum is even. The number of 1 cent coins which appear in a solution must be even, and so we can group the 1 cent coins in pairs, replacing them with 2 cent coins (if there is an odd number, we just throws the odd one out). Now we repeat the same procedure with the 2 cent coins, the 4 cent coins, and so on, until we either reach the target sum or find out that the target sum is not reachable. This algorithm runs in polynomial time.


Why are threads called the unit of dispatch?

"Unit of dispatch" just means "the thing that gets scheduled."


Difference between end carry and overflow

I'm assuming we are talking about Two's Complement integers (positive and negative of course).  You need to first understand the boundaries:

The largest positive value is:

$$
2^{n - 1} - 1 = 0111\ 1111\ 1111\ ...
$$

The "largest" negative (most negative value) occurs at:

$$
-2^{n - 1} = 1000\ 0000\ 0000\ ...
$$

Adding any positive value to $2^{n - 1} - 1$ will result in an overflow!  Likewise adding any negative value to $-2^{n - 1}$ will also result in an overflow (or perhaps more precisely and underflow--but that has a different meaning when it comes to floating point values).

It should be clear that adding anything "above" $1000\ 0000\ 0000\ ...$ ($-2^{n - 1}$) to $0111\ 1111\ 1111\ ...$ ($2^{n - 1} - 1$) will result in a carry!  Yet by the above we know that adding any of these values $\geq 1000\ 0000\ 0000\ ...$ will simply be subtracting a value that results in a valid (possibly negative if it's $-1$) result.  On the contrary, if we attempt to add a positive value such that the first digit is $0$, then we get no carry and yet we get overflow.

When we try to add two negatives ($1...$ and $1...$) we are bound to have a carry but this always results in $1\ 0000\ 0000\ ...$ added to some two's complement value.

The algorithm for determining overflow is very simple: if you add two positive numbers then you should get a positive and if you add two negative numbers then you should get a negative (and if you add a positive and a negative, you will never get the "wrong" result).

I don't know if that helps or not because I'm not too sure what you mean by "end carry".


Whether $K(a|a) = 0$ could depend on your universal computer. The only thing you can say in general is that $K(a|a) \leq C$ for some constant $C$ independent of $a$.

You can arrange for a universal computer for which $K(a|a) = 0$ for all $a$, and then indeed $K(b|a) > 0$ for all $b \neq a$, since there is only one program whose length is zero, and given $a$ it generates $a$.


Can someone clarify this unification algorithm?

First, unification algorithms are tricky. Studying other textbooks will help.

Second, things will probably get clearer if you look at actual code implementations. Have a look at the online code repository for your textbook. The code in Lisp, for example, is here.

A helpful note to remember when looking at first-order unification algorithms is that function symbols and predicates must match exactly in order to be correct.

On to your questions.

(Where is val declared?) This is a notational trick in the pseudocode that creates more confusion than good. It hearkens back to the old days of Lisp association lists. Maybe giving an example of theta would help: ((x 1) (y 2) (z 3)). This means x is bound to 1, y is bound to 2, and z is bound to 3. So var/val refers to a pair in theta like (x 1). So the first clause in UNIFY-VAR means, "if the pair (var val) is a member of theta, then return the result of doing UNIFY on whatever val is in that pair, with x and theta".
(How do function symbols get unified?) Remember that function symbols must match exactly as I pointed out above. So actually the clause else if x = y then return theta covers this. This is via a recursive call through an outer COMPOUND case.


I'm going to give the same answer as I gave the previous time this question came up.

First, understand that there is no good formal definition of "algorithm" at the time of writing. The key word here is "formal".

However, there are smart people working on it.

What we know is that whatever an "algorithm" is, it sits somewhere between "mathematical function" and "computer program".

A mathematical function is formal notion of a mapping from inputs to outputs. So, for example, "sort" is a mapping between a sequence of orderable items and a sequence of orderable items of the same type, which maps each sequence to its ordered sequence. This function could be implemented using different algorithms (e.g. merge sort, heap sort). Each algorithm, in turn, could be implemented using different programs (even given the same programming language).

So the best handle that we have on what an "algorithm" is, is that it's some kind of equivalence class on programs, where two programs are equivalent if they do "essentially the same thing". Any two programs which implement the same algorithm must compute the same function, but the converse is not true.

Similarly, there is an equivalence class between algorithms, where two algorithms are equivalent if they compute the same mathematical function.

The hard part in all this is trying to capture what we mean by "essentially the same thing".

There are some obvious things that we should include. For example, two programs are essentially the same if they differ only by variable renamings. Most models of programming languages have native notions of "equivalence" (e.g. beta reduction and eta conversion in lambda calculus), so we should throw those in too.

Whatever equivalence relation we pick, this gives us some structure. Algorithms form a category by virtue of the fact that they are the quotient category of programs. Some interesting equivalence relations are known to give rise to interesting categorical structures; for example, the category of primitive recursive algorithms is a universal object in the category of categories. Whenever you see interesting structure like that, you know that this line of enquiry will probably be useful.


Computational complexity for more general problems

I can answer for the first part.

Computational completely is usually defined using Turing machines, that operate over finite alphabets, so questions about algorithms over the reals cannot be answered in that framework.

With regards to possible approaches to machines over the reals, they can be broadly divided into machines that work over representation and machines that can directly and atomically manipulate real numbers.

See also this question here on SE.


Is there an NP-complete problem, such that the decision version of its counting problem is not PP-complete?

Putting your question in more precise terms, you ask whether the following claim holds:

$* \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow count_R \text{ is PP-complete}$

Where $count_R$ is defined as follows:

$count_R=\left\{(x,k) \big| \hspace{1mm} \left\lvert\left\{y : R(x,y)\right\}\right\rvert\ge k\right\}$.

We call a relation $R(x,y)$ NP-complete if it is computable in polynomial time, and the language it defines $L_R=\left\{x | \exists y \hspace{1mm} R(x,y)=1\right\}$ is NP-complete.

We talk in terms of relations, since as you mentioned, the counting version has to be defined relative to some specific verifier.

It seems that this is an open question, as (*) implies:

$** \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow \#R\text{ is #P-complete}$

Where $\#R(x)=\left\lvert \left\{y : R(x,y)\right\} \right\rvert$.

To see why * implies the above, let $R(x,y)$ be some NP-complete relation. Using (*), $count_R$ is PP complete, so $count_{\text{SAT}}\le_p count_R$. In that case, $\#SAT\in\mathsf{FP}^{\# R}$ and thus $\#R$ is $\# P$-complete (use binary search, where in each cutoff you apply the reduction from $count_{\text{SAT}}$ to $count_R$ and query the $\#R$ oracle on the result).

To my knowledge, (**) is currently open. See this related question from cstheory. Also related.


Determine if a string is a permutation of another string efficiently

You can establish a trivial lower bound of $\Omega(n)$, because you must at least observe all characters of each string (in worst case) to determine if they are permutations of each other. So $O(n)$ time complexity is the best you could do.

Perhaps you could improve the space complexity though. Raphael describes a unique approach here to achieve constant space and linear time using properties of prime numbers.


Applicability of Machine Learning on Images.

It looks plausible that this is the kind of problem machine learning will be good at.  I suspect you might be able to achieve much higher accuracy, but the only way to know for sure is to try it.

For your current approach, the size of your training set is reasonable, assuming you're using a linear SVM.  A linear SVM will have about 360 parameters, and your training set is larger than that, so this is not an unreasonable size of training set.

There are many things you could try, to see if they improve accuracy.  Here are two.

Translation invariance. The properties of an object don't depend on where it is located.  However, the way you're currently training the SVM doesn't take this into account, so you might be missing an opportunity to do a lot better.

One potential solution: first, take all of the positive samples in your training set (the ones that do contain a object) and shift them left or right so the object is in the same position in each (always exactly in the middle).  Take each negative sample and shift it a random amount. Then, train the SVM on the modified training set.  This builds a SVM model that recognizes images that contain an object at the center.  Once you've got a trained SVM model, given a new image I, try all possible ways to shift it and apply the SVM classifier to each; if any of those says "yes", then you've found an object.

A different potential solution that might work better: construct features that are inherently translation-invariant, by definition.  For instance, instead of using the 360 elements of the 1D array as a feature, use the average of the array, or the standard deviation.  Then train a classifier on those few features.

You can probably design some other, more complex translation-invariant features.  For instance, you could try computing the average or standard deviation of the first derivative of the 1D array (the average or standard deviation of $A[i+1]-A[i]$, over all $i$).  Or, rather than doing this on the reduced 1D array, even better, do it on the 2D array: compute some statistics of the first derivative (in the horizontal direction) of the 2D image, and similarly for the first derivative (in the vertical direction).  You could also build a histogram of the intensity distribution of the original 2D image (e.g., 10 buckets; the bucket for 0.2-0.3 counts the number of pixels whose intensity is in the range $[0.2,0.3)$).  You could grid the 2D image into 90x90 non-overlapping cells, where each cell is a 4x4 pixel square, compute the average intensity of each cell, and then compute a histogram of those values.  For instance, this might capture the fact that when there is an object there will be many cells that are all-white, whereas an image with no object probably will have few or no such cells.  Try different ideas along those lines, and you might find some that are effective.

Convolutional neural networks. By reducing to a 1D array, you've thrown away a bunch of information.  You could try applying a CNN classifier directly to the 2D image.  There's been a lot of work on how to do this in the computer vision community over the past 5 years, and CNN's seem to do significantly better than anything else.  You could take a look at the Caffe toolset (or Theano or Tensorflow or any of a number of others).  This might benefit from having more training images, but  you can try it on the set you've already got.

Regularization. Don't forget to use regularization and to optimize hyper-parameters (often, using cross-validation and grid search).


Turing Machine that computes maximum steps of halting machines

Hint: If you could compute $f(m,n)$, then given a Turing machine $M$ with $m$ states and an input $x$ of length $n$, the Turing machine will either stop within $f(m,n)$ steps or never halt.

This argument actually shows that it is impossible to compute any upper bound on $f(m,n)$. In other words, $f(m,n)$ grows faster than any computable function.


Calculate the minimum absolute difference between the maximum and minimum number from the triplet of 3 arrays

Can you see the following equality?
 abs( max(a,b,c) - min(a,b,c) ) = max(abs(a - b), abs(b - c), abs(c - a))

Here is a hint to prove the equality.

   Without loss of generality, we can assume a >= b >= c.

By the way, the first abs is not necessary since max(a, b, c) is always no less than min (a, b, c).


Rice's Theorem for Total Computable Functions

Almost

The correct answer is that a property of recursive languages is r.e. if and only if it can be verified by a finite number of values (though unlike in your example the exact number of values can be unbounded, so $k$ can depend on $n$). In fact, the wikipedia page for Rice's theorem has a section on this:

  ...the analogue says that if one can effectively determine for every recursive set whether it has a certain property, then only finitely many integers determine whether a recursive set has the property.

More precisely, a property is r.e. iff there is a r.e. set $T_1$ with the prefix property (i.e.- no string in $T_1$ is a prefix of another) such that $\phi_n$ has the property iff there is some $k$ such that the sequence $\phi_n(0), ..., \phi_n(k-1)$ is in $T_1$ (we can make sense of a sequence being in a set of natural numbers by encoding this as $p_1^{\phi_n(0)}\cdot p_2^{\phi_n(0)}\cdot ...\cdot p_{k}^{\phi_n(k-1)}$ where $p_i$ is the $i$th prime). A property would be recursive iff it is r.e. and co-r.e.

This pretty much says that we can get no more information out of the index $n$ than the function $\phi_n$ itself, because any computable property must be computable only using calls to the function $\phi_n$. This may sound trivial, but it is no means obvious since a priori the input $n$ might have some extra non-syntactic information computably nestled into it.

Rice's theorem essentially states that no extra non-syntactic information about partial recursive functions can be computably nestled into their Godel encodings. As it turns out this is also equivalent to the above characterization, so the same thing holds for total functions as well. I suppose one could make this statement even stronger by generalizing to even more general classes of functions, but I do not know if this is true.


How does asynchronous operations save time in I/O

Issuing the ten requests in parallel is unlikely to give you a tenfold speedup, but will usually give you some speedup. It depends on where the bottleneck is. If the images are 5 MB each and your Ethernet/WiFi connection can only transfer data at 1 MB/s, then your network card will essentially be tied up for 5 seconds per image, and issuing the requests in parallel probably won't help. If the images are 5 kB each and you have a gigabit fiber Internet connection, and the 5-second delay is due to the servers being very slow to respond, then your network card will be idle almost all of the time, and you may actually get all of the images back in 5 seconds total if you issue the requests in parallel.
The network card only sends and receives small isolated data packets, typically of about 1500 bytes. It doesn't understand the concept of a TCP or HTTP connection. When it's not sending or receiving packets related to one connection, it can send or receive packets related to another, even if the first connection is still open.
The book is wrong to assume that the 10 requests are perfectly parallelizable; usually that isn't the case. Also, the parallelism it's talking about has nothing to do with asynchronous I/O as such. You'd get the same speedup by starting 10 threads and issuing a blocking I/O call in each one. That might be a bit slower because of thread-creation overhead, but might also be faster because it uses more CPU cores if you have them. For the highest performance you have to create one thread per CPU core and use asynchronous I/O in all of them. NT has built-in support for that model through I/O completion ports.


Connection between non determinism and LL(1) conflicts

No algorithm can remove non-determinism (or ambiguity) from every grammar, not even for every grammar for a language which has a deterministic grammar.
Some deterministic grammars -- and even some deterministic context-free languages -- have no $LL$ parser. Such grammars are not necessarily ambiguous. An accurate deterministic parser obviously cannot be generated for an ambiguous grammar, but failure to generate a parser doesn't say anything about ambiguity.
Yacc-style precedence/associativity declarations do not, in general, solve grammar ambiguity. But they do work for a couple of common simple cases (operator precedence, dangling else) allowing for the use of simpler grammars. That's handy in practice, but it's a very limited technique.


Show that Halting problem $(\mathsf{HP\text{}})$ is $\mathsf{NP\text{-}Hard}$

Given a SAT formula $\varphi$, construct a Turing machine which iterates over all truth assignments for $\varphi$, and so determines if $\varphi$ is satisfiable or not. If it is, it halts. If it isn't, it doesn't halt (gets into an infinite loop).

As is apparent, in the same way we can show that the halting problem is coNP-hard (by reversing the decision rule at the end). Indeed, in the very same way we can show that the halting problem is hard for many other classes – in fact, for all classes defined by time or space constraints (deterministic, non-deterministic or randomized).

NP is the "length- and time-bounded" version of the halting problem, or rather, of $\Sigma_1$. The class $\Sigma_1$ consists of all predicates $P$ such that
$$ P(x) \leftrightarrow \exists y  \, \Pi(x,y), $$
where $\Pi$ is a computable predicate. NP is defined in a very similar way, by adding two restrictions:

$y$ has to be polynomially bounded (in $x$).
$\Pi$ has to be computable in polynomial time.

If you like this sort of thing, there is an entire field dedicated to this point of view, called Bounded Arithmetic.


Universal hashing - insert / search / delete

Let me try to explain this with an example. Let us say if m=10 and n=1000.
If I have m number of insertions in a table with m slots, it is going to be O(m). Right?
But if we have 1000 insertions in a table containing 10 slots, it is not the same math anymore. Since you will have to deal with collisions at a greater frequency. It no more remains linear math. Thus if the n stays small enough that it is in order of O(m), you can have expected Theta n for n inserts. If inserts increase at a number much greater than m, the collisions doesn't let it be linear.


I do closure under boolean operations with the MyHill-Nerode characterisation. Never saw it done that way. A right congruence $\sim$ saturates a language $L$ if
$$
 u \sim v \Rightarrow ( u \in L \leftrightarrow v \in L )
$$
or equivalently iff $L$ is an union of congruence classes. We use:

Theorem: (MyHill-Nerode) A language is regular if and only if there is a right-congruence of finite index that saturates $L$.

Now suppose we have regular languages $L_1, L_2 \subseteq X^{\ast}$, and denote $\sim_{L_1}, \sim_{L_2}$ some right congruences of finite index saturating them. Then
$$
 u \sim v :\Leftrightarrow u \sim_{L_1} v \land u \sim_{L_2} v
$$
is a right congruence (the intersection of both), and it refines both. Furthermore we have
$$
 [u]_{\sim} = [u]_{\sim_{L_1}} \cap [u]_{\sim_{L_2}}.
$$
Hence we have a finite number of equivalence classes. Also this gives that the intersection of equivalence classes $[u]_{\sim_{L_1}}$ and $[v]_{\sim_{L_2}}$ is either empty, or it has a common element $w$ and hence equals the equivalence class $[w]_{\sim}$. This gives that $L_1 \cap L_2$ is either empty or could be written as the union of equivalence class for $\sim$. By the above theorem $L_1 \cap L_2$ is regular.

For $L_1 \cup L_2$ it is an union of equivalence classes for $\sim_1$ and $\sim_2$, which are themselve unions of equivalence classes for $\sim$, hence it is also regular. And for complementation, this follows as the equivalence classes partition $X^{\ast}$, hence a right congruence working for $L_1$ works also for $X^{\ast} \setminus L_1$. $\square$

Additional comments: In your question you also mentioned the canonical Nerode right congruence
$$
 u \equiv_L v :\Leftrightarrow (\forall w \in X^{\ast} : uw \in L \leftrightarrow vw \in L)
$$
with $L \subseteq X^{\ast}$. This is the coarsest right-congruence saturating $L$. Now maybe it might be natural to ask if we can construct the Nerode right congruence of $L_1 \cap L_2$ or $L_1 \cup L_2$ easily out of the ones for $L_1, L_2$, or if the resulting intersection congruence arises as some Nerode right congruence. Maybe we can find such simple formulas like
$$
 u \equiv_{L_1\cap L_2} v \Leftrightarrow u \equiv_{L_1} v \land u \equiv_{L_2} v.
$$
But the above does not hold. And to my knowledge there does not exists any simple relation. For example consider $L_1 = (aa)^{\ast}$ and $L_2 = a(aa)^+$, then we have
$$
 L_1 \cap L_2 = \emptyset, \qquad
 L_1 \cup L_2 = X^{\ast} \setminus \{a\}.
$$
Now $\equiv_{L_1} \cap \equiv_{L_2}$ has at least four congruence classes, as it refines $\equiv_{L_2}$ which has exactly four congruence classes. But $\emptyset$ has precisely one class, and $X^{\ast} \setminus \{a\}$ has three (could all be easily seen by using minimal complete automata).

EDIT (2019.08.18).
The mirror and suffix operation are related to the left congruence
$$
 u \equiv^L v \Leftrightarrow \forall w \in X^* : wu \in L \leftrightarrow wv \in L.
$$
If $\equiv^L$ has finite index, similar as for the prefix-operation and the right-congruence, $\equiv^{\operatorname{suffix}(L)}$ has finite index. And
$u \equiv_L v$ iff $\operatorname{mirror}(u) \equiv^{\operatorname{mirror}(L)} \operatorname{mirror}(v)$; and as the mirror operation is a bijection on $X^*$ the last equation gives that $\equiv^{\operatorname{mirror}(L)}$ has finite index iff $\equiv_L$ has finite index (note that the left congruence has the same index as the right congruence for the mirrored words, but in general a right congruence for $\operatorname{mirror}(L)$ might have exponential many more classes as is shown by standard contructions from automata theory).

So these operations are handled if we can show that both congruences have finite index at the same time or not. For this lets look at the syntactic congruence
$$
 u \equiv_{S(L)} v \Leftrightarrow \forall x,y \in X^* : xuy \in L \Leftrightarrow xvy \in L.
$$
This congruence refines both congruences above, hence if it is finite, both congruence above are also finite. It is $u \equiv_{S(L)} v$ iff for all $w \in X^*$ we have $[wu]_{\equiv_L} = [wv]_{\equiv_L}$, hence we have a well-defined and injective map from the $\equiv_{S(L)}$-equivalence classes to the transformations on $\{ [w]_{\equiv_L} : w \in X^* \}$, and if the latter is a finite set, the set of those transformations is finite too, which implies that  $\equiv_{S(L)}$ is of finite index. So in total we have that $\equiv^L$ has finite index if $\equiv_L$ has finite index, the reverse is implied similar.


MIPS CPU (Single Cycle MIPS Processor)-R Type instruction ALUOp code confusion

First, there is a source of confusion between the table you're showing and the diagram.  The table and diagram both use the term "ALUOp" but for the diagram this is the term for the output of the "Control" going into the "ALU control", whereas for the table this is the term for the output of the "ALU control" going into the ALU!

  Can't ALUcontrol tell ALU what operations to do by just receiving 5-0th bits? If so, all the ALUOp signal can be all same for the R type.

Not directly, it doesn't appear so.  I don't see a simple bit pattern in the bit 5-0 that would result in the proper "ALUOp" shown in the table, so a lookup is necessary, which is what "ALU control" is doing when the ALUOp coming from Control is for 000000 (R-type).

  I don't know why ALUcontrol needs to receive data from both instruction and Control when ALUOp for R type looks useless.

This is because "ALU control" is also used by I-type instructions — lw & sw, addi/u, which use the add function of the ALU in computing an effective address, as well as slti, andi, ori, xori, which also require the ALU.  Note that the ALUOp for lw & sw is 010, the same as add (as they use the ALU to compute the effective address).  Further note that the ALUOp for sub and beq are also 110, which makes sense because a beq is comparing the two (albeit for equality, so xor might also have been used).

We don't see the other I-type instructions in the table, but you can imagine the slti/u also use ALUOp 110 for subtraction and addi/u also use 010 for addition, and that, andi, ori, xori, use the same codes as and, or, xor.

The J-type instructions have their own dedicated adders so, no need for ALUOp.


How do two H gates act on two entangled qubits?

The Hadamard gate performs the following operation on a single qubit:
\begin{align}
|0\rangle &\to \frac{|0\rangle + |1\rangle}{\sqrt{2}} \\
|1\rangle &\to \frac{|0\rangle - |1\rangle}{\sqrt{2}}
\end{align}
This gives the action on pure states. The action extends linearly to mixed states:
$$
\alpha|0\rangle + \beta|1\rangle \to \alpha\frac{|0\rangle + |1\rangle}{\sqrt{2}} + \beta\frac{|0\rangle - |1\rangle}{\sqrt{2}}
$$
What happens when there are seveal qubits around? In this case, it is common to denote $|a\rangle \otimes |b\rangle$ by $|ab\rangle$, for brevity. If we apply a Hadamard gate on the first qubit, then it only affects the first qubit:
\begin{align}
|0b\rangle &\to \frac{|0b\rangle + |1b\rangle}{\sqrt{2}} \\
|1b\rangle &\to \frac{|0b\rangle - |1b\rangle}{\sqrt{2}}
\end{align}
Similarly, if we apply a Hadamard gate on the second qubit, then it only affects the second qubit:
\begin{align}
|a0\rangle &\to \frac{|a0\rangle + |a1\rangle}{\sqrt{2}} \\
|a1\rangle &\to \frac{|a0\rangle - |a1\rangle}{\sqrt{2}}
\end{align}
The two operations commute.
What happens to a general mixed state? Denoting by $\stackrel{(i)}\to$ the application of $H$ on the $i$'th bit, we get
\begin{align}
&\alpha|00\rangle + \beta|01\rangle + \gamma|10\rangle + \delta|11\rangle \\
\stackrel{(1)}\to
&\alpha\frac{|00\rangle + |10\rangle}{\sqrt{2}} + \gamma\frac{|00\rangle - |10\rangle}{\sqrt{2}} +
\beta\frac{|01\rangle + |11\rangle}{\sqrt{2}} + \delta\frac{|01\rangle - |11\rangle}{\sqrt{2}} \\ =
&\frac{\alpha+\gamma}{\sqrt{2}} |00\rangle + \frac{\beta+\delta}{\sqrt{2}} |01\rangle +
\frac{\alpha-\gamma}{\sqrt{2}} |10\rangle + \frac{\beta-\delta}{\sqrt{2}} |11\rangle \\
\stackrel{(2)} \to
&\frac{\alpha+\gamma}{\sqrt{2}} \frac{|00\rangle + |01\rangle}{\sqrt{2}} +
\frac{\beta+\delta}{\sqrt{2}} \frac{|00\rangle - |01\rangle}{\sqrt{2}} +
\frac{\alpha-\gamma}{\sqrt{2}} \frac{|10\rangle + |11\rangle}{\sqrt{2}} +
\frac{\beta-\delta}{\sqrt{2}} \frac{|10\rangle - |11\rangle}{\sqrt{2}} \\ =
&\frac{\alpha+\beta+\gamma+\delta}{2} |00\rangle +
\frac{\alpha-\beta+\gamma-\delta}{2} |01\rangle +
\frac{\alpha+\beta-\gamma-\delta}{2} |10\rangle +
\frac{\alpha-\beta-\gamma+\delta}{2} |11\rangle
\end{align}
The Hadamard gate is Hermitian, and so applying it twice in a row results in the starting point: $HH = I$. Therefore if the oracle does nothing, you do get what you started from. But usually the oracle does change the qubits somehow.


Turing machines and languages -- recursive (enumerable) or not

Hints.

If you're trying to figure out some property of a Turing machine and the only thing you can think of is, "Check every input" then it's probably not recursive.
If a language is RE and so is its complement, both are actually recursive (this is a good way of proving that languages aren't RE: for example, the language of pairs $\langle M,x\rangle$ such that Turing machine $M$ does not halt on input $x$ is not RE for this reason).
If a Turing machine halts within 100 steps, how much of its input has it seen?

Note that L2 and L3 are subtly different so you can't use the same explanation for both (the answers are actually different).


A universal operator necessarily generates $\neg x$ for input $x,…,x$

There are two ways to define a universal operator: when constants are allowed, and when they are not allowed. If constants are allowed, then one can define a universal operator which doesn't satisfy the claim, as follows:
$$
T(x,y,z) = \overline{x \land y} \land z.
$$
This is universal since $T(x,y,1)$ is the NAND operator, but $T(0,0,0) = 0$.

Now suppose that constants are not allowed. Since $T$ is universal, there is a $T$-circuit which computes the NOT function $x \mapsto \lnot x$. Let us now consider the possible values that $T(x,\ldots,x)$ takes:

$T(x,\ldots,x) = \lnot x$: in this case the claim holds.
$T(x,\ldots,x) = x$: in this case, induction shows that every $T$-circuit in which the only inputs are copies of $x$ necessarily computes the value of $x$; in particular, no $T$-circuit computes NOT.
$T(x,\ldots,x) = 0$: in this case, when $x = 0$, induction shows that every $T$-circuit always computes 0; in particular, it doesn't compute NOT.
$T(x,\ldots,x) = 1$: similar to the preceding case.

This shows that $T(x,\ldots,x)$ must compute $\lnot x$.


Is it possible to have a zero knowledge proof with a P Prover?

If the prover has the same power as the verifier, then the verifier can simulate the entire interaction himself, which makes the interactive proof unnecessary. For example, if we have an interactive proof with a probabilistic polynomial verifier and a polynomial prover for some language $L$, then $L\in BPP$. When dealing with interactive proof systems with a polynomial verifier it suffices to consider PSPACE provers, since a PSPACE prover can find and send the messages that maximize the verifier's acceptance probability.
Note that the above refers to interactive proof systems in general, there's nothing specific to zero knowledge (zero knowledge simply adds the condition that for yes instances, the entire communication of the protocol can be generated by a simulator who only has access to the input).


How would the use of an external lookup table affect file compression?

There are compression programs such as zstd which explicitly allow a separate dictionary text, and stream-based compressors such as LZW can be easily converted to use a dictionary by prepending it on the input. The dictionary appears as a fixed prefix on the output and can be removed, ie $C(xy)=C(x)C(y|x)$.

The benefit of using one text as a dictionary for another is a function of their mutual information, which is based on Kolmogorov Complexity (an incomputable minimum).   However a compression algorithm turns out to be a good way to approximate it, using a technique known as Normalized Compression Distance.  The texts are compressed separately and together as above, and the difference between $C(y|x)$ and $C(y)$ measures similarity.  So, while it's difficult to predict the benefit, measuring it empirically has some uses.


Can this equation be solved in polynomial time?

Summary

Your problem remains NP-hard, despite the fact that the algorithm can choose the function $f$.  Consequently, no, you should not expect a polynomial-time algorithm.

The problem is at least as hard as the subset-sum problem.  Fortunately, subset-sum is one of the easier NP-hard problems, so if your problem instance is small enough, you might be able to use algorithms for subset sum to solve your problem.

Problem statement

I'm going to reformulate your problem statement, so we are all on the same page:

Input: integers $m,n, a_1,\dots,a_m$; and access to an oracle, as follows:
Oracle: has secret values $x_1,\dots,x_m \in \{1,\dots,n\}$; when provided a function $f:\{1,2,\dots,n\}\to \mathbb{N}$, the oracle outputs the value $a_1 f(x_1) + \dots + a_m f(x_m)$
Goal: find $x_1,\dots,x_m$

An algorithm

You could use algorithms for subset-sum to help solve your problem, using the following strategy.

Let $\delta_1$ denote the function so that $\delta_1(1)=1$ and $\delta_1(j)=0$ for all $j \ne 1$.  Send $\delta_1$ to the oracle, and call the result $k_1$, i.e., $k_1 = a_1 \delta_1(x_1) + \dots + a_m \delta_1(x_m)$.  Notice that $k_1$ is a sum of the a subset of the $a_i$'s, namely, those where $x_i=1$.  In other words, $k_1=\sum_{i \in S_1} a_i$ where $S_1=\{j : x_j=1\}$.  So, feed $a_1,\dots,a_m$ and $k_1$ into an algorithm for the subset sum algorithm, and ask it to find a subset of the $a_i$'s that sums to $k_1$.  If this subset sum problem has a unique solution, then the result will tell you which $x_i$'s have the value 1.

Next, let $\delta_2$ denote the function so that $\delta_2(2)=1$ and $\delta_2(j)=0$ for all $j \ne 2$.  Send $\delta_2$ to the oracle, and call the result $k_2$.  Do the same thing, using a subset-sum solver to find a subset of $a_i$'s that sum to $k_2$; if this solution is unique, that will be the set of $x_i$'s that have the value 2.

Repeat, for $\delta_1,\dots,\delta_n$, until you have learned all the value of all of the $x_i$'s.

If you're lucky, the subset-sum problem has a unique solution at each stage, and after solving $n$ subset-sum problems you can read off the values of the $x_i$'s.  If you're unlucky, it has multiple solutions, and now you might need to consider all combinations of solutions to find a combination where the subsets are disjoint.

(Incidentally, once you've queried the oracle on $\delta_1,\dots,\delta_n$, you can predict the response of the oracle on any other function, so there's not much point in querying it again.  This shows that $n$ queries to the oracle suffice; we'll never need more than that.)

The problem is NP-hard

Here is a reduction to show that the problem is as hard as subset sum.  In particular, we'll show that the special case of your problem where $n=2$ is as hard as subset sum.  Suppose we have a subset sum instance, namely numbers $a_1,\dots,a_m$ and a target $t$.  We'll show how to use any algorithm for your problem to solve this subset sum instance.

We will implement a sneaky oracle, which behaves as follows: when provided a function $f:\{1,2\} \to \mathbb{N}$, it returns the value

$$f(1) \cdot (a_1 + \dots + a_m) + (f(2)-f(1)) \cdot t.$$

Notice that the sneaky oracle doesn't have a particular set of values $x_1,\dots,x_m$ in mind.  Nonetheless, if there is a subset of the $a_i$'s that sums to $t$, the responses from the sneaky oracle would be equivalent to what we would obtain if we had an ordinary oracle where the $x_i$'s were 2 for all $i$ in that subset and 1 otherwise; and if there is no subset of the $a_i$'s that sums to $t$, the responses from the sneaky oracle are not equivalent to  any ordinary oracle (for any value of the $x_i$'s).

Now, ask the purported algorithm for your problem to work with this sneaky oracle and find values for the $x_i$'s.  If the algorithm for your problem finds a solution for the $x_i$'s, that yields a solution for the subset sum problem (simply include the $a_i$'s where $x_i=2$ in the subset).  If the algorithm for your problem doesn't find a solution for the $x_i$'s, there is no subset of the $a_i$'s that sums to $t$.

(Strictly speaking, this shows the case where $n=2$ is hard.  However, one can show that increasing $n$ does not make the problem any harder.  Thus, the case where $n=\sqrt{m}$ is also hard.)


Algorithm to solve constraint satisfaction problems

Use an algorithm to find a perfect matching in a graph.  Build a graph where each vertex represents a person, and draw an edge between each two people who don't share any characteristic, then look for a perfect matching.  If none exists, you can throw away that data and generate a new random sample, and repeat until you find a valid solution.


Runtime of a recursive algorithm to find a path in a DAG

If you take each recursive call and trace it back to the original call reach(s,t) then you get some directed path starting at $s$. Hence the running time of the algorithm is $\Theta(N)$, where $N$ is the number of directed path starting at $s$ in which $t$ is not an internal vertex.

The number of paths of length $k$ (containing $k$ edges) is at most $(n-1)(n-2)\cdots(n-k)$, since each such path consists of distinct vertices different from $s$ (here we use the DAG property). Since paths have length between $0$ and $n-1$, we get that
$$
N \leq \sum_{k=0}^{n-1} (n-1)\cdots(n-k) = (n-1)! \sum_{k=0}^{n-1} \frac{1}{k!} \leq e(n-1)!.
$$
In particular, $N = O(n!)$.


Given a specific computer system, is it possible to estimate the actual precise run time of a piece of Assembly code

I can only quote from the manual of a rather primitive CPU, a 68020 processor from around 1986: "Calculating the exact runtime of a sequence of instructions is difficult, even if you have precise knowledge of the processor implementation". Which we don't have. And compared to a modern processor, that CPU was primitive.

I can't predict the runtime of that code, and neither can you. But you can't even define what "runtime" of a piece of code is, when a processor has massive caches, and massive out-of-order capabilities. A typical modern processor can have 200 instructions "in flight", that is in various stages of execution. So the time from trying to read the first instruction byte, to retiring the last instruction, can be quite long. But the actual delay to all other work that the processor needs doing may be (and typically is) a lot less.

Of course doing two calls to the operating system makes this completely unpredictable. You don't know what "writing to stdout" actually does, so you can't predict the time.

And you can't know the clock speed of the computer at the precise moment you run the code. It may be in some power saving mode, the computer may have reduced clock speed because it got hot, so even the same number of clock cycles can take different amounts of time.

All in all: Totally unpredictable.


How to prove that a language is not recursively enumerable

Here are two methods.
Consider the complement
Theorem. If a language $L$ and its complement are both RE, they are both recursive.
Proof. Decide whether $w\in L$ by enumerating $L$ and its complement in parallel and accept/reject as soon as $w$ appears in one of the enumerations. $\Box$
So, if you can prove that $L$ is not recursive but its complement is RE, then $L$ is not RE.
Halting problems
Theorem. Let $\mathcal{M}$ be the class of Turing machines equipped with an oracle for the ordinary Turing machine halting problem. The halting problem for $\mathcal{M}$ is not RE.
Proof. Essentially the same as the proof that the ordinary Turing machine halting problem is not recursive. $\Box$
So, if you can reduce the halting problem for $\mathcal{M}$ to your problem, your problem is not RE.


match an array with a given set of arrays

You could calculate something like crc32 of the arrays and compare them with the crc32 of the new array. If the crc32's of the arrays match then you can do further check if the elements actually match (in case there is crc32 collision, which is very rare). If you know the new array exists in the set, you could select crc32 seed value which avoids the crc32 collisions, so once you find the crc32 match you can be sure it's the correct one without comparing the elements at all (just test max 24 ints). You could try something more lightweight than crc32 too if that's a performance issue.

If you would really want to push this, you could then sort the arrays by the checksum value and find the matching checksum with binary search, thus cutting the number of comparisons to log2(24)=5. Maybe not worth it for such a small amount of arrays though.


Doubts on the behavior of Unit Type in a type system

The short answer is that isomorphic types are not equal, despite behaving identically, and so the type system can distinguish between them. In a nominal type system, like the one you describe, types are essentially identified by their names, even if they are structurally equivalent. This is the case for the five unit types you describe: they are structurally equivalent, but nominally unequal, and so they are treated as distinct.

Note that the pattern matching aspect is orthogonal: you can think of the five unit types as existing in isolation. In most type theories, you can take the sum of any two types, even two that are (nominally) equal, e.g. Unit + Unit. You will still be required to pattern match, and will have two cases: the left Unit and the right Unit. The nominal aspect is unimportant, although many programming languages will use the names to distinguish between the different cases like this, instead of the indices of the summands (in particular, in languages where you are only allowed to take sums of distinct nominal types, like Standard ML).


Testing whether a determinant polynomial is identically zero

Is this a practical problem or a theoretical problem?

If it a practical problem, it looks to me like standard randomized algorithms for black-box polynomial identity testing should suffice to solve this.

Your polynomial is a multivariate polynomial of degree $n$ over the field $\mathbb{R}$.  Pick a set $S$ of real numbers with cardinality $2n$, draw $k$ numbers uniformly at random from $S$, and evaluate the polynomial at those points (substituting the first for $\alpha_1$, the second for $\alpha_2$, and so on).  Check whether the result is non-zero.  By Schwartz-Zippel, either your polynomial is identically zero or else the result will be non-zero with probability $\ge 1/2$.  Thus, we can repeat this test $m$ times.  If we get zero every time, output "the polynomial is identically zero".  Otherwise output "the polynomial is not identically zero".  You'll be wrong with probability at most $1/2^m$.

If you want to have a small seed, use a cryptographically secure pseudorandom number generator to generator the random numbers needed for this procedure.  Under a suitable cryptographic assumption, this will allow you to use only 128 bits of true randomness (or so).

This should be good enough for all practical applications.  Of course, it doesn't answer the theoretical question of whether this problem has a deterministic polytime algorithm.


Definition of a reachable ancestor (Skiena TADM 2nd ed section 5.9.2)

A small modification makes the definition agree with Skiena's algorithm.
"Let reachable_ancestor[v] denote the earliest reachable ancestor of vertex v, meaning the oldest ancestor of v that we can reach from a descendant of v by using at most one back edge."

If we view undirected edges as "two-way" directed edges, then to reach A from C would require two back edges: DB and BA.  Thus the earliest ancestor that can be reached from C by using at most one back edge is B.


Doubt regarding the implications of a 2-SAT constraint

$A\rightarrow B$ doesn't necessarily mean that $B\rightarrow A$. In your example, "$x_1$ is false then $x_2$ must be true" doesn't imply that if $x_2$ is true, $x_1$ must be false. Therefore, setting both $x_1$ and $x_2$ to true would not contradict the statement.
Also, as a side note, $\lnot x_1\rightarrow x_2$ is logically equivalent to $\lnot x_2 \rightarrow x_1$, so the two implications you described are identical.


Control of the combinatorial aspects of a dynamic programming solution

There is absolutely no problem adapting dynamic programming to count solutions without regard to order (i.e., when order doesn't matter). Let $D(S,m,n)$ be the number of ways to obtain a change of $n$ using the first $m$ coins of $S = S_1,\ldots,S_M$. We have $D(S,m,0) = 1$, $D(S,m,n) = 0$ when $n < 0$, and otherwise
$$
D(S,m,n) = \sum_{i=1}^m D(S,i,n-S_i).
$$
This recurrences forces the indices of coins used to be non-increasing: after using $S_i$, we are only allowed to use $S_1,\ldots,S_i$. Counting non-increasing (or non-decreasing) solutions is the same as counting all solutions without regard to order.


Is there a term for the general method used in XORed linked list?

It is a typical example of a space-time tradeoff trading increased time (CPU instructions required) for decreased space (memory required). There are many examples of this.

In this particular case I'd say it is a (simple) form of lossless compression. This because the data is stored in a minified but unusable form and needs some computation (decompression) done to receive the original (and usable) form, but no information is lost.


Is z-buffering the same as rasterization?

Z-buffering is easy to implement depth-buffering, where you check whether pixel is visible or not (in case of transparency, it is handled separately). This is optimisation to avoid calculating color at every pixel but instead check which are nearest to the screen, paying with memory.
Rasterization is general technique converting vector graphics into rasters, including filling triangle with pixels. Different technique is to use raytracing or photon mapping, in that case triangles are not rasterized (as in scanline rasterization) but rays (photons) are cast and traced.

So, yes, z-buffering is part of realisation of rasterization.


How to efficiently compute the most isolated point?

Use any algorithm for all nearest neighbors; then you can trivially solve your problem.  Such an algorithm finds, for each data point, its nearest neighbor.  The most isolated point is the one whose nearest neighbor is farthest away, so once you've solved all nearest neighbors, you can find the most isolated point by a simple linear scan.

Apparently all nearest neighbors can be found in $O(n \log n)$ time; see the references on Wikipedia.  Or, if you want something to implement, take any data structure for nearest neighbors, and for each point $p$, find its nearest neighbor.


A slightly different version of the halting problem

I won't give you the solution - I think you're on the right track. However I will give a possible way of making this question precise:

Prove that this problem is undecidable:

Input: A (code for a) Turing Machine $M$
Output: $\texttt{Accept}$ if the number of inputs for which $M$ halts is a finite number $\leq n$
$\texttt{Reject}$ otherwise.

Since there are an infinite number of inputs, if $M$ halts for a finite number of them, then it doesn't halt for an infinite number of them.

Of course, it's possible for a machine to halt on an infinite number of inputs, and not halt on an infinite number of inputs (say, halt on even numbers and not on odd numbers). In this case, a hypothetical machine for this problem would $\mathtt{Reject}$.

You might notice some similarity to the halting problem at this point.


That's not true even for DAGs: consider the following, with all edges directed left-to-right:

  o   o   o ... o
 / \ / \ /       \
x   o   o   ...   y
 \ / \ / \       /
  o   o   o ... o

There are $2^{|E|/4}$ paths from $x$ to $y$. In a graph with cycles, it can be even worse: consider a clique.


Edmonds-Karp Algorithm with both directed and undirected edges?

Replace each undirected edge $(u,v)$ by two directed edges, one in each direction: $u\to v$ and $v\to u$.  That gives you a graph with only directed edges.  Then the max-flow on that graph is the same as the max-flow on your original graph.


Is it an open problem if generalized resolution is always possible?

Resolution is refutation-complete. This means that if $S$ is a set of unsatisfiable clauses, then you can use resolution to derive the empty clause. Moreover, Resolution is sound, so you can only derive the empty clause if $S$ is unsatisfiable. Summarizing, given a set $S$ of clauses, you can use Resolution to derive the empty clause if and only if $S$ is unsatisfiable.

Unfortunately, sometimes generating the empty clause takes an exponential number of steps. Let $G$ be a random 4-regular graph on an odd number of vertices $n$, and let us associate with each of the $2n$ edges a variable. Consider the set of $\Theta(n)$ clauses stating that for every vertex, the XOR of the four variables corresponding to edges touching the vertex is 1. Since the number of vertices is odd, this set of clauses, known as a Tseitin contradiction, is unsatisfiable. Urquhart showed that with high probability, any Resolution refutation of this set of clauses has $2^{\Omega(n)}$ many lines (i.e., clauses); see Jakob Nordström's lecture notes.


No one knows, but:

It is suspected that neither factoring nor discrete logarithm are NP-complete, but we have no proof.  (Evidence for the suspicion: they are in NP $\cap$ coNP.  See, e.g., https://cstheory.stackexchange.com/q/159/5038, https://cstheory.stackexchange.com/q/167/5038 for factoring.  It's similarly easy to prove that discrete log is in NP $\cap$ coNP; see, e.g., How hard is finding the discrete logarithm?.  Moreover, if any problem in NP $\cap$ coNP is NP-complete, it follows that NP = coNP.  This would be an unexpected result.)
It is suspected that there is no polynomial-time algorithm for factoring or discrete logarithm, but we have no proof.  (Evidence for the suspicion: we haven't been able to find a polynomial-time algorithm for either, despite a lot of trying.)
There is no known (classical) reduction between discrete log and factoring.  However, I personally wouldn't be shocked if one were found, or if both were found to be instances of some broader problem, or something.  For instance, when we find an algorithm technique that works against one, historically often we've been able to adapt it to the other as well.  So, they seem to be connected or related in some deep way.


Comparison between Aho-Corasick algorithm and Rabin-Karp algorithm

Asymptotic running time analysis is not likely to be the best tool to pick between these two algorithms: asymptotic analysis ignores constant factors, and the constant factors will be critical here.  The two algorithms have basically the same asymptotic running time, so asymptotic analysis probably isn't very helpful to choose between them.

Instead, the right way pick between the two algorithms is through experimental analysis.  Identify a representative workload, and then benchmark the performance of both algorithms on your workload, on the kinds of machines you intend to use in practice.

Incidentally, it sounds like you might have a slight confusion about the asymptotic running time of Rabin-Karp.  On the one hand you say that Rabin-Karp has $O(nm)$ running time, but then in the next sentence you say Rabin-Karp has $O(n+m)$ running time.  Perhaps you are confused by the difference between expected (average-case) vs worst-case running time.

Since Rabin-Karp is randomized, expected (average-case) running time is the appropriate metric to use to predict real-world performance in practice.  In particular, here the average is taken over the random choice of hash function.  It's specifically not an average taken over the choice of strings.  Even for the worst possible string and pattern, the average running time will still be $O(n+m)$.  With a suitable hash function, the probability that the running time is longer than $c\cdot(n+m)$ is exponentially small in $c$.  To put it another way (and being slightly informal), there's only an exponentially small chance that Rabin-Karp takes longer than $O(n+m)$ time.  We already have to accept exponentially small chances of bad things happen -- for instance, there's a tiny but non-zero chance of a cosmic ray causing a bit-flip in your memory that causes the program to loop forever.  So, worrying about this exponentially small chance makes no sense.

From an engineering point of view, Rabin-Karp's running time is $O(n+m)$ [or it might as well be].  Ignore the $O(nm)$ stuff; that's not really relevant to practice.


The state $q_3$ is not necessary, because you couldn't have string with the pattern $bbb$ inside of them. So, just delete it. The next automaton accepts your language requirement.

Hope it helps


Approximation scheme for Multiple Choice Knapsack

The paper you cite is not available to me. However, according to this paper: "Improved Fully Polynomial time Approximation Scheme for the 0-1
Multiple-choice Knapsack Problem",

  0-1 MCKP is $\text{NP}$-hard [4] as it contains the 0-1 Knapsack problem as a special case [5, 13] but it can be solved in pseudo-polynomial time (emphasis added) through dynamic programming [7, 2].

Thus, 0-1 MCKP is not strongly $\text{NP}$-hard.

One of the citations is

[7] K. Dudzinski, S. Walukiewicz, “Exact Methods for the Knapsack Problem and its Generalizations”, European Journal of Operational Research, (28), (1987): 3–21.


Let us review the specification of the algorithm.

  In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors.

Right after the cost of link N2-N3 changes to 2, the distance vectors at different nodes are as follows. The only difference from before is the distance from N2 to N3 and the distance from N3 to N2 has been updated from 6 to 2.

N1: (0,1,7,8,4)
N2: (1,0,2,7,3)
N3: (7,2,0,2,6)
N4: (8,7,2,0,4)
N5: (4,3,6,4,0)

In the next round of exchange, all nodes exchange their distance vectors with their respective neighbors. In particular, N3 sends (7,2,0,2,6) to its neighbor N2 and N4. Right after this round of exchange, the knowledge of each node are as follows besides their knowledge of respective distances to their neighbors.

N1 knows (1,0,2,7,3) from N2.
N2 knows (0,1,7,8,4) from N1 and (7,2,0,2,6) from N3 and (4,3,6,4,0) from N5.
N3 knows (1,0,2,7,3) from N2 and (8,7,2,0,4) from N4.
N4 knows (7,2,0,2,6) from N3 and (4,3,6,4,0) from N5.
N5 knows (1,0,2,7,3) from N2 and (8,7,2,0,4) from N4.

Discarding current distance vectors, all nodes regenerate their distance vectors at the same time. So after, for example, a fraction of a second, the distance vectors at different nodes becomes the following.

N1: (0,1,3,8,4)
N2: (1,0,2,4,3)
N3: (3,2,0,2,5)
N4: (8,4,2,0,4)
N5: (4,3,5,4,0)

If no change of the network happens before the next round of exchange, then in the next round of exchange, each node will send above distance vectors to its neighbors. In particular, N3 will send (3,2,0,2,5) to its neighbor N2 and N4 in the next round.

However, if before the next round of exchange, it happens that the link between N1 and N2 goes down. Then N1 and N2 will update their distance vector immediately, but only with the distance between N1 and N2. Now the distance vectors at each node are as follows.

N1: (0,infinity,3,8,4)
N2: (infinity,0,2,4,3)
N3: (3,2,0,2,5)
N4: (8,4,2,0,4)
N5: (4,3,5,4,0)

After the next round of exchange, N3 knows the distance vector (infinity,0,2,4,3) from N2 and (8,4,2,0,4) from N4. So N3 will update its distance vector to (10,2,0,2,5).


How to sort an array $A[1..n]$ where all but $\lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$, at $\Theta(n)$ time?

In the rest of the answer I will slightly abuse the notation by treating $A$ as a set. For simplicity I will also assume that the integers to sort are distinct, so that we are dealing with sets instead of multisets. This assumption is easy to remove.
Construct a min-heap $H^-$ and a max-heap $H^+$, each containing all elements in $A$. Extract the minimum  $\lfloor \sqrt{n} \rfloor$ times from $H^-$ and let $S^-$ be the set of the extracted elements.
Similarly, extract the maximum $\lfloor \sqrt{n} \rfloor$ times from $H^+$, and let $S^+$ be the set of the extracted elements. The overall time required so far is $O(n) + O(\sqrt{n} \log n) = O(n)$. (Notice also that $S^- \cap S^+ = \emptyset$ since $2 \lfloor \sqrt{n} \rfloor \le n$ for $n > 1$).
Now you know that all the elements in $A \setminus (S^- \cup S^+)$ are integers between $0$ and $n^{3/2}$ (actually, between $\sqrt{n}$ and $n^{3/2}$, but this is irrelevant), and therefore can be sorted in time $O(n)$ using Radix sort (indeed, each integer in $S \setminus (S^- \cup S^+)$ has just two digits when written in base $n$).
Let $A'$ be the sorted version of $A \setminus (S^- \cup S^+)$.
To obtain a sorted version of $A$, we just need to insert the elements in $S^- \cup S^+$ into the right position of $A'$.
This can be done by first sorting $S^- \cup S^+$ in time $O(n)$ (any quadratic-time algorithm suffices since $|S^- \cup S^+| \le 2 \sqrt{n}$) and then merging the resulting sorted sequence with $A'$ a-la-Mergesort.


Finding the number of distinct strings in regular expression

In your example, think of the result as having filled four slots: _ _ _ _, each of which can take one or three substrings, namely 0, 1, or the empty string. Ignoring the empty strings, it's clear that there are sixteen possible results: 0000, 0001, 0010, ... , 1111.

With the empty strings, though, since we could make 10 by $(\epsilon)(\epsilon)(1)(0)$, or by $(\epsilon)(1)(\epsilon)(0)$, or four other arrangements. What now? Well, if we realize that the six possibilities we just had all correspond to the string 10, we've got it: we'll have all strings over $\{0,1\}$ of length zero, one, two, three, and four, namely

$\epsilon$ (1 of them)

$0, 1$ (2 of these)

$00, 01, 10, 11$ (4)

$000, 001, 010, \dots, 111$ (8)

$0000, 0001, 0010, \dots 1111$ (16)

For a total of $1+2+4+8+16=31 = 2^5-1$. This is a particularly nice example; in general it'll be far more complicated, like, say the the expression $(1  + 01)1(1(0+\epsilon) + (101(10+101)))$. Sad to say, there's no simple rule governing all cases.

By the way, welcome to the site!


Is there a point to an all-encompassing programming language?

You can make a language that does all these things. The problem is that it won't be able to do all these things well, because they're contradictory. For example, database manipulation is fundamentally about changing the state of the system, so it's directly opposed to purely functional programming¹. So is fault tolerance, where a program that's running code that's mathematically proven to terminate might actually fail to terminate because the machine crashes. Object orientation with the hiding of implementation-specific details is opposed to structural polymorphism where a function might inspect the state of its arguments and expects to know about all the ways in which an object can be built. Having static type guarantees is opposed to dynamic type analysis. A language can't provide safe memory accesses and precise memory management in all cases. And so on.

The best you can expect is a “kitchen sink” language that includes all the features that the designers thought of. The thing is, to effectively use some of the features, the programmer needs to restrict themselves to a subset of the language that copes with those features. Of the languages commonly used in industry, C++ is the most kitchen-sinky, and that makes it hard to use because you can never be sure what features a piece of code uses and what assumptions you can make on that piece of code. For example, the type of a Haskell function makes it apparent whether it has a side effect; the type of a Rust function makes its memory management behavior apparent; with C++, you have to look at the documentation and hope that it tells you what you need.

With a kitchen sink language, you really have multiple languages in one, without the benefit of a clear barrier between the languages. Multiple languages that are each good at their job works better.

¹  If you put the database state in a monad, like Haskell does, you're no longer doing purely functional programming. You're doing imperative programming with a type system that models the impurity.


Find the longest subsequence of two strings

You know the recipe for dynamic programming: define some subproblems, then show how to use solutions to smaller subproblems to help you solve larger subproblems.  So, what you have tried as candidate subproblems?

Hint: When you have a dynamic programming problem that takes a string as input, what are some candidate ways to define subproblems?  (Prefixes, suffices, substrings...)  Now, how might you apply that general advice here?

I'm not going to spell out the full answer, as this sounds like homework, and to learn from homework, you need to struggle with it yourself.


Turing machine that increments a binary number by 1

Hint: First write an informal description of the machine, then give a precise description as a transition diagram. Use the state of the Turing machine to hold the carry bit.


How does hashed inverted page table work?

From your picture, one definitely see a hash table collision solution. If one carefully examine it, will see that the table uses itself to solve the collision, that is Open Addressing.

In open addressing, the collision can be resolved by many methods;

Linear Probing
Quadratic Probing
Double hashing.

It might be Double Hashing or Quadratic Probing but the information is not enough to resolve.


(AVL Trees) What is the maximum possible difference between the number of nodes in the root node's subtrees?

I assume that we start labeling heights from $0$.

Actually your approach is right. You must consider the left-side (or right-side) sub-tree with the least possible amount of nodes and the right-side (or left-side) sub-tree with the most possible amount of nodes, and both sub-trees must be AVL trees too. For this purpose, we fix the height of left-side sub-tree to $h-2$ (doing so, the bottommost node of this sub-tree would be at height $h-1$ of the main tree) and we fix the height of right-side sub-tree to $h-1$. Now, we should answer following questions:

What is the minimum number of nodes in an AVL tree of height $h-2$?
What is the maximum number of nodes in an AVL tree of height $h-1$?

Answer to question 1: By recursions and assuming that $n(h)$ is the minimum number of nodes of an AVL tree of height $h$ we can easily get:
$$
\begin{array}{rl}
n(h) &=& n(h-1)+n(h-2)+1\\
n(1)&=&2\\
n(0)&=&1
\end{array}
$$

Answer to question 2: In this case, we're dealing with a perfect tree (which is an AVL tree too) and we must find the number of nodes in a perfect tree of height $h-1$.

So, the answer to your question would be:
$$
2^h - 1 - n(h-2)
$$

As an example, if $h=2$, this formula returns $2$, which is not the value you have got, and I think that's because you start labeling heights from $1$.


It doesn't really matter which way you decide to break the tightness. You could put all the elements less than or equal to the pivot in the first list and the ones larger than the pivot in the second list, or you could put only the elements smaller than the pivot in the fist list and the ones larger than or equal to the pivot in the second list.

You could even arbitrarily pick the list that will contain an element equal to the pivot (except the pivot itself), on an element-to-element basis. No matter how you will assign these elements to the lists, the algorithm will still work.

Another solution that slightly breaks the algorithm's description you gave is to put all elements smaller than the pivot in the first list $L_1$, all those larger than the pivot in the second list $L_2$, and insert as many copies of the pivot $x$ as there are elements equal to $x$ (including the pivot itself) between the sorted versions of $L_1$ and $L_2$.

As a final note: the pseudocode reported in your textbook seems wrong. You are supposed to recursively repeat the whole procedure on $L_1$ and $L_2$, not just steps $1$ to $4$ (otherwise you will never reach a recursion depth larger than $1$).


Can a greedy algorithm have more than one subproblems to solve after making greedy choice?

I think what you are talking about is Divide and Conquer (and Combine) techniques:

Divide the problem into a number of subproblems that are smaller instances of the same problem.
Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the solution for the original problem.
CLRS 3rd Ed Ch 4, pp. 65

If not D&C, then at least a variant. It seems you are making an greedy choice, then this divides the problem into multiple, and you solve these subproblems the same way. Consider the following problem which I think can be solved as you mentioned:

Given a directed binary tree $T$ (meaning edges are directed from parent to child) with positive integer values on the nodes, determine the directed path with maximal sum of node values.

Here is how we can solve this:

We make a "greedy" choice to include the root node. Since the values are positive, we know that the root node can only increase the sum of node values.
We now can either go left or right (not both since it is directed towards leaves).
Solve the left case, what is it's maximal path? Let's say it's of weight $L$.
Solve the right case, what is it's maximal path? Let's say it's of of weight $R$.
Now we combine these results, if $L > R$ then we prepend the root node to the path returned from the left case, else we prepend the root node to the path returned from the right case.
If we get down to a leaf node, simply return it because it will be it's own maximal path since values are positive.

So this is a kind of "greedy" algorithm in the sense that we make a greedy choice (include the root node always). However, it is much more of a divide and conquer algorithm based on the definition of D&C. This is why greedy must only be left with one subproblem. If we have multiple subproblems then we are either in the case of Divide and Conquer or Dynamic Programming most likely.


How many different trees can we form from given graph?

There is a simple algebraic algorithm based on the Matrix Tree Theorem.  Just make the Laplacian matrix of the graph and compute $N^{-1}$ times the product of its non-zero eigenvalues.


Write a regex to match string that does NOT contain a certain pattern

If a string does not contain $101$, then every $10$ either terminates the string or is followed by $0$. So if $r$ is a regular expression for all strings not containing $10$, then a regular expression for all strings not containing $101$ is
$$
(r100)^*r(10+\epsilon).
$$
You take it from here. Note that there are also other solutions.

Complementing a regular expression can be a very costly operation. For example, the set of strings over $\{1,\ldots,n\}$ not containing all symbols has a regular expression of length $O(n^2)$ (exercise), but its complement requires a regular expression of exponential size $\Omega(2^n)$. This follows from the "fooling set" lower bound on NFAs, and the fact that regular expressions can be converted into NFAs with constant multiplicative overhead.

A fooling set for a language $L$ is a collection of pairs $(x_i,y_i)$ such that $x_iy_i \in L$ but for $i \neq j$, either $x_iy_j$ or $x_jy_i$ is not in $L$. If $L$ has a fooling set of size $n$ then every NFA for $L$ has size $n$ (exercise). In the case of all strings over $\{1,\ldots,n\}$ containing all symbols, there is a fooling set of size $2^n$: $\{(S,\overline{S}) : S \subseteq \{1,\ldots,n\}\}$, where we identify a set of symbols with the word containing these symbols in order.


If graph isomorphism is in P, is then P = NP?

We don't know.

We do know that $\textbf{P} = \textbf{NP}$ implies graph isomorphism is in $\textbf{P}$, but the other implication has not been proven (to the best of my knowledge). It is suspected graph isomorphism is $\textbf{NP}$-intermediate (i.e., it is in $\textbf{NP} \setminus \textbf{P}$ and not $\textbf{NP}$-complete). This question as well as this other one list evidences supporting said suspicions.

Regarding your second question: If $\textbf{P} = \textbf{NP}$, then any (nontrivial) problem in $\textbf{NP}$ is trivially $\textbf{NP}$-complete because any (nontrivial) problem in $\textbf{P}$ is $\textbf{P}$-complete (and we have assumed $\textbf{P} = \textbf{NP}$). Hence, by contraposition, if the conclusion of this implication is false (i.e., there is a problem in $\textbf{NP}$ which is not $\textbf{NP}$-complete), then the premise (i.e., $\textbf{P} = \textbf{NP}$) must also be false.


Generating hard puzzles for a backtracking snake

Here's an idea for generating instances with a non-unique solution that will be difficult to solve by backtracking but actually are quite easy to solve:

Let $M$ be $h$ tall and $2w$ wide. Take the integers ${1, 2, ... w}$ and fill $M$ with them randomly. For $i = 1$ to $w$, replace column $w + i$ to be the column with only the value $i$.

We know that $M$ has no solution, because it requires $2w$ unique integers to bring the snake across the matrix.

Now, for the first $w$ columns of $M$, replace a random element of column $i$ with the number $w + i$.

Then, it follows that the sequence of integers corresponding to any solution is $w + 1, w + 2 .... 2w, 1, 2, ...... w$. This is very easy to find, unless you are searching by backtracking. In particular, the first $w$ columns have a unique correct choice.

Here's an example of a matrix made by this algorithm:

$$ \begin{array}{ccc}
1 & 5 & 2 & 1 & 2 & 3 \\
3 & 3 & 2 & 1 & 2 & 3 \\
4 & 1 & 1 & 1 & 2 & 3 \\
2 & 2 & 2 & 1 & 2 & 3 \\
2 & 3 & 6 & 1 & 2 & 3 \\
3 & 1 & 3 & 1 & 2 & 3 \\
1 & 1 & 1 & 1 & 2 & 3 \\ \end{array} $$

To make a given instance harder, just make the matrix arbitrarily taller.


Are fixed-point combinators general recursive?

Yes, fixed point combinators are sufficient for general recursion and Turing complete computations.

In my Awelon project languages, fixed point combinators are the only way to model recursion. In practice, working directly with fixed point is rather annoying. However, it isn't difficult to build more conventional loop primitives (while, until, repeat) and collections-oriented abstractions (fold, map, scan, foreach, etc.) above fixed points. I hope to build a big enough library of loop functions that I rarely need to directly use fixpoint.

And to answer David Richerby's follow-on question: Yes, there are some interesting things we can do if all we have is fixed point combinators.

It is possible to name any function by use of secure hash, which can be convenient for content-addressable linking models. With name-based recursion, you cannot use the secure hash of a function's name to refer to itself. Besides myself, it seems Paul Chiusano aims to take advantage of this [2].
The language is much more streamable, by which I mean that program execution can proceed by processing each element in a stream of instructions then forgetting it. This is a nice feature for mobile code or remote control applications. Conventional languages model loops by jumping backwards, which requires the computer hold onto the code (i.e. stored program computing).

Use of fixed point combinators is not a sufficient condition for these features. Other aspects of the language must also align. But fixed point combinators do not entangle program semantics with the namespace, which does simplify things.