Unfortunately this problem is NP-hard, so no computer scientist knows (or is admitting that they know! :-P) a way to solve it in time polynomial in the number of sticks.  Don't feel bad about using brute-force here -- it's essentially the best you can do.

First, let's reframe the rectangle problem as a decision problem, that is, a problem to which the answer is either YES or NO:

Rectangle: Given a multiset $Y = (y_1, \dots, y_m)$ of stick lengths and an area threshold $k$, is it possible to build a rectangle from the sticks in $Y$ having area at least $k$?

Squares are optimal solutions when they exist

Before getting into the reduction, we will need a property about what a maximal solution to the Rectangle problem looks like.  Under the constraint that $a+b=c$, $ab$ is maximised precisely when $a=b$, i.e., squares have uniquely maximum area among all rectangles of fixed perimeter.  You can verify this by substituting $b=c-a$ into $ab$ and then differentiating w.r.t. $a$: the derivative becomes zero at $a=c/2=b$, and this is clearly a maximum since the coefficient of the $a^2$ term is negative.  The practical significance of this fact is: If and only if it is possible to partition the stick lengths into 4 equal-size subsets, then the maximum-size area achievable is $s^2/16$, where $s$ is the sum of all stick lengths.

Reduction from Partition

I'll show this is NP-hard by reducing the NP-hard problem Partition to it.  In Partition, we are given a multiset of $n$ integers $X=(x_1, \dots, x_n)$, and our task is to partition this multiset into two parts having equal sum.

Given an instance $X=(x_1, \dots, x_n)$ of Partition, with total sum $t=\sum x_i$, we construct an instance $Y = (y_1, \dots, y_{n+2})$ of Rectangle by taking each $x_i$ as a stick length $y_i$, and adding two more "big" sticks, $y_{n+1}$ and $y_{n+2}$, both of length $t/2$.  (That is, $m=n+2$.)  Finally, we set $k$ to $t^2/4$.

If the answer to the constructed Rectangle problem instance is YES, then by the maximal-square property, it must be possible to partition $Y$ into four equal-sum parts, each having sum $t/2$.  Let $(A, B, C, D)$ be such a partition.  Two of these four multisets must each contain a "big" stick and nothing else, since the big sticks have to go somewhere, and combining one of them with any other sticks would mean that one side exceeds $t/2$, meaning that some other side must fall short of $t/2$, meaning that the rectangle is not square and thus of size strictly less than $t^2/4$ -- a contradiction.  Remove these two big sticks, leaving two remaining multisets of sticks, which must also be of equal sum (that is, also $t/2$): these two multisets represent a valid partition of the original $X$ into two equal-sum parts, showing that the answer to the original Partition instance is also YES in this case.

In the other direction, if the answer to the original Partition problem is YES, meaning that there is a way to partition $X$ into two equal-sum parts $U$ and $V$, then clearly the answer to the constructed Rectangle problem instance is also YES: We could simply use the four multisets $U$, $V$, $\{y_{n+1}\}$ and $\{y_{n+2}\}$.

Since a YES to either problem instance implies a YES to the other, it must also be that a NO to either instance implies a NO to the other: in other words, the answers to both problems are always the same.  And since the Rectangle problem instance can be constructed in polynomial time from the Partition instance, any algorithm that can solve Rectangle in polynomial time could also be used as a subroutine to solve Partition (any, by extension, every other NP-hard problem) in polynomial time.  Since Partition is an NP-hard problem, this implies that Rectangle is too.


What is the behavior of the given counter?

ANS: MOD8 COUNTER

It still is a mod 8 counter only. But the point where anyone can get confused is the clock speed and the nand gate delay. Basically as soon as we get 111 as the answer. the nand gate gets set to 0 and hence the reset is activated now one may argue that because of this the counter won't count further as it already has the reset pin on. However since the delay of nand gate is more than the time required for the counter to give next output thus before the nand gate could change the counter to 000. The counter would have already produced the next sequence that is 001. that would help it get out of the reset configuration. Steps can be written as follow:-

counter produces 111
nand gate receives 111 and starts processing it
counter produces 000
nand computes 0 and hence counter is set to reset i.e. 000.
nand receives 000, processes it and the counter gets out from reset state.
counter produces 001 as expected.

The only change one could observe with this configuration compared to the  normal 3 bit counter is the duration for which the counter would produce the state 000.
Rest all would remain the same.
Let me know if I could help you further.


What is the constant $C$ in the definition of asymptotic notations?

The basic idea of asymptotic notation is that "constant factors shouldn't matter". This has several different interpretations. Taking as our example big O, the simplest interpretation is:

  For all $C,D>0$ and functions $f,g$: $$ f = O(g) \Longleftrightarrow Cf = O(Dg). $$

This means that big O should be scale-invariant, that is, it should treat the functions $f$ and $Cf$ exactly the same. Stated differently, if $f_1,f_2$ differ by a constant factor, then $f_1,f_2$ should be treated the same.

In practice, the condition "$f_1/f_2=\text{const}$" is too restrictive. Instead, we would like to treat two functions $f_1,f_2$ in the same way as long as $f_1/f_2$ is bounded, that is, as long as $C_1 \leq f_1/f_2 \leq C_2$ for some constants $C_1,C_2>0$. That is, we would like that

  For all $C_1,C_2,D_1,D_2$ and functions $f_1,f_2,g_1,g_2$ satisfying
  $C_1 \leq f_1/f_2 \leq C_2$ and $D_1 \leq g_1/g_2 \leq D_2$:
  $$
f_1 = O(g_1) \Longleftrightarrow f_2 = O(g_2).
$$

You can check that the definition of big O satisfies this invariance property. The constant in the definition of big O ensures that. Indeed, while $2n \leq n$ doesn't hold, $2n = O(n)$ does hold.

The integer constant – $N_0$ – in the definition of big O isn't really necessary. It is there so we can accommodate functions which aren't positive or aren't even defined for small $n$. If your functions aren't pathological in that sense, then you can do away with $N_0$.

For these non-pathological functions (extended to non-integer points), the various asymptotic notations have equivalent definitions in terms of limits:

$f = O(g)$ if $\limsup_{n\to\infty} f(n)/g(n) < \infty$.
$f = \Omega(g)$ if $\liminf_{n\to\infty} f(n)/g(n) > 0$.
$f = \Theta(g)$ if both these conditions hold.
$f = o(g)$ if $\lim_{n\to\infty} f(n)/g(n) = 0$.
$f = \omega(g)$ if $\lim_{n\to\infty} f(n)/g(n) = \infty$.


Sampling numbers from a weighted set that sum to constant value

There's a close connection between counting the number of solutions and randomly sampling from the set of solutions.  Any time you need to randomly sample, it's often helpful to ask yourself how you'd count the number of solutions, and then you can often turn that into a way to randomly sample.

So, one approach is to use dynamic programming to count the number ways to select numbers from $S$ that sum to $k$ (weighted by their weights $W$), then use that to help you sample from this space.  Let me spell out the details more.

Define

$$f(S,W,k) = \sum_I \prod_{i \in I} w_i,$$

where $I$ ranges over all sets of indices such that $\sum_{i \in I} n_i = k$.  Notice that if all the weights were 1, then $f(S,W,k)$ would count the number of ways to select these numbers; in general, with arbitrary weights, you can think of $f(S,W,k)$ as a weighted count, where you sum up the weights of each candidate combination, and the weight of a combination is the product of the weights of the numbers selected.  You can compute $f(S,W,k)$ using dynamic programming, using the recurrence

$$f(\{n_1,\dots,n_j\},W,k) = f(\{n_1,\dots,n_{j-1}\},W,k) + w_j f(\{n_1,\dots,n_{j-1}\},W,k-n_j).$$

Now you want to sample a set $I$ with probability proportional to $\prod_{i \in I} w_i$.  This can be done, using your algorithm for computing $f(S,W,k)$.  In particular, if $S=\{n_1,\dots,n_m\}$, then flip a coin with heads probability

$${f(\{n_1,\dots,n_{m-1}\},W,k) \over f(\{n_1,\dots,n_m\},W,k)}.$$

If it is heads, then don't include $n_m$ in the solution: instead, recursively sample some numbers from $\{n_1,\dots,n_{m-1}\}$ that sum to $k$, and output that as the random sample.  If it is tails, then do include $n_m$ in the solution: recursively sample some numbers from $\{n_1,\dots,n_{m-1}\}$ that sum to $k-n_m$, then add $n_m$ to that combination, and output that as the random sample.  You can see that this induces the correct probability distribution on samples.

Overall, the running time will be comparable to the time to compute $f(S,W,k)$, or in other words, the running time will be $O(|S| \cdot k)$.  This is much better than the $O(|S|^k)$ naive solution.  It can still be very slow if $k$ is enormous, but if $k$ is not too big, it might be perfectly satisfactory.


That Wikipedia article is using a different definition of "balanced":

  A balanced binary tree has the minimum possible height.

Therefore, since a perfect binary tree of height $d$ has $2^{d}-1$ nodes, if a tree has $n$ nodes, the minimum possible height for that tree is $\left \lceil \log_2n \right \rceil$, and the tree you mention does indeed satisfy that condition.

Observe that the usual definition of "balanced tree" is in an asymptotic setting, i.e. depth is $\mathcal{O}(\log n)$.


Register images from a camera which has undergone pure forward translation

Without knowing a decomposition of the scene into objects and the depth of each object (distance to each object), it's not possible to achieve what you want.  A very-close object will be affected much more by the translation than a very-distant object.


Yes, you can do it.  Concatenate the two feature vectors to get a single feature vector of length 147; the first 144 components are from the HOG, and the last 3 components are from the RGB.  Then apply the SVM on the feature vector of length 147.  SVM doesn't care where the individual numbers came from.

Code is off-topic on this site.


What does "context" in "context-free grammar" refer to?

You are right, there always is a context in some sense. I don't think you can understand what "context" means in "context-free" without understanding a production.

A production is a substitution rule.  It says that, to generate strings within the language, you can substitute what is on the left for what is on the right:

A -> xy

This means that the abstract sequence A can be replaced by the character "x" followed by the character "y". You can also have more complex productions:

zA -> xy

This means that the character "z" followed by the abstract sequence A can be replaced by the characters "x" and "y".

A context-free production simply means that there is only one thing on the left hand side. The first example is context-free, because A can be replaced by "x" and "y" no matter what comes before or after it. However, in the second example, the character "z" has to appear before the A, and then the combination can be replaced by "x" and "y", so there is some context involved.

A context-free grammar is then just a grammar with only context-free productions.

The second example is actually an example of an unrestricted production. There is another category that is between context-free and unrestricted called "context-sensitive". An example of a context-sensitive production is:

zA -> zxy

The difference being that what comes before A (and after) on the left hand side has to be preserved on the right. This effectively means that only A is substituted, but can only be substituted in the proper context.


Understanding B tree key deletion step from CLRS algorithm

You are probably overthinking it by thinking in terms of predecessor/successor nodes.

The rule just says, if the key to be deleted has both children at least capacity, you cannot take a predecessor(or successor) from its left(or right) child without violating the B-Tree property. So, we decide that we will merge it with both its children and push the decision to delete one level downward. That's it.

An intermediate step in 2c. would be where G is pushed downward and merged with [DE] and [JK] to give

[[AB] , [C], [DEGJK], [L], [NO]]

Now we can apply the algorithm to this node [DEGJK], and since it's a leaf node, step 1 will apply here and we can simply delete G from it.


Minimizing the full adder - where did this XOR come from?

