How can I simplify the following Product of Sums: ab+ac'+a'b'+a'c+b'c'+bc?

Update It turns out that your initial simplification was incorrect. Here's a correct one. First, observe that
$$
(p+q)(p+q') = pp+pq'+pq+qq'=p +p(q'+q)+0 = p+p1=p
$$
so for the first two terms in your POS we have
$$
((a+c)+b)((a+c)+b') = a+c
$$
and, similarly, for the last two terms we have
$$
((a'+b)+c)((a'+b)+c') = a'+b
$$
so the full product simplifies to
$$
(a+c)(a'+b)\quad\text{ or, if you prefer }\quad ab+a'c+bc
$$
At this stage you haven't simplified this as much as possible. If you construct truth tables, you'll discover that $ab+a'c+bc=ab+a'c$, in other words the $bc$ term isn't needed here. It isn't obvious how one would discover that unless you've seen Karnaugh maps, for instance.


The class #P consists of those functions $f$ such that there is a polytime relation $R$ and a polynomial bound $p$ satisfying
$$
 f(x) = |\{ |y| < p(|x|) : R(x,y) \}|.
$$
In words, if we think of $y$ as a "witness" for $x$, then $f(x)$ should count the number of witnesses for $x$. For example, if $R(x,y)$ is the relation that $y$ is a cycle in the graph $x$, then (if you're careful enough) $f(x)$ will count the number of cycles in the graph $x$. You need to be a bit careful to count each cycle exactly once.


Why is quiescent consistency compositional, but sequential consistency is not

Sorry for the late reply, but I've just found the question (questions, indeed). I am studying concurrency as well and I'll try to share some ideas with you.

First, let's start with sequential consistency. A model has this property if operations appear to take effect in program order. In other words, the order in which lines of code are executed is the one specified in the source file. This prerequisite is thread-specific: operations involving different threads are unrelated by the program order. So, the property grants the following: operations issued by the same thread are executed in the same order specified by the thread source code. Operations issued by different threads can happen in any order. This prerequisite may seem obvious, but it is not always the case (compiler optimizations may change the order in which operations are issued, thus making the program order different from the source).

Your example is right, but let me give you some others. Consider this program P1 (I'll tag each line for an easy reference):

   int x = 1;

   void ThreadA()
   {
A1:    x = x * 2;
A3:    int a = x;
   }

   void ThreadB()
   {
B2:    x = 20;
   }

Is there a sequential execution in which, at the end, a = 40? Yes: B2, A1, A3.

B2 and A1 can be executed in any order (they belong to different threads). A1 is executed before A3 (program order = source code order).

Now consider this program P2:

   int y = 1;

   void ThreadA()
   {
A2:    y = 40;
   }

   void ThreadB()
   {
B1:    y = y / 2;
B3:    int b = y;
   }

Is there a sequential execution in which, at the end, b = 20? Yes: A2, B1, B3.

What about composition? Let's compose P1 and P2. We get P1∘P2:

   int x = 1;
   int y = 1;

   void ThreadA()
   {
A1:    x = x * 2;
A2:    y = 40;
A3:    int a = x;
   }

   void ThreadB()
   {
B1:    y = y / 2;
B2:    x = 20;
B3:    int b = y;
   }

If sequential consistency were compositional, then there should be an execution in which, at the end, a = 40 and b = 20. Is this the case? No. Let's give a formal proof oh why it can't be the case. I'll write "o1 → o2" to say that the operation o1 must be executed before operation o2.

In P1∘P2, due to sequential consistency, the following must holds: A1 -> A2 and B1 -> B2 (per-thread program order). In order to get a = 40 also B2 -> A1 must hold. In order to get b = 20 also A2 -> B1 must hold. Can you see the precedence chain? A1 -> A2 -> B1 -> B2 -> A1 -> ...

P1 and P2 were sequentially consistent, but their composition P1∘P2 was not.
Sequential consistency is not compositional. The example you provided was not tricky enough to show this fact.

Now, let's consider quiescent consistency. It's difficult for me to explain this property without using the object-oriented paradigm. In fact, quiescent consistency can be easily understood in terms of pending method calls on objects. Nevertheless, I'll try to stick with the imperative paradigm (pending method calls become functions started but not completed, objects become variables involved in functions).

A function call is composed by an invocation and a response. A function is pending if it has been invoked by a thread but it has not returned a response yet to such thread. A period of quiescence for a variable is a time interval in which there are no pending function calls (by any thread) operating on it.
A model has the quiescent consistency property if function calls operating on the same variable and separated by a period of quiescence appear to take effect in their real-time order (the one specified by source code). From the converse point of view, the definition states that operations on the same variable executed by functions called concurrently by different threads (not separated by quiescence) can happen in any order.

I've tried for many hours to design a meaningful example using only read-write operations to show you the difference between quiescent and sequential consistency, but I didn't succeed. Let me use another example involving sets. I will use a bit vector to keep track of which integers (from 0 to 4) are in the set:

   int set[5] = {0, 0, 0, 0, 0};  // 0 if i-th item is absent, 1 otherwise

   void add(int number) {
L1:    set[number] = 1;
L2:    temp foo = set[0];
   }

   void remove(int number) {
       set[number] = 0;
   }

   int contains(int number) {
       return set[number] == 1;
   }

   void ThreadA()
   {
A1:    add(1);
   }

   void ThreadB()
   {
B1:    add(2);
B2:    remove(2);
B3:    int res = contains(2);
   }

Is there a sequential execution in which, at the end, res = 1? No: due to sequential consistency B1 -> B2 and B2 -> B3, so B1 -> B3. So, remove(2) is always executed after add(2) and contains(2) will always returns 0.

Is there a quiescent execution in which, at the end, res = 1? Yes! Consider this execution:

Thread A invokes add(1) at A1.

Thread A executes L1 (but not L2). // since there is a pending call on the set, now Thread B is free to execute B2 before B1 because these calls involve the set as well

Thread B calls B2.  // invocation + response

Thread B calls B1.  // invocation + response

Thread A executes L2 and add(1) responds. // now there is quiescence on the set

Thread B executes B3.  // invocation + response

Now res = 1.

Unfortunately, I still can't answer the latest question on why quiescent consistency is compositional: I found your question while I was looking for this exact answer indeed. If I come up with something I'll let you know.

For a good reading on the topic have a look at chapter 3.3 of the book "The Art of Multiprocessor Programming" by Herlihy and Shavit.

EDIT: I've just found a great page explaining why quiescent consistency is compositional. And this is another very good reading!

EDIT2: Fixed little error in the sequential consistency composability example.


Do not understand a concept in analysis of open-address hashing

For any $i$, $q_i = p_i + p_{i+1} + p_{i+2} + \dots$.  Now look at $\sum_{i\geq 1}q_i$ and how many times each $p_i$ occurs.  $p_1$ occurs only in $q_1$; $p_2$ occurs in $q_1$ and $q_2$; and, in general, $p_i$ occurs only in $q_1,\dots, q_i$.  In other words, each $p_i$ occurs $i$ times in the sum of the $q_i$s.


Why is this implementation of the hash function bad?

Because

two sequences with the same acids in different order (e.g. two acids switch places) will have the same hash code;

this will only produce numbers from 0 to your large simple modulus instead of all $2^{32}$ or $2^{64}$ possibilities.


What textbooks includes explanations of advanced data structures found commonly in competitive programming?

Here are two books written especially for competitive programming:

"Guide to Competitive Programming", Antti Laaksonen:

The book is based on the book "Competitive Programmer's Handbook" by
the same author, which was already really good. This handbook is
still available for free on the author's
website. The commercial version is more comprehensive and contains more topics.
"Competitive Programming 3", by Steven Halim and Felix Halim:

Pretty much the classic book for learning competitive programming.
Maybe a little bit dated.


Is the type inference here really complicated?

This is a common limitation of type inferencing and it has to do with the distinction between parameters and results of a function. Generally type inferencing is done strictly with the parameters passed to a function. Consider just the expression:

ImmutableMap.builder().build();

This has to be a valid expression due to how the language works. This means the type inferencing has to work from this expression alone. There is of course nothing in this expression which reveals what type you are expecting, thus it cannot compile (the type of the expression is not known).

It really isn't a question of how complicated the inferencing is, but rather a question of the fundamental structure of the language. It is possible to design a language where the return type becomes an implicit parameter to a function. However, this starts to create a loop in the typing logic in languages where variables can be auto-type (like C++).

The reason this happens is because of how the syntax trees for such languages are built (this may be only in theory as the compiler may not match exactly). When you have an expression like the above you have a tree that might look kind something like this:

- Assignment
    - LValue: Map<String, Number> m
    - RValue: FunctionCall(
          FunctionCall( ImmutableMap, builder ),
          build
      )

In such languages the "RValue" is essentially an expression -- where expressons are something that resolves to a value. These are processed on their own, and thus limited to the variables and sub-expressions which occur in them. Type inferencing doesn't usually go up tree, thus the FunctionCall has no knowledge it is part of the Assignment tree and thus no knowledge of the "LValue" (what it is being assigned to).

This is the traditional way to process languages (it even applies to formal languages like lambda calculus). Languages don't have to work this way, but there it is the most commonly understood way parsing works. You can certainly make a syntax tree which forwards type information in an assignment, but that leads to the pitfall I mentioned if the "LValue" is auto-typed. If you attempt to allow both sides to infere their type you start entering a constraint based typed system (which again, is possible and I have worked on one before).

One practical way of doing this in some languages is to pass the return variables by reference (which isn't really possible in Java). In C++ I often do this where the function requires its return type. Instead of doing:

var = someFunc(...);

I'll do:

someFunc( var, ... );

And this allows the type of "var" to be known by the function (in this case for template resolution).


Algorithm to compute average length of a simple path

I guess you already know that a polynomial algorithm for counting the number of simple paths between two nodes would imply P=NP, this result is due to Valiant (The complexity of enumeration and reliability problems, 1979).
Now imagine, expecting to discover a contradiction, that you could compute $\text{avg}(G, u, v)$ in polynomial time.
Let $G+l$ be the graph resulting from adding a simple path of length $l$ between $u$ and $v$ in $G$. This new path is made of $l-1$ new nodes and it does not interfere with any previous path from $u$ to $v$, provided $l \geq 2$.
Then, $\text{avg}(G+3,u,v) - \text{avg}(G+2,u,v)$ = $1/(\#\text{Paths}(G,u,v)+1)$, from which you can get $\#\text{Paths}(G,u,v)$ in polynomial time. But we know this cannot be expected to be done in polynomial time, a contradiction.


Can the lambda functions in Church numbers be swapped?

Sure, except it's going to be more painful to use the numbers with the swapped arguments because in many cases you want to apply a Church numeral only to the argument $s$ and leave $z$ specified. Thus, instead of writing $c_n \, e$ you will have to write $\lambda z . c'_n \, z \, e$ whenever that happens.


The conjecture is true, and the proof strategy listed there can be made to work.

Let $s = (s_1,\dots,s_n)$ be a satisfying assignment for the variables that makes all of the constraints hold.  We'll write $E(s)$ for the result of evaluating the expression $E$ with the variables $S_i$ set to $s_i$.  In the following, define $U$ by the procedure listed in the question:  let $E_1 \ne \emptyset$, ..., $E_k \ne \emptyset$ be the constraints of second type; pick any element of $E_1(s) \cup \cdots \cup E_k(s)$, call it $x$; add $x$ to $U$; delete all of the constraints $E_i \ne \emptyset$ such that $x \in E_i$; and repeat.  Define $s'_i = s_i \cap U$.

Now I claim that $s'_1,\dots,s'_n$ is also a satisfying assignment that makes all of the constraints hold.

First, let's consider the constraints of the form $E = \emptyset$.  I claim that if $E(s) = \emptyset$, then $E(s') = \emptyset$.  In particular, I claim that $E(s) \cap U = E(s') \cap U$ for all set expressions $E$.  The proof is by recursion: by definition of $s'$, we have $S_i(s) \cap U = S_i(s') \cap U$; also if $t \cap U = t' \cap U$, then $\overline{t} \cap U = \overline{t'} \cap U$; and if $t_1 \cap U = t'_1 \cap U$ and $t_2 \cap U = t'_2 \cap U$, then $(t_1 \cap t_2) \cap U = (t'_1 \cap t'_2) \cap U$.  So this means that $s'$ satisfies all of the constraints of the first type (all of the constraints of the form $E = \emptyset$), since $s$ does.

Next, consider the constraints of the form $E \ne \emptyset$.  We know $E(s) \ne \emptyset$.  Therefore, there was a step in the iterative definition of $U$ when we chose some element $x \in E(s)$ and added it to $U$.  We proved earlier that $E(s) \cap U = E(s') \cap U$.  Since $x \in E(s)$ and $x \in U$, it follows that $x \in E(s') \cap U$, and thus $E(s') \ne \emptyset$.  This means that $s'$ satisfies all of the constraints of the second type, too.

We've shown that if there is any satisfying assignment for all constraints, then there exists a satisfying assignment where all sets are subsets of $U$.  This completes the proof of the conjecture.


Worst-Case Complexity of Quantifiers in Thompson's Construction

The point of a finite automaton is that the number of possible states that it can be in is finite. Specifically, if a NFA has $n$ states, then at any point in the input string, you can be in at most $n$ states at the same time.
The first observation is that you can precompute $\epsilon$ transitions. Define $\mathbf{closure} : Q \rightarrow 2^Q$ to be a function that takes a state and returns the state which are reachable using zero or more $\epsilon$ transitions. Then from this, we can compute an "extended" transition function $\delta^{*} : Q \times \Sigma \rightarrow 2^Q$, which maps a state and an input symbol to the set of states that are reachable from it, then you can use this algorithm to recognise a string:

Given the start state $s$, set $W := \mathbf{closure}(s)$. (Again, this can be precomputed.)
For each input symbol $a$, set $W := \cup_{s \in W}\,\delta^{*}(w, a)$.
Accept if there is a final state in $W$.

This algorithm looks like it takes $O(k^2n)$ space in the worst case, namely, the space to represent $\delta^{*}$. And the inner loop operation, $\cup_{s \in W}\,\delta^{*}(w, a)$, looks like it should take $O(k^2)$ time in the worst case.
This isn't quite true in the word RAM model, however. Consider that the space needed to store a set of states can be measured in bits; since $k$ is known in advance, the sets like $W$ and the codomain of $\delta^{*}$ can be represented as a bit vector, and set union can be a logical or. So in the word RAM model, the inner loop will actually take $O\left(\frac{k^2}{\log k}\right)$ time in practice.
Having said that, as you correctly guessed, Thompson's construction is not ideal for this use case. It has many advantages (not the least of which is that the space is linear in the size of the input regular expression), but the efficiency of its "obvious" recogniser algorithm is not one of them. As you rightly suspected, it produces a lot of unnecessary states that we can get rid of.
One obvious point is that it's trivial to optimise common "leaf" cases. For example, Thompson's algorithm will turn $a^*$ into a NFA with 4 states, but it should be obvious that you "need" fewer than that, and the complexity of the construction for $E^*$ is only needed because $E$ may be more complex.
Following this reasoning, it is possible, without too much difficulty, to construct an NFA with the following properties:

The number of states is equal to the number of alphabet symbols in the original regular expression (in some formulations, plus one for the start state, but here we will use a set of start states). That is, $a^*a^*ab$ should require exactly 4 states.
There are no $\epsilon$ transitions.
Every transition into a state $s$ has the same label.

Property 1 gives an accurate bound on the number of states which is computable at parse time.
Property 3 means that you can label states with alphabet symbols instead of transitions. Together with property 2, the transition function $\delta$ doesn't need to consider input symbols.
We define a normal NFA (NNFA) to be a 6-tuple $(\Sigma,Q,\delta,I,F,A)$ where:

$\Sigma$ is the alphabet.
$Q$ is a set of states.
$\delta : Q \rightarrow 2^Q$ (or, alternatively, $\delta \subseteq Q \times Q$) is the transition function.
$I \subseteq Q$ is the set of initial states.
$F \subseteq Q$ is the set of final states.
$A : Q \rightarrow \Sigma$ is a function which assigns labels to states.

Then the inner loop of the recogniser algorithm is to set:
$$W := \left\{ s\,|\,w \in W, s \in \delta(w), A(s) = \alpha\right\}$$
This should give you a lot of ideas as to how to implement this in data structures. For example, consider representing $\delta$ as a bit matrix and $A$ as a map from $\Sigma$ to a bit vector, where $A(\alpha)$ is the set of states $q$ which have the label $\alpha$. Then the inner loop becomes a bunch of bit vector unions (i.e. logical or operations) with a final bit vector intersection (i.e. a logical and). In the word RAM model, this is extremely efficient.
As to how to construct a NNFA, it's worth trying to come up with the idea behind it yourself, now that you know that it's possible. As a hint, start with Thompson's construction, and create a new automaton where the "new" states are the $\mathbf{closure}$ of every state which has a terminal transition coming into it. You can then think about how you could compute that automaton without explicitly constructing Thompson's automaton to begin with.
Once you've tried it, the best explanation that I've seen is Chang's PhD thesis. But here's the amazing part: Chang then goes on to give a compressed representation for a NNFA which takes $O(k)$ space, with a construction algorithm that uses $O(k)$ auxiliary space and $O(r)$ time where $r$ is (in some sense) the "size" of the input regular expression.
That effectively answers your question. There is indeed an algorithm which recognises regular expressions, which stores the automaton in $O(k)$ space, where $k$ is linear in the size of the input regular expression, and which takes $O(nk)$ time to recognise a string.


Since you're not sure where you read it, is it possible you are misremembering slightly what the result was?

In a B+ tree, we require that every node has between $n/2$ and $n$ children.  In other words, every node is required to have at least $\lceil n/2 \rceil$ children.  This means that any tree of depth $d$ where all leaves are at depth $d$ must have at least $\lceil n/2 \rceil^d$ leaf nodes.  Thus, any such tree must have depth at most $\lceil \log_{\lceil n/2 \rceil} L \rceil$, where $L$ is the number of leaf nodes.  Perhaps this is what you read.

Note that the number of key value is related  to the number of leaf nodes: $\lceil b/2 \rceil -1 \le L/K \le b-1$.  This would let you get a similar result in terms of $K$, for a full tree with all leaves at the same level.

Detail: Here I have ignored that the root is usually allowed to have as few as 2 children.  This has only a small effect on the answer.


Auto-generating a class hierarchy/inheritance tree from a data set of objects with properties

It looks like your problem can be solved by transitive reduction followed by some post-processing.

Build a directed graph, with one vertex per "object shape".  Draw an edge $u \to v$ if $u$ contains all of the fields of $v$ (possibly plus some more).  This should form a dag.  Now compute the transitive reduction of this dag.  The result should be a tree (or forest of trees).

This almost gives you the desired solution.  The one thing it doesn't do is invent new abstract base classes that weren't already present in the input.  So, we can do some post-processing to create them.  First, if the result has more than one tree, we'll create a new root (an abstract base class) that is a parent of all of those trees.  The result is a (directed) tree.

Examine each node that has more than two children.  This is the only place where we need to create new abstract base classes.  Let $S$ denote the set of children.  Now you have some choices about how you want to form a hierarchy based for $S$; there are multiple possibilities that are all consistent with the input data, and the question doesn't specify any criteria for choosing among them.  So, I'll have you let you decide on how you want to select among them.

What's the running time?  Constructing the graph and computing the transitive reduction can be done in $O(n^3)$ time, where $n$ is the number of different object shapes present in the input.   (In fact, given the structure of the input, in this particular case it can actually be done in $O(n^2)$ time, but maybe that isn't important, since I suspect in practice $n$ might be fairly small.)  The post-processing can also be done in $O(n^3)$ time (probably less if you care).  So the overall running time is at most $O(n^3)$.

Of course, we can de-duplicate the shapes in the input before doing any processing: there is no need to keep more than one object of any particular shape.  So, the running time depends only on $n$, the number of distinct shapes in the input, not on the number of objects in the input.  It's easy to do the de-duplication in linear time using a hash table.


How to show that some problem is in NP and that it's NP-complete

When performing a reduction it is important to keep in mind exactly what you are doing. In particular you are trying to reduce from a known hard problem (here subset sum, $\mathsf{SS}$) to your problem (here great subset sum, $\mathsf{GSS}$) such that yes-instances of the hard problem map to yes-instances of your problem and no-instances map to no-instances.

As mentioned in the comments, if you simply divide each number in $S$ by two (and also divide $n$ by two) you do not get an instance of $\mathsf{GSS}$; it might not be the case that $\frac{n}{2} \geq \frac{N}{2}$.

Please think about the problem a bit more before looking at the solution below.

   Let our $\mathsf{SS}$ instance be $S = \{s_1, ..., s_k\}$ with $\sum_{s_i \in S} s_i = N$ and target $n$. We construct the following $\mathsf{GSS}$ instance: $S' = \{s_1, ..., s_k, N\}$ with target $n' = N + n$. Observe that this is a $\mathsf{GSS}$ instance since $n' \geq \frac{1}{2}\sum_{s \in S'} s = N$. It remains to show that yes-instances map to yes-instances and no-instances map to no-instances. If some subset $A \subseteq S$ adds up to $n$ then $A \cup \{N\}$ adds up to $N + n$. If not then no subset of $S'$ adds up to $n'$ since $n' > N$ so this subset must contain $\{N\}$ and a subset of $S$ which adds up to $n$.


First, let us note that the number of ways to write $N$ as a sum of $S$ non-negative integers is exactly $\binom{N+S-1}{N}$. Indeed, the partition $N=x_1+\cdots+x_S$ corresponds to the string $\ast^{x_1}|\ast^{x_2}|\cdots|\ast^{x_S}$ (where $\ast^x$ means $x$ many stars), which contains $N$ stars and $S-1$ bars, and conversely any such string corresponds to a partition.

In your case you have the additional constraint that all $x_i$s are at most $N/2$. Note that at most one $x_i$ can be more than $N/2$. If $x_i > N/2$, then the number of ways to fill the rest of the $x_j$s is exactly $\binom{N-x_i+S-2}{S-1}$. Therefore the number of ways to write $N$ as a sum of $S$ non-negative integers which are at most $N/2$ is
$$
\binom{N+S-1}{S-1} - S\sum_{x=\left\lceil \frac{N+1}{2} \right\rceil}^N \binom{N-x+S-2}{S-2} =
\binom{N+S-1}{S-1} - S\sum_{y=0}^{\left\lfloor \frac{N-1}{2} \right\rfloor} \binom{y+S-2}{S-2} =
\binom{N+S-1}{S-1} - S \binom{\left\lfloor \frac{N-1}{2} \right\rfloor+S-1}{S-1}.
$$
You can calculate this closed form using $O(S)$ arithmetic operations.


$S$ contains every subtour except the tour with the depot. And for each subtour a constraint has to be added.

The meaning of $k=argmax_j\{z_{jt}\}$ has been answered in https://math.stackexchange.com/questions/1290142/explanation-of-textrmargmax-jz-jt-and-how-to-implement-it/1290178#1290178

I solved this with a callback as soon as a subtour is found.


Is it possible to reduce the number of variables in bin packing?

An integer program, or more properly an integer linear program, consists of a linear program together with integrality constraints stating that some of the variables are integers. As such, its objective function is always a linear combination of variables.

When the objective is minimization, it is admissible to have $\max$ operators (appearing positively) in the objective function. This means that there is an equivalent proper integer program. This program is obtained by introducing auxiliary variables, just as the variables $y_i$ are introduced in your example to implement $\max_j x_{ij}$.

To answer your question, it all depends on what you consider as an integer program. The standard definition only allows linear objective functions, and in this case the $y_i$ are necessary. If you also allow $\max$ operators in the objective function, then the $y_i$ are not necessary.


Pumping Lemma for regular languages proof doubt - Sipser Book

You missed what $j$ and $l$ are. Read the paragraph again. They are the two indices of the same state in the list of visited states. For example if some  automata goes from $s_1$ to $s_3$ to $s_5$ to $s_3$ to $s_7$, then you could pick $j = 2$ and $l = 4$, because both $2$nd and $4$th elements in the sequence are $s_3$.

They are always (and, assuming $n > p$, can always be) chosen different.
$y$ was defined as the substring which takes $r_j$ to $r_l$. $j \neq l$ and you need at least one symbol to change state, hence $|y| > 0$.
The substring $xy$ takes $r_1$ to $r_l$. A string of length $x$ visits $x+1$ states, so if we know that $xy$ visited $l \leq p+1$ states then $|xy| = l-1 \leq p$.


how to mapping reduce any r.e. language to the diagonal language K?

Let $A=L(M)$ be any r.e. language. We reduce $A$ to $K$ using the following reduction function $f(x)$.

Given any word $x$, construct a TM $N_x$ such that, when run on input string $y$, it ignores it, and simulates $M$ on $x$. If $M$ accepts, we make $N_x$ accept, otherwise we make $N_x$ diverge. We let $f(x) = \langle N_x \rangle$.

$f$ is clearly a total computable function. It is also simple to check that $x\in A \iff f(x)\in K$.

Note that $f(x)\in K$ means that the TM encoded by $f(x)$ halts on input $f(x)$. This means that $N_x$ halts on input $y = \langle N_x \rangle$. The value of $y$ is actually irrelevant, since $N_x$ will ignore it, and halt only when $M$ accepts $x$, i.e. when $x\in A$.

In a sense, the "trick" here was to ignore the diagonal property which is used in the definition of $K$, and just make $N_x$ halt on all inputs $y$ or diverge on all inputs $y$. In such way, we surely include the diagonal, and we simplify the reduction function $f$.

If we really wanted, it is possible to define a function $f(x)$ which produces the encoding of $N_x$, which always halts (or always diverges, if we prefer that) on any $y\neq f(x)$, and instead halts on the the diagonal $y=f(x)$ if and only if $x\in A$. Defining such $f$, however, is harder, and requires the second recursion theorem. Ignoring $y$ makes $f$ much simpler to construct.


Minimum Spanning Tree with one particular edge minimised(continued)

Run Kruskal's algorithm on the weighted graphs of all buildings as vertices and all pipes with original costs as edges with weights,  with the following modification. When we are going to select the next edge (pipe) whose weight (cost) is minimum among the available edges, we choose one among the active pipes first if there is such a pipe.

At end of the algorithm, we obtain a minimum spanning tree $T$ with weights $w_1\le\cdots w_{N-2}\le w_{N-1}=m$. The number of days needed to implement $T$ as the new active pipes, denoted $p$, is the number of pipes in $T$ that are not currently active.

With the enhancer used, the total minimal cost becomes $w_1+w_2+\cdots+w_{N-2}+s(w_{N-1})$, where $s$ is the function such that $s(w)=0$ for $w\le D$ and $s(w)=w-D$ otherwise. That formula is shown in the linked question and its answers.

Can we reduce the number of days from $p$ to $p-1$?

Claim 1. If $D\le m$, then the number of days cannot be reduced to $p-1$.

The proof of claim is left to readers as a (not immediate) exercise.

So let us run Kruskal's algorithm again from scratch, with a further modification. Immediately after we have tried selecting all pipes of cost $m$ that were active (there might be none of them), we will continue to try selecting all pipes that cost more than $m$ but no more than $D$ one by one. If it is successful at least once, that is, if such a pipe will connect two disconnected components, then we will include it in the plan and we will reduce the required days by one to $p-1$. Otherwise, the required days is $p$.


Go 45 to 65 years back in time when RAM was “core memory” - tiny magnetic rings with wires threaded between them. Core memory was not volatile.


External consistency doesn't have a fixed meaning. In this context, it has the meaning appearing in the very next sentence in the document:

  For any two transactions, $T_1$ and $T_2$ (even if on opposite sides of the globe):
  if $T_2$ starts to commit after $T_1$ finishes committing, then the timestamp for $T_2$ is greater than the timestamp for $T_1$.


Recurrence: space complexity to Tournament Method

First of all, when talking about space complexity, we need to make sure what exactly we are counting. There are two main issues:

Are we counting the space taken by the input?
How much space does a variable like mid or mml take? How much space does the return address take?

Regarding the first issue, usually we're not counting the space taken by the input; this space should be accounted for in the procedure creating the array. This convention is important in complexity theory for handling space complexity classes with small working space, and also makes practical sense.

Regarding the second issue, we actually have two kinds of variables here:

Addresses – the return address, mid, and perhaps other temporary values.
Array elements – the two components of mml and mmr.

The usual convention counts machine words rather than bits. Without explaining what exactly machine words are, it is usually assumed (and practically justified) that addresses take $O(1)$ machine words.

Regarding array elements, it depends on the type of the array. Here presumably the array elements are machine integers of machine floating points, and so they also take $O(1)$ machine words.

Having clarified these issues, let us get back to the algorithm. When analyzing the time or space complexity of an algorithm, we usually measure the complexity with respect to the input size $n$ (in machine words). In this case, we can identify the input size with the size of the array (measured in number of elements), although the input is actually a bit larger.

Suppose for simplicity that $n$ is a power of 2, say $n = 2^m$. When we trace the execution of the algorithm, we discover recursive calls for the following subarrays are made:

$A[0,2^m)$
$A[0,2^{m-1})$
$A[0,2^{m-2})$
$\ldots$
$A[0,1)$

(Here $A[a,b)$ consists of the elements $A[a]$ up to $A[b-1]$.) After the call on $A[0,1)$ executes, we get another call to $A[1,2)$, and so on and so forth.

At the particular point in time illustrated in the call stack above, the call stack is $m+1$ levels deep, and so the stack consists of $\Theta(m)$ machine words. That already shows that the algorithm requires $\Omega(m)$ space. Since the space taken by local variables is part of the call stack, the memory usage at any point in time is big Theta of the depth of the call stack (since each level requires $\Theta(1)$ machine words). It's not hard to check that the call stack never gets more than $m+1$ levels deep, and so the space is $\Theta(m)$.

When $n$ is not a power of 2, a very similar analysis shows that the space usage of the algorithm is $\Theta(\log n)$.


What are the known ambiguities in C language grammar?

Not sure if this answers your question, but I will contribute two details regarding lexing/parsing ambiguities in C in general. I hope these are still helpful.
Consider the expression T ** c;. Since C supports type declarations via typedef, the parser itself cannot decide whether this is multiplication with variables T and *c or a variable declaration of a pointer to pointer c of type T**. We'll need information fed into the parser by the lexer to decide which situation we're parsing (the lexer will resolve each valid type name to a type).
Another situation similar to the situation above gives rise to an ambiguity in the C syntax: In general, statements like a +++ b are ambiguous, since both (a++) + b and a + (++b) are valid. In this kind of situation, the C compiler follows the "longest match" rule: the compiler will match against the longest sequence of characters it can match.


If they only cross at a single vertex $v$, consider the distance from that $v$ to the four path ends. Since the lengths are odd, $v$ can not be in the exact middle of the paths. But then, are the paths really the longest ones?


Counting models satisfying a boolean formula

For any fixed $k$, a $k$-CNF with at most four clauses has at most $4k$ variables. So you can count the satisfying assigments with

count = 0
j = number of variables
for v1 = 0 to 1 do
    for v2 = 0 to 1 do
        ...
        for vj = 0 to 1 do
            if formula_value(phi, v1, ..., vj) == true
                count = count + 1

This runs in time $\Theta(2^j) = O(2^k) = \Theta(1)$, since $k$ is fixed.


Can A still be a key if two tuples are the same

Pragmatically, You are correct that when you declare something as a primary key, that it must correspond to one tuple.  Databases will not allow you to store a tuple in a table if the primary key already exists for a tuple in the table.

Theoretically, If $R$ is a relation with the following set A of attributes $\{a_1, a_2,..., a_n\}$, then a primary key on the relation $R$ would be a subset $P \subset A$ such that for $F:P \rightarrow A$, we have $\forall x,y \in P $ $F(x)=F(y) \rightarrow x=y$.  This basically just means that the primary key forms a one-to-one mapping from the domain of keys to the range of corresponding tuples.

If you have that two tuples are the same $A$ and $B$, then this implies that $A = B$,and we still have that $F(A)=F(B)$ so that there is no violation, in that sense.


Red-black tree. Adding a red child to a red node with a black sibling

Assume we have a black node $N$ with black child $L$ and red child $R$. Thus we have a red and black sibling. Recall that in a red-black tree all paths from root to leaf must have the same number of black nodes. The path $N-L$ contains two black nodes, the path $N-R$ just one. That means that both children of $R$ must be present, and must be black. So indeed, we can not add a new red child to $R$ because it already has black children. However, what can happen is that one of these black children turns red as consequence of a flag-flip. We then are in the situation you describe.


Is boolean formula isomorphism NP-complete?

Your problem is $\mathrm{co}$-$\mathrm{NP}$-hard so it may also be $\mathrm{NP}$-hard but very unlikely to be $\mathrm{NP}$-complete (i.e. to be in $\mathrm{NP}$).

We reduce from TAUT which is $\mathrm{co}$-$\mathrm{NP}$-hard. Given a TAUT instance $\varphi$ with variables $x_1,\dots x_n$, output $<\varphi, ((x_1 \lor \lnot x_1)\land\dots\land (x_n \lor \lnot x_n))>$. These two formulae are isomorphism iff. $\varphi$ is a tautology.


Enumerate all paths in a given series-parallel graph

Treat SPG as DAG
We can see easily that every path from the source to the sink in a series-parallel graph (SPG) always goes nearer and nearer to the sink. It can never go backwards. There is no sideways. For the example in the illustration provided in the question, it can never move "up". This phenomenon can be proved easily by structural induction.
So we can view a SPG as a directed acyclic graph (DAG) naturally, where every edge is assigned the direction such that its head is nearer to the sink than its tail. For the SPGs in the illustration of the question, the head of an edge is lower than its tail.
Many Algorithms for DAG
There have been many algorithms that lists all paths from a source node to a destination node in a DAG such as this one and this one.
Time-complexity and space-complexity
For simplicity, assume the given SPG is a simple graph. (The case of multi-graph is not much different.) We have $|E|\le2|V|-3$. This inequality will not be used here; it is shown just to illustrate an SPG is a relatively simpler graph.
What is the maximum number of paths from source to sink in an SPG of $n$ vertices?
A rough estimate is $2^{\Omega(n)}$. In fact, we can show that the maximum number of paths from source to sink in an SPG of $n$ vertices is $3^{4 - (n-2)\%5}4^{\lfloor(n-17)/5\rfloor +(n+3)\%5}$ for all $n\ge13$, which is $\Theta(4^{n/5})$. So the worst time-complexity for all algorithms is about $\Omega(n4^{n/5})$.
If the algorithm stores that all paths in full detail before outputting anything or if the space used by output is counted towards usages, then the space-complexity is $O(n4^{n/5}$). However, if the space used by output is not counted towards space-complexity, the space-complexity can be reduced to $O(n)$ if we use a depth-first search such as the following code in Python, assuming the adjacency list of the SPG is given in the input.
def list_paths(g, path):
    children = g[path[-1]]
    if len(children) == 0:
        print(path)
    else:
        for node in children:
            path.append(node)
            list_paths(g, path)
            path.pop()

"""
Output all maximal paths from source in O(n)-working-space-complexity.
The parameter g is assumed to be an adjacency list that represents a valid DAG.
"""

def list_all_paths(g, source):
    list_paths(g, [source])

g = {1: [2, 3],
     2: [4, 5, 6],
     4: [7],
     5: [7],
     6: [7],
     7: [8],
     3: [8],
     8: [9],
     9: [10, 11],
     10: [12],
     11: [13],
     12: [14],
     13: [14],
     14: [],
     }

list_all_paths(g, 1)

""" Expected Output
[1, 2, 4, 7, 8, 9, 10, 12, 14]
[1, 2, 4, 7, 8, 9, 11, 13, 14]
[1, 2, 5, 7, 8, 9, 10, 12, 14]
[1, 2, 5, 7, 8, 9, 11, 13, 14]
[1, 2, 6, 7, 8, 9, 10, 12, 14]
[1, 2, 6, 7, 8, 9, 11, 13, 14]
[1, 3, 8, 9, 10, 12, 14]
[1, 3, 8, 9, 11, 13, 14]
"""

By the way, the number of all paths can be computed directly in $O(n)$ time and $O(n)$ space by either recursive dynamic programming or iterative dynamic programming following a topological sort.

Exercise 1. Show the maximum number of paths from source to sink in an SPG of $n$ vertices is $3^{4 - (n-2)\%5}4^{\lfloor(n-17)/5\rfloor +(n+3)\%5}$ for all $n\ge13$, where $\%$ is the remainder operator. (For $n=12$, the maximum number is $4\times5=20$)

Exercise 2.  Verify the algorithm above in Python still works if the given DAG g is not a simple graph, i.e., that might be parallel edges. What is its time-complexity and working-space-complexity when $g$ is a SPG that is not necessarily a simple graph?


Here is one way to go about your part (a):

There are four places to be filled in the multiset using the $n$ distinct elements. Atleast one element has to occur exactly twice. That would leave 2 more places in the multiset. This means, atmost two elements can occur exactly twice. We can thus divide this into 2 mutually exclusive cases as follows:

Exactly one element occurs exactly twice: Select this element in ${n\choose{1}} = n$ ways. Fill up the remaining two spots using 2 distinct elements from the remaining $n-1$ elements in ${{n-1}\choose{2}}$ ways. Overall: $n \cdot {{n-1}\choose{2}} = \frac{n(n-1)(n-2)}{2}$ ways.
Exactly two elements that occur twice each: These two will fill up the multiset, so you only have to select two elements out of $n$ in ${n\choose 2} = \frac{n(n-1)}{2}$ ways.

Since these are mutually exclusive, the total number of ways to form the multiset is:
$$\frac{n(n-1)(n-2)}{2} + \frac{n(n-1)}{2}$$$$ = \frac{n(n-1)^2}{2}$$

Note, that $n \ge 2$ otherwise no element can be present twice. This is also obvious from the formula (when $n = 0, 1$).

You can check that the formula tallies with your counts.


The tribes function is the classical example of a transitive balanced function whose average sensitivity is $\Theta(\log n)$. Its maximal sensitivity is however $\Theta(n/\log n)$.

The addressing function is an example of a balanced function depending on all inputs which has sensitivity $\Theta(\log n)$ and average sensitivity $\Theta(\log n)$. It is simpler to describe this function as having an input of size $n + \log n$: the first $n$ bits describe a binary string $x$, and the last $\log n$ bits describe a number $i \in [1,n]$. The output of the function is $x_i$. At any point the function depends only on the $\log n$ bits of $i$ as well as the single bit $x_i$.


Handwritten character recognition as characters are being traced

There is a paper "Using Mobile Phones to Write in Air". It basically uses the mobile sensors and machine learning to detect words. The Results show that English characters can be identiﬁed with an average accuracy of 91:9%.

There are some open source projects like "hand-gesture-detection" on Google code. I think you can use them as the start for your project.


Your solution will work and, if implemented properly, will require $O(n)$ time where $n$ is the number of vertices of $T$ (to achieve this complexity you cannot just use a BST or a hashmap as a dictionary though).
Notice that you're using the fact that there is a unique path from the root of $T$ to each of the leaves.
Also running any shortest-path algorithm for DAGs on the weighted version of $T$ in which each edge $e$ weighs $-w(e)$ will work in $O(n)$ time. However this is overcomplicated as it requires finding a topological order of $T$ (which requires a DFS). In other words you are not taking advantege of the fact that $T$ is a tree and not just a generic DAG.
A quick way to solve this problem in $O(n)$ time is performing a depth first search starting from the root of $T$ while keeping track of the weighted depth $d$ of the current vertex. Whenever you traverse an edge $e$ "forward" (i.e., from a vertex to one of its children) you increase $d$ by $w(e)$, whenever you traverse an edge $e$ "backwards" (from a vertex to its parent) you decrease $d$ by $w(e)$.
It is very easy to implement this recursively.


Suppose HALTS is a TM that reads its input as a pair $M$ and $x$, where $M$ is a TM encoding and $x$ is any input to that TM.

Your question is if what would happen if we assumed HALTS solved the halting problem for all inputs $\langle M,x \rangle$ such that $x$ is not an encoding of a TM that is functionally equivalent to $M$.

I claim this implies a contradiction. I came up with this on the spot, so I welcome any and all criticism of my proof. The idea of the proof is that rather than diagonalizing something on itself, we make two mutually recursive TMs that behave differently on some input (thus are not functionally equivalent), but otherwise cause contradictions.

Let $D_1$ and $D_2$ be two mutually recursive TMs (which is to say we can simulate, print, etc, the description of $D_2$ inside the program of $D_1$ and vice versa). Note that we can make mutually recursive TMs from the recursion theorem.

Define $D_1$ and $D_2$ as follows: on input $x$, if $|x| < 10$ (10 chosen arbitrarily), then $D_1$ accepts and $D_2$ loops. (Thus, they are not functionally equivalent).

Given input $x$ with $|x| \ge 10$, define $D_1$ to simulate HALTS on $\langle D_2, x \rangle$ and halt if $D_2$ halts or loop if $D_2$ loops.

Given input $x$ with $|x| \ge 10$, define $D_2$ to simulate HALTS on $\langle D_1, x \rangle$ and loop if $D_1$ halts or halt if $D_1$ loops.

Then note that for any $x$ with $|x| \ge 10$, $D_1$(x) either halts or loops. If $D_1$ halts on input x, then we know HALTS($D_2$, x) determined that $D_2$ halts on input x. However, $D_2$ halting on input x implies that HALTS($D_1$, x) loops.

If $D_1$ on input $x$ loops, the contradiction follows similarly.

This is a contradiction unless $x$ is an encoding for a turing machine functionally equivalent to $D_1$ or $D_2$, in which case HALTS has undefined behavior. However, $x$ was chosen at arbitrary from all strings of size greater than $10$. Thus, it remains to show there exists a turing machine with an encoding of size greater than 10 that behaves differently than $D_1$ and $D_2$. We can construct such a machine trivially. QED.

Thoughts?


Induction Proof on Independent Set Variation Algorithm

Let $G$ be a graph with an independent set of size $k$, and let $v$ be an arbitrary vertex. There are two potential types of independent sets of size $k$ in $G$:

Independent sets not containing $v$: These are independent sets of size $k$ in $G \setminus \{v\}$.
Independent sets containing $v$: These are formed by adding $v$ to independent sets of size $k-1$ in $G \setminus \{v\} \setminus N(v)$, where $N(v)$ is the neighborhood of $v$.

Using an oracle for independent set, we can find which of these cases happen.

The basic idea can be implemented in many ways. Here is a recursive implementation, which uses the oracle $O(G,k)$, which answers whether $G$ contains an independent set of size $k$.

Procedure $I(G,k)$
Input: Graph $G$ and integer $k \geq 1$
Output: Independent set of size $k$ in $G$, or "No" if none exists

If $O(G,k)$ returns "No", then return "No".
Let $v \in G$ be arbitrary.
If $k = 1$, return $\{v\}$. Otherwise, continue.
If $O(G \setminus \{v\},k)$ returns "Yes", return $I(G \setminus \{v\},k)$.
Otherwise, return $O(G \setminus \{v\} \setminus N(v),k-1) \cup \{k\}$.


Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

It may be simply that it's mistaken to think that someone would reason their way to this argument without making a similar argument at some point prior, in a "simpler" context.

Remember that Turing knew Cantor's diagonalisation proof of the uncountability of the reals. Moreover his work is part of a history of mathematics which includes Russell's paradox (which uses a diagonalisation argument) and Gödel's first incompleteness theorem (which uses a diagonalisation argument). In fact, Gödel's result is deeply related to the proof of undecidability of the Halting Problem (and hence the negative answer to Hilbert's Entscheidungsproblem).

So my contention is that your question is in a sense badly founded and that you can't reach the Halting Problem without going past the rest (or something remarkably similar) first. While we show these things to students without going through the history, if you were a working mathematician it seems unlikely that you go from nothing to Turing Machines without anything in between - the whole point of them was to formalise computation, a problem many people had been working on for decades at that point.

Cantor didn't even use diagonalisation in his first proof of the uncountability of the reals, if we take publication dates as an approximation of when he thought of the idea (not always a reliable thing), it took him about 17 years from already knowing that the reals were uncountable, to working out the diagonalisation argument.

In reference to the "self-application" in the proof that you mention, this is also an integral part of Russell's paradox (which entirely depends upon self-reference), and Gödel's first incompleteness theorem is like the high-powered version of Russell's paradox. The proof of the undecidability of the Halting Problem is so heavily informed by Gödel's work that it's hard to imagine getting there without it, hence the idea of "self-application" is already part of the background knowledge you need to get to the Halting Problem. Similarly, Gödel's work is a reworking of Russell's paradox, so you don't get there without the other (note that Russell was not the first to observe a paradox like this, so prototypes of the diagonalisation argument has been around in formal logic since about 600BCE). Both Turing and Gödel's work (the bits we're talking about here that is) can be viewed as increasingly powerful demonstrations of the problems with self-reference, and how it is embedding in mathematics. So once again, it's very difficult to suggest that these ideas at the level Turing was dealing with them came a priori, they were the culmination of millennia's work in parts of philosophy, mathematics and logic.

This self-reference is also part of Cantor's argument, it just isn't presented in such an unnatural language as Turing's more fundamentally logical work. Cantor's diagonalisation can be rephrased as a selection of elements from the power set of a set (essentially part of Cantor's Theorem). If we consider the set of (positive) reals as subsets of the naturals (note we don't really need the digits to be ordered for this to work, it just makes a simpler presentation) and claim there is a surjection from the naturals to the reals, then we can produce an element of the power set (i.e. a real) that is not in the image of the surjection (and hence derive a contradiction) by take this element to be the set of naturals who are not in their own image under the surjection. Once we phrase it this way, it's much easier to see that Russell's paradox is really the naïve set theory version of the same idea.


Algorithm to efficiently determine whether a magazine contains all the letters in a search string

If this was a real life problem, and the search string contained n letters, while the magazine contained m letters, then this would take O (n + m) in time. Typically you would assume that n is very small compared to m, so this solution would take a lot more time than needed.

I'd create a counted set of the letter in the search string. If that counted set is empty (because the search string was empty) I'm done. Then iterate through the letters in the magazine; if a letter is in the counted set then remove it and I'm done if the set became empty. Otherwise, if the iteration finishes then I have a counted set of all letters that cannot be provided by the search string.

This will usually end quite quickly, long before all the letters in the magazine are examined.


Why is the inner product of -1,+1 binary variables at most $n-2$ and not at most $n-1$?

I just noticed that if we have one disagreement then we change one single entry from +1 to -1. Thus, the summation decrease by 1 because we are missing one of the +1's in the summation but on top of that because they are Rademacher vectors instead of simple binary 0,1 then it means that the +1 actually changes to -1, meaning the inner product decreases by an additional 1.

So it decreases by 2 cuz:

we lose a +1 in the summation
but we also replace the +1 with a -1

so total decrease is by two leading to $ \leq n-2$


What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$

Clearly T(n) = T(0) for all n. Which is constant, not linear. Is that really the question you wanted to ask?

And I just see a mathematical relation. I can’t see any recursion or tree or algorithm here.


Two or more threads executing concurrently require synchronization if and only if at least one of the threads accesses and modifies one or more variables (write access) accessed by the remaining threads (either read or write access). Therefore, if all of the threads access the same set of variables only for reading their values (read access), no synchronization is needed. You probably know that the access to variables by multiple threads when at least one of them writes at least one of the variables, must happen in a so-called critical section (or critical region) of code. You then synchronize the access by providing mutual exclusion using for instance a Posix mutex lock. This permits concurrent execution of multiple threads, so that the execution preserves correctness when updating one or more of the variables involved.

Of course, concurrent execution of multiple threads is the most efficient way of writing code in general. However, you may also imagine a different execution, in which the operations associated to each thread are executed sequentially and not concurrently, one after the other, in an order that is strictly equivalent to a concurrent, correct execution. This is called serialization of execution. What does it mean "strictly equivalent" ? Serialization must provide as a requirement exactly the same results that will be provided by a concurrent,  correct execution. Note that there are multiple possible concurrent and correct executions, but the outcome must be one and only one.

Now, do you really want to use serialization to synchronize your threads ? The answer is no, because a serialized execution is in general slower than a concurrent execution (obvious, since execution is sequential and not concurrent). In practice, serialization just gives you a criterion for correctness. You want your threads to execute concurrently, for performance reasons, however, you must ensure that the outcome is correct independently of the actual concurrent execution that took place.

As an example imagine two threads accessing a variable which is the amount of money you have deposited in your bank. If both threads just want to read that amount of money, no issue arises. However, if one or both the threads want to modify that value, a problem arises and you need to synchronize the access. For instance, one thread may be depositing money to your account (you in your bank), and the other thread ma be withdrawing money from your account (your wife from an ATM). In these cases, access to the variable holding the amount of money must be synchronized. Serialization in this case is simple: you must either first withdraw the money and then add the money, or, vice-versa, you first add the money to your bank account and then withdraw the money. In both cases, serialization provides the correct outcome. To grant a correct outcome in the case of a concurrent execution, you must instead protect the variable using a mutex lock, so that access to the variable is mutually exclusive for both the threads. Otherwise, the value of the variable when accessed from both threads without proper synchronization is actually undefined, which is very bad for your money! You may, for example loose part or all of of your money.

Another type of synchronization is not related to mutual exclusion. Imagine, for instance, that one thread can execute its operations only after another thread has completed. Another example: a thread can execute only when a specific condition is true, and this condition depends on another thread (this includes the previous example, but is a more general requirement, based on the evaluation of a predicate).
For instance, you may synchronize threads in this way by using Posix mutex locks and condition variables.

Serialization has been thoroughly studied in the context of database transactions. A serialized schedule provides a criterion for correctness of execution of concurrent transactions in databases, and there are protocols that ensure proper synchronization (e.g., two-phase locking). But the concept applies equally well to threads as well.


Why is TIME(n log (log n)) \ TIME(n) = ∅?

The quick explanation is that

$TIME[o(n\log n)]\subseteq REG\subseteq TIME[n]\subseteq TIME[o(n\log n)]$, and therefore $TIME[o(n\log n)]=REG$.

Similarly:

$TIME[n\log\log n]\subseteq TIME[o(n\log n)]\subseteq REG\subseteq TIME[n]\subseteq TIME[n\log \log n]$, so $TIME[n\log\log n]=REG$

But I think this is not the point you are missing.

You say that $TIME[n\log \log n]$ is regular. This is not exact. When we say that something
 is regular, we mean that it is a language $L\subseteq \Sigma^*$, which is regular (i.e. can be recognized by a DFA).

The class REG is not a language, but a set of languages. That is, $REG\subseteq 2^{\Sigma^*}$. Similarly, $TIME[f(n)]\subseteq 2^{\Sigma^*}$ for every function $f$. These are all classes of languages.

Since we have that $TIME[n\log\log n]\subseteq TIME[o(n\log n)]\subseteq REG$, then
$REG\setminus TIME[n\log\log n]=\emptyset$. This follows from the simple property that if $A\subseteq B$, then $A\setminus B=\emptyset$.


How to compute time complexity of a program if the time complexity of a function called inside a loop is known?

This is actually an example of amortized analysis. The easiest way to see what's going on is to separate $A$ as follows: $A=1^{n_1}01^{n_2}0\cdots1^{n_k}$. You can check that the function $f$ is called with arguments $n_1,n_2,\ldots,n_{k-1}$. Since $n_1+\cdots+n_k = n-(k-1)$, in particular $n_1+\cdots+n_{k-1} \leq n$, and so the total time spent running $f$ is $O(n_1+\cdots+n_{k-1}) = O(n)$. The time spent on executing the rest of the program is $\Theta(n)$, and so the total running time is $\Theta(n)$.

If we did want to use amortized analysis, the idea would be as follows. Suppose for simplicity that $f(m)$ runs in time $m$ (exactly). Each time the counter is incremented, we set aside another "time unit", and withdraw the time units set aside when $f$ is called. You can check that we always have enough time units in store. Under this scheme of accounting, incrementing the counter takes time $O(1)$, and calling $f(m)$ takes no time; this can only overestimate the actual running time (since we might have leftover time units). Therefore the total running time is $O(n)$.


Neural Network | What is the purpose of hidden layers and how many should I use?

It is actually not true that you can get any result that you want without any hidden layers. Consider for example a neural network with one input and one output. The only functions that such a network can be compute is threshold functions – whether the input is at most something or at least something (assuming the output is converted to Boolean).

Roughly speaking, the strength of neural networks as a computation model (rather than as a machine learning instrument) depends on two resources: size and depth. Every function can be computed (approximately) using only one hidden layer, but adding more hidden layers can dramatically reduce the size of the network needed to compute the function.

I think it is fair to say that at the moment, choosing the best network architecture involves some experience and some experimentation, since there is no good understanding of why neural networks work. Look up a paper on a similar task, and try similar parameters. There are known methods for estimating whether the network is too large or too small, and probably there are similar rules of thumb regarding depth.


Which is the best approach to solve Turing machines exercises?

There isn't really a "best way of reasoning". Mathematical proof is essentially a creative act and there isn't a straightforward recipe you can follow. I usually find it helps to treat Turing machine construction as a programming problem, which is basically what it is.


How to find sum of maximum K elements in range in array

This answer refers to the version of the question in which the interval $[l,r]$ refers to the values of the elements rather than their indices.

Without preprocessing: You can extract all elements in the range $[l,r]$ in linear time. You can then use the linear time selection algorithm to find the $k$'th largest element, and then you can easily find the sum of the $k$ maximum elements. Overall, you can answer each query in $O(n)$.

With preprocessing: Sort the array, and compute running sums. Given $l,r$, locate the subset of the array corresponding to this range using binary search, and then use the running sums to compute the sum of the $k$ largest elements in $O(1)$. Overall, this uses $O(n\log n)$ preprocessing and $O(\log n)$ time per query.


Computing the right tangent of two convex hulls

The paper of Preparata and Hong says:

We let $l_A$ and $r_A$ be two points of A such that $x_2(l_A) = \min_i {x_2(a_i)}$ and $x_2(r_A) = \max_i{x_2(a_i)}$; similarly $l_B$ and $r_B$ are defined in B.

and:

Without loss of generality, we shall also assume that $r_A = a_1$ and $r_B = b_1$.

So, in this notation, vertices in your two polygons will be numbered differently:
$$A=((1.2,1),(0.2,0.2),(0.3,1.3))$$
$$B=((3,2),(2,2),(2,3))$$
In simple words, the algorithm starts from rightmost vertices on both polygons and continues clockwise potentially until leftmost vertices - so, only lower sides of both polygons will be involved. Tangential vertices $(0.2,0.2)$ and $(3,2)$ will be found.
This paper has been published long time ago, and since then this algorithm has been clarified and simplified. The newest version of it starts from the rightmost vertex on the left polygon and the leftmost vertex on the right polygon, and continues clockwise for the left polygon and counterclockwise for the right polygon (to find lower tangential line). Also they usually check a vertex location relative to a line using the dot product instead of calculating and comparing slopes - because the tangential vertex has to have both its neighbors on the same side of the tangential line. For more information, pictures and code - please see this monograph, Section 3.8.


Proving a Language is Irregular using Myhill-Nerode

You need to come up with an infinite number of pairwise inequivalent strings. Try $x_i = 0^i$ for all $i \geq 0$.


Counting inversion pairs - $n^2$ results in $n \log n$ time?

Here is an even more amazing example. The determinant of an $n\times n$ matrix is a sum of $n!$ products, yet we can compute it in time $O(n^{2.373})$.
Here is another striking example. Given a binary string of length $n$, we can count the number of binary strings of the same length in time $O(n)$ even though there are $2^n$ of them.
What limits the running time is not the magnitude of the output but its length.

In this particular case, the output length is $O(\log n)$, so it provides no meaningful limit at all. Even though there could be up to $\binom{n}{2}$ many inversions, we can count them without listing them all, just as in the example of binary strings. As you mention, there is an $O(n\log n)$ algorithm doing that. It is conceivable that there is an even faster algorithm, though nothing faster than $O(n)$, since you need (in general) to read at least $n-1$ entries of the permutation before you can be sure what the number of inversions is.


Algorithm to determine if a top-down non deterministic tree automata accepts some tree?

Yes, you can do it in linear time.  Associate to each pair of a state $q$ a boolean variable $x_q$; the intended meaning is $x_{q,s}$ should be true if there exists a tree that is accepted by the automaton if we start with state $q$ at the root.  Then, each transition rule of the automaton corresponds to a Horn clause on these boolean variables. For instance, the transition rule $f(q_1,\dots,q_n) \to q'(f)$ corresponds to the Horn clause $(x_{q_1} \land \cdots \land x_{q_n}) \implies x_{q'}$.  Now, solve the associated HornSAT problem using any standard algorithm to find the minimal satisfying assignment to all of these clauses; this can be done in linear time.  If you find any final state $q$ of the automaton such that $x_q$ is set to true by this assignment, then the answer is yes, there exists a tree that's accepted by this automaton; otherwise, the answer is no.


I believe you left out big-Os around those bounds.

In any case, $\; \{0\} \subseteq \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\} \;$ and $\; \{0\} \subseteq \{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.04 in}2\hspace{-0.02 in}\}$ , $\;$ even though $\: \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\} \neq \{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.04 in}2\hspace{-0.02 in}\}$ .


The notation $\{a,b\}^*$ stands for all strings over the alphabet $\{a,b\}$. A word is in the language $L$ if it is of the form $ww$, where $w$ is an arbitrary word over the alphabet $\{a,b\}$. For example, taking $w = aba$, we see that $abaaba \in L$. If $w$ has length $n$ then $ww$ has length $2n$, and in particular every word in $L$ has even length. So $a \notin L$. But this idea isn't enough to prove that $ab \notin L$.

If $x$ is a word of odd language, then $x \notin L$. If $x$ has length $2n$, then write $x=yz$, where $y$ consists of the first $n$ characters, and $z$ consists of the last $n$ characters. Then $x \in L$ if and only if $y=z$. If $x=ab$ then $y=a$ and $z=b$ and so $y \neq z$, implying $ab \notin L$.


Alternatives for finding sources in a DAG

Use a priority queue to keep a list of all vertices with prioritization on in-degrees.
Pop off one vertex $v$ with in-degree zero, decrement the in-degree-count of the out-neighborhood of $v$.
Repeat until empty.
If the input graph is a DAG, this will give you a topological ordering.


Define a length function over $A^{*} \leftarrow{N}$ such that $length(l)$ outputs the length of $l$

Let F denote a “shape”, as your LIST and NAT shapes for example.

  Declaring $I := μF$ is tantamount to saying that $I$ is recursively defined by some $α : F(I) ≅ I$
    and moreover for any $β : F(K) → K$ there is a unique $f : I → K$ that respects the “F”-structure.

Since you define $A^* = μ(LIST)$, where the “LIST” structure on a set $X$ consists of a constant $c : X$
and a function $n : A × X → X$ --- c.f., your $nil, -·-$ --- we automatically obtain an operation $A^* → ℕ$ if
we can endow $ℕ$ with a “LIST” structure; namely a constant such as zero $0 : ℕ$ and an operation
on ℕ such as $A \times ℕ → ℕ : (a, n) ↦ s\, n$.

So by the μ-definition of lists, since we furnished ℕ with a LIST structure,
we have that there is a unique function, call it $length$, that respects the LIST structure in that
it takes the shape constants-to-constants and the shape functions-to-functions:
$$ \mathsf{length}(nil) \;=\; 0 $$
$$ \mathsf{length}(a \cdot l) \;=\; s(\mathsf{length}\, l) $$

Alternatively, these properties also serve to “define length by structural induction on  the shape of lists”.

Hope that helps a bit :-)


Showing that a Particular Word Problem is Decidable

Hint: Come up with a normal form for words in this group.


An easy way is as follows: For each vertex $s$, perform a BFS visit to discover the shortest cycle containing $s$.

When a visit from $s$ is performed a BFS tree $T_s$ is built and each non-tree edge $(u,v) \not\in E(T)$ for which $u$ and $v$ belong to different subtrees rooted in the children of $s$ in $T$ tree induces a cycle containing $s$.
Since, the shortest cycle containing $s$ must use a non-tree edge $(u,v)$ with this property, it will be found by the visit. You can optionally stop the visit early: if you find a cycle while visiting $u$, you can stop the BFS as soon as all the vertices in the level of $T$ containing of $u$ are visited.

The overall required time is $O(n \cdot m)$.


For each $i,m$ in the range $n/3 \leq i,m \leq 2n/3$, computing the recurrence requires going over $\Theta(n)$ values of the parameter $k$, hence calculating $u(i,m)$ for all of these values of $i,m$ requires time $\Theta(n^3)$.
Do you actually encounter such values of $i,m$ when calculating $u(1,1)$? It's not immediately clear to me, but you'll have to rule it out if you want to prove a better upper bound on the running time of your procedure.


Use of existential quantifier in tuple relational calculus

Something like { c.name | ... } is shorthand for something like

{z : (name) | (∃c) (z.name = c.name ^ ...) }.

As described on, e.g., the Wikipedia page, the fundamental form of the set comprehension (i.e. query) notation expects a variable to the left of the |. If you are familiar with anonymous functions/lambda notation, it is very similar to $\lambda z.(\dots)$. If we named it, it's like we're defining a predicate $P(z)\equiv(\dots)$. The upshot is that the notation effectively binds z (or c in the original form). But in your version without existential quantifiers, nothing is binding e or s. It's like you're referring to undeclared variables in a programming language.

Since whether the variables are bound with a universal or existential quantifier and where exactly that quantifier appears in the formula are all relevant, it would be difficult to infer which quantifiers should be added and where. (And as an additional possibility, we could just imagine that the variables are completely free and essentially become additional parameters to the anonymous predicate we're defining, but that doesn't fit in well with the Tuple Relational Calculus.) Prolog and Datalog do use a syntax that makes existential quantifiers implicit, but they are (in their basic forms) also limited to a language that 1) omits universal quantifiers, and 2) only allows formulas where existential quantifiers can always be pulled to being the outermost connective. Actually, when negation is added to Datalog, this stops being true and this implicit syntax starts to become ambiguous and confusing. Some implementations add an explicit existential and/or universal quantifier in such cases.

