Can a Multi-Tape Turing Machine have an infinite number of tapes?

You need a finite number of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.

Notice that it especially the number of heads should be bounded. Sure, you can use a 2d TM, however, there is still only one head in this model. If you would allow an infinite number of heads, then the configuration of a TM would be infinite. This will cause a lot of problems and would give a quite different model of computation.


Use of Myhill-Nerode Theorem to prove minimal number of states

You need to find $2^k$ words which belong to different equivalence classes of the Myhill–Nerode relation. Put differently, you need to find a collection of $2^k$ words such that for any two of them $x \neq y$ there is a word $z$ such that $xz \in L$ and $yz \notin L$ or vice versa.


One important thing to understand here is that the asymptotic analysis happens with respect to the parameters that are of interest to you. Here, for example, we are interested in the complexity with respect to the input $n$.

Typically, we assume that arithmetic operations (like the modulo or addition, etc) take a constant number of time. In a real system, one operation might indeed be more expensive than another. But, the important detail is that the time required by these operations does not depend on the input parameter $n$: it could be $1$, $100$, or $10^{\#\text{stars}}$, but it is still a constant as long as it does not scale with the parameter of interest.
So again, in summary, when we compute the asymptotic complexity of the function with respect to $n$, we can consider that all these operations take a constant time.

Based on the above, the code inside the for-loop also takes a constant time. Whether the condition is true or not is irrelevant. If it is false it will take some constant time, and if it is true it will take again some constant time (maybe more than before, but still constant).
Hence, overall, the time for one iteration is $\Theta(1)$.

Then, as you said, the overall complexity will be $\Theta(n) \cdot \Theta(1) = \Theta(n)$.


Their integrity is maintained by several features working in conjunction.

For synchronous code execution, function calls, i.e. invocations, generally require some management.  This management is named the calling convention.  Both caller and callee must agree on the same convention or else things break.  (It is possible for one caller and callee to agree, then have that callee, now play caller to call someone else, using an alternate calling convention they both agree upon.  This works but might make stack unwinding more complex for the debugger, or for error handling/exceptions.)  The calling convention dictates how parameters are passed (registers & stack), how return values are passed back, and certain registers don't participate in the invocation and are particularly designated for retaining their original caller-defined values across the call — meaning that if the callee want to use those designated registers it has to save them first, and then restore them before returning.

For asynchronous code execution of threads/processes, either the hardware provides multiple CPUs or the software is time-slicing the CPUs, or both.

If the hardware provides multiple CPUs (whether by hyperthreading or full blown CPUs), it provides sufficient register sets for all the CPUs, so it provides a  copy of the necessary processor state for each provided processors.  Some of the computation units may be shared (e.g. in hyperthreading), but the register state is duplicated.

When software (e.g. operating system) does time-slicing, it uses a clock or other interrupt to suspend one thread's operation, and resume another thread (that had may have been previously suspended in a similar manner).

The interrupt mechanism itself requires cooperation between hardware and software.  Generally speaking, the hardware provides the minimal features necessary, and leave the rest up to software — although on more modern processors, some features the software could do are taken over by the hardware so that operating systems don't require as much customization for new CPUs.

The interrupt mechanism was invented around the time of the DEC PDP-1 processor, ~1959, and was then called Sequence Break System.  Before that, processors ran mostly batch jobs and did I/O synchronously.  With the introduction of the interrupt mechanism, the processor can be signaled by an external connector to take an unscheduled branch to an interrupt handler aka interrupt service routine.  At every sequence point in the processors execution where it could service an interrupt, some hardware is checking that external pin to see if an interrupt is being requested.  A clock is one device that regularly interrupts, I/O devices also interrupt.  When an interrupt handler runs the hardware must preserve, minimally, any (register) state of the thread that it destroys in switching to the interrupt service routine, for example, the PC, since starting interrupt service routine is effected by making the CPU take an (unscheduled) branch.  This could be done by having two PC registers (one main one and a shadow one for remembering the old PC at time of interrupt) or by using some prearranged memory location to store the PC of the interrupted code.  Depending on the processor architecture some other shadow registers may be provided, like an alternate stack pointer.  These things would make the interrupt handler easier to program (though the initial handler still would have to be written in assembly, not even C).  Once the handler is running, it will save any other state for the interrupted thread, so that it can do some work using the CPU in a rather normal way, and still resume the interrupted thread later — maybe much later, after first giving some other threads a time slice.

Have a look at this answer for more information on the subject of interrupts.

See also MultiThreading on Single Core, and here Interrupts vs. Exceptions


Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?

Is what I wrote about big-O correct?

Yes.

  How do big-Theta sets relate to each other, if they relate at all?

They are a partition of the space of functions. If $\Theta(f)\cap \Theta(g)\not = \emptyset$, then $\Theta(f)=\Theta(g)$. Moreover, $\Theta(f)\subseteq O(f)$.

  Why do they relate to each other the way they do? The explanation is probably derivable from the formal definition of big-Theta (might be wrong here) and if someone could relate the explanation back to that definition it would be great.

A function $f$ is in $\Theta(g)$ if and only if there are constants $c_1,c_2>0$ such that $c_1 g(n)\leq f(n) \leq c_2g(n)$ for all sufficiently large $n$. Seeing that the above relation holds is a simple case of doing some substitutions:

Suppose there is some $a\in \Theta(f), a\in \Theta(g)$ and $b\in \Theta(f)$, then we know there exist constants such that (for sufficiently large $n$)

$c_1 f(n)\leq a(n) \leq c_2f(n)$

$c_3 g(n)\leq a(n) \leq c_4g(n)$

$c_5 f(n)\leq b(n) \leq c_6f(n)$

then

$c_5 c_3 g(n)/c_2 \leq c_5 a(n)/c_2 \leq c_5 f(n)\leq b(n)\leq c_6f(n)\leq c_6 a(n)/c_1\leq c_6c_4g(n)/c_1$

and thus $b\in \Theta(g)$.

  Is this also the reason why big-O is better for analysing complexity? Because it is easier to compare it to other runtimes?

It is not "better". You could say it is worse, because an algorithm being $\Theta(f)$ implies that it is $O(f)$ (but not vice-versa), so "$\Theta$" is a strictly stronger statement than "$O$".

The reason "$O$" is more popular is because "$O$" expresses an upper bound on the speed of an algorithm, i.e., it is a guarantee it will run in at most a given time. "$\Theta$" also expresses the same upper bound, but, in addition, also expresses that this upper bound is the best possible upper bound for a given algorithm. E.g., an algorithm running in time $O(n^3)$ can actually turn out to also run in $O(n^2)$, but an algorithm running in time $\Theta(n^3)$ can not also run in $\Theta(n^2)$ time.

From a practical perspective, if we want to know whether an algorithm is fast enough for a practical purpose, knowing it runs in $O(n^2)$ time is good enough to determine whether it is fast enough. The information that it runs in $\Theta(n^2)$ time is not really important to the practical use. If we have determined that an $O(n^2)$-time algorithm is fast enough for our application, then who cares if the algorithm that was claimed to be $O(n^2)$ is actually $\Theta(n)$?

Obviously, if you are going to give an upper bound on the running time of an algorithm, you will endeavor to give the best possible upper bound (there is no sense in saying your algorithm is $O(n^3)$ when you could also say it is $O(n^2)$). For this reason, when people say "$O$" they often implicitly mean "$\Theta$". The reason people write "$O$" is because this is easier on a normal keyboard, is customary, conveys the most important information about the algorithm (the upper bound on the speed) and people often can't be bothered to formally prove the lower bound.


Voronoi Diagram Drawing Variations and Charateristics

The Voronoi diagram of disjoint segments (b) has been thoroughly studied.

Image from GIS.

See:

  CGAL Manual, Chapter 43:
  2D Segment Voronoi Diagrams. CGAL link.

For the Voronoi diagram of circles (d), see:

  Jin, Li, Donguk Kim, Lisen Mu, Deok-Soo Kim, and Shi-Min Hu. "A sweepline algorithm for Euclidean Voronoi diagram of circles." Computer-Aided Design 38, no. 3 (2006): 260-272. Journal link.

  Huber, Stefan. Computation of Voronoi diagrams of circular arcs and straight lines. Magisterarbeit, 2008.

To quote the latter: "Lemma 1.4. The bisector between two circles (...) consists of ellipses and hyperbolas."
PDF download.


An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number

Take a look to knapsack problem.

Simple algorithm (not the optimal solution)

order the item descending
cut the n5/(x\x5) ("\" is integer division, i.e. 12\9=1) = 15 pipes to satisfy x5 = 9m and partially x1

Repeat step 2 for x3 = 7m and so on.


Is machine learning a subarea of expert systems?

That depends on your definition of an "expert system". Searching around, many definitions include a clear seperation between 'knowledge base' and 'inference rules', and machine learning most definitely does not always make this distinction.

In fact, unsupervised learning has no knowledge base whatsoever, and finds naturally occurring patterns in just unlabeled data.


The classic Hindley-Milner type inference algorithm requires each literal value to be unambiguously inferable to a type: 0 is an int, while 0.0 is a real. Haskell's type system has been enhanced to include a certain kind of bounded polymorphism, so that 0 can have any type that is a number (more precisely, of any type that is an instance of the Num type class: 0 is of type Num a => a).

See the wikipedia article on Hindley-Milner for further details on the algorithm (the article explanations are much better than anything I could write on that topic).


Getting speed difference between signal comparison using Dynamic Time Warping

There is no single "speed difference".  The way DTW works is that it checks whether you can find a match by slowing up and/or speeding up one of the signals.

For instance, suppose you want to match signal X to signal Y, which last 3 minutes.  It's possible that the best match might involve speeding up signal Y for the first minute, slowing it down for the second minute, and leaving its speed unchanged for the third minute.  Thus, there's no one speed, no one speed difference, and no simple answer to whether Y is faster than X or not.  Rather, the answer is: "faster in parts, slower in others".

Once you find the best match using DTW, you can easily recover in which parts Y was faster than X, and in which parts Y was slower than X.  I encourage you to do a bit more reading about how DTW works -- it'll probably all become clear as you understand the gist of the idea.


For each vertex of a tree count vertices closer than a specified value

As it is a contest problem, I will give you some tips which may be a good start point.

Consider an easier problem: the graph has a vertex $v$ and multiple paths going out of it (they are straight). Of course, the result for vertex $v$ is easy to compute (one DFS). Now try to use the binary search to find the result for remaining vertices (tip: make a sorted list of distances from $v$ to all the other vertices in whole graph and in each separate branch).
Now the real problem. Choose any vertex $v$. We can compute the result for it using usual DFS. What if we remove this vertex? Let's say we computed recursively the result in each of the generated subtrees. Then for each vertex $w$ other than $v$ we need to add the number of vertices $s$ outside the $v$-subtree containing $w$ (formally, vertices $s$ such that $d(s,w)\le L(w)$ and $s\to w$ path contains vertex $v$). Try to do it in total $O(n \log n)$ time using the experience from point (1.).
Can you choose such vertex $v$ in the graph such that the size of the subtrees after removing $v$ doesn't exceed half of the initial size? Assuming you can, prove that the total running time is $O(n \log^2 n)$.


how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

I don't think you're likely to find any such proof.  Given our current level of knowledge, as far as we know it is possible that $\textsf{P} \ne \textsf{NP}$ but $\textsf{NP} = \textsf{co-NP}$ (we cannot prove otherwise).  If that were true, then we'd have $\textsf{NPC} = \textsf{co-NPC}$ (and thus $\textsf{NPC} \cap \textsf{co-NPC} \ne \emptyset$)  yet $\textsf{P} \ne \textsf{NP}$.

See, e.g., Is the open question NP=co-NP the same as P=NP? and If NP $\neq$ Co-NP then is P $\neq$ NP.


Is this possible that quantum computer will be able to violate the Church thesis?

No.  A classical computer can compute anything a quantum computer can do, given long enough.  There are simple methods of simulation that cause an exponential slowdown, which suffices to show that if it is decidable on a quantum computer, it is decidable on a classical computer.  (We don't know whether the there might be other faster ways of simulating a quantum computer on a classical computer, but that doesn't affect decidability.)


As you pointed out, coherence is a property of an individual memory location while consistency refers to the order of accesses to all memory locations.  Sequential consistency is a strictly stronger property than coherence.  That is: every system that is sequentially consistent is also coherent at every memory location.  The opposite is not true, a memory that is coherent at every location is not necessarily sequentially consistent.  In fact, there are many real cache-coherent multiprocessors where the memory model is only weakly consistent (there are cases where different processors observe accesses to different locations happen in different orders.)

Proof of sequentially consistent implies coherent:

Given any trace from a sequentially consistent system, by definition that trace must have a total order that is agreed on by every processor in the system.  Now look at the accesses just to location $x$ in that trace.  Because a total order is transitive, the accesses just to location $x$ also have a total order on them that is agreed on by every processor in the system.  Thus all memory locations are coherent.

The reverse doesn't work out.  Consider two coherent memory locations $x$ and $y$ with just a single access to each $x_0$ and $y_0$.  All the processors agree on the order of accesses to location $x$ and all the processors agree on the total order of accesses to location $y$, but some processors may observe the order $x \rightarrow y$, while others may observe the order $y \rightarrow x$.  So coherence doesn't imply sequential consistency.

This can lead to surprising results.  For example

initially A=B=0
process 1               process 2
store A := 1            load B (gets 1)
store B := 1            load A (gets 0)

This trace is coherent:

for A the order is: proc2 loads A(gets 0), proc1 stores A:=1
for B the order is: proc1 stores B:=1, proc2 loads B(gets 1)

But it is not consistent! Since if proc2 load B returns 1, then proc1 store A := 1 already happened and proc2 load A should also return 1.


Extract Tree from multi-edge undirected graph

The problem is under-specified; nonetheless, I will try to help assuming that you are looking for the graph traversal tree.
To obtain such a tree, you can use a graph traversal algorithm such as breadth-first search. You can find a nice implementation of this algorithm in The Algorithm Design Manual by Steven Skiena.
Note that you need to adapt an important aspect of the algorithm:

Do not set a node as discovered unless the node has been visited from all of its incoming edges. Without this adaptation, each node will only be visited once, and, therefore, the behaviour of the algorithm will be the same as if multi-edges did not exist.

You will also need a data structure to store the tree of interest. In Skiena's implementation, this data structure is an array that is called parent: if node i is discovered from node j, then parent[i] = j.

The vertex that discovered vertex i is defined as parent[i]. Every vertex is discovered during the course of traversal, so, except for the root, every node has a parent. The parent relation defines a tree of discovery with the initial search node as the root of the tree.
Steven Skiena - The Algorithm Design Manual

However, note that you will need a slightly more complex data structure to support duplicated nodes.


Why does the GS1 DataMatrix encode diagonally instead of vertically or horizontally?

Not a full answer, but this AMS column considers the same question:
"The way in which bytes are stored as bitten squares might seem a bit peculiar, but if you think about how errors occur in the transmission of data matrices (for example poor printing, postage cancellation), it makes sense. The scheme is designed so that the minimum number of bytes are affected by such errors. Other features (the funny way in which `unrandomization' is applied) are not so clearly advantageous, and are pretty much a mystery to me."
http://www.ams.org/publicoutreach/feature-column/fcarc-data-matrix


Oh, I've found an $O(1)$ allocation strategy:
Because our memory is infinite, we may never deallocate: Just add memory at the end of the used space by incrementing a pointer.


The reverse of X[:i], the prefix of X up to the $i$-th position is equal to Y[n-i+1:], the suffix of Y from the $(n-i+1)$-th position onward.
Before the loop starts, which we could consider as $i=0$, we have that the reverse of the prefix of X of length zero is equal to suffix of Y of length zero.
Each step of the loop preserves the property for the previous value of i and makes the property true for the current value of i.
At the end of the loop the property is satisfied for i=n, which implies that the reverse of X is equal to Y.


Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary notation on its tape. Explain how it can count down from n to 0 in O(n) steps

Here is a rough sketch of how you can solve the second part.
Suppose that the number $n$ is of the form $2^k - 1$ for some non-negative integer $k$ and that the head of the Turing Machine is initially located at the end of the binary representation of $n$ (i.e., at the position of the rightmost, least significant, bit).
Proceed as follows:

While the current tape symbol is a $0$, replace it with $1$ and move the head to the left.
If the current symbol is $1$:

Replace the current symbol with a $0$
Move right until you reach the last non-blank symbol of the tape
Repeat from the beginning

Halt

In analyzing the time complexity, I will ignore the transitions that move right. This is because each of these transitions can be "charged" to a distinct transition that moved the head to the left, and we can safely ignore multiplicative constants in our asymptotic upper bound on the running time.
Notice how, once we ignore these transitions, at most a constant number of steps pass from the instant in which a TM flips a bit of the input tape, to the instant when the next bit flip happens. Then, to estimate the running time we can just count the overall number of bit flips.
Consider all values of $n$ from $2^k-1$ down to $0$, in this order.
The rightmost bit changes every time we move from one value to the next.
The 2nd to last bit changes every other time, the 3rd to last bit changes once every $4$ values, and so on.
In general, the $i$-th least significant bit changes once every $2^{i-1}$ values.
The total number of bit flips is then:
$$
n + \frac{n}{2} + \frac{n}{4} + \dots  = O\left(\sum_{i=0}^\infty \frac{2^k}{2^i}\right) = O(2^k) = O(n)
$$


Proving that L is not regular by showing that $\equiv_L$ has infinite index

Let me prove a stronger claim: every two words over $\{a\}$ are inequivalent with respect to your language. What this means is that for every $i \neq j$, there is a word $w \in a^*$ such that either $a^i w \in L$ and $a^j w \notin L$, or vice versa. Since $w \in a^*$, in fact $w = a^k$ for some $k$, and so we need to prove the following:

  If $i \neq j$ are natural numbers then there exists a natural number $k$ such that exactly one of $i+k,j+k$ is a power of 3.

Let $a_i$ be the smallest power of 3 which is at least $i$, and define $a_j$ similarly. If $a_i \neq a_j$, say $a_i < a_j$, then we can take $k = a_i$. So suppose $a_i = a_j = a$. Without loss of generality, $i < j$, and so $i+a < j+a$. The next power of 3 after $i+a$ is $3(i+a)$, and after $j+a$ is $3(j+a)$. Let $k = 2i+3a$. Then $i + k$ is a power of 3 by definition, but $j+a < j + k < 3(j+a)$ is not a power of 3.


What is the time complexity of this piece of code?

Let $f(n)$ be the answer for an input of size $n$.
then we have the following equation:

$f(n) = f(n - 1) + (n - 1)! * n = f(n - 1) + n!$

That's because you call the function for an input of size $n - 1$ which gives $f(n - 1)$, then you iterate over all permutations of size $n - 1$ which there are $(n -  1)!$ such permutations, and then you iterate over the position of the new element, which there are $n$ such positions. This gives us:

$f(n) = [\sum_{i=1}^n i!] < (n + 1)!$

You can easily prove this by induction.
So $f(n) = O((n + 1)!)$.


Functional Abbreviation for Inst Expression in Turing's 1936 Paper

The first part of the disjunction is for stating that the next "state/m-configuration" of the machine is the one established in $Inst(q_i, S_j, S_k, L, q_l)$ (in case z takes as value the next cell of y', i.e., y), the second part of the disjunct is used to say that the part of the tape not scanned by the machine preserves its value.


Relation between number of edges and vertices in a DAG

The maximum number of edges in a DAG with n vertices is $\Theta(n^2)$.

Refer https://stackoverflow.com/questions/11699095/how-many-edges-can-there-be-in-a-dag


Nearest Insertion Traveling Salesman Heuristic: is it faster to insert nearest nodes first?

Inserting a random point instead of a nearest point can be faster, but then you are not following the nearest insertion heuristic anymore. The key is to realize that the point is not the runtime efficiency of the algorithm, but rather the quality of the solution obtained. Indeed, remember that we are dealing with an NP-hard problem.

The nearest neighbor heuristic should return considerably shorter tours than random insertion. In fact, we can prove that the ratio of the nearest insertion heuristic's solution to the minimum tour length is bounded by $O(\log n)$, where $n$ is the number of cities. No such guarantee exists for the random insertion that you propose, i.e., such a heuristic can return very long tours.


How can we prove that $g = O(f) $ (Big-Oh notation)

I think you have the wrong definition for $\Omega$. When we write $g=Ω(f)$, informally this means that $g$ is bounded below by ${\displaystyle f}$  asymptotically. So, it is basically just the reverse way of saying $f=O(g)$, which means that $|f|$ is bounded above by ${\displaystyle g}$ (up to constant factor) asymptotically.

What you are describing is closest to the definition of Big theta $\Theta$.


Prove that $SEQ_{DFA}$ = {⟨A,B⟩ | A,B are DFAs and L(A) ⊆ L(B)} is decidable

There are several ways to prove that $SEQ_{DFA}$ is decidable. One of them is by using the fact that $EQ_{DFA}$ is decidable.

Assume that $L_1$ and $L_2$ are languages such that $L_1\leq_m L_2$ (that is, there is a mapping reduction from $L_1$ to $L_2$). It holds that if $L_2$ is decidable, then so is $L_1$. Hence,  in order to prove that $SEQ_{DFA}$ is deciadable, we reduce it to $EQ_{DFA}$. As hinted in the comment, we propose the following reduction.

The Reduction:
Let $C$ be a fixed DFA for the empty language, that is, $L(C) = \emptyset$. The reduction operates as follows. Given instance $\langle A= \langle Q_{A}, \Sigma, q^{A}_0, \delta_{A}, F_{A}\rangle, B= \langle Q_{B}, \Sigma, q^{B}_0, \delta_{B}, F_{B}\rangle\rangle$ of $SEQ_{DFA}$, the reduction computes a product automaton, $D$, for $L(A)\cap L(B)^C$ and outputs $\langle D, C\rangle$.
Correctness: $L(A)\subseteq L(B)$ iff $L(A)\cap L(B)^C = \emptyset$ iff $L(D) = \emptyset$ iff $L(D) = L(C)$. (the first equivalence mentioned in the comment is simple enough and thus is left for the reader).
Computability: the only non-trivial part is to compute $D$ given $A$ and $B$. We claim that $D$ is defined by $D = \langle Q_{A}\times Q_{B}, \Sigma, (q^{A}_0, q^{B}_0), \delta_{D}, F_{D}\rangle$. Where:

1) For every $(q, s)\in Q_{A}\times Q_{B}$ and $\sigma \in \Sigma$, $\delta_{D}$ is defined by: $$\delta_{D}((q, s),\sigma) = (\delta_{A}(q, \sigma), \delta_{B}(s, \sigma))$$

2) $F_{D} = F_{A}\times (Q_{B}\setminus F_{B})$.

Note that $D$ is a standard product automaton and thus for every finite word $w\in \Sigma^*$, we have that $\delta_{D}((q, s), w) = (\delta_{A}(q, w), \delta_{B}(s, w))$ (this can be proven by induction on $|w|$). Therefore, $w\in L(D)$ iff $\delta_{D}((q^{A}_0, q^{B}_0), w) \in F_{D}$ iff $(\delta_{A}(q^{A}_0, w),\delta_{B}(q^{B}_0, w) ) \in F_{A}\times (Q_{B}\setminus F_{B})$ iff $w\in L(A)$ and $w\in L(B)^C$ iff $w\in L(A)\cap L(B)^C$. Therefore $L(D) = L(A)\cap L(B)^C$ and thus we're done.


Find a sequence of integer powers faster than the naive algorithm

In the worst case, this seems to be optimal. If your $a_i$ are pairwise coprime,
e.g. $k$ different primes, they powers do not share any factors.

Of course, if $k$ is large but $c$ from your proposed restriction is small, there
may not be such a set; then, you powers share factors. You could exploit this
if you knew the shared factors for your $a_i$; but finding those is harder than
just computing all the powers.

So I daresay, no, you can not do this faster without more knowledge about the $a_i$.


Which type of control unit used in modern processor?

x86 are famous for using microcode, because there are a few complex operations, such as call gates or how the x87 calculates sines or exponentials, which cannot be reasonably constructed with a simple finite state machine. x86 also have very extensive patching resources, which allows to fix some bugs on released silicon, and which is probably handled through microcode (Some hints are probably in the patents from Intel and AMD).

Small ARM CPUs don't need and don't use microcode. The "R" and "M" classes.

High end ARMs such as Apple's... Who knows ? Besides the visible instruction set, there are also many hidden stuff, for example for debugging, self-testing the hardware and for power management, which may be based on microprograms.

The general trend nowadays, is that, even in x86, the instructions that need performance are decoded directly which is faster and more power efficient that fetching microcode memory.


Are all terms of type forall a. a operationally bottom?

Sure, just take R to be $\{(\bot,\bot)\}$, the relation which only relates bottoms.

This is a strict continuous relation, so it satisfies the requirements of the free theorem you linked to.


Progressive discrete multifunction optimization

There are two techniques that I suspect might be worth trying in this context:

Simulated annealing. Simulated annealing is a heuristic for optimization that works well when the objective function varies smoothly as a function of its parameters, based loosely upon some structure in the parameter space.  You can find a good discussion of how to use simulated annealing, in Steven Skiena's The Algorithm Design Manual.

In your context, you'll need some operations that tweak $S$ by a little bit.  Basically, you start from a specific choice of $S$ and then make small modifications, seeing which modifications increase the value of $\Phi(S)$, where $\Phi$ is the objective function.  When you find a $S'$ that increases the objective function, you keep that one and start modifying it.  This is basically hillclimbing.  Simulated annealing improves on that by doing random jumps to get out of local optima.

In your context, the objective function is

$$\Phi(S) = \sum_{f \in F} f(S).$$

There are many candidates for how to tweak $S$.  You could try adding a random element of $G$ to $S$ (or adding $k$ randomly chosen elements of $G$ to $S$) as one operation; removing a random element (or removing $k$ elements) as another operation; and so on.  Typically you take advantage of your domain knowledge to select a set of operations that might potentially make sense as "sensible" ways to vary $S$ by a little bit.  Then, you let the simulated annealing algorithm take over from there.

The useful thing about your context is that when you've found an optimal value of $S$ for functions $f_1,\dots,f_n$ (i.e., for objective function $\Psi(S) = f_1(S) + \dots + f_n(S)$), and then you later get an additional function $f_{n+1}$ to add to the set, now $S$ is a reasonable starting point to start the optimization process for $f_1,\dots,f_{n+1}$ (i.e., for objective function $\Psi'(S) = f_1(S) + \dots + f_{n+1}(S)$).  In particular, given your structure, we might expect that the optimum for $\Psi'$ might be "close" or "similar" to an optimum for $\Psi$, so the optimum for $\Psi$ is a good place to start the hill-climbing/simulated annealing for $\Psi'$.