Consider the truth table for $(\overline{B}\overline{C}+BC)$. It has 1's exactly when $B$ and $C$ get the same value, which is exactly when $(B\oplus C)$ gets 0, hence, $\overline{B\oplus C}$ is equivalent to $(\overline{B}\overline{C}+BC)$.


What is the reason of inaccuracy of operations on float numbers?

It's because 0.1 = 1 / 10 = 1 / (2 × 5) cannot be represented exactly in binary floating point.  This happens in C too:

 printf("%.20f", fmod(4.0,0.1));

prints 0.09999999999999978351.

Specifically, the only numbers that binary floating point can represent exactly are dyadic fractions of the form a / 2b, where a and b are integers.  Even more specifically, for IEEE single precision floating point numbers, a must be between -224 and 224 and b must, in effect, be between -151 and 104.  (Or at least approximately so; there are some tricky special cases like denormalized numbers.)  For double precision floats, the ranges are wider, but even so, a fraction like 1 / 10 cannot be represented exactly, because the denominator is not a power of two.


There's a loop hidden inside isPalindrome(). Possibly also one inside substring() and/or length(), depending on how they're implemented.

You can't just count loops. When we say that an algorithm runs in time $O(n^3)$, we mean that it takes "at most roughly" $n^3$ basic steps. You need to check whether the steps of the algorithm really are basic, or whether they also involve iterations through data structures.  "Basic" corresponds to something like "taking a fixed number of machine instructions, regardless of the input" but this is an informal analysis, so I'm not going to try to give a formal definition.

There's also the technicality that any algorithm that runs in, say, exactly $n^2$ steps runs in time $O(n^3)$, time $O(n^4)$, time $O(2^{2^n})$ and so on, since the definition of $O(\cdot)$ involves an "at most".


Can one consider living (biological) cell to be Turing Complete?

Every living organism has -- to our knowledge -- only a finite amount of resources available. So no, they can not be Turing-complete.

That said, there is quite a number of bio-inspired models of computation that can be studied formally. Sticker systems [1], for instance -- an abstraction of recombining DNA fragments -- can be shown to reach Turing-power when we assume infinite resources. Splicing systems [2] are another example.

I am not aware of any abstractions of entire cells. To my knowledge, we do not have a full understanding of how cells work so that is out of reach -- today.

Note: Turing-completeness requires programmability resp. universality. Can you elicit any response from a cell by applying suitable stimuli? I wouldn't think so. In my opinion, any given cell is more likely to correspond to a specific program with a specific purpose.

Sticker Systems by G. Păun and G. Rozenberg (1998).
Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors by T. Head (1987).


Formulas for which any equivalent CNF formula has exponential length

Try parity. Parity of $n$ variables has formulas of size $O(n^2)$, but every clause in the CNF must be of width $n$, so there must be at least $2^{n-1}$ of them.

Here are some more details. The $O(n^2)$ formula for parity is obtained by a recursive construction. For simplicity, let's assume that $n = 2^m$ and only count leaves. We use the following formulas:
$$
\begin{align*}
\operatorname{parity}(x_1,\ldots,x_{2n}) = &(\operatorname{parity}(x_1,\ldots,x_n) \land \lnot \operatorname{parity}(x_{n+1},\ldots,x_{2n})) \\ \lor &(\lnot \operatorname{parity}(x_1,\ldots,x_n) \land \operatorname{parity}(x_{n+1},\ldots,x_{2n}))
\end{align*}$$
and $\operatorname{parity}(x_1) = x_1$. Let $P(n)$ be the number of leaves in $\operatorname{parity}(x_1,\ldots,x_n)$. Then
$$ P(2n) = 4P(n), \quad P(1) = 1. $$
The solution to this recurrence is $P(2^n) = 4^n$. Since parity of $n$ variables can be obtained from parity of $2^{\lceil \log n \rceil} < 2n$ variables, in total parity for $n$ variables can be realized using a formula containing at most $4n^2$ leaves. The length of a binary encoding of the formula is $O(n^2\log n)$ (the $\log n$ factor comes from the fact that the indices have length $\log n$).

Regarding CNFs, let's consider DNFs instead; the situation is symmetric. Suppose $\phi = T_1 \lor \cdots \lor T_\ell$ is a DNF for $\operatorname{parity}$. Each $T_i$ must contain $n$ variables: given the values of even $n-1$ variables, you cannot be certain that $\operatorname{parity}$ is true. So each term "catches" one $1$-input of $\operatorname{parity}$, of which there are $2^{n-1}$.


Hint:

   Use the techniques in How hard is finding the shortest path in a graph matching a given regular language?.


Do approximation results for CSPs hold even when domains are of finite but different size?

This is known as multi-sorted CSPs (a sort in logic is a type of variable). See An Algebraic Approach to
Multi-sorted Constraints by Bulatov and Jeavons, for example.


Examples of higher order algorithms ($\mathcal{O}(n^4)$ or larger)

Most simple example gives nested cycles: we know that, if we want, for example, find similar elements for 2 arrays, then we used 2 nested loops and therefore we have $O(n^2)$ complexity.
Hence, every 4 nested loops gives complexity $O(n^4)$, $k$ nested loops $O(n^k)$.
Another examples Karmarkar's algorithm, AKS primality test


Is Semantic Preservation Soundness (or Correctness) or Completeness

This is really a question about the notion of operational correspondence.