The upshot is, at the most fundamental level, all variables need to be bound, either by a quantifier or by the set comprehension syntax. There do exist various shorthands and conventions that are often used that can cloud this picture up, but ultimately every variable is introduced by some binding form.


Instantiating a class with a sig'd type in Coq

You are missing propositional extensionality. It is not provable in straight Coq but you can assume it. And while you are at it, if your going to do math, you will also want function extensionality. Both forms of extensionality follow from univalence, which is also an extensionality principle, except that this one is for the universe of types.
If you prefer to avoid all this you can go down the road of setoids: you equip every types with an equivalence relation that serves as the equality relation. You then have to keep proving that your functions preserve these relations. It's a lot of "fun".


Coercing a list of nodes into the most probable tree

In the end, I ended up solving my particular problem using Stochastic Context Free Grammars.

There may be some additional cost incurred for production, or otherwise probability operations that you can't express in the CFG. The probabilistic Earley algorithm (Stolcke, 1995) allows us to intervene in the parsing process somewhat by producing callbacks on scannning a token (or predicting / completing).

I have arbitrarily chosen my rule probabilities, but you can train them using the inside-outside algorithm, although that will probably mess up the the soundness of any probability-tinkering callbacks.

Practically, this question lead me to create a Probabilistic Earley Parser for Javascript and for Java. These libraries only allow the user to multiply scan probability given a token at a position the sentence, but it is easy to add other callbacks with more information. Please create an issue in Github if you need this. Also, these libraries do not support training a grammar on a test set (inside-outside), because I did not have time to implement this.