To extend on that idea, you might also try remembering multiple values of $S$ from the previous round: say, sets $S_1,\dots,S_m$ that give the $m$ largest values of $\Phi(\cdot)$ that you encountered during your optimization with the objective function $\Psi$.  Now, when you add another function in the next round
and want to find an optimum for $\Psi'$, you could try starting from each of $S_1,\dots,S_m$ as candidate starting values for the hill-climbing / simulated annealing.  This might be effective in practice -- you'd have to try it out to see.
Memoization. Since computing $f(S)$ is very expensive, you might use memoization to ensure you never compute it more than once.  In particular, you might keep a hashtable with mappings $(f,S) \mapsto f(S)$, so that you never need to compute $f(S)$ for any particular combination of a function $f$ and a set $S$ more than once.  This might help you out.

Also, when starting the optimization process for the objective function $\Psi'$, you might try computing $\Psi'(S)$ for each $S$ such that you computed $\Psi(S)$ in the previous round. Since $\Psi'(S) = \Psi(S) + f_{n+1}(S)$, the memoization will ensure that (if you computed $\Psi(S)$ previously) $\Psi'(S)$ can be computed relatively efficiently: it only requires evaluating $f_{n+1}(S)$, since $f_1(S),\dots,f_n(S)$ will already be in the memoization table.