The paper Towards a Unified Approach to Encodability and
Separation Results for Process Calculi by Daniele Gorla (http://wwwusers.di.uniroma1.it/~gorla/papers/G-CONCUR08.pdf) is concerned with correctness criteria for translations between process calculi.

In his work, Gorla introduces a notion of behavioural equivalence; I will leave it out here in order not to complicate the explanation overly.

Let $[ \! [ \; ] \! ]$ be an encoding, let $\rightarrow_1$ be the transition relation defined for the source language and let $\rightarrow_2$ be the transition relation defined for the target language. If we have that

If $S \rightarrow_1 S'$ then $[ \! [ S ] \! ] \rightarrow^*_2 [ \! [ S' ] \! ]$, we say that the encoding is complete
If $[ \! [ S ] \! ] \rightarrow^*_2 T$, then there exists a $S'$ such that $S \rightarrow^*_1 S'$ and $T \rightarrow^*_2 [ \! [ S' ] \! ]$, we say that the encoding is sound.

So yes, the notion mentioned in the questions is indeed that of completeness. The notion of soundness is shaped by the fact that the target language will often be richer than the target language or contain syntactic constructs whose behaviour does not correspond to anything in the source language. This explains why we speak of the intermediate configuration $T$ in the definition instead of requiring injectivity.


Worst case analysis of bucket sort using insertion sort for the buckets

You should first understand the proof that bucket sort runs in expected linear time if insertion sort is used. At some point in the proof, the worst-case running time of insertion sort  shows up. See what happens when you plug in instead the worst-case running time of any other sorting algorithm.

The reason insertion sort is used in practice is that we expect the buckets to be small, and for small lists, insertion sort is much faster than anything else. Even when implementing merge sort or quicksort, insertion sort is used when the list gets small enough (say below 20 items or so).


First simplification: this algorithm, by inspection, cannot say YES when it shouldn't, since saying YES is immediately after a test verifying that the sum at the current positions is $b$.

Second simplification: It always terminates, since $i$ and $j$ move in a monotone way up and down respectively, and one always moves.  Thus, eventually they become equal and the loop ends.

So let's assume that that answer is YES, and $x$ and $y$ are the indices we are interested in, after sorting, with $x$ as small as possible and then $y$ as large as possible (we may have several possible pairs with the right sum).  Here is the invariant:

At the start of the loop, $i\le x$ and $j\ge y$.

If $i=x$ and $j=y$, then the algorithm will stop and say YES.  The loop invariant is trivial at the start, and also trivial when $i<x$ and $j>y$.  But if $i=x$, and $j>y$, then, since the array is sorted $A[i]+A[j]>b$, because of how $y$ was selected.  So $j$ decreases in all future iterations until it reaches $y$.  The other case, where $j$ gets to $y$ first is symmetric.

As noted above, the algorithm always terminates, which implies the algorithm will actually say YES, so we are done.

Edit: Since this question is about proof writing, here is another option, which I think is more confusing and more gritty.  I do not know if Tony Hoare would approve or not.

Here is the invariant:  A the top of the loop,

If $s<i$, then, for any $x\in [n]$, $A[s] + A[x] \neq b$
If $t>j$, then, for any $x\in [n]$, $A[x] + A[t]\neq b$

Again, this holds vacuously at the beginning.  Now we check some cases:

If $i = j$, then in any pair of indices $x$ and $y$ at least one of $x$ or $y$ is smaller than $i$ or bigger than $j$.  This rules out the input being a YES.  The loop ends and says NO, so we are in good shape.
Assume the loop did not end. If $A[i] + A[j] = b$, the answer is YES, and the algorithm works.
Assume $A[i] + A[j] \neq b$.
Subcase: If there is a $j'$, by hypothesis $j'<j$, such that $A[i] + A[j'] = b$, then $A[j'] < A[j]$ because the array was sorted, so $A[i] + A[j] > b$, which causes $j$ to decrease.  This shows that the invariant is maintained for $i$.  To see it for $j$, just note that if there is an $x$ such that $A[x] + A[j] = b$, then $x < i$, which is ruled out by the inductive hypothesis.
Subcase: If there is a $i'$, by hypothesis $i'>i$, such that $A[i'] + A[j] = b$, then $A[i'] > A[i]$ because the array was sorted, so $A[i] + A[j] < b$, which causes $i$ to increase.  This shows that the invariant is maintained for $j$.  To see it for $i$, just note that if there is an $x$ such that $A[i] + A[x] = b$, then $x > j$, which is ruled out by the inductive hypothesis.
Subcase: If neither of the other two cases holds, then the invariant is maintained trivially.

Finally, we note that the gap between $i$ and $j$ always gets smaller, so they must eventually become equal, and the algorithm will stop.

Remarks: This is the exact same argument, but more difficult to follow.  You too can write proofs like this using some expert techniques:

Don't say what the algorithm does.  Here, if the input is a YES, the algorithm ALWAYS gives you certifying indices that are as close to the ends as possible.  The 2nd proof cleverly hides this in a case analysis.
Don't give names to things.  Having hidden what the algorithm does, also don't name the stopping point.
Don't factor out easy cases.  This algorithm clearly works for NO instances.  By not noting that up front, we get a more complicated invariant.


How can I infer inputs to a function, given an output?

In the worst case, this is impossible.  However, there are techniques for inversion that can work on some programs.  Of course, you shouldn't expect them to work on all programs given that the problem is hard.

Here are a few standard approaches:

Theorem proving. Use the VCGen part of a theorem prover to generate a precondition formula, where if the formula is true, that implies that the function produces the desired output (or divides by zero, etc.).  Then, use an automated solver to try to find a satisfying assignment to that formula.
Symbolic execution. Execute the function symbolically, and build up a symbolic expression that represents the output of the function, in terms of a bunch of variables (unknowns) that represent the inputs to the function.  Then build a formula by setting that expression equal to the desired output, feed that formula to a SMT solver and ask the solver to find a satisfying assignment for the formula.
Concolic execution.  Pick concrete values for the inputs to the function.  Execute the function on those inputs and record what path it took.  On the side, build up a symbolic expression that represents the output of the function, if it follows the same path.  Build up a "path constraint", which is a formula that is the conjunction of all of the branch conditions followed: the path constraint is a formula over symbolic variables representing the inputs, where inputs that make the path constraint true will cause the function to execute the same path that was previously recorded.  Then, write down a formula that represents the statement "the function takes that path, and its output is equal to the desired value", and feed this to a SMT solver or SAT solver and ask it to find a satisfying assignment.  See concolic testing.

These approaches have different tradeoffs and perform differently, but as you can see, they are similar conceptually.  Here are some significant differences:

Theorem proving and symbolic execution can have problems with loops.  For instance, theorem provers usually require you to supply a loop invariant for every loop.  Concolic execution circumvents this by not trying to reason about all possible paths; only a single one.
Theorem proving and symbolic execution can have problems with state space explosion, as the number of possible paths through the function can be exponentially (or even infinitely) large.  Concolic execution circumvents this by not trying to reason about all possible paths; only a single one.
Theorem proving can use more expressive logics, such as fist-order logic.  Symbolic execution and concolic execution often use propositional logic or a SMT extension.

You can find lots of reference material on these approaches.  For instance, today they're taught in a number of advanced (e.g., graduate) program analysis courses, and there are many publications in the research literature on these topics.


Machine Learning: if test, validation errors are same, the model with lower train loss is better at generalization?

Though usually the test error is your primary goal, I can imagine some specific cases when the train error also matters. One possible example: training set has much more 'hard' inputs than the test set.

If you ever visually examined MNIST, you've probably seen that some images are puzzling even for a human, while others are much easier to tell. If one would split the training/test set differently, it's possible to see that training error would be higher than the validation or test error.

However, it's important to say that a situation like that indicates that data is probably poorly collected or split. So in this case it's better not to choose model A vs model B, but to check the data.


If I am not wrong then it can be inferred that :

  $f=\lambda x.(x−y)$ means that while computing the value of the expression the
  expression will vary only with "x" and similarly when "lambda " is
  placed with x the other variable y" will be kept as a constant .

Yes, intuitively that's how it works.

What you're looking is called Currying and it's explained fairly early in this book (in fact, I think it's the next section but I don't have a copy now to check). So when we want to work with functions with many arguments we often do it like this:

$$ f(x,y,z) = x\times y + z$$

But you can break this into simpler functions, $(x \times y)$ and $(+z)$. The multiplication can be broken into even simpler terms, first I provide $x$, then just multiply by $y$, that is, $f^{\star}(y) = x\times y$.

Defining some 1-argument functions:

$$
\begin{align*}
plus_z &:= f^\prime(s) = s + z\\
 times_y &:= f^\star(s) = s\times y
\end{align*}
$$

Combining these we can rewrite $f$ as:

$$ f(x,y,z) = f^\prime(f^\star(x)) = plus_z (times_y ~ x) $$

Writing this in using $\lambda$ we have:

$$ \lambda x y z. (x\times y + z)  \equiv \lambda x.\bigg(\lambda y. \Big(\lambda z. (x\times y + z ) \Big) \bigg)$$

What the author has shown is that you can take a function with many arguments and transform it into many simpler functions with just one argument, the bigger function is just a composition of the simpler ones.

So just how the proof works? In your book the following functions are defined:

$$
\begin{align*}
h^\star &= \lambda x . (\lambda y . x − y)\\
h(x,y) &= x-y
\end{align*}
$$

You want to show that $ h^\star = h$. To do that just take any two arguments $a$ and $b$. First evaluate $h^\star$ in $a$.

$$ h^\star(a) = (\lambda x. (\lambda y. x - y))(a) = \lambda y. a - y$$

This gives you a simpler one argument function $h^\prime = h^\star(a)$.

  How was $(λy.a−y)(b)=a−b$ concluded

The same way $(\lambda x. (\lambda y. x - y))(a) = \lambda y. a - y$ was concluded. Just evaluate the function in $b$.

$$ h^\prime(b) = (h^\star(a))(b) = (\lambda y. a - y)(b) = a - b$$

Which is the same result computed by $h(a,b) = a - b$.


Your problem is essentially the same as set cover, a classical NP-complete problem.

In set cover, we are given sets $S_1,\ldots,S_n$ together covering a universe $U$, and the problem is to find the smallest subset that still covers $U$. The only difference between this and your problem is that you want to cover some $V \subseteq U$. You can get the classic formulation by intersecting all sets with $V$.


I don't get very well the point of the requirement in the problem of a randomized algorithm. Or maybe I am misinterpreting what is the notion of problem size with respect to which the running time is required to be polynomially bounded. With respect to the number of entries of $A$ and $B$ there is the following deterministic algorithm.
The requirement of $C$ having rational entries, or more generally entries in the same field as the entries of $A$ and $B$ points to using the Frobenius/Rational normal form (FNF). The Jordan normal form is inconvenient because, in general, it requires working in a field extension in which the characteristic polynomials of $A$ and $B$ factor completely (split).
Just like in the case of Jordan normal form, there are invertible matrices $P_1,P_2$ such that $P_1AP_1^{-1}=A_f$ and $P_2BP_2^{-1}=B_f$ and $A_f, B_f$ are the Frobenius normal forms of $A,B$, respectively. The additional property that we mentioned before is that all these matrices have entries in the same field as the entries of $A$ and $B$.So, if your matrices have integer entries, then these matrices will have rational entries.
Now, the matrices $A$ and $B$ are similar if and only if $A_f=B_f$. When this happens we can compute the required $C$ from $P_1AP_1^{-1}=A_f=B_f=P_2BP_2^{-1}$, since we get $(P_2^{-1}P_1)A(P_2^{-1}P_1)^{-1}=B$. So, we can take $C=P_2^{-1}P_1$.
The FNF can be computed (without emphasis on efficiency) by considering the polynomial matrices $A-xI$ and $B-xI$ and reducing them to their Smith normal form. This consists in a combination of Gauss elimination (row/column reduction, if you call it that way) combined with Euclid algorithm to compute some polynomial GCDs that are required. The Smith normal form tells you the invariant factors, and then the Frobenius normal form is the block-diagonal matrix in which the blocks are the companion matrices of the invariant factors. The sequence of steps to reduce $A-xI$ and $B-xI$ to their Smith normal forms give you the $P_1$ and $P_2$ required above.
Justifying all these claims requires a long exposition of the linear algebra (and either explicitly or implicitly the structure theorem of finitely generated modules over a principal ideal domain). This can be found in many linear algebra books. One that I know has it is Dummit and Foote's Abstract Algebra.

A guess of how randomization could be used is by trying random vectors $v$ and finding the maximal Krylov subspaces that it generates. This is, the space generated by $v,Av,A^2v,A^3v,...$, which ought to be generated by finitely many of those vectors. Each one of those give you a cyclic invariant subspace of $A$, which tell you a block of the Frobenius normal form. Then pass to the quotient space by this subspace and repeat until you find all blocks of the FNF. Understanding the theory is required again to see why.


How do I test if a polygon is monotone with respect to an arbitrary line?

It is possible.

Consider you polygon and consider the "concave" vertices. They define exactly which lines will intersect the polygon more than twice. In the following figure I marked the intervals (in red) of forbidden angles. If you put them together and see a hole in the red disk, then there are authorized angles $δ$ (in blue). The polygon is then monotonous with respect to any line of slope $-1/\tan δ$ (in green).

Now the algorithm.

Let $v_i=(x_i, y_i)$ be the $i$th vertex of the polygon. First compute the absolute angle $α_i$ of the edge $(v_iv_{i+1})$ and the inner angle $β_i$ of the vertex $v_i$. Use the function atan2 available in all good programming languages.

$$α_i=\mbox{atan2}(y_{i+1}-y_i,x_{i+1}-x_i)$$
$$β_i = α_{i+1}-α_i+
  \left\{
  \begin{array}{ll}
  0 & \mbox{ if } α_{i+1} ≥ α_i \\
  2π & \mbox{ if } α_{i+1} < α_i \\
  \end{array}
  \right.
$$

Reverse the order of the vertices if they are not in the counterclockwise order, i.e. if $s=\sum_i β_i-nπ$ is not negative. ($s=-2π$: counterclockwise, $s=2π$: clockwise).

The following is only for the $m$ inner angles bigger than $π$ that is, $β_j>π$. The red ones in my pic. The goal is to find an angle $δ$ that is not in $∪_j[α_{j+1},α_j]$ modulo $π$. Namely such that for all $j$ such that $β_j>π$:

$$(δ<α_{j+1} ∨ α_j<δ) \mbox{ if } α_{j+1}<α_j$$
$$(α_j<δ<α_{j+1}) \mbox{ if } α_j<α_{j+1}$$

where $α_j$ is here the normalized value of $α_j$ in $[0,π)$. The second case correspond to an interval that goes beyond $π$ (so this time $δ$ must be "inside").

There is probably a faster way to do this but one in $O(n^2)$ is to sort the values $α_j\mbox{ mod }π $ into $γ_1,…γ_m$ and to test for $δ∈\{\frac{γ_1}2,\frac{γ_1+γ_2}2,…,\frac{γ_{m-1}+γ_m}2,\frac{γ_m+π}2\}$.

If you have find some $δ$ then $L$ exists and is of slope $-1/\tan δ$. Otherwise $P$ is not monotonous.


Does the specific size of matrices affect the performance of matrix operations?

While you can only be 100% certain when you ask the authors, most authors use this simply because you have to choose one value. The specific value doesn't matter too much, only the order of magnitude. Taking a power of 2 seems to be a natural choice.

You can also take a setup which uses a power of two and reduce the number by one. The computation time should be roughly equal, probably be a bit lower. If it is noticeably higher, there might be a performance benefit of using the choice of the author.

See also

Datascience.SE: Why the number of neurons or convolutions chosen equal powers of two?
Quora: Should I use powers of 2 when choosing the size of a batch size when training my Neural Network?


How to merge a lot of trees into one single graph?

Yes, this is sort of common subexpression elimination.

Simple approach for binary trees: introduce nodes 1 for a ... 6 for f.

Traverse your trees. When you have new pair like (1, 2) or (4, 5) introduce for them new nodes like 7 and 8, when you hit old pair, add edge from it.

You will need unordered map from pair of nodes to node, representing this pair:

(1, 2) -> 7
(3, 4) -> 8
(7, 8) -> 9
etc...

More on CSE avaliable by following links from wikipedia

If tree is not binary tree, first make it binary tree with first child / right sibling procedure. CSE in compilers most often is done on three-address code (like GIMPLE in GCC), i.e. on binary expressions only just because it is really more convenient


Clock solitaire game and principle of deferred decision

You can show that as long as the game goes on, the next card being picked is a random card chosen uniformly among the cards not already picked. We can imagine the same process continuing even if the game does stop. From that point of view, what we have is a completely random order of the deck; the game stops once the fourth king is reached; we win if the fourth king is the last card. Now the probability that the fourth king is the last card is the same as the probability that the last card is a king, which is 1/13.


Is spectral radius of a graph related to its radius?

No, the two notions are unrelated. To see this, we construct a pair of graphs with the same spectrum, but different radius. Graphs that have the same spectrum are called co-spectral. There exist non-isomorphic graphs that have the same spectrum.

This page  shows two co-spectral graphs with different radius: the 4-cycle and point has infinite radius, as it is disconnected, but the co-spectral 4-star has radius 1.

The other way around, two graphs of the same radius with a different spectrum, isn't hard to see either. Simply take two graphs with a different number of nodes  and the same radius, their spectra must differ as their adjacency matrices have different size.

The word radius is quite general, so it is no surprise to see it in two unrelated terms.


What follows is taken from Tsuyoshi Ito's comment.

In the case of DAG, all paths can be enumerated in polynomial space and therefore the problem cannot be EXPTIME-complete unless PSPACE=EXPTIME. The natural decision version (given a DAG G, its vertices s and t, and numbers x and y, decide whether there is a path from s to t whose length is between x and y) is in NP.


Is logical address generated by CPU and MMU same if Physical and Virtual address space are same?

It can be but not necessarily.

The MMU can be setup to translate adresses. There is nothing stopping you from having swapping physical adresses between, say, two logical segments and still have the same amount of logical and physical adresses. Sounds a bit unusual to me, but not impossible.


How to calculate the number of tag, index and offset bits of 2 different caches?

Assuming that your machine is byte addressable(1 word = 1 byte), Let us solve the problem step by step.

1.

Physical address = 36 bits. Since 32 bytes/line and size of cache line = size of main memory block, this means block offset = 5 bits. Hence remaining 31 bits is block number( = tag + index).

number of cache lines = 128KB/32B, therefore, 12 bits for index and hence remaining 19 bits for tag.

2.

Physical address = 36 bits. Since 64 bytes/line and size of cache line = size of main memory block, this means block offset = 6 bits. 2-way associative cache means that two lines in one set.

number of sets = total cache lines/2 = (512KB/64)/2 = 2^12 , therefore 12 bits for set, and hence remaining 18 bits for the tag.


Be careful, a polynomial algorithm, that finds a minimal unsatisfiable core of a given CNF , doesn’t mean that =, because the algorithm could output a Boolean formula  such that if  is unsatisfiable,  is a minimal unsatisfiable core of ; if  is satisfiable,  is a subset of the clauses of  and it is satisfiable. Therefore, the output of the algorithm is a CNF but we don’t know if it is satisfiable or not.

The basis of this statement seems to be a slight misunderstanding of the UNSAT to MINIMAL UNSATISFIABILITY reduction given in The complexity of facets resolved.  This reduction is not a way to produce an unsat core even if the original formula is unsatisfiable.  What the reduction does is embed the original formula into a new formula carefully crafted such that satisfiability is unaffected but the new formula's CNF clauses no longer overlap in the assignments that they forbid.  Because each clause forbids different assignments and because the formula's clauses cover all possible assignments, removing any one clause is guaranteed to make the result satisfiable, which is the definition of a minimally unsatisfiable formula.  But this new formula is not an unsat core of the original formula and tells you nothing about how to find such a core.  The original formula and the new formula are equisatisfiable and thus are related, but they aren't related in a way useful in finding an unsat core for the original formula.
As for practicality, by this the Wikipedia article means "easily implemented once you have a certificate of unsatisfiability for a given Boolean formula."  If you already have a tool to generate such a certificate, you can produce an unsat core using a polynomial number of calls to that tool.  If the tool requires exponential-time relative to the size of the formula, then you're still looking at an exponential process to find an unsat core.  But it is just as "practical" as determining whether the formula is unsatisfiable in the first place.


In a nondeterministic automaton, a given string may have multiple possible paths through the automaton, since the path may include $\varepsilon$-transitions and may reach nodes where there is more than one possible non-$\varepsilon$-transition. A given string may also have no possible path if all the ways to traverse the automaton reach a point where there is no outgoing transition with the correct letter. If there's no possible path through the automaton, the string is rejected, just as if there are paths but none of them reach an accepting state. To determine whether a string is accepted, what matters is only whether there is a way to reach an accepting state, not what happens on paths that don't lead to an accepting state.

You can add a sink state to your automata: add a state $q_s$ which has outgoing transitions to itself (and only to itself) on all letters ($q_s \xrightarrow{0} q_s$, $q_s \xrightarrow{1} q_s$) and add transitions from other states wherever a letter is missing ($q_0 \xrightarrow{0} q_s$, $q_0 \xrightarrow{1} q_s$, $q_1 \xrightarrow{1} q_s$, $q_2 \xrightarrow{0} q_s$). Since there is no way to reach an accepting state via $q_s$, adding this state and these transitions doesn't change the language that the automaton recognizes.

“Completing” the automaton in this way isn't very useful for a nondeterministic automaton. It lets you ensure that every string has at least one path, but note that some strings now have more paths — for example the string $0$ used to only have the path $(q_0, q_1, q_1)$ but now also has $(q_0, q_s)$. The situation is different with deterministic automata. A deterministic automaton must have a transition at every state for every letter. There's a convention to allow some transitions to be missing. Such an incomplete automaton (with missing transitions, i.e. the “transition function” is only a partial function) is equivalent to a complete automaton (where the transition function is a function) which has one extra state, called a sink state, with the missing transitions leading to it and outgoing transitions only to itself. This is a useful convention with deterministic automata, where it's useful to draw automata without “useless” transitions but easier to reason on complete automata where all transitions are present. With nondeterministic automata, since a string doesn't have a unique path through the automaton, making an explicit sink state isn't particularly useful.


How to characterize equivalence classes induced by Myhill-Nerode theorem?

To prove that the classes $C_k$ are equivalence classes for the Myhill-Nerode relation we need to show

For any strings $x,y \in C_k$ there does not exist a distinguishing extension of $x$ and $y$. This proves $C_k \subseteq [w]$.
For any $x \in C_j$ and $y \in C_k$ there does exist a distinguishing extension. Since every string $\omega$ belongs to some $C_k$ this shows that the $C_k$ form a partition of $\Sigma^*$.

These together show that the $C_k$ are exactly the equivalence classes under $\sim_L$.

Let $N(w)$ denote $N_0(x) - N_1(x)$.

For the first part, note that $x, y \in C_k \implies N(x) = N(y)$. Then for any extension $r$, we have that

$N(xr) = N(x) + N(r) = N(y) + N(r) = N(yr)$

and so $xr \in L \iff yr\in L$. Thus $r$ cannot distinguish $x$ and $y$.

For the second part, we have that $N(x) \neq N(y)$.
Assume WLOG $N(x) > 0$.

Then the extension $1^{N(x)}$ distinguishes $x$ and $y$ since $$N(x1^{N(x)}) = N(x) - N(x) = 0 \implies x1^{N(x)} \in L$$
while
$$N(y1^{N(x)}) = N(y) - N(x) \neq 0 \implies y1^{N(x)} \notin L$$

Intuitively, we interpret the equivalence classes as "states" of some machine for deciding the language. This is literally true in the case of regular $L$, but even in this infinite case we can interpret "state" to mean $k$. Once two strings are in the same state, there is no going back: there is no further information that we can feed to the machine and cause it to diverge.

In this particular case, we look at the definition of the language and note that the only information that we care about is $N(w)$. Since this information in some sense captures all we need to know about a string, it makes sense that strings that are identical under this classification can never be distinguished by the language.

There is certainly no algorithmic way of classifying $\sim_L$ in full generality since even deciding whether two strings belong to the same class is undecidable clearly for undecidable languages $L$.

In the restricted case of context free languages I don't know of any generic canonical characterization. There are some relevant discussions here and here


How to solve T(n)=2T(√n)+log n with the master theorem?

Let us actually use the master theorem.

Define $S(n) = T(e^n)$ for all $n$. Then
  $$S(n) = T(e^n) = 2T(\sqrt{e^n}) + \log(e^n) = 2T(e^{n/2}) + n = 2S(n/2) + n$$
Now we can apply the second case of the master theorem to $S(n)$ for $a = b = 2$ and $f(n) = n$ to obtain
  $$ S(n) = \Theta(n\log n)$$
So for $n\gt0$,
  $$ T(n) = S(\log n) = \Theta(\log n \log\log n)$$


Why can we write almost any nonzero 2-adic integer in the same form?

The pattern $x = (\alpha01^a10^b)_2$ is very easy to match. For example, the number $1=0^\infty1$ matches the pattern with $\alpha=0^\infty, a=b=0$. Try matching some other numbers yourself. The only thing this pattern asks for, is for the string "$01$" to appear somewhere in the sequence of bits. The only numbers to fail this condition are $0=0^\infty$ and $-2^b=1^\infty0^b$.


Set $V_i' = V_i \cap V'$. You can solve this by finding the maximum matching using at most $k$ vertices from $V_1'$ and at most $x-k$ from $V_2'$ for all $k \in [0, x]$. This in turn can be found with maximum flow.

To find this maximum matching, we modify the usual reduction to maximum flow. Let $s$ be the source and $t$ the sink. Let $l$ and $r$ be auxiliary vertices. Add an edge from $s$ to $l$ with capacity $k$, and an edge from $r$ to $t$ with capacity $x-k$. All other edges will have capacity $1$. Add an edge from $l$ to every $x \in V_1'$, and from $s$ to every $x \in V_1 \setminus V_1'$. Add an edge from every $y \in V_2'$ to $r$, and from every $y \in V_2 \setminus V_2'$ to $t$. For $(x, y) \in E$, add an edge from $x$ to $y$. Now the maximum flow gives a maximum matching using at most $k$ vertices in $V_1'$ and $x-k$ in $V_2'$.

We can thus solve the problem in $\mathcal{O}(x \cdot M)$ where $M$ is the complexity of maximum flow. The maximum flow problems are very similar, so we can improve on this.

We can increase or decrease the capacity of any edge by $1$ while maintaining the maximum flow in $\mathcal{O}(|E|)$. First calculate the maximum matching using no vertices in $V'$. Then, increase the capacity of the edge from $s$ to $l$ by $x$. Then at every step increase the capacity of the edge from $r$ to $t$ and decrease the capacity of the edge from $s$ to $l$ while maintaining a maximum flow. Output the largest matching produced. The complexity will be $\mathcal{O}(|E| \sqrt{|V|} + x \cdot |E|)$ if we use Dinic to find the initial bipartite matching.


Finding a lower bound for the expression $\ln^k(n)$

The notation $\log^k n$ most likely stands for $(\ln n)^k$ (this is a common abuse of notation).
In this case the claim is trivially when $\varepsilon=0$ true since $n^\varepsilon=1$ and $\ln^k n = \Omega(1)$.
For constant $\varepsilon>0$ and $k \ge 1$ you have:
$$
\lim_{n \to +\infty} \frac{\ln^k n}{n^\varepsilon} =
\lim_{n \to +\infty} \left( \frac{\ln n}{n^\frac{\varepsilon}{k}} \right)^k =
\left( \lim_{n \to +\infty}  \frac{\ln n}{n^\frac{\varepsilon}{k}} \right)^k =
\left( \lim_{n \to +\infty} \frac{1}{n \cdot \frac{\varepsilon}{k} \cdot n^{\frac{\varepsilon}{k}-1}}\right)^k
= \left( \lim_{n \to +\infty} \frac{k}{\varepsilon n^\frac{\varepsilon}{k}} \right)^k
 = 0,
$$
showing that $\ln^k n = o(n^\varepsilon)$, and hence that the claim is false.


Why does the Toffoli gate output c XOR (a AND b) instead of just a AND b?

As the comments said, if it worked like i asked, it would neither be reversible, nor a unitary matrix.

Both things are required for quantum computing!


Why an ARM processor with 32 bits address bus can address 4 billion different bytes?

While there have been computers built that use bit addressing, notably the Burroughs 1700, 1800, and 1900 mainframes and the Intel iAPX-432, the vast majority of machines use byte addressing.

This means that each possible address corresponds to a potential byte in memory.
Thus a 32 bit address would have a span of $2^{32}$ or $4,294,967,296$ bytes.

For completeness, the other category of machines use word addressing, where each address value corresponds to a word of memory. Examples here include the PDP-10 and CDC-6600 as well as many specialized DSP and embedded processors still in use.


As far as number of sequences are concerned, it depends on how you read the problem statement.

  Now a program accesses the pages numbered 1, 2, …, 100 in that order,
  and repeats the access sequence THRICE.

From this line, I perceive that program has accessed this sequence once and again repeats this sequence thrice. So, total four times.

But, I think here number of sequence is not that important. We just need to find page replacement pattern of the given policies in the options, which is similar to Optimal Page Replacement policy.

For the above sequence, which is

  1 2 3 4 .... 99 100 1 2 3 4 .... 99 100 1 2 3 4 .... 99 100 1 2 3 4 .... 99 100

Both First-In-First-Out and Least-Recently-Used policies perform the same way and give same number of page faults. (Not always, but for this sequence)

For both of these policies, the number of page faults are 400. A program will make a replacement for every new page. For the first 20 pages from sequence, program replace the older pages 101 to 120. Then for every new page, a replacement is made in similar fashion.

21st page in place of 1st page

22nd page in place of 2nd page and so on.

After every 20 iteration, a frame will contain entire new set of pages.

Similarly, Last-In-First-Out performs the same way as Most-Recently-Used for this sequence and gives same number of page faults as Most-Recently-Used policy.

Here every time the last page is replaced by the new one.

So, 120th page is replaced by 1st page

1st page is replaced by 2 and so on.

So, here also 400 page faults occurs.

But, I don't think any of the given policy performs the same way as Optimal PR.

In Optimal PR, we'll have 100 + (100-19) + (100-19) + (100-20) = 342 page faults.


Calculate ϴ dependent on n for an algorithm with constant c

I calculated the amount of operations to (c-n)*(n-1)

Not quite. If $n > c$ then the cost is not negative: it should be $(n-1) \max(c-n, 0) = \Theta(n) \max(c-n, 0)$. When $n$ is large (and in particular when $n > c$) what does this reduce to?


If X is in NP then $\overline{X}$ is in NP. True, false or "we don't know"? Why?

The answer is unknown.
If $X\in NP$ and $\bar X\in \mathcal{NP}$ than by definition it's a so called "co-NP" problem ($X\in \mathcal{coNP}$). It's still an open problem if $\mathcal{NP} = \mathcal{coNP}$.
An example:
Some problems are known to be in coNP. E.g. to decide if two number $n,m$ have a common divisor $>1$. This problem is in $\mathcal{NP}$ because there exists a polynomial verifier to check if a "proof" that some $n,m$ have common divisor $>1$ exists. The verifier accepts e.g. a number $p$ if $p>1$ and $p|n \land p|m$ the verifier accepts the proof. Now lets show that the complement of this language is also in $\mathcal{NP}$. We need to construct a verifier that accepts a proof that two numbers don't have a common divisor $>1$. You might notice that this is a bit more difficult but it can be done. The verifier accepts the prime factorization of $n$ and $m$ and checks that these are really the prime factorization of $n$ and $m$ and then that they don't have a common element.
Now try SAT...
Now if you take e.g. the $SAT$ problem and you try to find a verifier for $\overline{SAT}$ you have to find an algorithm that can given a certain proof verify that a boolean expression does not have a solution in polynomial time. If you think about it this is quite tricky (some how you have to deduce from the proof that none of the exponentially many variable assignments is valid) and it's currently not known whether $SAT\in \mathcal{coNP}$.


Number of times statement is executed in complex nested loop

We can determine the exact value of $s$ as a function of $n$. For the sake of brevity, let $\lambda = \left \lfloor \lg n \right \rfloor$. We can replace the inner loop with:

  $s \leftarrow s+n-k$

At the end of the program we'll have:

$$
s= \sum_{h=0}^{\lambda} n - \left \lfloor \frac{n}{2^h} \right \rfloor = n \left( \lambda + 1 \right) - \sum_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor
$$

Our problem is now rewriting the last term in a nicer form. . Certainly $n$ has a unique representation in base $2$, in particular it is true that

$$
n = \sum_{u \in S} 2^u
$$

for some $S \subseteq \mathbb{N}_{\le \lambda}$.

Therefore we have:

$$
\sum_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor = \sum_{h=0}^{\lambda} \sum_{u \in S} \left \lfloor 2^{u-h} \right \rfloor =  \sum_{u \in S} \sum_{h=0}^{\lambda} \left \lfloor 2^{u-h} \right \rfloor =
\sum_{u \in S} 2^{u+1} -1
$$

But then:

$$
\sum_{u \in S} 2^{u+1} -1 = 2n - |S|
$$

Piercing it all together, at the end of the program we will have:

$$
s = n \left ( \left \lfloor \lg n \right \rfloor - 1\right) + \textbf{1}(n)
$$

where $\textbf{1}(n)$ is the Hamming norm of $n$, that is, the number of ones in its binary representation.


Can Homotopy Type Theory be used to derive more efficient algorithms on more efficient data representations from less efficient ones?

You ask if we could derive a more efficent way to compute even? Yes, we could of course. The point however is that compilers could not.

Having a compiler automatically perform very fancy optimization techniques is a hard problem. In fact, if you ask for too much the problem may become undecidable, and for almost all interesting cases at least extremely hard. Even just asking whether two simple types are isomorphic quickly leads to open research questions.

What we have gained from HoTT is not a magic wand, but rather a formalism that provides a very good and structured way of thinking and reasoning about isomorphism, equivalence and equality in general. One can think easily enough about "small scale" notion of equivalence, for example when we focus just on one particular data structure, such as a dictionary, but it's a whole other matter to be able to talk about all notions of equivalence at the same time.

In your particular case it is easy to see what it would mean to have an equivalence between two implementations of natural numbers. But how about equivalence of large software components? Or equivalence of implementations of partial differential equation solvers? How do we even being to think about it? HoTT has an answer.


"inconsistent" here means basically the internal implementation is not reflecting the reality of thread activation and lock availability. aka "defective". ie its not functioning correctly as a thread lock. eg the lock may indicate "active" but no thread has acquired the lock or the lock indicates "inactive" but some thread acquired a lock.
the contradiction is that according to "deadlock free", a lock will eventually be acquired by at least some thread that requests it. but if its in an inconsistent state then some thread is running but the lock indicates that nothing is locked. but then any new thread cannot succeed in obtaining the lock (without running at the same time as A).

note a wrinkle/subtlety from an online ref[1] that closely matches the book exposition (same authors):

  Note that a program can still deadlock even if each of the locks it
  uses satisﬁes the no-deadlock property. For example, consider threads A and
  B that share locks 0 and 1. First, A acquires 0 and B acquires 1. Next,
  A tries to acquire 1 and B tries to acquire 0. The threads will deadlock
  because each one waits for the other to release its lock

[1] Multiprocessor Synchronization and Concurrent
Data Structures Maurice Herlihy / Nir Shavit


recursion code counting down and counting up

Look at the definition of your countdown function.

If I call countdown (5), then it prints "before: n = 5", then it does lots of stuff including lots of printing, then it prints "after: n = 5" and finishes. So your output must start with "before: n = 5" and it must end with "after: n = 5" and all kinds of things might happen in between.

And that's exactly what happens.


Non-deterministic algorithms and Tautologies

An algorithm computing $V$ can be thought of as a non-deterministic algorithm which gets only the first parameter $\tau$ and guesses $P$, verifying that $P$ is a proof of $\tau$.

If you've ever seen the definition of NP using witnesses, in this definition $V$ is accepts the language of all tautologies $\tau$ with proofs in a certain proof system. The witness that such a proof exists is the proof itself $P$, and the function $V$ verifies that the proof is valid for $\tau$.

Another equivalent way of defining a proof system is as a polynomial time function which accepts a proof $P$ and outputs a proposition $\tau$. The two properties satisfied by such a system $S$ is (i) for all $P$, $S(P)$ is a tautology, (ii) for every tautology $\tau$ there exists a proof $P$ such that $S(P) = \tau$. It is an easy exercise to convert between the two definitions.

If you want to learn more, look up Cook–Reckhow proof system.


What is this algorithm? Create a tree's equivalent hierarchical network

Your question contains the implicit assumption/premise that this transformation has a name.  I don't know why you would expect it to have a special name.  The transformation is not anything special or complicated and as far as I know it does not have any special name.  It appears that you are just taking a tree, and making a second copy of it (with all edges reversed; with all nodes cloned), and then just gluing the two copies together (identifying both copies of each leaf).

For future reference, I don't think questions like "please tell me if this function has a special name" are a good fit for this site.  This site is for technical questions that admit an objectively evaluable answer and that relate to a real problem you have.  How do you expect to evaluate an answer that says "No, it doesn't have a special name"?  There is no reference one can cite to back up that answer, and no objectively verifiable evidence one can provide to support such an answer.  Moreover, questions about naming aren't a very good fit.  How will knowing whether there is a special name help  you solve a real problem?  (If you were thinking "it might help me find references that help me solve problem X", then you would be better off by just describing problem X.)


Programming languages and Model of computations

Functional programming languages can often be thought of as built on the lambda calculus.
Imperative programming languages can often be thought of as built on the RAM (Random Access Machine) model of computation.
Some hardware description languages can be thought of as being built on the finite-state machine model, or on digital circuits.
Some declarative languages can be thought of as built on Datalog.
Some concurrent languages can be thought of as built on the actor model or on process calculi (e.g., CSP, the $\pi$-calculus, etc.).


Reference Request: Overlaps between complexity theory and dynamical systems?

This is a well-researched area. For a representative result, see Kawamura's proof that solving ODEs is difficult.

A different line of works studies the hardness of computing Nash equilibria and related problems. See for example the recent breakthrough of Bitansky, Paneth and Rosen, who base hardness of cryptographic assumptions; earlier work based it on complexity theoretic assumptions.


Is there any difference between these two languages?

Yes there is. $w \in \{ a, b\}$ means that $w$ may be either $a$ or $b$, while $w \in \{ a, b\}^*$ means that $w$ may be a string over $a$ and $b$ including the empty string $\epsilon$. In particular $L_1$ is a language having only $a$ and $b$, i.e, $L_1 = \{a, b\}$.


Scheduling Problem Optimisation using LP solvers

Yes, your program can be modelled as an integer linear programming (ILP) instance, and yes, Gurobi is an ILP solver and can be used to solve your problem once you express it as ILP.  I suggest you spend some quality time with a textbook that describes linear programming and integer linear programming.


Efficiently locating the maximum value in interval over large amounts of data points

This can be solved with a balanced binary tree.  Each such query can be answered in $O(\lg n)$ time.

Build a balanced binary tree, where each leaf holds a point, and the tree is keyed on the $x$-coordinate of the points (so the leaves contain the points, sorted from left to right).  Augment the tree, so that in each node $t$ of the tree, you store a pointer to the highest and lowest of all the points within the subtree rooted at $t$.

Now we are given an interval $[\ell,u]$, and asked for the highest point whose $x$-coordinate is within that interval.  It turns out that any such interval can be expressed as a union of $O(\lg n)$ subtree.  In other words, you can find nodes $t_1,t_2,\dots,t_k$ such that (1) every leaf that is a descendant of some $t_i$ has an $x$-coordinate in the interval $[\ell,u]$, (2) every leaf whose $x$-coordinate is in the interval $[\ell,u]$ is the descendant of one of these $t_i$'s, and (3) $k = O(\lg n)$.  Recall that the augmentation tells you what is the highest leaf under each $t_i$.  So, to answer the query, take the highest of all those: that will be the highest leaf whose $x$-coordinate is within $[\ell,u]$.  Since we only need to examine $O(\lg n)$ nodes, the running time is $O(\lg n)$.

How do you find those $k$ nodes?  That's described here: Delete a consecutive range of leaves from a binary tree.  You can verify that you can find those $k$ nodes explicitly in $O(\lg n)$ time, given $\ell$ and $u$.

Conveniently, this data structure works both for the static case (where the set of points doesn't change) as well as the dynamic case (where we want to insert and delete points).  You can insert and delete points in $O(\lg n)$ time: in particular, you can update the augmented information within those time bounds (you just have to touch each node on the path to the root from the inserted/deleted node).


Why time complexity of union-find is $O(lgN)$ with only "Union by Rank"?

Firstly, here is the precise statement of the case 2 in OP's question.

  A sequence of m MAKE-SET, UNION, and FIND operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank in worst-case time $O(m\log_2 n)$.

In fact, it is trivial to see that the MAKE-SET and UNION operations run in $O(1)$ time. So the question is really about the time-complexity of the FIND operation.

Here are the properties of the disjoint-set forest you can prove.

Given any node $u$ that has been added to the set of union-find data structure, the ranks of the nodes in a path from $u$ to its root is strictly increasing.
A node $u$ which is root of a sub-tree with rank $r$ has at least $2^r$ nodes. (This fact can be proved by induction on $r$).
Every node has rank at most $\log_2 n$.

With properties 1 and 3, it should be easy to prove the desired time complexity.

The above explanation follows roughly the section 21.4 in Introduction To Algorithms, third edition by CLRS. Readers are encouraged to read the chapter 21 of that book.


Take a look at rate-distortion theory, which studies information transmission in settings where a certain distortion is allowed (such as audio, image, or video compression).


Number of paths starting from a given edge using adjacency matrix

Note that counting the number of (non empty) paths starting from edge $(q_1, q_2)$ is the same as counting the number of (possibly empty) paths starting from vertex $q_2$. That way, the answer can be given as an array of size $|V|$ for a graph $G = (V, E)$ instead of a matrix of size $|V| \times |V|$.
Knowing that fact, here is an algorithm to compute this array $a$:

compute a topological sort $(v_1, …, v_n)$ of $G$ (this is possible because $G$ is supposed to be acyclic);
for $k$ from $n-1$ to $1$, set $a[v_k] = 1+\sum\limits_{v \text{ adjacent to }v_k} a[v]$, since $(v_k, v)\in E$, that means that $v$ appears after $v_k$ in the topological sort, so the value $a[v]$ has already been computed. Moreover, if the sum is empty, it means that $v_k$ is a sink node, meaning it has no exiting edge, so the only path is the empty path.

The algorithm has a total complexity $O(|V| + |E|)$, which is optimal.
Now, note that the complexity of the previous algorithm suppose you know the adjacency list of the graph $G$. If you only know the adjacency matrix of $G$, then I suggest you first compute the adjacency list of $G$ (time complexity $O(|V|^2)$).


So you can't find out everything about the value of a qubit. That doesn't mean you know nothing about it. And, sure, quantum computing probably would be more powerful if you could find out everything about the value. But, again, the fact that you can't do everything doesn't mean that you can't do anything.

In particular, you know that the measured value of a qubit drawn from a probability distribution constructed by some quantum algorithm. The algorithm will, presumably, construct a distribution that's quite tightly concentrated about the true answer. And you can always repeat the computation to get multiple samples.


In a DBMS what are the implementation details that make set operations faster than cursors?

Set-based operations are iterative at a "low level", and are not necessarily any faster to execute than cursors under all circumstances.
The main advantage with set-based operations is that they are well-defined operators which can be analysed algebraically, and the order of operations thus rearranged or simplified by the database engine, or the exact algorithmic implementation altered - not just at the time of writing the query, but possibly later at the time of subsequent executions of the query.
What is "simple" or "fast" here is constantly re-determined by the database engine at runtime based on the statistics it collects about actual whole database performance.
By contrast, there is much less flexibility for the database engine in the case of cursors, and if every action in a database were written as a cursor then overall performance could become abysmal (or the system more recalcitrant to any changes) far sooner than when set-based operations are used which provide the database engine a large latitude for optimisation.
The most straightforward analogy is the performance of a modern optimising compiler for a high-level language, versus writing everything in assembly language, although this does not quite capture the ongoing monitoring that a database engine performs.


Cyclic Redundancy Check Codewords Finding the Original Message

You should do arithmetic modulo 2. Modulo 2, $-1$ is the same as $+1$.


Is it possible fo find a vertex-cover of size $\lceil \log |V| \rceil$ in polynomial time?

Let the input graph be $G=(V,E)$ and let $k$ be the (maximum) size of the vertex cover of $G$ we are searching for. Proceed as follows:

If $E=\emptyset$ return the trivial empty solution.
Otherwise, if $k>0$:

Pick an arbitrary edge $(u,v) \in E$.
Recursively search for a vertex cover $S$ of size (at most) $k-1$ on the graph $G - u$. If $S$ exists return $S \cup \{u \}$.
Recursively search for a vertex cover $S$ of size (at most) $k-1$ on the graph $G-v$. If $S$ exists return $S \cup \{v \}$.

Return "no solution exists".

The time complexity of the above algorithm can be described by the following recurrence relation, where $n$ is the number of vertices of the input graph for your problem.
$$
T(k) \le 2T(k-1) + O(\mbox{poly}\, n) \quad \mbox{and} \quad T(0)=O(1).
$$
Therefore $T(k) = O( 2^k \cdot  \mbox{poly}\, n )$.
In your case $k=\lceil \log n \rceil$, therefore the overall time needed is $O( \mbox{poly}\, n )$.


I assume you want to put items $w_1$ to $w_{i_1}$ into the first bin, $w_{i_1+1}$ to $w_{i_2}$ into the second bin, etc. etc. The number n of bins is given. This can be done with something similar to dynamic programming.
Examine all possible choices for $_1$ and calculate the error from bin 1 for each of these choices.
Then examine all possible choices for $i_2$. For each $i_2$ pick all possible $i_1$ and pick one where the total error from bin 1 and bin 2 is as small as possible. For each $i_2$, remember which $i_1$ was used with it.
Then examine all possible choices for $i_3$ etc. For $i_n$ there is obviously only one choice, and you have the solution.
You will notice that you make quite a few stupid choices. If you have 10 bins, X = 100, and the sum of weights is 1,000 then puting items with very little weight or total weight over 200 into the first bin is likely stupid. To help with this we find a non-optimal solution with a greedy algorithm. Then we don't accept anything that must be worse than the greedy algorithm. In the example, if the greed algorithm finds a solution with error = 100, then we would never put less than 50 or more than 150 in weight into the first bin.


Functional programming with branches that have no order?

Here's the problem:

You always need some way to resolve ambiguity when there are overlapping clauses
There is no easy syntactic way to ensure that clauses don't overlap.

So, if you can think of a way for the behavior of if to be well defined when there are overlapping clauses, that doesn't depend on the ordering of the clauses, then you can do what you're asking for.

And, there are, of course, a bunch of ways to define this: you could always default to the simplest matching condition (with the shortest code), you could attach an integer at runtime to each case and use the one with the highest number, etc.

But at their core, the process of looking at overlapping cases and choosing one, basically involves ordering the cases in some way. Requiring the user to specify the ordering, and having the order in the source code match the "priority" of each clause, seems like the simplest option.

There is likely a way to ensure that ordering doesn't matter in a dependently-typed language, when you can actually construct a proof that all your clauses are mutually exclusive. Or, you can re-order clauses in an optimizer, if a static analyzer identifies a place where all the clauses are mutually exclusive.

Or, if you're in a non-deterministic language like Prolog, you can just explore all the branches that succeed, and have an if expression return multiple answers. But for most languages, this isn't compatible with their deterministic semantics.

In general, you can't just ignore the order.


Compute the edit distance between two words in which substitution is not allowed

You can use the same dynamic programming algorithm as the one for the Levenshtein distance with a bit of modifications.
Let $u=u_1…u_n$ and $v=v_1…v_m$ be two words. We want to build a $(n+1)\times(m+1)$ matrix $M$ such that for $0\leq i\leq n$ and $0\leq j \leq m$, $M[i][j]$ is the edit distance between $u_1…u_i$ (or $\varepsilon$ if $i = 0$) and $v_1…v_j$. The answer is then $M[n][m]$.
Now note that for $0< i\leq n$ and $0< j \leq m$:

if $u_i = v_j$, then $M[i][j] = \min\left\{\begin{array}{rl}M[i-1][j]+1 & (\text{deletion of }u_i)\\M[i][j-1]+1&(\text{insertion of }v_j)\\M[i-1][j-1] & (\text{no modification})\end{array}\right.$
otherwise, $M[i][j] = \min\left\{\begin{array}{rl}M[i-1][j]+1 & (\text{deletion of }u_i)\\M[i][j-1]+1&(\text{insertion of }v_j)\end{array}\right.$


Algorithm of Communication with Failures

The problem you state is very close to the problem of Byzantine Agreement with faulty links. Yet, it is not clear to me what is the guarantees you seek out of your algorithm.

The algorithm you give does not solve the Byzantine-agreement problem. Specifically, if the party that holds the message is corrupt, and it begins by sending $v_0$ to some player but also $v'$ to other player, then your algorithm will not converge (that is, maybe everyone will have $v_0$, but they will also have $v'$ and will not know what is the message that was originally sent). If you don't care about the parties having $v'$ as well, then why not just sending the message to all the parties (then repeated by each node)?

Note that when links fail, there is a question of connectivity. For instance, if one of the nodes is not connected to any other nodes (all the edges between are faulty), then that node will never get the message. Of course, if the number of faulty edges $f$ is less than $n/3$, and assuming each two nodes are connected, there is no problem at all.

The following paper might be at your help:
Vassos Hadzilacos, Connectivity requirements for Byzantine agreement under restricted types of failures, Distributed Computing, Volume 2, Issue 2, pp. 95-103, 1987. That paper deals with Byzantine agreement with $t$ faulty nodes and $k$ faulty links, and it holds for any architecture of the underlying graph (as long as some connectivity condition holds).

You might also want to take a look at the case where only nodes are faulty.
See for instance, K. Perry, Randomized Byzantine Agreement,
IEEE Trans. on Software Engineering, Vol SE-11, Issue 6, pp. 539-546, 1985.


Edit distance (Levenshtein-Distance) algorithm explanation

You got the recursive definition wrong. It's

$\qquad\displaystyle d_{ij} =
  \min \begin{cases}
         d_{i-1, j}  + c_\mathrm{del}(b_{i}) \\
         d_{i,j-1}   + c_\mathrm{ins}(a_{j}) \\
         d_{i-1,j-1} + [a_j \neq b_i] \cdot c_\mathrm{sub}(a_{j}, b_{i}) \end{cases}$

where the $c_{\mathrm{op}}$ are fixed costs for the respective operations, all of which are $1$ here. You'll note that for alternatives one and two, insertion and deletion (which correspond to a vertical resp. horizontal step in the matrix), don't care if the current symbol matches any other -- you introduce a gap symbol, anyway!

Following this definition, clearly $2+1$ (insertion of $o$) results in the entry you highlight. Note that the alignment computed (implicitly) up until this point is

$\qquad\begin{array}{cccc}
  - & o & - & - \\
  s & o & l & o
\end{array}$


Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G

The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this?

First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has an encoding of size $V^2$. However, if an adjacency list encoding is used, we would only need an encoding of size $O(E \log V + V)$.

Your algorithm does indeed run in $O(n)$ time for a dense graph (with $\sim V^2$ edges); does it also run in $O(n)$ time if the graph is sparse ($O(V)$ edges)? In that case, the encoding might be shorter (if an adjacency matrix is used). Is your algorithm still $O(n)$ in that case? If it enumerates over all potential edges or creates and adjacency matrix, it would not be.

CLRS wants to avoid peculiarities with having to implement the algorithm in a particular way or having to specify a specific encoding, which is why they state "you could certainly implement this algorithm to run in $O(n^2)$ time". The "certainly" means "in any case, you can get $O(n^2)$, but it might be possible to do better". In any case, all they care about is that it is polynomial, which both $O(n)$ and $O(n^2)$ are.


Trie traversal to maximise XOR in a tree but with a condition

You can simply use persistent tries.

Let $T[x]$ denote a trie containing all keys in the path from root to $x$, assume $y$ is a child of $x$, $T[y]$ can be constructed in $O(\log U)$ time from $T[x]$, where $U=2^{32}$. This is trivial even if you use normal tries; but the key point is "persistent" data structures enable you to store all $T[\cdot]$ at the same time. As an intuition, notice that when we construct $T[y]$ from $T[x]$, only $O(\log U)$ nodes in $T[x]$ changes.


How to compare two circular sequences in linear time?

Start with computing the lexicographlcally least circular substrings$^1$ of the both circular sequences and then compare them directly.

Alternatively you can check for the substring $A$ (the first seqience) in the string $BB$ (a concatenation of $B$, the second sequence) circular sequence with itself) using for example the KMP$^2$

You might also be interested in the application of the Suffix Trees (also Suffix Arrays) and this thesis reviewing the applications to DNA sequences.

$^{[1]}$(described in K. S. Booth. Lexicographically least circular substrings.
Inf. Process. Lett., 10(4/5):240-242, 1980., and here
$^{[2]}$(Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt,  SIAM J. Comput., 6(2), 323–350. Fast Pattern Matching in Strings


You get overflow if the result is larger than the maximal integer, in this case 32767. You get underflow if it is smaller than the minimal one, in this case -32768. (In the context of floating-point operations, underflow happens when a non-zero number is rounded to zero.)


Matrix multiplication in recurrent neural networks

Matrix-by-matrix multiplication is very different from scalar-by-scalar. It has no connection to repeated addition, and in fact isn't even commutative: it's entirely possible that $AB \neq BA$. It's only called multiplication because it has some similar properties to repeated addition of scalars.

Matrix multiplication requires that the inner dimensions match. Nothing more, nothing less. You can multiply an (a×b) matrix by a (b×c) matrix, for instance, and the result is an (a×c) matrix. For the full details, Wikipedia has a good summary.

In addition, that code isn't adding or multiplying $U$ and $x[t]$. Rather, it's removing one dimension from $U$, taking only the columns (or rows depending on your definitions) which correspond to 1s in $x[t]$.


Does $c^n = O(2^n)$ and $log_c(n) = O(log_2(n))$ for any constant $c$?

Additionally to already answered in user5876164's comment let me say, that you cannot express $3^n=k \times 2^n+o(2^n)$, because if we assume it for some $k$, then we obtain: $\left(\frac{3}{2}\right)^n=k+o(1)$, which is impossible, as $\left(\frac{3}{2}\right)^n \to \infty$.


Why is the target function minimized at (0,0) if I can get to a negative number?

Is easy to prove that $(0,0)$ is the maximum of your suggested target function, so it may be an errata of your text.

Your second question is way more interesting, the answer is no, if you change your target function to another linear function the maximum or minimum may change, suppose you change your target function to $x+y$, the minimum now is $(0,0)$, previously it was $(1,1)$.

However, as you suggested in the comments, if you only change your function by a positive scaling factor $a$, the maximum/minimum remain the same. This is easy to prove as
$$\alpha\leq \beta\iff a\alpha\leq a\beta$$
holds (I leave the details to you).

In general, there are branches of linear programming called "postoptimization" and "sensitivity analysis" in which your second question is studied in detail, for example, describing algorithms to obtain an optimal solution of the same problem for various target functions in almost the same running time of solving just one problem.


Increment and Decrement on binary semaphores when their values are $1$ and $0$ respectively?

A binary semaphore has the wait() and the signal() method. The one which causes a process to stop is the wait() method, while the one that increments the counter x in the semaphore is signal(). If signal is called when x=1, then the call is just ignored because the queue of blocked processes is empty, and x has already its maximum value. The process that called signal() doesn't block.


As @D.W. is suggesting, you can use the binary search technique which takes $O(\log n)$ time, where $n$ is the number of elements in the list.
Furthermore, if you want to know the corresponding period, there are many ways to it.
For example, You can make a separate array of periods and then perform a binary search on it.

Furthermore, you can improve the query time to $O(1)$ by maintaining an array of size 1440 = 24x60 as follows:
The $i^{th}$ entry of the array corresponds to the time $a:b$ where $a = i /60$ and $b = i \mod 60$. And, the value at $i^{th}$ entry is $1$ if time $a:b$ is in the list else it is $0$. Therefore, you can check in $O(1)$ time if an entry exist in the array.
To know the period in $O(1)$ time, you can maintain additional information in the array about the period in which the time lies. For example: an $i^{th}$ entry lies in $2^{nd}$ period. So basically it would be a two-dimensional array.


How get the permutation of two lists but the elements of each list remain in the same order?

Generate a string chi with len(lst1) 0s and len(lst2) 1s, e.g. for lst1 = [x, y] and lst2 = [a, b, c], you generate chi = [0, 0, 1, 1, 1].  Then you shuffle chi to obtain your "characteristic vector".  This new list will dictate the order in which to output elements from lst1 and lst2.

I hope this Python program speaks for itself:

from random import shuffle

def permutation(lst1, lst2, chi):
    idx1 = 0
    idx2 = 0
    for i in range(len(lst1) + len(lst2)):
        if chi[i] == '0':
            yield lst1[idx1]
            idx1 += 1
        else:
            yield lst2[idx2]
            idx2 += 1

lst1 = 'xy'
lst2 = 'abc'

chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))

Outputs:

11001
abxyc

10011
axybc

00111
xyabc


Multiple Variables in Asymptotic Notation

Suppose that we consider $f(n,m) = 1$ and $g(n,m) = n$ as functions on $[0,\infty)^2$. Assume, for the sake of contradiction, that $f(n,m) = O(g(n,m))$. According to the definition, there exist $M,C>0$ such that $|f(n,m)| \leq C|g(n,m)|$ whenever $\max(n,m) \geq M$. In particular, this should hold for $(n,m)=(0,M)$, yet in this case $|f(n,m)| > 1 > 0 = C|g(n,m)|$.
The problem disappears if the domain is $[1,\infty)^2$. Indeed, in this case we can take $M=C=1$, since $g(n,m) = n \geq 1 = f(n,m)$ for all $n,m \in [1,\infty)^2$.
Perhaps the problem is with unpacking the definition. According to the Wikipedia definition, $f(\vec{x}) = O(g(\vec{x}))$ if there exist $M,C>0$ such that the following holds:

If $x_i \geq M$ for some $i$, then $|f(\vec{x})| \leq C|g(\vec{x})|$.

Equivalently,

If $\max(\vec{x}) \geq M$, then $|f(\vec{x})| \leq C|g(\vec{x})|$.

It should be noted that this definition is not standard, and one could think of other definitions. Two particularly natural alternatives are (i) requiring all entries of $\vec{x}$ to be large, and (ii) requiring the inequality $|f(\vec{x})| \leq C|g(\vec{x})|$ to hold for all $\vec{x}$.
(The second option is related to the fact that for functions $f,g\colon \mathbb{N} \to \mathbb{N}_{>0}$, the usual definition of $f=O(g)$, which is a special of the definition above, is equivalent to a definition which holds for all $n \in \mathbb{N}$.)


I have an idea and will be happy to know if it is correct, or can be corrected.

Consider the integer linear program:

\begin{align}
\text{maximize} && \sum_{j\in Y} y_j - \sum_{i\in X} x_i
\\
\text{subject to} && y_j - x_i \leq 0 && \forall (i,j)\in E
\\
&& 0\leq x_i \leq 1,~~ 0\leq y_j \leq 1 && \forall i\in X, j\in Y
\\
&& x_i\in \mathbb{Z},~~ y_j\in\mathbb{Z} && \forall i\in X, j\in Y
\end{align}
In this program, there is a variable $x_i$ for each node $i$ in $X$, and a variable $y_j$ for each node $j$ in $Y$.
Let $X'$ be the subset of $X$ defined by $\{i\in X: x_i=1\}$, and $Y'$ the subset of $Y$ defined by  $\{j\in Y: y_j=1\}$.

The constraints $y_j - x_i \leq 0$ ensure that, if some vertex $j$ is in $Y'$, then all its neighbors are in $X'$, so $X'\supseteq N(Y')$.
The objective is to maximize the difference $|Y'|-|X'|$. If the optimal solution is at least 0, then $|Y'|\geq |X'| \geq |N(Y')|$, so $Y'$ is the required set. On the other hand, if the optimal solution is negative, there is no such set.

In general, integer linear programs are hard to solve. But in this case, the matrix of constraints is Totally unimodular. It satisfies the Hoffman-Gale conditions: every entry in the matrix is one of $+1, 0, -1$; every row in the matrix contains at most two nonzero entries; and if there are two nonzero entries, they have opposite signs. Therefore, we can solve the LP without the integrality constraints, and we are guaranteed to get an integral solution which gives us $Y'$.

The only problem is that the above LP does not guarantee that $Y'$ is non-empty. Adding a constraint such as $\sum_{j\in Y} y_j\geq 1$ would invalidate the argument of total-unimodularity. A possible solution is to solve $|Y|$ different linear programs: for each vertex $j\in Y$, solve the LP with the constraint $0\leq y_j \leq 1$ replaced with the constraint $y_j = 1$. If for some $j\in Y$ the objective is at least 0, we have found a non-empty $Y'$ as required. Otherwise, such $Y'$ does not exist.


Let us reduce direct connectivity to CYCLE. We are given a directed graph $G$ and two vertices $s,t$. Suppose that $G$ contains $n$ vertices. We create $n$ copies of the vertices of $G$. For each edge $x \to y$ in $G$, we add an edge from the $i$th copy of $x$ to the $(i+1)$th copy of $y$. We also add an edge from the $n$th copy of $t$ to the first copy of $s$. The new graph contains a cycle iff $t$ is reachable from $s$ in $G$.

We can construct the new graph from the original graph in logspace. Hence this is a logspace reduction, which shows that CYCLE is NL-hard.


Subset sum problem, given that a valid subset exists

This problem is as hard as the primary subset sum problem.

Suppose you have a polynomial time algorithm (say the time with input size $n$ is bounded by a polynomial $f(n)$) for this problem, then for any instance of size $n$ of the primary subset sum problem, you can run this algorithm directly with at most $f(n)$ time. If the instance indeed has a solution, this algorithm will return a valid solution. Otherwise, this algorithm will return nothing, a meaningless string, or a wrong solution, etc. Anyway, the algorithm returns a valid solution if and only if the instance has a valid solution, and you can check in polynomial time whether this algorithm returns a valid solution. This results in a polynomial time algorithm for the primary subset sum problem.


How to solve for the precondition give a postcondtion that must satisfy two conditions

The rules for $wp$ are straightforward for non-loops:

$$wp(c_1 ; c_2, V) = wp(c_1, wp(c_2, V))$$
$$wp(x := e ; V) = V\left[x \mapsto e\right]$$

Plugging in the original values, you need to compute

$$
wp(a := i + 2; i := i + 1, (a = 7) \wedge (i = 5))
$$

The first rule applies here, giving

$$
wp(a := i + 2, wp(i := i + 1, (a = 7) \wedge (i = 5)))
$$

In the second $wp$ expression, the second rule applies, giving

$$
wp(a := i + 2, (a = 7) \wedge (i + 1 = 5))
$$

Now the second rule applies again to the remaining $wp$:

$$
((i + 2) = 7) \wedge (i + 1 = 5)
$$

Now, you just need to know that the above is always false, regardless of the value of $i$. There are various automatic approaches to do this (since these are linear equations, you could use the simplex method). In this case, since they're so simple, you could just normalize your equations into $i = constant$:

$$(i = 7 - 2) \wedge (i = 5 - 1)$$

Knowing $7 - 2$ and $5 -1$ are constant expressions, you can get
$$i = 5 \wedge i = 4$$
which would imply
$$4 = 5$$
which is always false, so the original statement must be always false.


Proof that uniform circuit families can efficiently simulate a Turing Machine

Here is the basic idea. We'll take P as an example.

Given a Turing machine running in polynomial time, we construct, for each input length, a layered circuit in which each circuit represents the current configuration of the Turing machine:

For each cell, the contents of the cell.
For each cell, whether the head is there.
The current state of the machine.

The number of layers is the same as the polynomial upper bound on the running time, and the width of each layer (number of cells) is the maximum space used by the machine.

The initial layer is initialized directly from the input. Each other layer is constructed from the preceding layer (using the convention that once the machine halts, its configuration remains static). Finally, the output is extracted from the last layer. The construction is uniform, as the description hopefully makes clear.

This shows that you can convert Turing machines running in time $T(n)$ and space $S(n)$ to uniform circuits of size $O(T(n)S(n))$. This can likely be improved.


Suppose $T(n,d) = 2T(n/2,d) + T(n,d-1) + dn$, that $T(1,d) = d$, that $T(n,1) = n\log n$, and that $n$ is a power of $2$. Then
$$
T(n,d) = dn\log n + T(n,d-1) + 2T(n/2,d-1) + \dots + nT(1,d-1).
$$
In particular,
$$
\begin{align*}
T(n,2) &= 2n\log n + n\sum_{i=0}^{\log n} i \\ &\approx
2n\log n + \tfrac{1}{2}n\log^2n, \\
T(n,3) &\approx 3n\log n + 2n\sum_{i=0}^{\log n} i + \tfrac{1}{2}n \sum_{i=0}^{\log n} i^2 \\ &\approx
3 n\log n + n\log^2 n + \tfrac{1}{6} \log^3 n,
\end{align*}
$$
and so on. More generally, we can think of $T(n,d)$ as a degree $d$ polynomial of the form $n\sum_{i=1}^d c_{d,i} \log^d n$. The coefficients are given by $c_{d,1} = d$ and $c_{d,i+1} = c_{d,i}/(i+1)$. Unrolling the recurrence, we obtain
$$
T(n,d) \approx n \sum_{i=1}^d \frac{d+1-i}{i!} \log^d n.
$$
In particular,
$$ T(n,d) = \frac{1}{d!} n\log^d n + O(n\log^{d-1} n). $$


Prominent applications not suited for distributed computing

Most of the old (de)compression algorithms were not suitable for parallel or distributed computing. The variable length nature prevented decompressing later parts of the input stream before decompression of earlier parts was finished. And adaptive dictionaries often prevented compressing later parts of the input stream before compression of earlier parts was finished. Both issues can probably be avoided at reasonable cost, and maybe some modern (de)compression algorithms actually do this.
Nearly all cryptographic hashes will not be suitable for speedup by distributed computing. Any feature which could be exploited to make distributed speedup possible also risks being exploitable to weaken the cryptographic security of the hash.
Many popular black box opimization algorithms are not suitable for distributed computing in their basic form. Especially local optimization algorithms like the Nelder–Mead method or the Broyden–Fletcher–Goldfarb–Shanno algorithm are inherently sequential. But even more global algorithms like simulated annealing are local (and  sequential) in their basic form, even so it is possible to develop parallel forms for them.


The more usual (and slightly stronger) formulation of the exponential time hypothesis is that there is $\epsilon > 0$ such that solving 3SAT requires time $\Omega(2^{\epsilon n})$ (see, for example, Abboud, Backurs and Williams), where $n$ is the number of variables.

The strong exponential time hypothesis states that for each $\epsilon > 0$ there exists $k\ge3$ such that solving $k$SAT requires time $\Omega(2^{(1-\epsilon)n})$ (again, see the paper mentioned above).

Showing that SETH implies ETH isn't trivial. The idea is to show that $k$SAT reduces to sparse $k$SAT, which is $k$SAT restricted to instances with $O(n)$ clauses. Such instances can be coded as 3SAT instances with $O(n)$ variables. Therefore if we can solve 3SAT in time $O(2^{\gamma n})$ for every $\gamma>0$, then we can also solve $k$SAT in time $O(2^{\gamma n})$ for every $\gamma>0$. For the details, consult Impagliazzo, Paturi and Zane, Which problems Have strongly exponential Complexity?.


Is $2^{1+\sqrt{mn}}$ an upper bound for the size of the DFA resulting from the determinisation of n DFAs of size m

No.  Asymptotically, the size can be as large as $\sim m^n$.

Let $p_1,\dots,p_n$ denote the $n$ largest prime numbers that are at most $m$.  Let

$$L_i = \{x : x \not\equiv 0 \pmod{p_i}\},$$

where we assume the number $x$ is expressed in unary.  Then $L = L_1 \cup \dots \cup L_n$ has the form

$$L = \{x : x \not\equiv 0 \pmod q\},$$

where $q = p_1 \times \dots \times p_n$.

Note that, with this construction, each $L_i$ has a DFA of size at most $m$ (in particular, of size $p_i$).  However, the minimal DFA for $L$ has size $q$, which is close to $m^n$.  In particular, the size of the minimal DFA for $L$ is asymptotically larger than $2^{1 + \sqrt{mn}}$ (as a function of $n$, treating $m$ as fixed).


Search for range in continuous function satisfying some condition

Let $x_1,x_2,\dots,x_n$ denote the $x$-values where the two curves intersect; you say you know how to find these.  Let's add $x_0=-\infty$ and $x_{n+1}=+\infty$.  Then in each interval $[x_i,x_{i+1}]$, either the red curve is consistently above the green curve or vice versa, so label that interval with the color of the curve that is on top.  This is easy to do by picking an arbitrary $x$-value in $(x_i,x_{i+1})$ evaluating the height of both points at that point.
Now your problem reduces to the following: find $x_i,x_j$ that maximize $x_j-x_i$, such that all of the intervals $[x_i,x_{i+1}],[x_{i+1},x_{i+2}],\dots,[x_{j-1},x_j]$ are labelled red.
This problem can be solved in a straightforward way, in linear time.  Iterate through $j:=1,2,\dots,$, scanning from left-to-right, keeping track of the smallest $i$ such that all intervals between $x_i..x_j$ are labelled red.  Thus, when you encounter a red interval $[x_{j-1},x_j]$, you do nothing; when you encounter a green interval $[x_{j-1},x_j]$, you reset $i := j$.  Keep track of the longest range you've found so far as you do the linear scan.


Construct initial marking for marked graph so that the graph is live and safe

Why can't you find a live and safe marking?

Number the transitions from left to right $t_1,t_2,t_3,t_4,t_5$ and the places from left to right $p_1, \ldots, p_{12}$,

We need to find a firing sequence that is possible, fires all transitions at least once, has net effect zero, and never produces an unsafe marking.

It doesn't matter where we start: if the net is live, we can "cycle" any such firing sequence by moving its starting transition to the end or vice versa.

So we may as well start with the "thick" transition in the middle, $t_2$. For it to be enabled, its input places must be marked. For the firing sequence we'll construct to be safe, its output places must be empty. So let's fire it. Now, its input places are empty, and its output places are marked. We must now be able to fire $t_3,t_4,t_5$. This is possible iff exactly one of $p_9,p_{10},p_{12}$ was (and is) marked. We can then fire all three in a row. So let's pick $p_9$ as the one that was set. Then, after firing $t_2$, $t_3$ will be able to fire; firing it will enable $t_5$; firing that will enable $t_4$; firing that will put the token back into $p_9$.

After firing $t_3$, $p_4$ will be set, enabling $t_1$. The firing of $t_1$ and of $t_3,t_5,t_6$ are independent: they don't influence each other.

Having fired both $t_1$ and $t_3,t_5,t_6$, we're back at our initial marking. The net doesn't actually give us a choice: we must fire $t_3$ first, and then both $t_1$ and the sequence $t_5,t_6$ to enable $t_2$, and no alternative firing sequences exist.

So with the initial marking $p_2,p_6,p_8,p_9$, the only possible firing sequences of this net are given by the regular language $(t_2t_3(t_1|t_5t_4))^* = (t_2t_3(t_1t_5t_4 \cup t_5t_1t_4 \cup t_5t_4t_1))^*$. All of the reachable markings are safe.

By the way the example is drawn, there appears to be theory behind this example. This marked graph is special in that it is composed from three plain cycles (the ovals) by fusing some of their transitions. I'll bet Reisig's book proves that all marked graphs constructed in such a way are live and safe.

Your second question: what if we remove the place marked in yellow? Well, this only removes a constraint on the firing sequences: all existing firing sequences will continue to exist, but new ones may arise.

Indeed: after $t_4$  has fired, or in the initial marking above, $t_3$ can now already fire before $t_2$. However, this is merely a relaxing of the order in which transitions are fired, and it doesn't produce any unsafe or unlive markings.
So the net remains live and safe. I suppose you'll have to prove this.

I'll guess there is another lemma in the book proving that this is true in general: that removing places from a live and safe marked graph always leaves it live and safe. I haven't read the book, so I'm not sure.


Is there a combinator that introduces brackets to a combinatory logic expression using just B?

$X=B(BBB)(BB)$ answers the first question. Indeed,

$B(BBB)(BB)abcdef=BBB(BBa)bcdef=B(B(BBa))bcdef=B(BBa)(bc)def=BBa(bcd)ef=B(a(bcd))ef=a(bcd)(ef).$

For the second question, yes, this may be done in general. Here's a rough proof: if we have $Xabc\ldots xyz = (\textrm{expr})(yz)$, this becomes $Xabc\ldots xyz=B(\textrm{expr})yz$, so $Xabc\ldots x = B(\textrm{expr})$. If $(yz)$ is nested inside other brackets, like, for example, $Xabc\ldots xyz=(\textrm{expr})(x(yz))$, we get $Xabc\ldots xyz=B(\textrm{expr})x(yz)=B(B(\textrm{expr})x)yz$, and again we may then consider just $Xabc\ldots x=B(B(\textrm{expr})x)$. We may then do a further step: $Xabc\ldots x=B(B(\textrm{expr})wx)=BB(B(\textrm{expr}))x$, which means that $Xabc\ldots w=BB(B(\textrm{expr}))$. Continuing doing this, we end up with just $X$ on the left hand side and an expression involving (possibly bracketed) $B$'s on the right hand side.