For an exposition of my use case, consider the chapter in my master thesis Automatic Assignment of Section Structure to Texts of Dutch Court Judgments, Inferring a Section Hierarchy


Formal Binary String Regular Expression (each pair of 00 must have 11 before it)

Here is a way to describe a binary string in which every 00 must have at least two 1s before it.
It is a string that
$\quad$ starts with zero or one 0;
$\quad$ followed by zero or more blocks, where each block is
$\quad\quad$ either one or more 1s followed by a 0, such as 10, 110, 1110, etc,
$\quad\quad$ or two or more 1s followed by two 0s, such as 1100, 11100, 111100, etc;
$\quad$ followed by zero or more 1s.
Translated into regular expression, the description above becomes
$\quad$ (0|ε)(11*0|111*00)*1*

You might want to ask, how can we arrive that kind of description?
The observation here is that the number of consecutive 0s in the string is at most 2, a very small number. That indicates that we can break down the string by enumerate different possibilities of consecutive 0s. To paraphrase rici's comment, we could try using enumeration to simulate conditionals.

Of course, there is a mild stroke of luck involved in the approach above on that language.  As a last resort, we can always use a heavier machinery such as constructing a DFA for the language (which can be done in one or several ways) and then converting the DFA to a regular expression.


The condition of the Pumping lemma is fulfilled for words of the form $ab^kc^kd^k$.