Finally, if you know anything more about the structure of the $f$'s, you might try looking into branch-and-bound style techniques.

Again, these are just ideas.  You are in the space of heuristics, so there are no guarantees.  You'll have to try out these techniques in your particular application domain to see how well they work.  In practice often you may need to try out different parameter settings and make some application-specific tweaks to these general techniques, so be prepared to experiment and try out different stuff.


Using backtracking to find all possible permutations in a string

Backtracking is a general algorithm "that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution." (Wikipedia).

So, basically, what you do is build incrementally all permutations. As soon as as you build a single permutation, you backtrack and build another one, and so on until you generate all $n!$ possible permutations, say, on $n$ symbols.

Example: $n=3$, $S=\{1,2,3\}$.

You start with $1$. Then you move forward an choose $2$ (since $1$ has already been chosen), and then you choose $3$. At that point you have built the first permutation $123$. Then you backtrack and select $3$ instead of $2$, then select $2$, and you have $132$. You backtrack again, but you have already used $2$ and $3$, so you backtrack again (one level up where), and choose $2$ instead of $1$, then you select $1$, and finally $3$, so you have $213$.
The following picture should clarify the basic idea:

In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.

As for implementation, the backtracking is usually implemented using recursive call(s) as in your example. I assume that you have necessary programming skills to implement this basic idea yourself, in particular solving problems using recursive calls.


How to get the expected running time of an algorithm

Usually you assume uniform distribution on inputs which share a certain parameter.
You could assume uniform distribution on e.g.

All inputs of length $n$, e.g. if your input looks like $w_1\#\dots\#w_k$, where $w_i\in\{0,1\}^*$, $n=k-1+\sum_{i=1}^k|w_i|$.
All multisets (bags) of $n$ integers up to $k$
All $n$-tuples of integers integers up to $k$ (different,since e.g. $\{1,2\}_b$ corresponds to $(1,2)$ and $(2,1)$ and $\{1,1\}_b$ only to $(1,1)$)

You can combine this with an assumption about the distribution of the parameter, say the size $n\sim \mathrm{Geo}(0.5)$. However, this is unusual, most would consider the limit of probabilities as your parameter $n\rightarrow\infty$ instead.

If you choose 3, the probability of no repeated numbers can be calculated this way:
There are different $\binom{k}{n}$ sets of size $n$ and each set corresponds to $n!$ $n$-tuples. There is a total number of $k^n$ $n$-tuples, so
$$P(\text{no repeated number})=\frac{\binom{k}{n}\cdot n!}{k^n}$$


Iterative Fibonacci algorithm correctness proof, finding loop invariants

It kind of depends on what formalism you want to use for this proof.. But the core-idea which holds for pretty much any such formalism is the following:

Suppose you establish some invariant $I$ you will want to be able to make the following conclusion

$$
m < 3 \land I \implies X
$$

where $X$ tells you that the values $i,j$ and $k$ have the right values.

You are on the right track with the argument $I = I' \cup \{ m = n \mod 3 \}$, however $I' = \{m \geq 0\}$  is way too weak to establish that $\texttt{Fib}(n)$ returns the $n$th Fibonacci number.

Try the following:

Find some existential (for some value, eg. $z$) claim about the relationship of $n$ and $m$ (seems like you already did so)
Now use that value $z$ to show $\{ k = F_z, i = F_{z-2}, j = F_{z-1} \}$1

I hope this will help you!

1: Depends on your claim about $m$ and $n$, could also be shifted $\{ k = F_{z+2}, i = F_z, j = F_{z+1} \}$ as in gnasher729's answer which is simpler. The core idea is the same.


Formalisms in concurrent and/or distributed programming?

The most widely used formalism is the $\pi$-calculus by Milner, Parrow and Walker. It is an extension of CCS, and comes in many variants, some of which (the asynchronous $\pi$-calculus) attempt to be a formalisation of the actor model. There are now many typing disciplines for $\pi$-calculi, the simplest of which are probably Honda's session types. Such types are slowly diffusing from research papers to research implementations.


Trouble finding average case of a find max algorithm

Let me start with your main question "where my mistake took place exactly?" - in short, the whole point is in the wrong choice of the probability distribution  for $Pr(t_n=t)$. You are considering the number of changes in the maximum, i.e. how many times maxNum was updated, but you are using probabilities for the  location the maximum in the array.
Before starting analysis, let me say, that, for example, CLRS  Introduction to Algorithms, Third Edition, on page 120, calls formula you are using "cumbersome" for calculating and choose indicator function way. Donald Ervin Knuth in TAOCP Volume 1, Third Edition, 1997, pages 96-101 are using generating functions mechanism.
Now in more detail: for simplicity, let's consider the case when you have only 4 elements in the array and let us consider only such 4s in which all elements are different i.e. $(a, b, c, d)$, where all are different. I bring the pseudocode for this case from the book  Jeffrey J. McConnell, Analysis of Algorithms: an Active Learning Approach , 2001, page 3
maxNum = a
if b > maxNum then
    maxNum = b
end if
if c > maxNum then
    maxNum = c
end if
if d > maxNum then
    maxNum = d
end if
return maxNum