Pick $v=a$, $u=x = \varepsilon$, and $w$, $y$ arbitrary.


The language $L$ is not regular, as can be proved using Nerode's method. Consider the following words $w_n = a^n b$ for $n \in \mathbb{N}$. Then $w_n^2 \in L$, but for $n \neq m$, $w_n w_m \notin L$. Hence any automaton for $L$ must be in a different state after reading each $w_n$, which contradicts its finiteness.


How to determine offset bits when addressing CPU cache?

If you need to address a space consisting of $2^N$ values, then you need $N$ address bits.
In your example, $2^N = 32$ and $N = 5$.


Is SAT in P if there are exponentially many clauses in the number of variables?

Unless I'm missing something, it's trivially in P as the length of the formula is exponential in the number of variables. Hence all $2^{n}$ truth assignments can be generated and checked in polynomial time in the length of the formula.


Compiler Question : Does the parser detect Errors in these examples or the Semantic routine?

It's impossible to say in general; it depends on the compiler resp. the exact definition of the syntax.

If your language contains special syntax for array declarations, the parser will note that it doesn't find an integer literal between the brackets.

For array accesses, the language probably allows arbitrary arithmetic expressions (including function calls) between the brackets. So the parser will create an expression tree, and only the type checker will determine that the expression is not of type integer.


Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?