where your loop is simply decomposed into separate lines and in 1-st line is not used negative infinity. As we are considering function $T$ the number of maxNum updatings, i.e. number of assignements, then, obviously $T$ have values 1,2,3,4. Probability distribution for $T$ can be counted directly and is
$Pr(T=1)$: $\frac{1}{4}=\frac{4}{16}$
$Pr(T=2)$: $\frac{1}{4}+\frac{1}{4}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{7}{16}$
$Pr(T=3)$: $\frac{1}{4}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{4}{16}$
$Pr(T=4)$: $\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{1}{16}$
Anticipating the question of how these calculations were obtained, let me say that it is enough to simply consider the possible options for finding the maximum in the all fours and count their fractions.
To calculate general case, where we have $n$ elements in array it's more easy to find reccurence relation for $T(n)$:
$$T(n) = n \cdot T(n-1) + (n-1)!$$
and from here obtain expected value
$$\frac{ T(n)}{n!} = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n-1} + \frac{1}{n} = \sum_{i=1}^{n}\frac{1}{i} - 1 =\\
= \ln n + \gamma + \varepsilon_{n} -1 = \ln n +O(1)$$
where $\gamma$ is Euler–Mascheroni constant and $\varepsilon_{n} \sim \frac{1}{2n}, n\rightarrow \infty$.
Addition.
Now more about calculating probabilities in case of 4s $(a, b, c, d)$  where all are different:
The proportion of such fours in which the maximum is in the first place, i.e. maximum is $a$, is equal to the proportion of such fours in which the maximum is in second place , i.e. maximum is $b$, and is $\frac{1}{4}$. Same for cases with $c$ and $d$.
Such fours where maximum is $a$ and only they gives $1$ assignement for maxNum, i.e. $T=1$,  and so we obtain $Pr(T=1)$: $\frac{1}{4}=\frac{4}{16}$.
Such fours where maximum is $b$ gives $2$ assignements, $T=2$, but we can obtain $2$ assignements also from cases where $c$ or $d$ is maximum, so we can say, that $Pr(T=2)$ includes $\frac{1}{4}$ plus some more numbers i.e. we obtain first summand for $Pr(T=2)$.
Now let's take fours where maximum is $c$. This case can produce values $2, 3$ for $T$: when $b \gt a$, then $T=3$ and when $b \lt a$, then $T=2$. As proportion for both is $\frac{1}{4}\cdot \frac{1}{2}$, then we obtain second summand for $Pr(T=2)$ and first summand for $Pr(T=3)$.
Last we consider 4s where maximum is $d$. Hope it's easy to understand, that here we have $4$ parts with equal proportion $\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}$: 1) $b \gt a, c \gt b$ which gives $T=4$, 2) $b \gt a, c \lt b$ and $b \lt a, c \gt a$ which gives $T=3$, 3)$b \lt a, c \lt a $ which gives $T=2$. Correspondingly we obtain all remained summands.
At end let me say, that it's easy to write code for some virtual experiment, for example on python from random import uniform, I can share if needed, and check, that practical frequences approximates theoretical probabilities.


If $A \leq B$, $B \leq \overline{A}$, and $B$ is r.e., is $A$ recursive?

Notice that $A \leq B \leq \overline{A}$. Since $B$ is r.e., $A$ is r.e., hence $\overline{A}$ is co-r.e. Since $A \leq \overline{A}$, $A$ is also co-r.e. Hence $A$ is recursive.


Do Karnaugh maps yield the simplest solution possible?

Karnaugh maps do not always give the simplest expression possible, but they do always give the simplest "Sum of Products" expression possible (https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html).


Your first problem is $\mathsf{NP}$-Complete. Membership to $\mathsf{NP}$ is trivial. To see that it is $\mathsf{NP}$-hard, you can reduce it from Subset Sum. Let $\langle S_1, W_1 \rangle$ be an instance of Subset Sum. Define $S_2$ as the multiset obtained by multiplying each number in $S_1$ by $100$, and $W_2 = 100 W_1$. The instance for your problem is $\langle S_2, W_2 \rangle$.

If there is a set $C_1 \subseteq S_1$ such that $\sum_{x \in C_1} x  = W_1$, then let $W'$ be the sum of the elements in corresponding subset for $S_2$. We have $W' = \sum_{x \in C_1} 100x = 100 \cdot W_1 = W_2 \in \left[W_2-10, W_2+10\right]$.

If there is a set $C_2 \subseteq S_2$ such that the sum $W' = \sum_{x \in C_2} x$ of its elements satisfies $W_2-10 \le W' \le W_2+10$, then pick $y   = W' - W_2$, so that $W'  = W_2 + y$ and $y \in [-10, 10]$.
We must have $y=0$ since $W' = W_2 + y = y \pmod{100}$ and $W'$ must be a multiple of $100$. This shows that $W' = W_2$  and that the corresponding subset of $S_1$ has a sum of $\sum_{x \in C_2} \frac{x}{100} = \frac{W'}{100} = \frac{W_2}{100} = W_1$.

Your second problem is already known to be $\mathsf{NP}$-Complete even when when no vertex occurs in more than three triples. See problem SP1 in  "Garey & Johnson, Computer and intractability: a guide to the theory of NP-completeness".


Let $G$ be a graph with $2n$ vertices, and choose any node $v$. The edges touching $v$ have weight $n$, and all other edges have weight $-1$. Note that any Hamiltonian cycle in $G$ will have two edges touching $v$ (which add up to $2n$) and $2n-2$ edges of weight $-1$, so the total weight of the cycle is exactly $2$.
Therefore, if $G$ has a hamiltonian cycle, it has a cycle of weight exactly $2$.
Moreover, assume $G$ has a cycle of weight exactly $2$. Such a cycle can either include $v$ or not. If it doesn't include $v$, all its edges will be negative, contradicting a total weight of $2$. If it includes $v$, then it must include two edges of weight $n$, and thus the remaining part of the cycle must be a path, using only edges of weight $-1$, and with total weight equal to $-2n+2$. That meeans such a path must contain $2n-2$ edges, and therefore have $2n-1$ nodes. When connecting said path to-and-from $v$, you have a Hamiltonian cycle.
This means that if you could decide in polynomial time whether $G$ has a cycle of weight $2$ (which is a fixed constant), you could decide whether it has a Hamiltonian cycle in polynomial time.


Markov Model to compute the probaility on the $n^{th}$ day

Yes, you just add up the probabilities of all the possibilities. However, there's a conceptually clearer way of doing it that's less error-prone.

The transition matrix tells you the probability of moving from one state to another in one step.  The probability that it rains the day after tomorrow given that it's nice today is, as you've seen, given by
$$\Pr(N\to N)\,\Pr(N\to R) + \Pr(N\to R)\,\Pr(R\to R) + \Pr(N\to S)\,\Pr(S\to R)\,.$$
If you look at this closely, you'll see that it's exactly the (Nice, Rain) entry of the square of the transition matrix.  Similarly, the $n$th power of the transition matrix tells you the probability of moving between two states in $n$ steps.

Powers of the transition matrix can be computed efficiently with repeated squaring – for example $M^7 = (M^2)^2\times M^2\times M$ and there's the bonus that you get all the $n$-step probabilities instead of just one.


Best data structure for a queue with random reads?

Take any dictionary data structure and link its entries in whichever order suits you. In essence, you retain the $\Theta$-costs from the basic structure.

In search trees, this is called threading. It gives you constant-time access to the first and last element, respectively, and maintaining the threading takes only constant-time overhead for each dictionary or queue operation. As a consequence, you get $\Theta(\log n)$ access by key, $O(1)$ access to front and back of the queue (without modification), and $\Theta(\log n)$ insertion and deletion.

If you use hashtables you get $O(1)$/$\Theta(n)$ (AC/WC) access by key, $O(1)$ access to front and back of the queue (without modification), and $O(1)$/$\Theta(n)$ (AC/WC) insertion and deletion. The usual caveats apply.


Is detecting "doubly" arithmetic progressions 3SUM-hard?

This is an open problem.

Possibly some weak form of 3SUM-hardness could be proved by adapting a result from Mihai Pătrașcu's STOC 2010 paper "Towards Polynomial Lower Bounds for Dynamic Problems".  First, let me define a sequence of closely related problems.  The input to each problem is a sorted array $A[1..n]$ of distinct integers.