The complexity is measured as a function of the size of the input.
You don't have here an array of $n$ numbers but a number $n$.
 The size of the input is $O(\log n)$ (to store a number $n$ you need $\lfloor log_2(n) + 1 )\rfloor$ bits).
Hence, $O(\sqrt n)$ is not polynomial in the size of the input.

The answer to the second question is a direct consequence. Since the size of the input is logarithmic in $n$, an algorithm with logarithmic time complexity with respect to $n$ (and therefore, polynomial wrt the size of the input) would be efficient.

As an example, consider a number $M$ of size $n$, an algorithm with time complexity $O(log^k M)$ for a constant $k$, corresponds to a polynomial time algorithm (in the size of the input) of time complexity $O(n^k)$.


An essential hint: "Assume that f and g are nondecreasing". That is essential. Without it the statement is false, for example $f (n) = 2$ and $g = 1 + 2^{-n}$, where log f (n) = 1 and log g (n) ≈ $2^{-n}$.

The problem here is showing that f (n) = O (g (n)) implies log f (n) = O (log (g (n)). So how does "g is non-decreasing" help? Well, if n ≥ N then 1 < g (N) ≤ g (n) and 0 < log g (N) ≤ log g (n).

f (n) = O (g (n)) means "there are $N, c > 0$ so that we have $f (n) ≤ c·g (n)$ for $n ≥ N$". So there are $N, c > 0$ so that $\log f (n) ≤ c + \log g (n)$ for $n ≥ N$. Now we need to somehow relate c and $\log g (n)$. We have $c = (c \div \log g (N)) · \log g (N) ≤ (c \div \log g (N)) · \log g (n)$, because $g (n)$ is not decreasing. Therefore $\log f (n) ≤ (c \div \log g (N) + 1) · \log g (n)$, so we found a constant c' = (c / log g (N) + 1) such that $\log f (n) ≤ c' · \log g (n)$ for n ≥ N and that means $\log f (n) = O (\log (g (n))$.


How is it possible for a problem to be NP-Complete under polylog-time reductions?

What you probably heard was that many problems are NP-complete under logspace reductions, for example 3SAT. All this means is that (say) the algorithm in Cook's theorem can be carried out in logarithmic space, and that many reductions among problems can be carried out in logarithmic space. Wikipedia contains a relevant discussion of various notions of reducibility and their relation to NP-completeness.


Regular expression for even/odd string on alphabet

How about an expression for even strings $((a+b)\cdot(a+b))^*$ and deriving the one for odd strings from it: $((a+b)\cdot(a+b))^*\cdot(a+b)$?


A special case for the subset sum problem: selecting from powers of two

First, look at the bits that are set in $M$ and write it as $M = m_1+m_2+\dots$ where each $m_i$ is a power of two and such that $m_1$ is the smallest power of two, and so on.

If the numbers $x_i \in X$ are distinct powers of two and you can use each one zero or one times, the problem is trivial: If all $m_i$ are found in $X$, then $M$ can be formed by them, otherwise it can't. This is because missing powers of two can't be formed by a) any combination of larger powers of two or b) distinct smaller powers of two.

If the numbers $x_i$ aren't guaranteed to be distinct, it's a bit more complex. Missing powers of two still can't be formed by larger powers of two, but they can be formed by non-distinct smaller powers of two.

Let's look at how smaller powers of two can form larger powers of two. If you have powers of two $A = [a_1, \dots, a_n]$ that are smaller than a power of two $N$, and $S=\sum_{i=0}^n a_i$, then $N$ can be formed by them iff $S \ge N$. Let $b$ be the smallest power of two in $A$ and $c$ its number of occurences in $A$. If $c$ is odd, one $a_i=b$ can't combine with anything to form a higher power of two and the corresponding bit will be set in $S$. The others can be replaced with $\lfloor \frac{c}{2} \rfloor$ copies of the number $2b$ in $A$. If we continue this with higher powers of two until we get to $N$, we find that we can form $\lfloor \frac{S}{N} \rfloor$ copies of $N$ with $A$.

So, start with $m_1$. If it's found in $X$, we remove it and move to the next power of two. If it's not, we calculate the sum $S$ of all $x_i$ smaller than $m_1$ and remove them from $X$. If $S \lt N$, then $M$ can't be formed by $X$. Otherwise, we add $\lfloor \frac{S}{m_1} \rfloor - 1$ copies of $m_1$ to $X$ and continue in the same manner with the next smallest power of two in $M$.