3SUM: Are there distinct indices $i,j,k$ such that $A[i] + A[j] = A[k]$?
Convolution3SUM: Are there indices $i<j$ such that $A[i] + A[j] = A[i+j]$?
Average: Are there distinct indices $i,j,k$ such that $A[i] + A[j] = 2 A[k]$?
ConvolutionAverage: Are there indices $i<j$ such that $A[i] + A[j] = 2A[(i+j)/2]$? (This is the problem you're asking about.)

In my PhD thesis, I proved that all four of these problems require $\Omega(n^2)$ time in a decision-tree model of computation that allows only queries of the form "Is $\alpha A[i] + \beta A[j] + \gamma A[k] + \delta$ positive, negative, or zero?", where $\alpha,\beta,\gamma,\delta$ are real numbers (that don't depend on the input).  In particular, any 3SUM algorithm in this model must ask the question "Is $A[i] + A[j]$ bigger, smaller, or equal to $A[k]$?" at least $\Omega(n^2)$ times.  That lower bound doesn't rule out subquadratic algorithms in a more general model of computation — indeed, it is possible to shave off some log factors in various integer RAM models.  But nobody knows what sort of more general model would help more significantly.

Using a careful hashing reduction, Pǎtrașcu proved that if 3SUM requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then Convolution3SUM requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time.  Thus, it's reasonable to say that Convolution3SUM is "weakly 3SUM-hard".  For example, if Convolution3SUM can be solved in $O(n^{1.8})$ time, then 3SUM can be solved in $O(n^{1.9})$ time.

I haven't ground through the details, but I'd bet that a parallel argument implies that if Average requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then ConvolutionAverage requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time.  In other words, ConvolutionAverage is "weakly Average-hard".

Unfortunately, it is not known whether Average is (even weakly) 3SUM-hard!  I suspect that Average is actually not 3SUM-hard, if only because the $\Omega(n^2)$ lower bound for Average is considerably harder to prove than the $\Omega(n^2)$ lower bound for 3SUM.

You also ask about the special case where adjacent array elements differ by less than some fixed integer $K$.  For 3SUM and Average, this variant can be solved in $O(n \log n)$ time using Fast Fourier transforms as follows.  (This observation is due to Raimund Seidel.)

Build a bit vector $B[0..Kn]$, where $B[i]=1$ if and only if the integer $A[1]+i$ appears in the input array $A$.  Compute the convolution of $B$ with itself in $O(Kn\log Kn) = O(n\log n)$ time using FFTs.  The resulting array has a non-zero value in the $j$th position if and only if some pair of elements in $A$ sum to $2A[1] + j$.  Thus, we can extract a sorted list of sums $A[i]+A[j]$ from the convolution in $O(n)$ time.  From here, it's easy to solve Average or 3SUM in $O(n)$ time.

But I don't know a similar trick for Convolution3SUM or ConvolutionAverage!


Can parameters other than $n$ be always ignored in big $O$ notation?

In general you cannot erase things. A bivariate function $f$ is $O((n+k)\log n)$ if there exists a constant $C>0$ such that for all legal settings of the parameters $n,k$, we have $f(n,k) \leq C(n+k)\log n$. Here a setting of parameters is legal if it can actually happen – for example, if $V,E$ are the number of vertices and edges in a simple graph, then we always have $E \leq V(V-1)/2$, any other setting being illegal. If in some context you know that $k \leq Bn$, then in that context (which restricts the set of legal settings of parameters) $f = O(n\log n)$. In any other context, you cannot drop the $k$.

In your particular case, the Bentley–Ottmann algorithm, it is generally not the case that $k = O(n)$, and so $k$ cannot be dropped.


What are the strongest known type systems for which inference is decidable?

[EDIT: Voilà a few words on each]

There are several ways of extending HM type inference. My answer is based on many, more or less successful, attempts at implementing some of them.
The first one I stumbled upon is parametric polymorphism. Type systems trying to extend HM in this direction tend toward System F and so require type annotations. Two notable extensions in this direction I came across are :

HMF, it allows type inference for all System-F types, which means that you can have universal quantification "in the middle" of a type, their appearance is not implicitly situated at the highest scope like for HM polymorphic types. The paper clearly states that no clear rule exists as to how many and where type annotations may be needed. Also the types being those of System F, terms usually don't have a principal type.
MLF is not only an extension of HM, it's also an extension of System F that regain the principal type property of HM by introducing a kind of bounded quantification over types. A comparison has been made by the authors, MLF is strictly more powerful than HMF and annotations are only required for parameters used polymorphically.

Another way of extending HM is through variation of the constraint domain.

HM(X) is Hindley-Milner parameterised over a constraint domain X. In this approach, HM algorithm generates the constraints that are sent to a domain solver for X. For the usual HM, the domain solver is the unification procedure and the domain consists of the set of terms build from the types and the type variables.
Another example for X could be constraints expressed in the language of Presburger arithmetic ( in which case type inference / checking is decidable ) or in the language of Peano arithmetic ( no longer decidable ). X varies along a spectrum of theories, each with its own requirements regarding the amount and localisation of type annotations needed and ranging from not at all to all of them.
Haskell's type classes are also a kind of extension of the constraint domain by adding type predicates of the form MyClass(MyType) ( meaning that there exists an instance of MyClass for the type MyType ).
Type classes preserve type inference because they are basically an (almost) orthogonal concepts they implements adhoc polymorphism.
As an example, take a symbol val of type val :: MyClass a => a for which you can have instances MyClass A, MyClass B etc. When you refer to that symbol in your code, it's actually because type inference is already performed that the compiler can infer which instance of the class to use. This means that the type of val depends on the context in which it is used. That's also why running a single val statements leads to an ambiguous type error : the compiler can't infer any type based on the context.

For more advanced type systems like GADTs, type families, Dependent types, System (F)ω, etc., type are not anymore "types" they become complex computational objects. For example it means that two types not looking the same are not necessarily different. So type equality becomes not trivial ( at all ).

To give you an example of the actual complexity let's consider the dependent type of list : NList a n where a is the type of objects in the list and n is its length.
The append function would have type append :: NList a n -> NList a m -> NList a (n + m) and the zip function would be zip :: NList a n -> NList b n -> NList (a, b) n.
Imagine now we have the lambda \a: NList t n, b: NList t m -> zip (append a b) (append b a). Here the first argument of zip is of type NList t (n + m) and the second of type NList t (m + n).
Almost the same, but unless the type checker knows that "+" commutes on natural numbers, it must reject the function because (n + m) is not literally (m + n). It's no longer about type inference / type checking, it's about theorem proving.

Liquid types seem to be doing some dependent type inference. But as I understand it, it's not really dependent type, more something like usual HM types on which additional inference is made to compute static bounds.

I hope this helps.


Dijikstra's algorithm with "hull" value catch

Use the product construction to build a graph on $NK$ vertices and $MK$ edges, where each vertex records both which island you are at and how much hull you have left.  Then, use Dijkstra's algorithm on that graph.  The graph can be built on the fly and does not need to be constructed explicitly.


Can we easily check if we can place two not-intersecting circles inside a convex polygon

Let $P$ be the given polygon. Let $Q$ be the set of points inside $P$ whose distance to the boundary of $P$ is at least $r$. Your requirement can be met iff the diameter of $Q$ is at least $2r$. Indeed a radius $r$ circle lies inside $P$ iff its center is in $Q$, and two such circles are disjoint iff the distance between their centers is at least $2r$.

The problem of finding $Q$ is called inward polygon offsetting. That link has a lot of discussion about the general case, but it should be much simpler when $P$ is convex.

Suppose the vertices of $P$ are $p_1,\ldots,p_n$ in counterclockwise order. Let $R$ denote rotation counterclockwise by $90^\circ$. Let $n_i$ be the outward unit normal vector to edge $p_ip_{i+1}$, namely $n_i=R(p_i-p_{i+1})/|R(p_i-p_{i+1})|$. Let $e_i$ denote this edge shifted by $r$, namely the line from $p_i-rn_i$ to $p_{i+1}-rn_i$. Now we can iteratively construct a path $q$ which will become the boundary of $q$. In iteration $1$, let $q=e_1$. In iteration $i$, find the intersection of $q$ with $e_i$, discard the part of $q$ after the intersection and append the part of $e_i$ after the intersection (we should look for the intersection starting from the end of $q$; the more segments we have to check, the more vertices we can discard, so the algorithm will still be $O(n)$). After $n$ iterations, find where $q$ intersects itself and discard excess vertices to obtain a closed path; this is the boundary of $Q$.

Once we have $Q$, we can find its diameter using the Rotating calipers algorithm.


There are basically two possible types of derivations:

Ones that start $S \to^* X^naY^n$.
Ones that start $S \to^* X^nbY^n$.

Derivations of the first type will produce $a^{2n+1}$, those of the second type will produce $b^{n+1} a^n$.


Efficient algorithm to compute the minimum of multiple piecewise linear functions

This is basically an instance of the line segment intersection problem.  One standard approach is to use a sweep line algorithm.  For instance, the Bentley-Ottman algorithm would be a reasonable choice, and is not too difficult to implement.

At each iteration of the algorithm, we have some value of $x$, and we calculate what is the next largest value of $x$ where something interesting happens.  Here, "something interesting" is either (1) two pieces intersect each other at a point, or (2) we reach the end of one of the current pieces.  Then we advance $x$ to this next value.

At each iteration, we keep track of which pieces are currently active (i.e., $x$ is within the domain of that piece) and the order of the pieces, ordered by their $y$-value for that particular value of $x$.  Store them in sorted order, sorted by $y$-value.

All of the interesting bit is in how we determine the next largest value of $x$ where "something interesting" happens.  Fortunately, this is easy.  For each pair of adjacent active pieces (adjacent in their sorted order), we can find whether they intersect and where, and if it corresponds to a larger value of $x$, add it to a priority queue.  Also, for each active piece, we can add its right endpoint (the largest value of $x$ in its domain) to the priority queue.  Then finding the next "interesting" value of $x$ amounts to an ExtractMin operation on the priority queue.  Also, when you move to the next largest interesting value of $x$, it's easy to update the set of active pieces and maintain them in sorted order.

Let $n$ denote the total number of pieces among the $f_i$'s, and $k$ the total number of intersections between pieces.  Then each iteration can be implemented in $O(\lg n)$ time, and the number of iterations can be upper bounded by $O(n+k)$, so the running time will be $O((n+k) \lg n)$.


This is a very general trick, which can be used for other purposes than hashing. Below I give an implementation (in pseudo-code).

Let three uninitialized vectors $A$, $P$ and $V$ of size $n$ each. We will use these to do the operations requested by our data structure. We also maintain a variable $pos$. The operations are implemented as following:

init:
  pos <- 0

set(i,x):
if not(V[i] < pos and P[V[i]] = i)
  V[i] <- pos, P[pos] <- i, pos <- pos + 1
A[i] <- x

get(i):
if (V[i] < pos and P[V[i]] = i)
  return A[i]
else
  return empty

The array $A$ simply stores the values that are passed through the $set$ procedure. The arrays $V$ and $P$ work as certificates that can tell if a given position in $A$ has been initialized.

Note that at every moment the elements in $P$ ranging from $0$ to $pos-1$ are initialized. We can therefore safely use these values as a certificate for the initialized values in $A$.
For every position $i$ in $A$ that is initialized, there is a corresponding element in the vector $P$ whose value is equal to $i$. This is pointed by $V[i]$. Therefore, if we look at the corresponding element, $P[V[i]]$ and its value is $i$, we know that $A[i]$ has been initialized (since $P$ never lies, because all the elements that we're considering are initialized). Similarly, if $A[i]$ is not initialized, then $V[i]$ may point either to a position in $P$ outside the range $0..pos-1$, when we know for sure that it's not initialized, or may point to a position within that range. But this particular $P[j]$ corresponds to a different position in $A$, and therefore $P[j] \neq i$, so we know that $A[i]$ has not been initialized.

It's easy to see that all these operations are done in constant time. Also, the space used is $O(n)$ for each of the vectors, and $O(1)$ for the variable $pos$, therefore $O(n)$ in total.


Are there search problems that cannot be written as decision problems?

In terms of decidability, they are equivalent. Indeed, in order to turn a decision problem into a search problem we do the following:

Run the decision algorithm
If it outputted "no", return "no solution exists"
Else, create a list called $Active$, and a counter $w\in\Sigma^*$.
Until you find a solution, repeat the following 5-6 steps:
Create a new instance of an algorithm that checks whether $w$ is a valid solution, and add this instance to $Active$.
For every instance in $Active$, run the algorithm one more step. If any one of them returned "true", return the $w$ associated with it. Otherwise, increase the counter $w$ by one.

Intuitively, the word $w$ enumerates over all $\Sigma^*$, and for each one we check wether it is a valid solution. Since the decision algorithm must have returned "true", there is a valid solution, say $w^*$. Since $w$ enumerates over all $\Sigma^*$, then it will also go through $w^*$ and thus will find the valid solution.

In terms of computation time, the two might differ. It depends on the language itself, and on the granularity of the time complexity you are trying to achieve. For example, $SAT$ has a known search to decision reduction that runs in polynomial time. This means that you can solve the search problem by a polynomial factor of the decision problem. But it wont help you if you are looking for a sub-polynomial factor instead.


Call by need compared to pass by function

Call-by-need is more than call-by-name.  Call-by-name is syntactic sugar for wrapping a closure (thunk) around each argument and then passing the pointer to the closure.  Your example shows what call-by-name turns into under the covers.

Call-by-need goes one step further by memoizing.  If an argument is used twice in a function then the thunk corresponding to that argument is only evaluated once, the result is stored, and then on the second (and after) use of that argument the stored value is returned instead of paying the cost of reevaluating the function.

This only works because Haskell is pure functional.  That means that every function call always returns the same result for the same inputs.  With a language with any mutation you can't make this guarantee, so it is much harder to do call-by-need automatically.  SML allows mutation.


Writing a regular grammar for a regex of decimals

Regular grammars (of the right-regular variety) are essentially equivalent to NFAs, in the sense that they include roughly the same information. Once you convert your regular expression to an NFA, you can easily construct from it a right-regular grammar.

What doesn't seem possible is adapting your logic to construct a regular grammar. Unfortunately, there is no simple way to convert an arbitrary context-free grammar to a regular one; indeed, it is undecidable to determine whether a given context-free grammar corresponds to a regular language.


Binary subtraction with numbers in 2's complement

You cannot represent –173 using 8 bits, since the range is –128 to 127.
To subtract two numbers in two's complement, you use the identity $a - b = a + (-b)$. In your case, $a = 10100110$, $b = 01010011$, and $-b = 10101101$. Adding $a$ and $-b$, there is overflow, so you know that the number is outside the range.


Does Assembly Language depend on an Assembler or the family of processor?

Q0: > does that mean that the family of processors doesn't define an Assembly Language but it is rather the Assembler that we use since it actually parses the code?

It's not the processor/family that defines the detailed syntax of the assembly language for a particular CPU - the Assembler program is what defines the assembly language it accepts. You can have two different/incompatible assembly languages for the same processor/family.

Of course the CPU itself will determine what concepts are needed in the assembly language - e.g. 16 registers or 8, of different sizes, etc.

Q1: So for the same processor we can have two different Assembly Code which when assembled using the right assembler can produce the same Machince Code?

Yes. "right assembler"=>"corresponding assembler"

Q2: So let's say I have a PC running another family of processor (ARM) and write an Assembly Code and assemble it by MASM which produces machine code compatible for the 80386 processor. Now, without executing, it I copy the machine code over to another PC with the 80386 processor, would the code run Okay?

No, because the machine code is processor-/family-specific and you are copying between different processor/family

Q3: If I have two PCs with 80386 processors, one running Windows & the other linux. If I use MASM to assemble a source code on Windows for the 80386 processor, why then, when I copy the machine code over to Linux, it won't execute? Both PCs are running the same processor and machine code is the same! How does OS come into play here? (Please assume no OS specific API function has been used)

At a low level the generated binary code of e.g. an instruction to move a constant into a register is obviously compatible between these two PCs because it is aimed at the same processor/family.

HOWEVER even if it isn't obvious in the assembly code you write, when turned into a binary this is inevitably tightly related to the Operating System - all useful executable programs rely on many Operating System services and these are not the same between your two PCs, so the program won't run in any meaningful way. Maybe it might be possible for the ultra pedantic to come up with a raw binary which could be run on any operating system, but if it's independent of the operating system then it couldn't do anything useful like input or output which is provided by the OS, so while it might prove a point, that point wouldn't actually be very useful.


Bytes from integer using bitwise operators

Contrary to what you think, extracing bytes by shifting and masking is completely unrelated to the storage order (both little-endian and big-endian storage schemes exist and don't influence the results).

An int variable is represented by 32 bits. The least significant byte is made of the eight least significant bits and you obtain them by

i & 0xFF
0b 111111111 0101010 01010101 000000000 => 0b 00000000 00000000 00000000 00000000

The neighboring byte is made of the eight neighboring bits; you discard the eight least significant bits by shifting (>>), then mask out:

(i >> 8) & 0xFF
0b 11111111 10101010 01010101 000000000 => 0b 00000000 00000000 00000000 01010101

And similarly for the remaining two bytes, with shifts of 16 and 24 (most significant byte).

Notice that I cared not to use the terms left/right and first/last, which are meaningless as they refer to some graphical representation or memory storage order. In the examples, the numbers are understood as binary numbers written with lsb on the right (and spacers for clarity), which is the most common convention.


Short answer. The language $L_1$ is clearly regular. Further, $L_3 = L_1L_2^{-1}$ is a quotient of $L_1$ and hence it is regular since the quotient of a regular language by any language (regular or not) is regular. So you don't care about $L_2$, but you do care about $L_1$.

More details. Let $L$ and $R$ be languages. Then $LR^{-1} = \{ u \in A^* \mid ur \in L \text{ for some }r \in R\}$. Therefore $LR^{-1} = \bigcup_{r \in R} Lr^{-1}$. If $L$ is regular, there are only finitely many languages of the form $Lr^{-1}$, each of which is regular (this is the dual form of Nerode's lemma) and hence $LR^{-1}$ is a finite union of regular languages and thus it is regular.


Assign few binary variables to make all polynomials identically zero

I'll propose two algorithms.
SAT
Every binary multivariate polynomial $f$ can be represented in the form
$$f(x) = \sum_{S \in \mathcal{F}} \prod_{i \in S} x_i,$$
where $\mathcal{F}$ has one set per monomial of $f$, representing the variables included in that monomial.  A multivariate function is identically zero iff all monomials have coefficient 0.  So, we can express your problem as follows.
Let us represent the partial assignment by sets $M$,  where $M$ indicates the set of variables that are are assigned and $v$ their values, and $\overline{M} = \{1,2,\dots,100\}\setminus M$ the complement of $M$.  Then the condition is that after we make the partial assignment and simplify by collecting monomials, all monomials must have coefficient zero.  This can be represented as
$$\Phi(M,v) = \bigwedge_{R \subseteq \overline{M}} \bigg[ \sum_{\substack{S \in F,\\S\cap \overline{M}=R}} \prod_{i \in S \cap M} v_i = 0 \bigg].$$
That's a huge logical formula, but it can be equivalently expressed with fewer clauses as
$$\Phi(M,v) = \bigwedge_{S \in \mathcal{F}} \bigg[ \sum_{\substack{T \in \mathcal{F},\\S\cap \overline{M}=T \cap \overline{M}}} \prod_{i \in S \cap M} v_i = 0 \bigg].$$
If $f$ has $n$ monomials, $\Psi(M,v)$ can thus be expressed as a sum of $n^2$ products of subsets of $v$.  This can be expressed as a SAT formula of size $O(n^2)$, by introducing boolean variables to represent $M,v$ and applying the Tseitin transform.
Now your problem can be expressed as checking whether there exist $M,v$ such that
$$\Phi_1(M,v) \land \dots \land \Phi_{100}(M,v) \land |M| \le k,$$
where $\Phi_i(M,v)$ is the formula corresponding to requiring $f_i$ be identically zero.  This can be checked with a SAT solver, and you can use binary search over $k$ to find the smallest $k$ for which this is satisfiable.
Unfortunately, if each $f_i$ has $n$ monomials, I suspect this will lead to a SAT instance with a small constant times $5000n^2$ CNF clauses, which sounds awfully large for existing SAT solvers to handle.
There are some optimizations that might make this more practical:

If we know that we are looking for an assignment to $k$ variables, the size of the formula for $\Phi(M,v)$ can be further reduced by additionally adding the constraint $|S \triangle T|\le k$ to the $T$'s we sum over, where $\triangle$ denotes the symmetric difference of sets.)

It might be helpful to use CryptoMiniSAT or some other SAT solver with built-in support for XOR (as each sum is a large XOR of boolean variables).

I'm not sure whether this will be enough to make your problem practically solvable in this way, though.
2QBF
We can formulate your problem as an instance of 2QBF as
$$\exists m, v . \text{wt}(m) \le k \land \forall w . f_1(m \;?\; v : w)=0 \land \dots \land f_{50}(m \;?\; v : w)=0,$$
where $m,v,w$ range over $\{0,1\}^{100}$, $k$ is a parameter, $\text{wt}(m)$ represents the Hamming weight of $m$ (the number of 1's in it), $m$ is a mask indicating which variables are assigned, $v$ indicates the values of the assigned variables, $w$ represents an assignment to the other variables, and
$$(m \;?\; v : w)_i = \begin{cases}v_i &\text{if }m_i=1\\
w_i &\text{if }m_i=0,\end{cases}$$
i.e., $m \;?\; v : w = (m \land v) \lor (\neg m \land w)$.  If you can test satisfiability of this kind of 2QBF formula, you can use binary search over $k$ to find the minimum number of variables to assign to.
So, you could try applying standard algorithms for 2QBF to your problem.  See https://cstheory.stackexchange.com/q/11022/5038.  I don't know whether to expect that to be successful -- the problem size might be a bit large for this to work.
2QBF is harder than SAT and unlikely to be solvable with multiple queries to a SAT solver (see Is 2QBF in P^NP?).


How can I generate Rubik's cube algorithms equivalent to a given algorithm?

Solutions

Finding solutions of a Rubik's cube is infeasible by enumeration (BFS - too much space required), DFS takes too much time and does not guarantee the optimal solution, I highly doubt that optimal solution would be required.

There are at least three algorithms worth noting: Kociemba's algorithm, Thistlewaite's algorithm and Iterative deepening $A^*$ (Korf's). Here is a methods comparison. Iterative deepening needs admissible heuristic, which for Rubik's cube is the sum of 3D Manhattan distances calculated separately for corners and cubies. Due to Korf, it also needs pattern database to achieve optimal solution in reasonable time.

Algorithm Optimization

For optimizing any given algorithm all above will work in reasonable time, including BFS for short algorithms. To make small number of turns in overall solution the structured system should yield low number of turns in average, Friedrich method is mainly used for manual solving with medium number of algorithms (more than 100 is huge number to learn at once, not that challenging to program), so instead of optimizing single steps it would be better to find system that scores better. For example ZBLL method with 493 algorithms (including mirrors) with average about 40 turns, Friedrich scores about 56.

Solving Between States

This step is inevitable: the modification of the stop condition in the search tree - at some point while processing partial algorithm the stop condition should be changed to check only target pieces and already solved ones. There is no good way to mitigate this effect, at initial phases enumerating all possible permutations of the cube is too memory and time consuming. Searching for shorter algorithm without changed condition (via ready to use solver or own algorithm) will yield very long solution, because all pieces will be preserved e.g. the last layer while solving the middle layer. To really improve the overall score instead of shortening given moves it is far more valuable to implement look ahead (e.g. better last layer orientation while solving the second one, or increasing number of algorithms possibly merging phases together).

There is also Hamilton circuit for Rubik's cube with included graph for cosets - this is not a full solution, but still worth reading.


Reduction of graph chromatic number to hypergraph 2-colorability

This is an error in Lovász' paper. However, a correct reduction is not too hard to come by. See this answer on math.se, in which a slight modification of the reduction you quote is shown to work.


Complexity of Estrin polynomial evaluation

The question is not particularly clear, but if I'm correct to assume that you're asking about Estrin's scheme for polynomial evaluation then Wikipedia confirms that it uses $n + \lfloor \lg n \rfloor$ multiplications.


Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail?

Let's take a look at the case of size 7 first. Here, we want to show a linear upper bound for $T(n)$.
Thus, we choose the recurrence relation $T(n) \leq T(n / 7) + T(5 / 7 n) + dn$ (remember, it is an upper bound).
We guess that the solution is of the form $T(n) \leq cn$ for some constant $c$ and prove it with induction:
$$T(n) \leq T(n / 7) + T(5 / 7 \cdot n) + dn \leq c \cdot n/7 + c \cdot 5/7 \cdot n + dn = 6/7 \cdot cn +dn. $$
To this end, we choose $c = 7 d$, resulting in $T(n) \leq cn$.

Now we want to show a lower bound for size 3 (for the worst-case, tho!).
So we have find a lower bound for its recurrence equation, namely:
$$T(n) \geq T(n/3) + T(2/3 \cdot n) + dn .$$
The list of medians takes $T(n/3)$ since there are $n/3$ medians (resp. blocks).
In the worst case, we have to recursively search in an area of size at least $2/3 n$.
Clearly, this recurrence relation is not linear.
To get an intuition for this, imagine that we would have equality.
Assuming a solution of the form $T(n) = cn$, we get $T(n) = 1/3 \dot cn + 2/3 \dot cn + dn$.
Since $d>0$, $T(n) > cn$ which contradicts our assumption.

For more information, check out the analysis on Wikipedia.

The key part is that for block size $3$ the sizes of the recursive calls add up to $n$, which does not help to reduce the running time.

If you have more questions, feel free to ask!


How is Hypergraph Isomorphism (HI) reduced to Graph Isomorphism (GI) in polynomial time?

A description is given in the first paragraph of [1], where HI stands for Hypergraph Isomorphism and GI for Graph Isomorphism:

Given a pair of hypergraphs $X=(V,E)$ and $X'=(V',E')$ as instance for HI, the reduced instance of GI consists of two corresponding bipartite graphs $Y$ and $Y'$ defined as follows. The graph $Y$ has vertex set $V \uplus E$ and edge set $E(Y) = \{\{v,e\} \mid v \in V, e \in E, v \in e\}$, and $Y'$ is defined similarly. Here, $C \uplus D$ denotes the disjoint union of the sets $C$ and $D$. It is easy to verify that $Y \simeq Y'$ if and only if $X \simeq X'$ assuming that $V$ can be mapped only to $V'$ and $E$ can be mapped only to $E'$. This latter condition is easy to enforce.

The other direction is trivial as every graph is also a hypergraph.

[1] Arvind, Vikraman, Bireswar Das, Johannes Köbler, and Seinosuke Toda. "Colored hypergraph isomorphism is fixed parameter tractable." Algorithmica 71, no. 1 (2015): 120-138.


Why Miller–Rabin instead of Fermat primality test?

The Rabin-Miller algorithm also tests, given a number $n$, whether $Z_n$ has a nontrivial root of Unity.

Carmichael numbers pass the Fermat test (for every basis $a$), but for every Carmichael number $n$, there exist many numbers $a$ such that the test for unity roots fails on $a$ (that is, the sequence $a,2a,...,2^ra$ eventually displays a nontrivial root of unity).

Thus, we have the following:

For Fermat's test, if a composite number $n$ is not Carmichael, then the probability that the test will detect compositeness is at least $1/2$. However, the test will fail all Carmichael numbers.

For the Rabin-Miller test, every composite number will be detected with probability at least $1/2$. This means that the correctness probability is independent of the input (there are no "hard" inputs). This is what makes this algorithm stronger.


Let us denote the solution for a string $w$ and a set $A$ of remaining letters by $s(w,A)$. Also let $A = a_1 < \cdots < a_n$. If $w$ equals $>^{n-1}$ then clearly the solution is $a_n a_{n-1} \ldots a_1$. If $w$ starts with a run of $\ell$ many $>$'s (possibly $\ell=0$), then the first $\ell+1$ letters of any solution must be $a_{\ell+1} \ldots a_1$ or lexicographically larger. Conversely, there always is such a solution – we can construct one recursively. This shows that
$$
 s(>^\ell<x,\{a_1,\ldots,a_n\})=a_{\ell+1}\ldots a_1 s(x,\{a_{\ell+2},\ldots,a_n\}), \quad s(>^{n-1},\{a_1,\ldots,a_n\}) = a_n \ldots a_1.
$$
Since this greedy construction always "eats away" a prefix of the alphabet, it can easily be implemented in linear time.


What is the 2's complement answer of 16.5?

It seems that WolframAlpha is using fixed-point representation. In effect, it is doubling your number and then representing it as two's-complement.

In more detail, WolframAlpha is guessing that you are interested in fixed-point representations of the form
$$
xxxxxxx.x
$$
in binary, that is, 8 bits in total, with the "decimal" point at the fixed position between the 7th and 8th bits. Using two's complement, you can represent all numbers from $-64$ (represented as $1000000.0$) to $+63.5$ (represented as $0111111.1$).


Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Hint:

This question is telling us to find an algorithm in $O(V+E)$ which immediately suggests us some kind of search in the graph, i.e, DFS.
Using $\pi$ we should be able to build a candidate tree $T$ rooted in $s$ to test if it's shortest-path tree.
In each shortest-path tree, we have that for every $v \in V(T)$, $v \neq s$, the equality $d(\pi(v)) + w(\pi(v), v) = d(v)$ holds.


Counting the number of minimal covers of a binary matrix

It's easy to show that some inputs can produce an exponential number of minimum covers.  Consider the following 3x3 matrix:

110
100
000

This can be minimally covered in exactly 2 ways: either using a single vertical 2x1 rectangle and a single 1x1 rectangle, or a single horizontal 1x2 rectangle and a single 1x1 rectangle.

Thus placing $k$ non-overlapping copies of this gadget in a grid will produce an instance with $2^k$ distinct minimal covers.  You could, for example, tile an $n$ by $n$ grid with $n^2/9$ of them to produce an instance with $2^{n^2/9}$ minimal covers.

(It's possible that a better gadget exists -- that is, smaller gadgets that would increase the coefficient in the exponent.  More interestingly it's possible that instances with asymptotically more minimal covers exist.)


Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$

$\log_{100}n \in \mathcal{O}(log(n))$ since base change is a constant.

$\log n \in \mathcal{O}(n) $
$\log n \in \mathcal{O}(n^2) $
$\log n \in \mathcal{O}(n^3) $
$\log n \in \mathcal{O}(n^{3/2}) $
$\log n \not\in \mathcal{\omega}(n) $
$\log n \in \mathcal{o}(n \log n) $

This table gives the order;

First of all;

$$\lim_{n \rightarrow \infty} \frac{n \sqrt n}{n \log n} = \infty$$ by using this;

$f(n)= n\sqrt n + n\log n \in \mathcal{O}(n\sqrt n )$.

$ n\sqrt n \not\in \mathcal{O}(n)$
$n\sqrt n \in \mathcal{O}(n^2) $
$n\sqrt n \in \mathcal{O}(n^3) $
$n\sqrt n \in \mathcal{O}(n^{3/2}) $
$n\sqrt n \in \mathcal{\omega}(n) $
$n\sqrt n \not\in \mathcal{o}(n \log n) $,


Efficiently generating a prime polynomial of a given degree

It suffices to construct an irreducible polynomial of degree $n$ over $GF(2)$ (as this immediately induces an explicit construction for $GF(2^n)$).  So, how do you generate an irreducible polynomial?

One approach is to repeatedly choose a random polynomial of degree $n$, then test whether it is irreducible.  You can test for irreducibility by factoring the polynomial over $GF(2)$.  There are standard algorithms for polynomial factorization; they run in polynomial time.  Moreover, about a $1/n$ fraction of all polynomials are irreducible (see here).  It follows that on average about $n$ iterations will suffice, and since each iteration can be done in polynomial time, the whole thing runs in (randomized) polynomial time.


Please refer the theorem 7, in On Truth-Table Reducibility to SAT
and the Difference Hierarchy over NP  and On Truth-Table Reducibility to SAT by
Samuel R. Buss. The problem you mentioned is the original result by Buss. Hemachandra proved one of the inclusions in his PhD thesis.


It seems that you're trying to prove that $\#\mathrm{3SAT}$ is in $\mathrm{NP}$. Since $\#\mathrm{3SAT}$ is $\mathrm{\#P}$-complete, and $\mathrm{\#P}$ seems to be harder than anything in the polynomial hierarchy, it's very unlikely that $\#\mathrm{3SAT}\in\mathrm{NP}$.

The error in your attempted proof is that your certificate doesn't have polynomial length. A satisfying assignment has length $\Theta(|x|)$ (the formula can't have more variables than its length, but it could be of the form $(x_1\lor x_2\lor x_3) \land (x_4\lor x_5\lor x_6) \land\dots$). The number $y$ could have any value between zero and $2^{|y|}-1$, so your certificate has length about $|x|2^{|y|}$, which is exponential in the input size.

However, the question asks you to prove that it's $\mathrm{NP}$-hard, not that it's $\mathrm{NP}$-complete. You just need to prove that there's a polynomial-time reduction from some $\mathrm{NP}$-complete problem to $\#\mathrm{3SAT}$.


So here is my take on this. You reduce 3SAT (or SAT, the 3-literal limit does not make anything easier here) to 2P2N in the following way:

As noted above, you cannot easily add variables with an enforced equivalent truth mapping as existing ones (specifying $x \Leftrightarrow y$ in CNF requires 1 positive any 1 negative literal of each $x$ and $y$, so you cannot extend this to an arbitrary number of "copies"). At least not directly: $(x \Leftrightarrow y) \wedge (y \Leftrightarrow z) \wedge (z \Leftrightarrow w)$ will leave you with no free literals for $y$ and $z$. However, an equivalent to the above is
$(x \Rightarrow y) \wedge (y \Rightarrow z) \wedge (z \Rightarrow w) \wedge (w \Rightarrow x)$ (note that $x \Rightarrow y \equiv \overline{x} \vee y$). Hence, this "chain" requires you to use up your two positive, two negative literals for your existing variable $x$, but leaves you with one free negative respectively positive literals for each of $y$, $z$ and $w$. These you can use to replace any occurences of $x$ or $\overline{x}$.


A half-space is said to be homogeneous if the hyperplane that defines it contains the origin.

(Source: S. Vempala, A Random Sampling based Algorithm for Learning Intersections of Half-spaces. Journal of the ACM 57(6) article 32, 2010. PDF.)


How to convert a Turing Machine program to a tiling using Wang Tiles?

(partial answer) via wikipedia, the conversion/reduction of TMs to Wang tiling was 1st proven in this paper, & there are possibly later simplifications:

Berger, R. (1966). "The undecidability of the domino problem", Memoirs Amer. Math. Soc. 66 (1966). (Coins the term "Wang tiles", and demonstrates the first aperiodic set of them).


How to express the existence of winning strategy of the starter of a game in temporal logic?

I don't think it's possible in CTL nor LTL to model two competing players.

You would probably need ATL (Alternating-time Temporal Logic).  In ATL, the formula $\langle\langle A \rangle\rangle \phi$ says that agent (or coalition) $A$ can enforce $\phi$ to come about.  In your case, $\langle\langle P_1 \rangle\rangle \text{Win}_1$.

In modal µ-calculus, it should definitely be doable.  Something like $\mu Z . \big( \text{Win}_1 \lor \Diamond \Box Z \big)$?


Transform a set of points to have a minimum distance between them

Using log-barrier constraints (suggestion from the comments) along with a Nelder-Mead simplex approach got fantastic results.
As clarification to some of the other comments, the points were in Euclidean space comprised of real numbers.


Proof for Unusual QuickSort Partition Scheme

Welcome to the fascinating world of sorting algorithms!

Apparently, you get the terminologies the other way around.

What you have implemented is none other than the classic/standard/conventional version of quicksort by Hoare partition scheme.

The version of quicksort that you knew of, "which takes form of: elements smaller than piv | piv ~ piv | elements greater than piv", is probably a variation of quicksort using a variation of Lomuto partition scheme that is good at sorting arrays with many repeated elements.

Exercise 1. Will your code still be correct if the line int m = start + (end - start) / 2; is changed to int m = start;?

Exercise 2. Will your code still be correct if the lines int m = start + (end - start) / 2; int v = a[m]; is changed to int v = (a[start] + a[end]) / 2? .


Heuristic algorithms for the dense assignment problem

This paper has a painfully detailed table on what you can achieve using (currently known) deterministic, randomized and $\epsilon$-approximation algorithms. To summarize, for the bipartite case (all assuming integer weights bounded by $N$):

Deterministic time $O(n^2 \sqrt n \log N)$.
Randomized $O(n^{2.373} N)$.
$(1 - \epsilon)$-approximation in $O(n^2 \epsilon^{-1} \log N)$.

These algorithms are mostly very complex and go through $LP$ formulations. It is unlikely that any of them are truly what you're looking for. Also, regarding their use of space, I am not sure, but you can follow the papers for the different algorithms and see for yourself, if you can make them work in less space. (By the way, isn't your cost function already using quadratic space?)

If you want a heuristic with no provable guarantees, then I recommend the simple local search. You basically start with some random permutation (this is a feasible assignment, since your bipartite graph is complete) and make random swaps that improve the cost. If you do many such searches, you get a good solution more often then not. You can make the whole thing run in $O(t (n + s))$ time and linear space, if you do $t$ searches (from random permutations), each for $s$ steps. Choose $t, s$ to trade-off quality of the solution with complexity.


What us difference between distributed computing and workgroup computing?

Workgroup is Microsoft's term for peer-to-peer local area network. Computers running Microsoft operating systems in the same workgroup may share files, printers, or Internet connection.
They call small local area networks such as home or hospital as 'workgroup'. But it's performance is best with fewer number of computers. You can share resources like printers, scanner, etc,. between computers connected on workgroup. Also, it is not safe for sensitive information and there is no centralized management of the resources.

Whereas, distributed computing is the field of study in computer science.  E.g. distributed database, aircraft control systems, routing algorithms, grid computing could computing etc.,

Now, I ask you one question: Can workgroup be that part of distributed computing or vice verse or both are possible? I hope this question will help you dig out more information and learn little bit more about workgroup and distributed computing.


The number 0.00000072 has no exponent.
My best guess is that this question is about scientific notation. Every non-zero real number can be written in the form $\pm d_0.d_1d_2d_3 \ldots \times 10^e$, where $d_0 \neq 0$. Here $e$ is the exponent. Some examples:

$32 = 3.2 \times 10^1$. The exponent is $1$.
$-0.0014 = -1.4 \times 10^{-3}$. The exponent is $-3$.
$3.14159 = 3.14159 \times 10^0$. The exponent is $0$.

Hopefully now you can solve the question on your own.


Yes, you could express machine code in unary.  How do I know?  Well, anything that can be represented in binary, can be represented in unary.  Machine code can be represented in binary (as a binary string of bits)... therefore it can be represented in unary (as a unary string).
It wouldn't be useful or practical to do so.  It's not just less comfortable; it's much worse than that.  Conversion to unary involves an exponential increase in size (a string that takes $n$ bits in binary would take $2^n$ symbols in unary), so it would be totally infeasible in practice.  But in theory, you can imagine it; there's no barrier in principle.


Can terms "interpreter" and "processor" be used interchangably?

Usually, an interpreter is defined in computing terms: it executes instructions by issuing instructions to some lower level of processing. A processor is defined in physical terms: it executes instructions in electronic circuits. It's an interpreter if its behavior is ultimately defined by computer scientists, and a processor if its behavior is ultimately defined by physicists.

There's an exception: if the interpreter is defined in terms of emulating something that would normally be a physical processor, it's called a processor.

But it's only a matter of terminology. There's no profound distinction here. Just go with the flow.

Mu. It's an interpreted machine language. Many processors work that way anyway (where do you draw the line between instruction decoding and interpretation? why would you want to draw a line?).
Mu. It's a processor, and the processor is interpreted.
Mu. If you posit that the language is interpreted then by definition it's interpreted by an interpreter. The interpreter may be a processor.


Why can't we prove decidability of $L= \{ \langle M \rangle : M$ accepts $ \epsilon \}$ with a configurations graph?

$D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.

The problem here is that, even if you define the TM so that there are only finitely many accepting configurations (e.g. by requiring that the final tape be empty), the configuration graph itself may have infinitely many vertices. This is because the configuration includes the contents of the tape, and the tape contains however many cells the TM has written to, which is in general unbounded.

Every vertex can be identified by a finite string (the configuration description), and each vertex is connected to only a finite number of other vertices (determined by the transition relation), so the graph is locally finite. But the whole graph may still have an infinite number of vertices that are reachable.


Proving that a specific grammar is ambiguous

The word $ababab$ can be derived in two different ways.

If you don't see why, I suggest starting with the simpler grammar $A \to AA|a$.


The advantage in using base 2 is that we know all of the psp's base 2 up to $2^{64}$. It has been verified that none of these psp(2)'s passes a Lucas test when the parameters $P, Q$ are chosen in accord with any of the methods in the Baillie/Wagstaff paper.

If you choose a random base, there might be some composite $n$ that passes both the Fermat and Lucas tests. For example, $n = 5777$ is a strong psp base 76, and is also a Lucas pseudoprime.

By the way, if you implement a Lucas test, I would also recommend adding the following check, which is virtually free once you reach the end of the Lucas calculation. If $n$ is an odd prime and $(n, QD) = 1$ where $D = P^2 - 4Q$, (and, as usual, $\left(\frac{D}{n}\right) = -1$ (a Jacobi symbol), then $V_{n+1} \equiv 2Q \pmod n$. If $D, P$, and $Q$ are chosen by method $A^*$ (see Baillie/Wagstaff), then 913 is the only odd composite number up to 25 billion for which this congruence holds. (The B/W paper gives a limit of $10^8$, but I've recently carried the calculation farther). So, in addition to the sprp(2) and slprp(P,Q) tests, this congruence adds additional strength to the primality test.


Divide sequence of numbers from 1 to n into 2 groups with minimum difference

It turns out that the strategy depends on $n$ mod $4$.

To see why, one computes the total sum of all these numbers, which is $n(n+1)/2$. The parity of this sum depends on $n$ mod $4$: if $n$ is congruent to $0$ or $3$ mod $4$, the total sum is even; otherwise the total sum is odd.

When the total sum is odd, it is not possible to divide the set into two parts with equal sums. The minimum difference you can expect is therefore $1$.

If $n = 0$ mod $4$: you already figured out how to do that.

If $n = 1$ mod $4$: divide $2, \cdots, n$ using your strategy, and add the extra $1$ to any side. This achieves the minimum difference $1$.

If $n = 2$ mod $4$: divide $3, \cdots, n$ using your strategy, and add the extra $1$ and $2$ to each side to get the minimum difference $1$.

If $n = 3$ mod $4$: divide $4, \cdots, n$ using your strategy, and add $1$ and $2$ to one side, and $3$ to the other side to get the minimum difference $0$.


How to identify strongly confluent cellular automatas?

Suppose we fix $n$ and want to ask about confluence of the system on $n$-bit states.  Then one approach you could try would be to use BDDs.

Build a BDD for the transition relation $\to$, where for two $n$-bit states $s,t$ we say $s \to t$ if you can get from $s$ to $t$ in a single step.  Now, build a BDD for the reflexive, transitive closure $\to^*$.  (This can be built in a fixpoint computation, by looking for the least fixpoint of the equation $\to^* = \to^* \circ \to \lor \; \text{id}$; i.e., set $R$ to be the identity relation, and then iteratively replace $R$ with $R \circ \to \lor \; \text{id}$, where the latter relation $R'$ is defined such that $sR'u$ holds iff $s=u$ or there exists $t$ such that $sRt$ and $t\to u$.  Iterate until convergence.)  If you're lucky, the BDD for $\to^*$ won't be too large.

Now, once you have a BDD for $\to^*$, you can use standard BDD operations to check directly whether the convergence criteria applies.  In other words, you check the validity of the formula

$$\forall a,b,c . (a\to^* b \land a\to^* c \implies \exists d . (b \to^* d \land c \to^* d)).$$

This only gives you the answer for fixed $n$.  If you want to know if it is confluent for all $n$, I don't know how to check that.  Also, this procedure might take exponential time in the worst case.  So, you might be able to systematically check small values of $n$, and then heuristically guess that if there is a counterexample to confluence, then hopefully it'll show up for some small $n$... but this isn't guaranteed to be sound in general.


Context-free grammar to a pushdown automaton

This is basically the language of all palindromes over $\{a, b\}$ which can contain an arbitrary number of $b$'s in the middle. First, you could build a PDA for palindromes. This is a fairly standard language, so you should be able to find plenty to get you started. Then, you need to add a way to read an arbitrary number of $b$'s after you're done pushing new symbols to the stack, and before you start popping symbols. So the basic steps here:

Read $a$'s and $b$'s and push to the stack;
Read any number of $b$'s;
Read $a$'s and $b$'s and pop from the stack.

Please let me know if you need more guidance. Note that you're going to need to use nondeterminism here, so don't worry about it. This is a not a deterministic language (unless I'm mistaken... which has happened before).


Can you have a binary search tree with O(logn + M) property for the following case

The data structure you are looking for is called a range tree. Range trees are usually used for geometric data, but they can be used here as well. In 1d, a range tree is simply a balanced binary search tree with the data stored at the leaves and the internal nodes augmented with the min and max element stored in the subtree. They have running time $O(\log n+ k) $  where $n$ is the total number of objects in the tree and $k$ is the number of objects reported. You will have to structure your queries slightly differently to use a range instead if a prefix. So add a special min and max character to your alphabet, call them 0 and 1 for convenience. Now to find all strings with prefix "CA", " you would search for all strings in the range (CA0, CA1).

As noted in the comments above, a trie is the structure one would normally use for this type or query. But the computational model used is slightly different, so it's hard to compare. The running time would be the length of your longest output string + k.


Do exponential functions grow faster than logarithmic?

I think you may be confused about the definition of Big O - graphing f(n) and g(n) shows f(n) surpassing g(n) at nearly every scale.

O(f(n)) > O(g(n) because g(n) is a fractional power polynomial, which is by definition sublinear (if you linearly plug numbers into a square root, cube root, etc., the rate at which the output increases decreases with each successive computation). g(n) is a "n log star n" polynomial meaning it follows the form of a log to a power multiplied by n. The rate of growth of these types of functions far exceeds fractional polynomials and its not hard to see why - n is a term of the function, so we know its at least linear.

Here's a helpful resource: https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities


Why does Insertion sort take linear time in this case?

Count the number of times each of the 5 new element is moved in the array:
The areay is of length $n$, and thus each of the 5 elements move at most $n$ times. The place of all other elements is correct, and thus there is at most $5n$ swaps required to "correct" the array, hence $O(n)$ swaps.