To show that this isn't always the case, imagine you added $e^n$ elements, then it would take

$$O(\log(n+e^n))=O(\log(e^n))=O(n)$$

But what does that really mean? It's not that your binary tree takes $O(n)$ time on $n$ elements to find something. Rather, it takes $O(\log(m))$ time for $m=n+e^n$ elements.

I can understand why you would be confused; if you had to search linearly through a list, and then you added $n^2$ elements, it would take $O(n^2$) time in terms of the original input, but not the new input, for which it would take $O(m)$ time on $m=n+n^2$ elements.

Chances are you didn't want to solve for the asymptotic solution; it generally doesn't make sense to. What you probably want is the approximation $\log(n+n^2)\approx\log(n^2)=2\log(n)$; that is,

  For a self-balancing tree, squaring the input size doubles the search time.


Undirected graphs with self-loops on $n$ vertices have $\binom{n}{2} + n = \binom{n+1}{2}$ potential edges. Therefore the are $2^{\binom{n+1}{2}}$ different graphs. For $n = 1,2,3,\ldots$, this is
$$ 2^1, 2^3, 2^6, 2^{10}, 2^{15}, 2^{21}, 2^{28}, 2^{36}, 2^{45}, 2^{55}, \ldots $$


Incremental View Maintenance for projection

Just realize the reason after posting the question.
Counterexample:
R =

A  B

1  2

1  1

1  1

ΔR =

A  B

1  1

1  1

1  1

Assume we want ΠA(R - ΔR)

The true answer is first R - ΔR:

A  B

1  2

Then project A:

A

1

However, if ΠA(R - ΔR) = ΠA(R) - ΠA(ΔR).
ΠA(R):

A

1

1

1

ΠA(ΔR):

A

1

1

1

ΠA(R) - ΠA(ΔR) = ∅

ΠA(R - ΔR) = ΠA(R) - ΠA(R min ΔR).

R min ΔR:

A  B

1  1

1  1

ΠA(R min ΔR):

A

1

1

ΠA(R) - ΠA(R min ΔR):

A

1


How to replace one symbol with two on Turing machine's tape

The way I'd do it is as follows:
The syntax is from the Turing simulator I link to below. It is

[transition name],[symbol]
[next transition],[new symbol],[direction]

The actual code:

name: Binary to Unary
init: moveright2
accept: end

moveright2,_
moveright1,_,>

moveright2,0
moveright2,0,>

moveright2,1
moveright2,1,>

moveright1,_
moveleft,1,<

moveright1,0
moveright1,0,>

moveright1,1
moveright1,1,>

moveleft,_
sub1,_,<

moveleft,0
moveleft,0,<

moveleft,1
moveleft,1,<

sub1,0
sub1,1,<

sub1,1
moveright2,0,>

sub1,_
blankout2,_,>

blankout2,_
blankout1,_,>

blankout2,1
blankout2,_,>

blankout1,1
end,_,>

Basically move till you've passed two blanks(Step 1), then write a 1(Step 2), move left till you find a blank(Step 3), treat the number to the left as a binary number and subtract one from it(see below for details on how this works)(Step 4), Then repeat steps 1-4 until you can't subtract any more(in my case the subtract routine turns all 0's in the number we've been subtracting from to 1 and then hits a blank), go back turning all ones to blanks till you hit a blank, then go one farther turning that one into a blank.

It turns 101 into 11111

Subtraction routine, start at the far right of the number, if it's 0 change it to one and move left doing the same thing to each digit you come across, if it's one see step 1


In the binary system (much like in all numbering systems), order has meaning. If you write $0110$ this means $0\times2^3+1\times2^2+1\times2^1+0\times2^0$. Similarly, $11111111$ means $1\times2^7+1\times2^6+1\times2^5+1\times2^4+1\times2^3+1\times2^2+1\times2^1+1\times2^0=255$.

Now, assuming you had a function that produced a random bit as output, you would have 8 distinct bits if you called that function 8 times, which would form no kind of greater structure (that is, you would have e.g., 8 ones, but they would not mean 255 because they are not in an ordered structure, it's just 8 disjoint pieces of data).

On the other hand, if your function randomly selects the values of 8 bits and returns them, you would just have an array (or vector) of bits, which also do not represent a number.

In that sense, you can have the function output any number of bits you want. If you want two bits, you get 11 or 01 or 00 or 10, if you want three bits you get 111 or 000 or 100 or 010 or 001 or 110 or 101 or 011 etc. Note that in the way that you have phrased the question, these would not actually translate into numbers.


how to get rows with more than 1 appearance of a specific column in relational algebra

Here is a relational algebra expression given $R_2$ described in the question that uses set division operator
$$
\Pi_{\text{PostId}, \text{AuthorId}}(R_2) \div \sigma_{\text{AuthorId} = E}(\Pi_{\text{AuthorId}}(R_2))
$$
$\sigma_{\text{AuthorId} = E}(\Pi_{\text{AuthorId}}(R_2))$ will return a set $\{E\}$. Then by the definition of set division operator, we can see that only $(2,E)$ and $(4,E)$ belong to the $R_2$. Thus, the above relational algebra expression will return $\{2,4\}$. Also, we observe that both 2 and 4 are the only PostIDs that have more than one appearance. Thus, the above relational algebra expression gives the right answer.


Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p

Mod(2^N-1) algo:

Split number into N-bit parts (i.e. extract digits in 2^N-ary system). Sum up these parts. If result is higher than 2^N-1 - reiterate. Because

256 mod 255 = 1
2*256 mod 255 = 2
256*256 mod 255 = 256 mod 255 = 1
...
A*2^N mod (2^N-1) = A
A*2^N*2^N mod (2^N-1) = A*2^N mod (2^N-1) = A
...

Mod(2^N+1) algo:

Split number into N-bit parts. Sum up these parts with changing signs. If result is higher than 2^N+1 - reiterate. Because

256 mod 257 = -1 mod 257
2*256 mod 257 = -2 mod 257
256*256 mod 257 = -1*256 mod 257 = 1
...
A*2^N = -A (modulo 2^N+1)
A*2^N*2^N = -A*2^N = A (both equations are modulo 2^N+1)
...

Mod(2^N-K) - multiply by K each next digit

Mod(2^N+K) - multiply by -K each next digit


Find out if a path exists avoiding circular obstacles

Your assumption using binary search is a good assumption, that means
that we can assume we know the radius, and focus only on the subproblem:

Given a rectangle and a set of circles, is it possible to navigate in
the rectangle from the top left corner to the bottom right corner
without touching a circle.

If a circle is covering either the starting point or the end point, we
can abort immediately, so we'll assume they don't.
We will create a graph consisting one vertex for each circle, and one vertex for the south east edges of the rectangle, and one vertex for the north west edges of the rectangle, in other words:
$$V = \{ v_c \mid \text{$c$ is a circle} \} \cup \{v_{\text{se}}, v_{\text{nw}} \}$$
Then we create the edges as follows:
$$E = \{ e = v_{c_1} v_{c_2} \mid \text{$c_1$ and $c_2$ overlap}\} \cup \{ e = v_{c} v_{s} \mid \text{$c$ touches side $s$}\}$$
In other words an edge between two objects if they overlap
geometrically.
If the south east sides are connected to the north west sides, then
it means that you cannot travel from the lower left part of the
rectangle to the upper right part of the rectangle.
In other words, you only need to see whether $v_{\text{se}}$ is
connected to $v_{\text{nw}}$ in your constructed graph, which would
isolate the starting point from the end point.

Yes instance

No instance (south is connected to west)


TSP genetic algorithm: what mutation function for adjacency representation?

The core of your problem is this: you want a simple mutation operator that sends any $n$-cycle to another $n$-cycle.

Recall that every permutation on $n$ symbols can be decomposed into cycles.  To count as a TSP tour, you need the permutation to be a single cycle, i.e., it to be a $n$-cycle.  So given a TSP tour (a permutation that is a $n$-cycle), you want your mutation operator to give you another TSP tour (another $n$-cycle).

Here are multiple approaches you could take:

Don't represent the tour in your adjacency representation.  Instead, represent it as a $n$-cycle: represent it as a list of the vertices visited, in the order they are visited.  Then, you can swap any two elements in the list and get another tour (another $n$-cycle).  For instance, you'd represent your example path as the list [1,5,2,4,3].  Swapping the second and third position gives you [1,2,5,4,3], which is another valid path.
Represent the path in adjacency representation.  Do the same operation as above, but now apply it directly to the adjacency representation: emulate its effect on the adjacency representation.  So, given 5 4 1 3 2, you decide you're going to swap the order that 5 and 2appear in.  This can be done by replacing the5with a2, and replacing the2with the second element (4), and replacing the second element with2`.
Pick a suffix of the path, then splice that into the middle of the path.  For instance, suppose you can decompose the path into $A \to \dots \to F \to G \to \dots \to P \to Q \to \dots Z \to A$.  Then you could change this to $A \to \dots \to F \to Q \to \dots \to Z \to G \to \dots P \to A$ by splicing the $Q \to \dots \to Z$ part right after $F$.  You can take any suffix and splice it in, at an earlier position, like this.  This can be done via a not-too-complex transformation on the adjacency representation, by changing only three elements in the adjacency representation (in this example, you change the successor for $F,Z,P$).


Binary Search Tree Stability Data Structure

You can ensure that the inorder is stable by modifying the insertion routine (if necessary) so that when it compares an element $x_1$ already in the tree to the new element $x_2$, if $x_1 = x_2$ then it answers that $x_1 < x_2$.

Caveat: I'm not sure that this works for self-balancing trees.


The communication complexity of Hamming distance mod $4$

Consider the following task $f$: Given $x,y \in \{0,1\}^n$, Alice and Bob need to determine whether $d(x,y) \bmod{4} \in \{0,1\}$, where $d(x,y)$ is the Hamming distance between $x$ and $y$.

Let $M_f$ denote the matrix corresponding to this problem: $M_f(x,y) = 1$ if the answer is Yes, and $M_f(x,y) = -1$ if the answer is No. The discrepancy method shows that
$$
R_\epsilon(f) \geq \log \frac{1-2\epsilon}{\lambda_{\max}(M_f)/2^n}.
$$
In our case, you can calculate that $\lambda_{\max}(M_f) = 2^{\lceil n/2 \rceil}$ (I checked this for a few $n$ using Krawtchouk polynomials, but presumably there is a simple proof, since all the eigenvalues are nice). For even $n$, this implies that
$$
R_\epsilon(f) \geq \log \frac{1-2\epsilon}{2^{-n/2}} = \frac{n}{2} + \log(1-2\epsilon).
$$

(When $n$ is odd, the lower bound is slightly worse.)

Exactly the same bound is obtained if we replace the condition $d(x,y) \bmod{4} \in \{0,1\}$ with the condition $d(x,y) \bmod{4} \in \{0,3\}$.


How does an operating system implement the C library?

It's hard to give a full answer to this question, as it would basically amount to an introductory text in operating system design, so I will try to give some pointers.

First of all, if you really want to know (including all the gritty details) how an operating system actually works, there's probably no way around looking at an actual implementation of one. Luckily, there's xv6 providing quite a good example, see xv6 and follow the references there.

Before diving into the code, it's probably a good idea to have a look at the basic components of an operating system, see Operating System Components.

I think your question has three main aspects

How does an operating system load a (compiled) C program?
How does such a program interact with the system it runs on?
How does the operating system prevent bad things from happening and regain control once the program is running?

(Warning: The following might be oversimplifying things)

For the first question, see Loader. A compiled C program is just binary data. When loading (let us ignore some bookkeeping that is also going on around this), the operating system copies this binary data simply into memory, does some initialisation (e.g. copy arguments at places the program can find it) and then sets the instruction pointer to the start of the loaded program. Basically, from this point on the program is in control (see below). Eventually, the program (hopefully) will issue a system call, namely exit, when it is done, thus handing control back to the operating system, see Exit (system call (it might also terminate by using a simple return in main, but let us ignore that case for the moment).

This leads to the second question. The interaction with the operating system takes place via system calls. These, in turns, are implemented via interrupts. Roughly speaking, you can think of a special processor instruction being called (i.e., it's a feature of the processor), which stops the execution of the current code and starts the execution of an interrupt handler, which is part of the operating system. The interrupt handler than tries to figure out why it was called and will act accordingly. How does the processor know where to find the interrupt handler? This is part of the loading process of the operating system at boot time, see e.g. Kernel startup stage.

For the third question, see Process management:

  There are two possible ways for an OS to regain control of the
  processor during a program’s execution in order for the OS to perform
  de-allocation or allocation:

  The process issues a system call (sometimes called a software interrupt); for example, an I/O request occurs requesting to access a
  file on hard disk.
  A hardware interrupt occurs; for example, a key was pressed on the keyboard, or a timer runs out (used in pre-emptive multitasking).

The situation is slightly different on multi-core architectures, as there obviously the operating system and the loaded program can run concurrently.

For the memory related question, see Memory protection. Again, the short answer is that this is supported by processor features, i.e., the operating system can set boundaries when loading a program leading to an interrupt when these boundaries are violated. Another important feature related to this are CPU modes.

To sum things up, in order to understand operating systems, it's also important to understand computer architecture, as many features of an operating system are based in corresponding features of processors. I always found the following a good introductory textbook: "Computer Organization and Design: The Hardware/Software Interface" by David Patterson and John Hennessy.

Finally, the following (Linux-specific) example might help. The usual

#include <stdlib.h>
#include <stdio.h>

int main(void) {
    printf("Hello, world!");
    exit(0);
}

will turn into assembler code as follows (more or less..., stolen from the Wikipedia article on Netwide Assembler)

; compile on 64-bit Linux using
; nasm -f elf syscall.asm
; ld -m elf_i386 -s -o syscall syscall.o

global _start

section .text
_start:
    mov eax, 4 ; system call number 4: write
    mov ebx, 1 ; file descriptor 1: stdout
    mov ecx, msg
    mov edx, msg.len
    int  0x80  ; Passes control to interrupt vector
                   ; invokes system call, in this case system call
                   ; write(stdout, msg, strlen(msg));

    mov eax, 1 ; system call number 1: exit()
    mov ebx, 0 ; exit status 0
    int 0x80   ; Passes control to interrupt vector
               ; invokes system call, in this case system call
               ; number 1 with argument 0, i.e., exit(0)

section .data
msg:    db  "Hello, world!", 10
.len:   equ $ - msg

Once actually compiled, this will look like (just the part between the first and last column, the rest is for illustration purposes, generated using xxd programName)

0000000: 7f45 4c46 0101 0100 0000 0000 0000 0000  .ELF............
0000010: 0200 0300 0100 0000 8080 0408 3400 0000  ............4...
0000020: cc00 0000 0000 0000 3400 2000 0200 2800  ........4. ...(.
0000030: 0400 0300 0100 0000 0000 0000 0080 0408  ................
0000040: 0080 0408 a200 0000 a200 0000 0500 0000  ................
0000050: 0010 0000 0100 0000 a400 0000 a490 0408  ................
0000060: a490 0408 0e00 0000 0e00 0000 0600 0000  ................
0000070: 0010 0000 0000 0000 0000 0000 0000 0000  ................
0000080: b804 0000 00bb 0100 0000 b9a4 9004 08ba  ................
0000090: 0e00 0000 cd80 b801 0000 00bb 0000 0000  ................
00000a0: cd80 0000 4865 6c6c 6f2c 2077 6f72 6c64  ....Hello, world
00000b0: 210a 002e 7368 7374 7274 6162 002e 7465  !...shstrtab..te
00000c0: 7874 002e 6461 7461 0000 0000 0000 0000  xt..data........
00000d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000f0: 0000 0000 0b00 0000 0100 0000 0600 0000  ................
0000100: 8080 0408 8000 0000 2200 0000 0000 0000  ........".......
0000110: 0000 0000 1000 0000 0000 0000 1100 0000  ................
0000120: 0100 0000 0300 0000 a490 0408 a400 0000  ................
0000130: 0e00 0000 0000 0000 0000 0000 0400 0000  ................
0000140: 0000 0000 0100 0000 0300 0000 0000 0000  ................
0000150: 0000 0000 b200 0000 1700 0000 0000 0000  ................
0000160: 0000 0000 0100 0000 0000 0000            ............

This is the thing (or rather, a binary representation thereof) the operating system loads into memory. We might also want to have a look at it with objdump -s -d programName which gives some more information

Contents of section .text:
 8048080 b8040000 00bb0100 0000b9a4 900408ba  ................
 8048090 0e000000 cd80b801 000000bb 00000000  ................
 80480a0 cd80                                 ..
Contents of section .data:
 80490a4 48656c6c 6f2c2077 6f726c64 210a      Hello, world!.

Disassembly of section .text:

08048080 <.text>:
8048080: b8 04 00 00 00       mov    $0x4,%eax
    8048085: bb 01 00 00 00       mov    $0x1,%ebx
804808a: b9 a4 90 04 08       mov    $0x80490a4,%ecx
    804808f: ba 0e 00 00 00       mov    $0xe,%edx
8048094: cd 80                int    $0x80
    8048096: b8 01 00 00 00       mov    $0x1,%eax
804809b: bb 00 00 00 00       mov    $0x0,%ebx
    80480a0: cd 80                int    $0x80

You see that this program has two system calls. The first one is write which outputs the "Hello, world!", the second one is the exit. These two system calls correspond to the int 0x80 in the assembler code that generates a software interrupt, see INT instruction and http://www.linfo.org/int_0x80.html Before making a system call via int 0x80 we need to tell the Linux, which system call we want (plus set up any other relevant parameters). System calls are identified by numbers, e.g. 1 is exit, 4 is write, see http://syscalls.kernelgrok.com/

Again, to sum this part up: System calls are translated into int 0x80 instructions (plus necessary parameter handling before that). Once the program runs and hits an int 0x80 instruction, the processor will give control to the operating systems interrupt handler which sees that it has to handle a system call and then does things accordingly.


Is L2 = {a^n| n is a product of one or more primes} regular?

According to the Fundamental Theorem of Arithmetic, any integer $>1$ can be written as a product of one or more primes (in a unique way).  So, it seems that your language can be simplified as $\{a^n\mid n\geq 2\}$.