Saving time finding a result by guessing first?

Yes, it absolutely would save time.  You are quite right, and you are onto a good idea -- that idea is frequently used to speed up image matching.

The core challenge is: how do we come up with an estimate where the result might be, more efficiently than using the correlation algorithm?  It's not obvious how to do that, short of doing a correlation (which wouldn't actually save any time).

Fortunately, there are ways to do that.  A standard approach is to use an image pyramid.  You downscale the image to a lower resolution, then look for a downscaled version of the T in that smaller image (again using correlation).  Because the image is smaller, the correlation calculation goes faster.  Then that gives you a pretty good estimate where the T is, and instead of searching the entire full-resolution image, you only need to check a small portion of the full-resolution image.  If you find multiple matches in the downscaled image, you can check all of them on the full-resolution image.


Hoare logic, proving conjunction rule from basic rules, possible or not?

Your reasoning is fine as far as the derivability of this rule. To respond to the latter part of your last paragraph, if the rules you've listed are all the rules available, then those are the only rules you can use. A derivation is a tree of applications of rules. You need to be able to state what rule you're using at each node in that tree. A(n explicit) proof that this rule was derivable would be an actual derivation, i.e. tree of rule applications.

There's a different and (slightly) harder question that you probably were not asked which is whether the Conjunction Rule is admissible. That is, could the Conjunction Rule be added without causing any problems, i.e. unsoundness.


Looking for an algorithm to generate an identicon/avatar from genome data

If all you want is uniqueness, you could use a visual hash.  Hash all of the data (say, with SHA256), then apply a visual hash.

A visual hash is a function $H$.  Given a short binary string $x$ (say, 256 bits long), the visual hash computes $H(x)$, a random picture that is a visualization of $x$.  The output of the hash is a visualization of the string -- a picture or image of some form -- with the property that different binary strings will lead to different images.  Also, $H$ is a deterministic algorithm, so if you hash the same binary string twice, you'll get the same picture both times.

Below I list some visual hash schemes that have been proposed, along with sample images produced by each scheme.

Random Art for PGP keys

https://user.xmission.com/~atoponce/art/

(As you'll notice, this is actually a visualization of multiple different schemes at once.)

See also the following research paper:

Hash Visualization: a New Technique to improve Real-World Security.  Adrian Perrig and Dawn Song.  Proceedings of the International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC), Hong Kong, July 1999.

VizHash GD

http://sebsauvage.net/wiki/doku.php?id=php:vizhash_gd

JrSnowflake

https://wiki.debian.org/JrSnowflake

Older: README, source

OpenSSH's Visual Host Key

+--[ RSA 2048]----+
|   .+            |
|   + o           |
|  o o +          |
|   + o +         |
|  . o E S        |
|   + * .         |
|    X o .        |
|   . * o         |
|   .o .          |
+-----------------+

https://stackoverflow.com/a/3601278/781723


The question is at least poorly worded, since it does not specify $k \leq n$ or require a simple cycle. So any positive-value arbitrage cycle can be "pumped" to generate a cycle with unbounded positive value.

If we add the requirement that the cycle is simple, then finding the simple cycle with the maximum product of the weights is equivalent to finding the simple cycle with the maximum sum of the logarithms of the weights, which is indeed the NP-hard Longest Simple Cycle problem.

Usually, these arbitrage questions ask to find a cycle with positive return, if one exists. This can be done by negating the logarithms of the weights and checking for negative cycles. This question asks for the best cycle, though.


Birkhoff-von Neumann theorem for bistochastic digraphs

From Roger A. Horn "Topics in Matrix Analysis", section 3.2 page 164-165.

  A matrix $Q$ is said to be doubly substochastic if its entries are nonnegative and all its row and column sums are at most one.

The doubly stochastic matrix
$\begin{bmatrix} Q & I-D_r\\I-D_c & Q^T\end{bmatrix}$
is a dilation of $Q$, where $D_r$ and $D_c$ are diagonal matrices with the row and column sums of $Q$ respectively. This dilation allow to reduce the generalization of the Birkhoff-von Neumann theorem for substochastic matrices to the original theorem

  Every doubly substochastic matrix is a finite convex combination of partial permutation matrices.

The bistochastic digraphs are doubly substochastic matrices, so the generalized Birkhoff-von Neumann theorem can be applied directly for them. Or one can just apply the same reduction directly. This means taking the original digraph and a copy of the digraph where all edges are reversed, and connecting the sources and sinks to their copy by suitable oriented edges of weight 1.

However, it turned out that the notion of a doubly substochastic matrix is more suitable with respect to the original motivation for this question than the notion of a bistochastic digraph. It is a good thing that the above construction directly covers that case too.


Why is randomness a problem? (i.e. why do we care about derandomization?)

Complexity theory is a mathematical theory which aims at addressing one shortcoming of computability theory, namely, it takes into account the use of resources. While it is true that in its early days it aimed to capture the notion of "practical computation" (even particular flavors such as parallel computation, supposedly captured by NC), it has since drifted apart and taken off from reality. As an example you can take higher steps on the polynomial hierarchy, higher complexity classes such as PSPACE, classes defined using alternation, and so on. Indeed, much of this material dates to the early days of complexity theory, showing that it lost touch with reality quite quickly.

Traditionally the two most important resources studied by complexity theory are time and space. However, other resources have also interested complexity theorists, for example alternation and randomness (not to mention the world of circuit complexity). Philosophically speaking, it is a fascinating question whether randomness dramatically reduces the computation time of some problems, or whether the gain is only polynomial (as hinted by the conjecture P=BPP). However, it does not seem to have any practical relevance, though not for the reason you mention. In practice there is no need for actual physical randomness (other than for cryptographic purposes), and pseudorandom number generators work well enough.


I am guessing that overheads P, S, and T exclude per page/segment overheads and are per-process overheads (if they are per-system overheads, the adjustments are obvious), so the overhead of each process would be P + page_count * 4 bytes for paging, S + segment_count * 8 bytes for segmentation, and T + segment_count * 8 bytes + page_count * 4 bytes for segmentation and paging.

(The inclusion of a maximum segment size is confusing since insufficient information is provided to determine if any of the 8 segments in process P4 are larger than 256 KB, though at most one segment can be.  Since the mean segment size is significantly less than the maximum allowed size, I just assume that no segment needs to use two segment table entries.)

It might help clarify the equations to substitute A < B < C with A = B + k1 = C + k1 + k2 (where k1 and k2 are greater than zero).  It should then be straightforward to determine what values of k1 and k2 are needed for equality and so derive the conditions under which each memory management method has greater overhead (with negative values for k1 or k2, of course, being impossible).


Note that for $w\in\{0,1\}^n$ it holds that:

$w\in L^*\iff w\in L \lor \left(\exists i\in \{1,...,n-1\} : w_1...w_i\in L^* \land w_{i+1}...w_n\in L\right)$.

You can translate the above into a dynamic programming algorithm for deciding $L^*$. One way to do that is keeping an array $A[i]$, where $A[i]=1\iff w_1,...,w_i\in L^*$, and filling it from $i=0$ upwards. The running time $T(n)$ is bounded by $T(n)\le T(n-1)+T_L(n)$, where $T_L(n)$ is the time required for deciding membership to $L$ on inputs of length $n$. Hence, $T(n)\le nT_L(n)$, which is polynomial if $L\in P$.

This works fine if $L\in P$, however when $L\in P/Poly$, you have a polynomial time machine $M(x,y)$ and a sequence of advice $\{\alpha_n\}_{n\in\mathbb{N}}$, where $\alpha_n\in\{0,1\}^{p(n)}$ for some polynomial $p$, such that $x\in L \iff M\left(x,\alpha_{|x|}\right)=1$. The above procedure requires deciding membership to $L$ on inputs of length at most $n$. Thus, your advice for deciding $L^*$ on length $n$ inputs will be $\beta_n=\alpha_0,\alpha_1...,\alpha_n$ (which is still polynomial), and whenever you need to check membership to $L$ on a word $w$ of length $0\le i\le n$, execute $M(w,\alpha_i)$.


Build a grid graph, with one node per entry in the matrix, and edges between each pair of adjacent nodes.  Also add a source node $s$ with an edge from $s$ to each blue node, and a sink node $t$ with an edge from each white node to $t$.  Set the capacity of each edge to 1, except the $s$-to-blue edges have capacity $\infty$, and the white-to-$t$ edges have capacity given by the cost of allowing that white node to become blue.
Now, find the minimum $(s,t)$-cut in this graph, using any network flow algorithm.  The $s$ side of this cut will contain all of the nodes that become blue, and the edges that cross the cut will indicate where to place blocks (for blue-to-white edges that cross the cut) and which white nodes become blue (for white-to-$t$ edges that cross the cut).

Why does this work?  We're going to treat the final colors as defining a cut $(B,W)$: $B$ contains all nodes that are ultimately blue (and $s$), and $W$ contains all that remain white (and $t$).  This means that any edge between an ultimately-blue node and an ultimately-white node crosses the cut, which matches the problem requirement that such an edge must have a block on it.  Also, if $b \in B$ is any node that was originally white but becomes blue, then the edge $b \to t$ crosses the cut (since $t \in W$), so we think of it as having a block between it and $t$.  Finally, we want to know the cheapest way to choose a set of blocks.  The total cost of a set of blocks is the sum of the capacities of the edges that were blocked, so this total cost matches the total capacity of the edges that cross the cut $(B,W)$, i.e., the capacity of the cut.  So, finding a min-capacity cut will find you the cheapest way to place a set of blocks that match the problem requirement.


What's the fastest known algorithm for generating $k$-subsets of an $n$-set?

Knuth's Algorithm R Revolving-Door combinations is generally accepted as the current best for algorithms and time complexity for generating combinations.


Flags register in an out-of-order processor

The flags register is handled using one of the standard techniques for dealing with dependencies in out-of-order processors.  Either

the registers are renamed (there are multiple physical flags registers, and the renaming and retirement mechanisms make sure the correct physical flags register is being used by each instruction) or
the scheduler respects anti- and output- dependencies, in which case the two CMP instructions execute in-order because the second is output-dependent on the first.

Same thing with ADD instructions.  In a machine with ADDs that set an overflow flag, the overflow flag needs to be handled either by renaming or by stalling on anti- and output- dependencies.


A $k$-SAT instance over $n$ variables, monotone or otherwise, has at most $2^n - 2^{n-k}$ solutions.  This is simply the number of possible settings of the $n$ variables minus the least number of settings a single $k$-CNF clause can exclude, assuming all the variables in the clause are distinct.  You only have to consider the case of a formula with a single clause because adding more clauses can never increase the number of satisfying assignments.


Understanding paging and internal fragmentation

If each page is 4 KB and segment has arbitrary size, then you lose from 0 to 4095 bytes on each segment, i.e. 2 KiB at average
I think it can be called internal fragmentation for pages, but external one for segments


A "natural" decidable problem not in $\mathsf{NP}$?

From an answer to a related question on NP-hard problems which are not contained in NP: probably the most natural example is determining whether two regular expressions (including the Kleene star for arbitrary repetition, and a squaring operation to allow compact expressions of very large fixed numbers of repetitions) are equivalent. The resulting problem is EXPSPACE complete. Because EXPSPACE contains NEXP, which contains NP strictly (by the time hierarchy theorem), this is a decideable problem which is not in NP.


Does the "dictionary of stacks" ADT have an accepted name?

The implementation with a linked list is called association list, or alist for short.

I don't think there's a universal term for the interface. I'd call it a dictionary with shadowing of keys (pushing (k,v2) when the data structure already contains (k,v1) shadows the existing binding for k).


What does feedforward inversion mean in the context of convolution and catastrophic codes?

The paper deals with sequential encoding and decoding of codes. Maybe you have heard of "block codes": these codes take a message $M\in \{0,1\}^k$, perform some computation, and then output a code-word $c_M \in \{0,1\}^n$.(1). A main drawback of encoding systems for such codes is that need to know the entire message $M$ in order to output $c_M$.
This is not the case in convolution code.
Sequential circuits
Convolution codes are usually designed so that there is a very simple and sequential encoding algorithm. By "sequential" I mean that the system reads $M$ bit by bit, and immediately(2) outputs some part of $c_M$. Say, if the rate is $k/n=1/2$, then for every bit of $M$ given as an input to the encoder, the encoding system outputs the next $2$ bits of the codeword (even without knowing the rest of $M$). After the entire input $M$ is fed into the encoder, we will get the entire codeword $c_M$.
This sequential nature of encoding is what the paper means by "feed-forward": you always input the next part of the data, and that's enough for the system to proceed and give output, as a function on the current state of the encoder. This is/was crucial in memoryless implementations (those can't hold the past bits of the message $M$), or implementations that could not wait to have the entire $M$ due to the large delay incurred (those don't know the future bits of the message $M$).
Thus, a "feedforward inverse" is simply a sequential decoding algorithm. ("inverse" is the algorithm that inverses the code, that is, the decoding system).
Delay
The delay $L$ is explained in the first paragraph of the paper:   (below, not a precise quote)

An inverse with delay $L$, for a sequential circuit with $k$ inputs and $n$ outputs [= a decoder for the encoder], is a sequential circuit with $n$ inputs and $k$ outputs, that cascaded with the encoder, yields an overall sequential circuit with delay $L$.

That is, take the encoder, and connect the decoder immediately to the output of the encoder. Now start feeding the input into the encoder. $L$ is the amount of "clocks" until you see the same bit at the output of the decoder.

(1) The alphabet needs not be binary, this is just for simplicity.
(2) Or after a fixed number of clocks.


In this implementation of Hoare-partitioning Quicksort, why are additional checks for $i \leq j$ needed?

I am having trouble seeing why in the inner while-loops, the condition $i\le j$ is needed in addition to checking $M[i]\le p$ (or $M[i]\gt p$).  The pseudocode given in the Wikipedia article does not seem to do this additional check. There is a potential problem in the given implementation that if all elements in $M[l+1..r]$ are less than $p$, the first while loop would not terminate when not checking for $i≤j$. However, that does not explain the necessity of checking $i≤j$ in the second inner while loop.

As you suspected, it is not needed to check the condition $i≤j$ in the second inner while loop.

One usual way to prove that condition is not needed is by analyzing all possible cases and establishing various invariants as well as employing the powerful tool of mathematical induction, which will probably convince anyone who can follow through the proof with enough patience. Although I have done that below, it is actually not convincing to myself because of the subtlety in the
Hoare's quicksort as shown in Hoare's quicksort is deceptively simple, the devil in selecting element at index hi as pivot, a slight modification of Hoare's partitioning, what happens if both indexes land on the pivot. Even if I have checked my proof tens of times, it might still miss a corner case or two. As shown/implied by many answers at why is writing down mathematical proofs more fault-tolerant than writing computer code?, a traditional mathematical proof for a moderate computer program is probably far from fully satisfactory or fully correct in general. It is more like how we can understand/believe the program is correct in a high level.

Instead, I have written a program that tests the implementation of Hoare's quicksort with that condition removed.

Here is the testing program.

That program tests the sorting algorithm against every permutation of every possible way $n$ competitors can rank in a competition, allowing for the possibility of ties, up to a certain number of competitors.

What are all possible ways $n$ competitors can rank in a competition? Here is an example for $n=3$. There are four different sorted ranks, [1, 1, 1], [1, 2, 2], [1, 1, 2] and [1, 2, 3]. If a comparison sorting algorithm can sort all permutations of each of those four arrays, which counts to 13, it will sort any array of size 3 correctly. By the way, the number of ways $n$ competitors can rank in a competition is the Fubini numbers.

If a simple sorting algorithm like the current one does not work, it should fail for an array whose size is smaller than 8. For extra insurance, I have run that program against arrays size up to 11. These testing proves that condition is not needed.

A brief mathematical proof

Since many people would prefer a traditional proof, here is a sketch of a mathematical proof of the correctness of the implementation either with or without that additional check.

Let us assume l < r. Throughout the method, M is a constant reference to the array while l and r are constant indices. The pivot p = M[l] is constant, too. All we need to prove is that at the end of outer while loop, M[l] is the pivot, followed by elements not bigger than the pivot up to index j inclusively or no elements if l >= j, followed by all other elements, which are bigger than the pivot. (Then by mathematical induction on r - l, we can prove easily that the method does sort the subarray of M from indice r to l inclusively.)

We can establish the following invariant at the end of each iteration of the outer while loop.

Elements from l + 1 to the smaller of i and j are not bigger than the pivot
Elements from j + 1 to r are bigger than the pivot.

The first inner loop, while ( i <= j && M[i] <= p) { i = i + 1; } will find the smallest index i such that i <= j && M[i] > p or  i == j+1.
The second inner loop, either while (M[j] > p) { j = j - 1; } or while (i <= j && M[j] > p) { j = j - 1; } will find the largest $j$ such that M[j] <= p.

Why is the condition i <= j not necessary? Let us elaborate as here is the crux of current question.

There are two cases at the start of this loop depending on the result of above inner loop.

i <= j && M[i] > p.  As we are looking for an element that is not larger than the pivot going from index j to smaller indices, the latest time we will succeed must before current i. That is, i <= j will always be satisfied throughout the loop. That is, the condition i <= j is not necessary.
i == j+1. The first inner loop must have missed the above case, since j is smaller than j + 1. That means M[j] > p was not satisfied. So at the start of current loop, we have both i > j and M[j] <= p. Using either version of the second inner while loop, we will break the loop right away.

if (i < j) { swap(M, i, j);}. This swap extends both the left hand side of elements that is not bigger than the pivot and the right hand side of elements that is bigger than the pivot.

To tell the truth, I used program to double check various invariants and propositions in the mathematical proof.

Many further questions can be raised, which go much beyond the scope of the current question.

How to improve the performance of the testing problem?
How to reduce the number of test cases needed for a specific size?
Is there a way to determine rigorously an upper bound of the size of the array that need to be tested to prove the correctness of a sorting algorithm given its description?


Partitioning a boolean circuit for automatic parallelization

One approach for formulating this as an ILP problem could be to have zero-or-one variables $x_{i,t},y_{i,t},z_t$, with the intended meaning that $x_{i,t}=1$ if the $i$th gate is evaluated in the $t$th instruction (not as part of a batch), or $x_{i,t}=0$ otherwise; and $y_{i,t}=1$ if the $i$th gate is evaluated in a batch in the $t$th instruction, or $y_{i,t}=0$ otherwise; and $z_t=1$ if the $t$th instruction is a batch instruction, or $z_t=0$ otherwise.

Your problem can then be represented as an integer linear program, with some constraints to enforce consistency of these boolean variables:

Each gate is assigned to a single instruction: $\sum_t x_{i,t} + y_{i,t}=1$.
Non-batch instructions are assigned a single gate: $\sum_i x_{i,t} = 1-z_t$.
Non-batch instructions don't set any $y$ values: $\sum_i y_{i,t} \le C z_t$, where $C$ is a large constant equal to the maximum batch size (or the number of gates, if there is no limit).
Gates can only be batched together if they compute the same logic function: $y_{i,t} + y_{j,t} \le 1$ for each pair of gates $i,j$ that have a different logic function.
A gate can only be evaluated once all of its inputs are ready: $x_{i,t} + y_{i,t} \ge x_{j,u} + y_{j,u}$ for each pair of gates $i,j$ such that the output of $i$ is an input to $j$, and for each pair $t,u$ with $t<u$.

(I'll assume you treat NOT gates as free and don't try to assign them to any instruction; they just happen automatically.)

Now any consistent assignment to the $x$'s and $y$'s will correspond to a valid way to implement the circuit.  The cost of this assignment will be $9 \sum_t z_t + c \sum_{i,t} y_{i,t} + k$, where $c$ is the tiny proportional term and $k$ is the total number of instructions in the schedule (both $c$ and $k$ are constants).  If you pick a value for $k$, the maximum number of instructions allowed, you can use an ILP solver to minimize $9 \sum_t z_t + c \sum_{i,t} y_{i,t} + k$ subject to the inequalities above, and this will give you the best way to schedule your boolean circuit using $k$ instructions. Then, I suggest you search over different values of $k$, solving an ILP for each one, to find the best boolean circuit.

Be prepared: ILP is NP-hard, so finding the optimal solution might take a very long time if the circuit is large and you're aren't very lucky.  Some ILP solvers have the ability to terminate their search after a fixed time limit and return the best solution they've found so far, which might be useful if that happens.


1- The PDAs in the video seem to have a transition function of the form $\delta: Q\times (\Sigma\cup\{\epsilon\}) \times (\Gamma \cup \{ \epsilon\}) \to 2^{Q\times (\Gamma \cup \{\epsilon\})}$, so you are allowed to take a nondeterministic transition without reading any input letter and without popping a letter from the stack. Note however, that you are allowed to push a single letter (or none) to the stack in a transition that you take.
2- The PDAs from Wikipedia do not allow you to take a transition without popping a letter from the stack (note that as Yuval said:  the stack is initialized with a "bottom of stack" symbol), however note that, unlike the PDAs in item 1, you can push an entire word in the stack in a transition that you take.
So you have two variants of PDAs that have slightly different syntax, however it is not hard to prove that a PDA from one variant can simulate a run of a PDA from the other variant, and thus both variants recognise the same class of languages, CFL. A high-level explanation of how both variants can simulate each other is given next. A PDA $A$ of the 1st variant simulates a run of a PDA B of the 2nd variant by first pushing a "buttom of stack letter", then $A$ mimics the transitions that $B$ takes: in the case where $B$ takes a transition that pushes a word of length $\geq 2$ into the stack, you can introduce new states that push that word, and then move to the state that $B$ moves to. Conversely, a PDA $B$ of the 2nd variant simulates a run of a PDA $A$ of the 1st variant by first popping the "buttom of stack letter", then $B$ mimics the transitions that $A$ takes: the non-trivial part here is to mimic popping $\epsilon$ from the stack. This is easy as $B$ is allowed to push an entire word into the stack: popping $\epsilon$, and then pushing a word $w$, is equivalent to popping a letter $\sigma$, and then pushing the word $\sigma\cdot w$.


What is the name for closure-type functions that use the call-site environment?

You are talking about static vs. dynamic scoping of variables. Most langauges today have static scoping, but famously the early LISP had dynamic scoping.

Scoping is a general feature of a programming language and is not something that a closure does (although I suppose one could organize things so that it does). In any case, look up "dynamic" and "static" scoping.


How to distinguish whether a sample is from distribution $\chi_1$ or $\chi_2$?

Hint: Run $A$ on lots of samples $x_1,\ldots,x_n$ and compute the average $(A(x_1)+\cdots+A(x_n))/n$.


Divide an integer into the sum of consecutive positive numbers

Here's an alternative way of viewing D.W.'s hint. Using the formula $\sum_{i=1}^m i = \frac{(m+1)m}{2}$,
$$ \sum_{i=a+1}^b i = \sum_{i=1}^b i - \sum_{i=1}^a i = \frac{b^2+b}{2} - \frac{a^2+a}{2} = \frac{(b-a)(b+a+1)}{2}. $$
Given a factorization $2n = xy$, we can solve the system $x = b-a$, $y = b+a+1$. The result is $b = (y+x-1)/2$, $a = (y-x-1)/2$. So we want $x,y$ to have different parities (this is only a restriction if $n$ is even) and $y \geq x+1$. Also, $b \neq a+1$ corresponds to $x \neq 1$.

For example, for $n = 15$ we have $2n = 30 = 2 \cdot 15 = 3 \cdot 10 = 5 \cdot 6$. These correspond to the following pairs $(a,b)$:
$$ (6,8),(3,6),(0,5). $$
These, in turn, correspond to the representations
$$
15 = 7+8 = 4+5+6 = 1+2+3+4+5.
$$

This leads to an $O(n)$ algorithm (in the appropriate computation model). I'll let you work out the remaining details.


Distribution of resources from providers to maximum number of receivers

This problem is a case of maximum flow problem.
Suppose we are given internet providers $p_1, p_2, \cdots, p_m$ and residents $r_1, r_2, \cdots, r_n$. Consider a flow network specified as the following.

Nodes are $s,\ p_1, p_2, \cdots, p_m,\ r_1, r_2, \cdots, r_n,\ t$, where $s$ and $t$ are two extra nodes standing for the source and the sink.
There is an edge between $s$ and each $p_i$ with capacity $k_i$.
There is an edge between $p_i$ and $r_j$ with capacity 1 if $p_i$ can provide internet to $r_j$.
There is an edge between each $r_j$ and $t$ with capacity 1.

What we want is to find the maximum flow from $s$ to $t$.
There are many algorithms to solve a maximum flow problem in polynomial time. For example, Ford–Fulkerson algorithm and Dinic's algorithm are pretty popular. Source code that implement those algorithms in various programming languages can be found easily.
All those algorithm will produce an integral maximal flow, so we will not worry in case the computed maximal flow stipulates that some provider should provide 0.42 or $\frac{\sqrt2}2$ internet to some resident. You can check the integral flow theorem.


$Q$ represents the average of a discrete random variable.  Sometimes there are no customers waiting in line, sometimes there's one, and sometimes there are many.  So there is some probability distribution for $Q$.  The difference between a two-server queue and a single-server queue that's twice as fast, is the expected service time when the queue is empty except for the one customer receiving service.  That's the transition from state 1 to state 0 in the Markov chain:

Intuitively, when a customer reaches the head of the queue the service in the two-server system will take twice as long as with the single server that's twice as fast.  The expected service time with the two-servers is $S$, while the expected service time with the single fast server is $S/2$.  What's less intuitive is that customers will, on average, spend somewhat less time waiting to get to the head of the queue with the two-server system.

To see this, consider the case of a customer that arrives when there is one customer currently being serviced.  In the two-server case the arriving customer immediately gets the other server.  The total expected response time in this case is $S$, but that's all service time, no waiting time.  In the fast single-server case the arriving customer waits, on average $S/2$ time for the preceding customer to finish and then gets, on average, $S/2$ amount of service.  The total expected response time in this case is also $S$, but it's half service time and half waiting time.  Let's work out the exact difference:

Fast Single-Server

This is an M/M/1 queue with arrival rate $X$ and completion rate $S/2$.  The steady state distribution, $\pi_i$ for the Markov chain in the fast single-server case is
$$\pi_i = (1-U)U^i$$
where $U$, the server utilization, is $XS/2$.

Then the expected number of customers in the queue is
$$ Q_f = \sum_{i=0}^\infty \pi_i i    =
       \sum_{i=0}^\infty (1-U)U^i i =
  (1-U)U\sum_{i=0}^\infty U^{i-1} i      =
  \frac{(1-U)U}{(1-U)^2} = \frac{U}{1-U}.$$

Then by Little's law
$$ R_f = \frac{Q_f}{X} = \frac{U}{X(1-U)} = \frac{XS/2}{X(1-U)} = \frac{S/2}{1-U}, $$
but we want to represent $R$ as service time + waiting time, so
$$ R_f = \frac{S}{2} - \frac{S}{2} + \frac{S/2}{1-U} = \frac{S}{2} + \frac{-S/2 + SU/2 + S/2}{1-U} = \frac{S}{2} + \frac{US/2}{1-U} = \frac{S}{2} + \frac{S}{2}Q_f. $$

So we have that the waiting time is
$$ W_f = \frac{S}{2}Q_f = \frac{SU}{2(1-U)}.$$

Two Slow Servers

This is an M/M/2 queue.  We will again let $U = S X/2$ (this is Little's law for the utilization of each of the two servers, the reason the result is the same as in the fast-server case is that now $X$ is halved rather than $S$ being halved.)  The steady state distribution is:
$$ \pi_0 = \frac{1-U}{1+U} $$
and
$$ \pi_i = 2 U^i \pi_0, \;\;\; i \geq 1.$$

Now
$$ Q_s = \sum_{i=0}^\infty \pi_i i = \frac{2U}{1-U^2}.$$
(Derivation left as an exercise.)

Then by Little's law we get
$$ R_s = \frac{Q_s}{X} = \frac{S}{1-U^2} = \frac{2}{1+U}R_f, $$
which we want to represent as service time ($S$) plus waiting time.

$$ R_s = S - S + \frac{S}{1-U^2} = S + \frac{SU^2}{1-U^2} = S + \frac{S}{2} U Q_s, $$
and the waiting time is
$$ W_s = \frac{S}{2} U Q_s = \frac{SU^2}{1-U^2} = \frac{2U}{1+U} W_f.$$

Summary

The two slow servers always have a service time twice that of the fast server.  The two slower servers have a total response time that is $2/(1+U)$ times the fast servers' total response time.  ($0\leq U<1$, so the response time is always worse.)  But the two slow servers have a waiting time that is $2U/(1+U)$ times the fast server's waiting time, and so there's less waiting time with two slow servers.


How to find subset of vectors whose sum has certain characteristics

The question has changed.  I'll answer the updated question.  Here are three candidate algorithms; the first is faster than $O(m^n)$ time, and the second might be faster as well for some parameter values.  I will assume that the vectors are from $\mathbb{R}^d$, i.e., $d$-dimensional vectors (in  your example $d=3$).

Try all subsets

There are exactly ${n \choose m}$ subsets of $m$ vectors.  You can try each, compute what its sum is, and count how many $x$'s it has.  The running time will be $O(nd \cdot {n \choose m})$, and can be optimized to run in time $O(d \cdot {n \choose m})$.  Note that ${n \choose m} \le 2^n$ and can be significantly smaller than $m^n$, so if we ignore the dependence on $d$, this is faster than your $O(m^n)$ time to beat.

Try all target vectors

Alternatively, we can try all possibilities for which $m$ locations (coordinates) in the sum contain a $x$.  There are ${d \choose m}$ such possibilities.  For each, we will try to find a subset of the input list whose sum has a $x$ in those special locations (coordinates), and no $x$ in any other location (coordinate).  We'll temporarily ignore the requirement to have a subset of size exactly $m$.

Note that any valid solution must use only vectors that whose special coordinates all have entries from $\{0,x\}$ (in particular, no special coordinate can contain a $1$).  (Any vector with a $1$ in any special coordinate can't be included in any valid combination; if it were included, the sum in that coordinate would be either $\ge x+1$ or $\le n$, according to whether we include any other vector with a $x$ in that coordinate or not.)

So, let's focus only on those $m$ coordinates, and ignore (throw away) all the others.  In this way each $d$-vector is reduced to a $m$-vector.  Then, we look for a subset of the input vectors that sums to the $m$-vector $[x,x,\dots,x]$.  This is a multi-dimensional subset-sum problem.  This particular subset-sum problem has a special form: it turns out to be an instance of the  exact cover problem, and can be solved with standard algorithms for exact cover.  The running time will be exponential in $m$.  So, we'll solve the exact cover problem in $m$ dimensions, and then check each solution to see whether it is a valid solution to the original problem.

We repeat this ${d \choose m}$ times (once for each subset of $m$ coordinates).  The running time to solve each instance of the $m$-dimensional exact cover problem is exponential in $m$, and we must solve ${d \choose m}$ of them, so the running time will be something in the vicinity of $O({d \choose m} \cdot 2^m)$.

Alternatively, given a target vector (a set of $m$ special coordinates), we could use integer linear programming to search for a subset of $m$ of the input vectors that sum to $[x,x,\dots,x]$ in those $m$ coordinates.  This will again take time exponential in $m$, in the worst case, for each target vector, though in practice it might be faster.  One nice thing about integer linear programming is that it lets you directly express the constraint that the subset must be of size $m$.  Also, it may be fairly easy to implement this approach using an off-the-shelf ILP solver.

This algorithmic approach may be better or worse than the other schemes, depending on the values of $m,d$.  If $m$ is very small or very close to $d$, this approach may be an improvement on the others.

Dynamic programming

There is a dynamic-programming algorithm whose running time is $O(nd  \cdot 3^d)$.  Basically, we have a table that keeps track of which $d$-dimensional vectors can be expressed as a sum of some subset of the input vectors.

Given an entry of a vector, we'll classify into one of three categories: $0$ (meaning the entry is $0$), $☹$  (meaning the entry is not $0$ and not $x$), and $x$ (meaning the entry is $x$).  These have the obvious addition rules, e.g., $☹ + x = ☹$, $☹ + ☹ = ☹$, and so on.  Thus, each vector mapped to a template where its entries are classified in this way; a template is a value $t \in \{0,☹,x\}^d$.  A template stands for one or more vectors.

Now, for each template $t \in \{0,☹,x\}^d$, the table keeps track of whether any vector that matches the template $t$ can be reached by summing any subset of the input vectors.  This table will have at most $3^d$ entries, since there are at most $3^d$ possible templates.  You can fill in the entries of the table using dynamic programming in $O(nd \cdot 3^d)$ time.  Finally, we check the table to see whether the template $[x,x,\dots,x]$ is expressible as a sum of input vectors.  YAs described, this tells you whether any valid combination exists; you can augment this algorithm to keep track of all valid combinations.

This might be workable if $d$ is not too large; otherwise, it will be highly inefficient.  It has the benefit of being not too difficult to implement, but it is probably strictly worse than the prior algorithm in asymptotic efficiency.

Integer linear programming

Finally, it is possible to encode your problem directly as an instance of ILP.  I suggest you introduce zero-or-one variables $X_1,\dots,X_n$, with the intent that $X_i=1$ means input vector $v_i$ is included in the combination.  Also, define $w = \sum_i X_i v_i$, and introduce zero-or-one variables $Y_{j,0},Y_{j,1},Y_{j,x},Y_{j,2x}$ for $j=1,\dots,d$, with intended meaning as follows:

$Y_{j,0}=1$ means that $w_j$ is zero.
$Y_{j,1}=1$ means that $w_j$ is not divisible by $x$.
$Y_{j,x}=1$ means that $w_j$ is $x$.
$Y_{j,2x}=1$ means that $w_j$ is a multiple of $x$ that is strictly larger than $x$ (i.e., $2x$ or $3x$ or ...).

I'll show how to enforce consistency of these variables in a moment using linear inequalities.  Once we've done that, all that remains is to require that $X_1 +\dots + X_n=m$ (a combination contains exactly $m$ of the input vectors) and $Y_{1,x}+\dots+Y_{d,x}=m$ (exactly $m$ of the coordinates sum to $x$) and then test whether the entire system of inequalities is feasible, and if so, report all solutions.  That can be done using an off-the-shelf ILP solver.

To enforce the consistency of the $X$'s and $Y$'s, we add the following linear inequalities:

$Y_{j,0}+Y_{j,1}+Y_{j,x}+Y_{j,2x}=1$ for each $j$ (exactly one of those four cases must be true).
$X_i \le 1-Y_{j,0}$ for each $i,j$ such that $v_{i,j}>0$ (something that sums to zero can't have any nonzero terms in the sum).
$\sum_{v_{i,j}>0} X_i \ge 1-Y_{j,0}$ for each $j$ (if it doesn't sum to zero, at least one of the terms in the sum is nonzero).
$\sum_{v_{i,j}=1} X_i \ge Y_{j,1}$ for each $j$ (something that sums to a non-multiple of $x$ must have at least one term that is a $1$).
$X_i \le Y_{j,1}$ for each $i,j$ such that $v_{i,j}=1$ (if the sum has a term that is a $1$, then it sums to a non-multiple of $x$, since $x>n$).
$\sum_{v_{i,j}=x} X_i \ge Y_{j,x}$ (anything that sums to $x$ must have at least one term that is an $x$).
$\sum_{v_{i,j}=1} X_i \le 1-Y_{j,x}$ (anything that sums to $x$ cannot have any terms that are a $1$).
$\sum_{v_{i,j}=x} X_i \ge 2Y_{j,2x}$ (anything that sums to a multiple of $x$ larger than $x$ must have at least two terms that are an $x$).
$\sum_{v_{i,j}=1} X_i \le 1-Y_{j,2x}$ (anything that sums to a multiple of $x$ larger than $x$ cannot have any terms that are a $1$).

Hardness

Your problem is NP-hard.  Consider the special case of your problem where all entries are in $\{0,x\}$ (no input vector contains a $1$), where $m=d$, and where there are at least $m$ copies of the all-zeros vector in the input list.  This special case is equivalent to exact cover, which is NP-hard.  If a special case of your problem is NP-hard, then your problem is certainly NP-hard.  So, we shouldn't expect an efficient algorithm for your problem.   See What is the definition of P, NP, NP-complete and NP-hard?, What are common techniques for reducing problems to each other?, and Dealing with intractability: NP-complete problems for some reference material on those subjects, or grab a good algorithms textbook.


Non context free language that is pumpable?

As you say "thus escaping the language" which means your example language is not pumpable: for $m=1$ we cannot pump $d$ and stay in the language. Instead consider $D= C \cup \{a,b,c\}^*$. Now we can pump $d$ whenever it is present, and we can pump any string that does not contain $d$.


Is this a correct description of Dijkstra's algorithm

Not bad. May I suggest a few improvements?

Distinguish between the algorithm (what you do) and the argument (the
proof of why it works).
Your D, which you say is a list, is better thought of as a
map/associative-array from Node to [distance, Node], where the former
Node is the predecessor of the latter.
Start the computation with {start-node -> [0, nil]} in D.
Define the graph G as a mapping Node -> Set of [distance, Node],
where the distance is the edge length from the former to the latter
node. This makes the iterative step easier to describe precisely.

The point of Dijkstra's algorithm is that the tentative distances turn out to be final. The way to prove this is to show that - given that it is true of D so far - it is true at the next step too. This is called the inductive hypothesis. Given that it is true of the initial D, which it is, it is true of all the Ds thereafter, including the final one.


What is the difference between a block and a procedure?

In programming languages I 've seen, they are not the same.

A procedure (or function) definition is a block of code with a header, that specifies 0 or more arguments, and a name. It allows the procedure to be called by specifying its name and a list of argument values. In many languages, anonymous functions or procedures can be defined, which have a block of code and a header with arguments, but no name. In some languages, a block can act as an anonymous procedure or function without arguments; in other languages, it cannot.

For instance, in C, Java and C#, a block just serves to group statements and create a scope for local variables; it cannot be used as a procedure/function.

In Perl, on the other hand, blocks can be used in contexts that expect procedures/functions (subroutines), and in PostScript, a block denotes a code object (a procedure) that can be bound to a name.

I've never used blocks in Lisp, but apparently, the situation is much the same there: a Lisp procedure (function, in Lisp) contains a block, implicitly, but a block by itself does not constitute a procedure. It cannot be called by giving its name and values for its arguments, if I understand correctly.


How to construct object oriented programming in pseudo code?

Pseudocode has no formal definition. Use whatever notation you want, as long as it is either self-explanatory (even for people unaware of C++) or explained in the text.

I suggest looking at several textbooks and papers to see what the "industry standard" is, and using something similar.


How can I determine an algorithm from a table of numbers?

On input $n$, output
$$
0^2 - n^2, 1^2 - n^2, 2^2 - n^2, \ldots, (3n-1)^2 - n^2.
$$
In pseudocode:

  For integer $k$ from $0$ to $3n-1$, print $k^2-n^2$.


Accurate way to compute the sum of exponentials

Let $a = \max_i a_i$. Then your expression is equal to
$$
a + \log_2 \frac{\sum_i 2^{a_i-a}}{n},
$$
and this should be a very good approximation (this is "renormalization"). Don't forget to add the numbers in decreasing order of magnitude (that is, sort the $a_i$'s so that they are in decreasing order).


Euclidean algorithm and well define ness on the underlying set

We can think of the GCD algorithm as taking place inside a directed graph. The vertices of the graph are all pairs $(a,b)$, where $a,b \geq 0$. If $a \neq 0$, then there is an edge from $(a,b)$ to $(b \bmod a, a)$. The algorithm starts at some vertex $(a,b)$, follows the unique outgoing edges, until (hopefully) reaching a leaf $(0,b)$, at which point it outputs $b$.

We can consider a more general situation, in which we are given a directed graph in which every vertex has at most one outgoing edge, and a starting vertex. We start at that vertex, and follow the unique outgoing edges, stopping if we ever reach a leaf. In this generality, we cannot be certain that the process always terminates. In fact, if the graph contains a directed cycle and we start with a vertex on the cycle, the process will ever terminate!

Consider for example the graph on $1,2,3$ with edges $1\to 2$, $2 \to 3$, $3 \to
1$. On this graph, the iterative process will never terminate.

There is another reason for the process to not terminate: there might be an infinite directed path.  For example, consider the directed graph on the integers in which the edges are $a \to a+1$. This graph contains no cycles, but nevertheless the process does not terminate.

To show that the GCD algorithm always terminates, we define a potential function $\phi$ on the vertices by $\phi(a,b) = a$. If $(a,b) \to (b \bmod a,a)$ then
$$
\phi(b \bmod a,a) = b \bmod a < a = \phi(a,b).
$$
Therefore the potential decreases. Since the potential is always a natural number, and these are well-ordered, it cannot decrease forever, and therefore the algorithm necessarily terminates.

To finish, let me mention the Collatz conjecture. Consider the directed graph on the positive integers in which the edges are $2n \to n$ and $2n+1 \to 3n+2$ for all $n \geq 1$. The Collatz conjecture states that the process considered above always terminates, no matter what the starting vertex is. The conjecture is suspected to be true, but nobody knows how to prove it.


It seems I didn't understand the question.
There is no regular expression for this language because it is not regular. You can prove it using the pumping lemma.


Can the processor just turn off the interrupt request line?

It depends on the processor arhitecture, but yes, most processors can turn off interrupts.  Shutting them completely off is usually only done in special situations like booting or critical error handling.

More commonly, interrupts are blocked until the CPU returns from the interrupt handling routines.  These routines should typically do the minimum amount of processing required, then return from interrupt to finish any work (forking down to a lower level for most of the work).

An older system I'm most familiar with, the VAX architecture, allowed for multiple interrupt levels (up to 31) and when an interrupt occurred the CPU would run at an IPL level corresponding to that interrupt.  All other interrupts at or below that IPL would be blocked until the IPL was lowered below the level of pending interrupts, then the pending interrupt would be delivered.  There was also a SETIPL instruction that allowed critical system code to block certain types of interrupts while critical code executed.  On single processor systems this was an effective synchronization technique that prevented multiple streams from changing data structures in an uncontrolled manor (multiprocessor systems required using other techniques like spinlocks).  Some problem with blocking interrupts are that multiple pending interrupts would be delivered as a single event and devices with unserviced interrupts sometimes get timeout errors.  So running at elevated levels for extended periods is discouraged.


How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$

Let us define 4 non-terminals $X_{00}, X_{01}, X_{10}, X_{11}$ and the start variable $S$. The rules are as follow:
\begin{align}
S &\rightarrow X_{00},\\
X_{01}&\rightarrow \epsilon,\\
X_{00}&\rightarrow 0X_{10},\\
X_{00}&\rightarrow 1X_{10},\\
X_{01}&\rightarrow 0X_{11},\\
X_{01}&\rightarrow 1X_{00},\\
X_{10}&\rightarrow 0X_{00},\\
X_{10}&\rightarrow 1X_{11},\\
X_{11}&\rightarrow 0X_{01},\\
X_{11}&\rightarrow 1X_{10},\\
\end{align}
where the first index tells the parity of the number of zeros and the second one the parity of the count of ones.

Try to prove the correctness as an exercise.


Let $T=\{\tau_1,\cdots, \tau_k\}$ be the set of truth assignments. Consider the tree of the truth assignments $2^\omega$.

Consider the formula
$\Gamma_T = \{ \underset{\tau \in T}\lor \tau_{|n} \mid n \in \omega\}$
where $\tau_{|n}$ is the formula that expresses $\tau$ up to atom $p_n$, i.e. $\underset{i\leq n}\wedge l_i(\tau)$
where
$l_i(\tau) = \begin{cases}
p_i & \tau(p_i)=\top \\
\lnot p_i & \tau(p_i)= \bot
\end{cases}$.

It is easy to show that every $\tau \in T$ we have $\tau \vDash \Gamma_T$.

For any $\tau \notin T$, there is some $n\in \omega$ such that $\tau_{|n}$ is different from those in $T$ and therefore $\tau$ does not satisfy $\underset{\tau \in T}\lor \tau_{|n}$ and therefore $\tau\nvDash \Gamma_T$.

There is a topological characterization of the sets of truth assignments that can be defined. Consider $2^\omega$ as space of points with product topology. Consider the sets of points that can be captured using sets of formulas. They are closed under finite unions (consider the disjunctions of the pairs of formulas from the product) and arbitrary intersections (union of two sets).

You may be interested in Stone duality and type (model theory).


An infinite subsequence of random numbers in Kolmogorov sense

If $x$ is Kolmogorov random then $C_U(ax+b) \geq \log x - O(\log a + \log b + 1)$ (why?), and so
$$
\frac{C_U(ax+b)}{\log (ax+b)} \geq \frac{\log x - O(\log a + \log b + 1)}{\log x + O(\log a + \log b + 1)} = 1 - O\left(\frac{\log a + \log b + 1}{\log x}\right).
$$
Since there are infinitely many Kolmogorov random numbers $x$, your result follows.


How does the Galil's rule work on Boyer-Moore algorithm?

The algorithm is based on a simple principle. Suppose that we are trying to match a substring of length n. We are going to first look at character at index m. If that character is not in the string, we know that the substring we want can't start in characters at indices 1 2....n

If that character is in our string, we will assume that it is at the last place in our string that it can be. We will then jump back and start trying to match the string from that possible starting place. This piece of information is my first table.

Once I start matching from the beginning of the substring, when I find a mismatch, I can't just start from scratch. I could be partially through a match starting at a different point. For instance if I'm trying to match anand in ananand successfully match, anan, realize that the following a is not a d, but I've just matched an, and so I should jump back to trying to match my third character in my substring. This, "If I fail after matching x characters, I could be on the y'th character of a match" information is stored in the second table.

Note that when I fail to match the second table knows how far along in a match I might be based on what I just matched. The first table knows how far back I might be based on the character that I just saw which I failed to match. You want to use the more pessimistic of those two pieces of information.


What is the different between Dijsktra's algorithm and KNN?

Almost everything.

$k$ nearest neighbor is a classification algorithm. It stores a list of [(features1, label1), (features2, label2), ..., (features-n, label-n)]. When it gets a new item features it calculates the distance to each of the $n$ stored items. It finds the $k$ closest ones. It returns the label which is most often in those $k$ examples.

Dijkstras algorithm is a graph search algorithm. It takes a graph $G = (V, E)$, a start node $s \in V$ and a target node $t \in V$ as input and returns the shortest path (v_1, \dots, v_n) with $v_1, \dots, v_n \in V$ from $s$ to $t$.

(You might be interested in the label correction algorithm, a generalization of Dijkstras algorithm)

How they can be related. Somehow.

$k$ nearest neighbor can also operate on graphs. If you have a graph-like structure and your distance measure is e.g. the number of hops from a node, then you would use breadth first search.


How to choose waiting process in a preemptive priority-based scheduler

“Preemptive priority” is a property of a scheduler, it is not a complete specification. Under preemptive priority scheduling, you choose the waiting process that has the highest priority. If there are multiple process with that priority, knowing that the scheduler is preemptive priority-based isn't enough to know what it will do. If you want to completely describe a scheduler, you need to specify that case as well.

Two common choices that are used together with preemptive priority-based scheduling are preemptive round-robin (interrupt processes after a certain time if another process with the same priority is ready) and non-preemptive round-robin (a ready process is only ever interrupted by a higher-priority process). But there can be more complex algorithms as well.


Given all pairs shortest paths matrix, find graph with minimum total sum of edges

I think your approach works even if you did not give much details.

Let's call $A$ the matrix. First you sort all pairs ($i$, $j$) with $i < j$ and $A_{ij}$ increasing. You also have initially a graph $G$ with all nodes and no edges.

Then you process the pairs ($i$, $j$) one by one deciding whether to add an edge between nodes $i$ and $j$:

compute $D$, the total weight of the shortest path existing in $G$ from $i$ to $j$ ($+\infty$ if no path).

if $D < A_{ij}$, the problem has no solution,
if $D = A_{ij}$, do nothing,
if $D > A_{ij}$, add the edge between $i$ and $j$ of weight $A_{ij}$ to $G$.

If the shortest path from $i$ to $j$ is undirect, it necessarly has already been placed as you sorted your pairs increasing.


NFA-epsilon: epsilon loops, and how do I deal with them?

if you had a chain of epsilon-arches, would you just jump to the end of the chain instantaneously

I am not sure for "instantaneously", but I would say it accepts the empty string $\epsilon$.

  would this cause a loop and in-turn cause the string to never halt, or would it just create another fork (endlessly?)?

Your input string will be accepted. On any input, a NFA runs by creating many branches of computation in parallel and if one of them reaches the accept states, after it reads the last symbol of the input, then your string is accepted and the entire computation halts. You kind of choose at least onе fork that leads the NFA to the accept state.

  how would I approach said NFA-epsilon example with these example strings: 1011100, 0101111?

Right the first string is not accepted, the second one is accepted.


Computing $n$th lexicographically smallest permutation of length up to $k$

Your kind of problem reduces to the problem of enumeration. For example, suppose that you wanted to know the first letter of the $n$th lexicographically smallest non-empty string of length at most $k$ over the alphabet $S$. You could easily solve that if you could calculate the number of strings of length at most $k$ that start with a given letter.

More generally, the enumeration problem you have to solve in your case is:

  How many strings of length up to $k$ over the alphabet $S$ start with the prefix $w$?

This is not such a hard problem, and I'll let you solve it on your own. I'll also let you figure out how to use the result in order to solve your problem.


In order to write the documentation of the structure of the JSON objects returned from your API you can follow two approaches:

describe the common attributes and of the objects returned by every function of your API; and then for each API function describe the specific attributes (their type, meaning, and example);
Many APIs that use JSON to exchange data are documented using this approach: e.g. Google APIs for various services, Facebook Graph API, Twitter API, ...
In this case I think it is not correct to use the term "schema".
or you can give a formal description of the output using a schema definition language like JSON-schema (designed by the IETF) and that plays the same role of the XML schema definition language for XML.
But I don't know if JSON-schema is an established standard (there is an active Google group, but I didn't find any "notable" example, ... ).
In this case you should provide a valid (json-)schema for the output of each function.

If you choose this approach, then you should say that name and age are two required properties of the (json-)schemas of the (json-)objects returned by the functions of your APIs (but obviously you should provide the full-schemas, too)


Maximum number of steps a Turing machine makes

In general, it is impossible to even determine if it will ever halt. And if it halts, determining the number of steps is also impossible. Check out the busy beaver game for details.

There are general techniques that work in a large proportion of cases of practical interest, for a start check out the reference question here. But there have been complete libraries written on the intricacies of the matter...


What is a brief but complete explanation of a pure/dependent type system?

Let's have a go. I'll not bother about Girard's paradox, because it distracts from the central ideas. I will need to introduce some presentational machinery about judgments and derivations and such.

Grammar

  Term   ::=   (Elim)   |   *   |   (Var:Term)→Term   |   λVar↦Term

  Elim   ::=    Term:Term   |   Var   |   Elim Term

The grammar has two mutually defined forms, "terms" which are the general notion of thing (types are things, values are things), including * (the type of types), dependent function types, and lambda-abstractions, but also embedding "eliminations" (i.e. "usages" rather than "constructions"), which are nested applications where the thing ultimately in the function position is either a variable or a term annotated with its type.

Reduction Rules

  (λy↦t : (x:S)→T) s   ↝  t[s:S / y] : T[s:S / x]

  (t : T)  ↝  t

The substitution operation t[e / x] replaces every occurrence of the variable x with the elimination e, avoiding name capture. To form an application that can reduce, a lambda term must be annotated by its type to make an elimination. The type annotation gives the lambda-abstraction a kind of "reactivity", allowing application to proceed. Once we reach the point where no more application is happening and the active t : T is being embedded back into the term syntax, we can drop the type annotation.

Let's extend the ↝ reduction relation by structural closure: the rules apply anywhere inside terms and eliminations that you can find something matching the left-hand side. Write ↝* for the reflexive-transitive (0-or-more-step) closure of ↝. The resulting reduction system is confluent in this sense:

  If s ↝* p and s ↝* q, then there exists some r such that p ↝* r and q ↝* r.

Contexts

  Context   ::=     |   Context, Var : Term

Contexts are sequences which assign types to variables, growing on the right, which we think of as the "local" end, telling us about the most recently bound variables. An important property of contexts is that it's always possible to choose a variable not already used in the context. We maintain the invariant that the variables ascribed types in the context are distinct.

Judgments

  Judgment   ::=   Context ⊢ Term has Term   |   Context ⊢ Elim is Term

That's the grammar of judgments, but how to read them? For a start, ⊢ is the tradional "turnstile" symbol, separating assumptions from conclusions: you can read it informally as "says".

  G ⊢ T has t

means that given context G, type T admits term t;

  G ⊢ e is S

means that given context G, elimination e is given type S.

Judgments have interesting structure: zero or more inputs, one or more subject, zero or more outputs.

INPUTS                   SUBJECT        OUTPUTS
Context |- Term   has    Term
Context |-               Elim      is   Term

That is, we must propose the types of terms in advance and just check them, but we synthesize the types of eliminations.

Typing Rules

I present these in a vaguely Prolog style, writing J -: P1; ...; Pn to indicate that judgment J holds if premises P1 through Pn also hold. A premise will be another judgment, or a claim about reduction.

  Terms

  G ⊢ T has t   -:   T ↝ R;   G ⊢ R has t

  G ⊢ * has *

  G ⊢ * has (x:S)→T   -:   G ⊢ * has S;   G, z:S !- * has T[z / x]

  G ⊢ (x:S)→T has λy↦t   -:   G, z:S ⊢ T[z/x] has t[z/y]

  G ⊢ T has (e)   -:   G ⊢ e is T

  Eliminations

  G ⊢ e is R   -:   G ⊢ e is S;   S ↝ R

  G, x:S, G' ⊢ x is S

  G ⊢ f s is T[s:S / x]   -:   G ⊢ f is (x:S)→T;   G ⊢ S has s

And that's it!

Only two rules are not syntax-directed: the rule which says "you can reduce a type before you use it to check a term" and the rule which says "you can reduce a type after you've synthesized it from an elimination". One viable strategy is to reduce types until you've exposed the topmost constructor.

This system is not strongly normalizing (because of Girard's Paradox, which is a liar-style paradox of self-reference), but it can be made strongly normalizing by splitting * into "universe levels" where any values which involve types at lower levels themselves have types at higher levels, preventing self-reference.

This system does, however, have the property of type preservation, in this sense.

  If G ⊢ T has t and G ↝* D and T ↝* R and t ↝ r, then D ⊢ R has r.

  If G ⊢ e is S and G ↝* D and e ↝ f, then there exists R such that S ↝* R and D ⊢ f is R.

Contexts can compute by allowing the terms they contain to compute. That is, if a judgment is valid now, you can compute its inputs as much as you like and its subject one step, and then it will be possible to compute its outputs somehow to make sure the resulting judgment stays valid. The proof is a simple induction on typing derivations, given the confluence of -->*.

Of course, I've presented only the functional core here, but extensions can be quite modular. Here are pairs.

  Term   ::=   ...   |   (x:S)*T   |   s,t

  Elim   ::=   ...   |   e.head    |   e.tail

  (s,t : (x:S)*T).head ↝ s:S

  (s,t : (x:S)*T).tail ↝ t:T[s:S / x]

  G ⊢ * has (x:S)*T   -:   G ⊢ * has S;   G, z:S ⊢ * has T[z / x]

  G ⊢ (x:S)*T has s,t   -:   G ⊢ S has s;   G ⊢ T[s:S / x] has t

  G ⊢ e.head is S   -:   G ⊢ e is (x:S)*T

  G ⊢ e.tail is T[e.head / x]   -:   G ⊢ e is (x:S)*T


Is resolution complete or only refutation-complete?

Resolution is complete as a refutation system. That is, if $S$ is a contradictory set of clauses, then resolution can refute $S$, i.e. $S \vdash \bot$.

This is sufficient since $T \vdash A$ is equivalent to $T \cup \{\lnot A\} \vdash \bot$. So if we want to see a formula $A$ is derivable from $T$, we only need to check if there is a refutation proof for $T \cup \{\lnot A\}$ which can be checked using resolution.


Pizza commercial claim of 34 million combinations

Ok, A bit more detailed answer than in the comments.

Choosing $k$ out of $n$ is done by ${n \choose k} = \frac{n!}{k!(n-k)!}$. So for things like the size of the pizza, where you have 4 options (and you need to choose one, coz pizza cannot be both medium and extra-large at the same times) you have only $4$ options. Indeed, ${4 \choose 1}=\frac{4!}{3!}=4$.

The interesting part are things like the non-meat options. You have 15 and can choose any set of up to 15. Mathematically, this means ${15 \choose 0} + {15 \choose 1} + \cdots + {15\choose 15}$.

As you mentioned, there is a nice formula for such sums:
$$\sum_{i=0}^n {n \choose i} = 2^i$$
thus, for the non-meat options you have $2^{15}=32768$ options, as you said.
(see here for more formulas).

Lastly, to combine all the options, you just multiply them. If you have 4 possible sizes, and, say, 4 possible crusts, then you have $4\times 4=16$ different combinations overall.

So, multiplying everything you get 16.106.127.360, which is larger than 34 million.


You shouldn't be able to beat the complexity of brute-forcing (because of having to check all possible assignments in the case that the CSP is not satisfiable). Instead, I offer the possibility of smart brute-forcing:

Solve the CSP normally and find a single assignment that satisfies it, if one exists. Add the negation of that assignment as a new constraint and jump back to the immediate last decision assignment you made and continue from there. This is a typical procedure for SAT solvers which traverse Implication Graphs and add conflicting clauses as constraints before backtracking to the last assignment decision. However, in the case of solving a SAT problem, each boolean variable can only have one of two possible assignments which is not true for the domains of constraints of CSPs, so you might actually need to backtrack further to find another complete assignment of all variables if one should exist (as per usual brute-forcing).

Let's suppose you have a CSP of three variables $A, B, C$. If you find a solution to the CSP whereby (let's say) C was assigned last, you could backtrack to the point right before making the assignment to C and continue from there, seeing if the same assignments of $A$ and $B$ could lead to a second solution with a different assignment of $C$. After finding your second solution, you could immediately terminate, knowing that the CSP is ambiguous. However, you might have to very well check all possible assignments of each variable in the case your initial solution to the CSP were the only solution (or even when your CSP is not satisfiable), in which case it would be unambiguous. So clearly, this procedure would only improve your efficiency for ambiguous CSPs where any two of all solutions differ with a single variable assignment.


How does MCTS handle games with large numbers of poor moves?

Issues like these are essentially solved in the MCTS itself. The principle of the algorithm is that it tries to make the best pick, rather than guaranteeing it (if done in this randomized fashion rather than a 'pure MCTS' fashion). The trees are built up out of large amounts of collected data, aggretating success rates in the nodes. Nodes that end up being succesful more often will have a larger likelihood of being picked. This process of positive reinforcement means that nodes that always lead to a victory will, over the course of many playthroughs, approach a 100% pick rate.

In your example, node A will have a rougly 50/50 success/failure ratio throughout any number of playthroughs (due to the coinflip). Node B will have a 10/90 ratio of success/failure at first but will approach a 100/0 ratio as the number of playthroughs nears infinity (node C will end up always being picked due to the 100% success rate, and this propagates to node B).

The result is that node B will gradually end up being picked more often than node A, reinforcing the effect and causing it to be picked even more often.

The image on the wikipedia page illustrates it very well; the nodes with a high chance of success gradually make up a larger fraction of the total 'node weight' on a level, thus increasing the odds that it is picked with every playthrough.


How to trigger a thread to start working using semaphore?

When using semaphores or locks, you don't do anything else than acquiring the semaphore (resp. the lock), and then do what you want.  For example, if you want to use a lock, then you typically have two threads

# thread 1
lock.acquire()
# here is all the work for thread 1
lock.release()

and the other thread is completely identical:

# thread 2
lock.acquire()
# here is all the work for thread 2
lock.release()

Now, the first to obtain the lock gets to run the code first, and the other thread needs to wait until the lock is released.

Here's an example of a Python program that prints a series of 0s and 1s depending on the order of execution:

import time
import threading

lock = threading.Lock()
lst = []

def f1():
    for i in range(10):
        lock.acquire()
        lst.append("0")
        lock.release()
        time.sleep(0.1)

def f2():
    for i in range(10):
        lock.acquire()
        lst.append("1")
        lock.release()
        time.sleep(0.1)

t1 = threading.Thread(target=f1)
t2 = threading.Thread(target=f2)
t1.start()
t2.start()
t1.join()
t2.join()

print("".join(lst))

Feel free to run it in your own terminal.

(Note that I used lock.acquire() and lock.release(), but the "correct" way is to use a context manager and use with lock: ....)

See also:  Lock, mutex, semaphore… what's the difference?


Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?

By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then $P=NP$. So, short answer is - no.
However, its possible to think instead of solving the problems fully, to approximate a solution, or to solve them randomly. There are attempts at attacking from those points of view, but they are not perfect at all. Randomization isn't known to help "as-is", and many NP-hard problems are known that are also hard to approximate (finding an approximation will yield $P=NP$)
There are also attemps taking a look at notions much stronger than the usual turing machine. For instance, the quantum computer can be considered one. Another obvious example is the non-deterministic turing machines, in which - by definition - $NP$ would be in polynomial time.


Proving $ \{ \langle D_1, ... ,D_K \rangle : \text{ where } D_i \text{ are DFAs and } {\bigcap}_{i=1}^k L(D_i) = \emptyset \} $ is NP-Hard

The language $L$ is in fact PSPACE-complete, so in particular it's both NP-hard and coNP-hard. Here is a quick sketch of the proof.

$L$ is in PSPACE. This part is easy. The intersection of the DFAs can be realized as a DFA with $n^n$ many states, hence if the intersection is non-empty, there must be a word of length $n^n$ accepted by all DFAs. Counting up to $n^n$ requires $O(n\log n)$ space, so there is an NPSPACE machine for $L$: the machine guesses a word of length at most $n^n$ and verifies (in parallel) that the word is accepted by all DFAs. Savitch's theorem shows that NPSPACE=PSPACE, so we're done.

$L$ is PSPACE-hard. The reduction is from TQBF, which is the problem, given a formula $\varphi(x_1,\ldots,x_n)$, to decide the truth value of $\psi = \exists x_1 \forall x_2 \exists x_3 \cdots \varphi(x_1,\ldots,x_n)$. Consider some iterative algorithm for evaluating $\psi$: it goes over all possible assignments of $x_1,\ldots,x_n$, and computes intermediate values of $Q x_i \bar{Q} x_{i+1} \cdots \varphi(y_1,\ldots,y_{i-1},x_i,\ldots,x_n)$ (where $Q \in \{\forall,\exists\}$). We can write this computation as one long string $w$. The computation can be verified locally: for example, if all we wanted is to verify that $w$ is a $\#$-separated list of all numbers from $0$ to $2^n-1$ in binary (i.e. for $n=2$, $\#00\#01\#10\#11$), then we can write several regular expressions which verify this:

$w$ is a $\#$-separated list: $(\#(0+1)^n)^*$
$w$ starts with $0^n$: $\#0^n\Sigma^*$
$w$ ends with $1^n$: $\Sigma^*\#1^n$
The LSBs in $w$ behaves correctly: $(\#(0+1)^{n-1}0\#(0+1)^{n-1}1)^*$
The MSBs in $w$ behaves correctly: $(\sum_{i=0}^{n-2} \#0(0+1)^i0(0+1)^{n-2-i})^*\#01^{n-1}\#10^{n-1}(\#1(0+1)^{n-1})^*$
Similar (but more complicated) regular expression ensure that the other bits behave correctly.

All these expressions (and the corresponding DFAs!) are of length polynomial in $n$, and there is a polynomial number of them, so using DFA intersection you can express the fact that $w$ is of the given form.

The actual $w$ is more complicated, but the idea is the same. At the very end of $w$ will appear the actual value of $\psi$, and we can add a regular expression which verifies that $\psi$ is true. This reduces TQBF to DFA intersection.

The classical reference is Kozen's Lower bounds for natural proof systems, or you can check my account (Section 4) which proves a different result but contains everything that you need to prove that $L$ is PSPACE-hard.


Count unhappy numbers in a large interval

I suggest you to start reading this Wikipedia page for an explanation, and then select from Rosetta code an implementation in one of the programming languages you know and to study it. Many algorithms are either based on caching or detecting the loop 4, 16, 37, 58, 89, 145, 42, 20, 4, ...

A dynamic programming solution, implemented in Haskell, is available here.

EDIT

The C source code available here uses the GNU GMP library to test for happiness of very large numbers. You can use it to test far beyond $10^{18}$, assuming you have enough memory. The code is for windows, but is easily portable to linux and Mac OS X.


Do relativized relations between complexity classes tell us anything about the nonrelativized relation?

I am by no means an expert, but 2 things come to mind:

Because if we know things like $A^L \neq B^L$, for some $L$, then a proof of $A = B$ need to be non-relativizing. This puts constrains on the techniques used for such a proof, and thus it is helpful in the way towards getting a proof.

Because if you prove $A^L = B^L$, and the oracle is not very strong, then it seems that you are narrowing down the possibility of $A \neq B$, as with some extra help they become equal. This can arguably be evidence towards believing that $A = B$. To me it feels like saying that John and Peter were equally strong in a fight with boxing gloves. That doesn't necesarily mean that they will be equally strong without the gloves, as one of them could be weaker but use the gloves better. Nevertheless, the information about their fight with gloves is arguable evidence of their relative strength.


regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$

Yes, the regular expressions $r_1=\Lambda+(a+b)^*b$ and $r_2=(b+aa^*b)^*$ are equivalent.  There are several ways of doing this.

Just observe that both of them match the empty string and all strings ending with $b$.

Convert them to automata and then produce automata for $L(r_1)\setminus L(r_2)$ and $L(r_2)\setminus L(r_1)$. Minimize both automata and find that they both accept the empty language.  (Actually, you'll find that you make a ton of mistakes and at least one of the automata accepts something, and at least one of the minimizations is wrong. But, if you were a computer, this wouldn't be an issue.)

Clearly both regular expressions match the empty string, so let's show that they match the same non-empty strings, too.  Suppose that $w\in L(r_2)\setminus\{\Lambda\}$. Then we can write $w=w_1\dots w_\ell$ where each $w_i$ is a string that either matches $b$ or $aa^*b$. In particular, $w_\ell$ must match one of these things, so the last character of $w_\ell$ is a $b$, so $w\in L(r_1)$.
Conversely, suppose that $w\in L(r_1)\setminus\{\Lambda\}$. Write $w=s_1\dots s_n$, where each $s_i\in\{a,b\}$. Suppose there are $\ell$ $b$s in $w$ and let these be at positions $p_1, \dots, p_\ell$. Because $w\in L(r_1)$, $p_\ell=n$ (the last character is $b$).  For convenience, let $p_0=1$. We can now write $w=w_1\dots w_\ell$, where $w_i=s_{p_{i-1}+1}\dots s_{p_i}$. For each $i\in\{1, \dots, \ell\}$, we have $w_i=a^{p_i-p_{p-1}-1}b$, so each $w_i$ matches either the regular expression $b$ or $aa^*b$. Therefore, $w$ matches $(b+aa^*b)^*= r_1$.

By the way, a fourth equivalent regular expression is $(a^*b)^*$, which you can see by observing that the inner part of $r_1$ is equivalent to $b+a^+b$, which is $a^*b$.


The hint is another way of describing the same language. For the two languages to be the same, one must have: $x=p$, $y=p+q$, $z=q+r$, and $w=r$. Notice that these do satisfy the constraints $y\gt x, z\gt w$ and $x+z=y+w$ provided that $q,r\gt 0$. Now the structure of the hint language makes it easy to write a grammar.

$S \to ABA$

$A \to aAb|ab$

$B \to bBa|ba$


The second definition isn't valid, since it's self-referential. Given the first definition, the second statement is an easy theorem that follows from the first definition.

Indeed, suppose we define NP-completeness using the first definition. Let's see that the second definition is true.

$\Longrightarrow$ If $L$ is NP-complete then for all $L'$ in NP, $L'$ reduces to $L$. In particular, SAT reduces to $L$. Since SAT is NP-complete by Cook's theorem, there exists an NP-complete problem $L'$ (namely SAT) that reduces to $L$.

$\Longleftarrow$ Suppose $L$ is in NP and some NP-complete problem $L'$ reduces to $L$. We will show that every problem $M$ in NP reduces to $L$, and so $L$ is NP-complete. Given a problem $M$ in NP, since $L'$ is NP-complete, $M$ reduces to $L'$. Since $L'$ reduces to $L$, $M$ also reduces to $L$, and we're done.

The proof used two properties: (1) there exists some NP-complete problem, (2) reducibility is transitive: if $A$ reduces to $B$ and $B$ reduces to $C$ then $A$ reduces to $C$.

Finally, any two NP-complete problems reduce to each other (via the definition), and in this sense they form an equivalence class of the reduction relation.


"Ways to make change for a dollar": How to optimize with constraints

The way I understand this, it seems to be the classic coin change problem with a few constraints which you have provided. Although if we try to consider all the subsets of the available coins this problem will definitely take exponential time in terms of number of coins available. (The size of the power-set , each subset has to be considered although few optimizations exist but still it doesn't reduce the time to polynomial). For reducing the time taken we can employ the optimization called memorization.

  return change(list, (number - list[0])) + change(list[1:], number)

If you see the line closely in your solution you can see the problem has overlapping subproblems which will be computed again and again. For optimization we try to remember the results of the subproblems and return this precomputed result if we encounter the same sub-problem again.However, as you can guess there is a space-time trade-off here. For speeding up we need to remember the results for this we need atleast $\mathcal{O}({n})$ space (n is the sum which we are trying to make.).

For overlapping subproblems consider the example of making a sum of N using coins 2,3 and, 5.

Suppose solution is given by F(n), then

let us choose the permutations i can make using 2:

Then F(n) = 1+F(n-2)

Now let us choose coin 3:

F(n) = 2+F(n-5)
.
.
.
.
 We calculate this quantity and return the result.
However suppose if we choose 5 in the starting step.

then F(n) = 1+ F(n-5)

We now have to calculate F(n-5) again. Hence overlapping subproblems exist.

For the constraints which you have mentioned we can add those constraints by maintaining a count of each coin as well as total count of the coins used at each step of the recursive call to our function (In the function which is named $change(list, number)$ in your implementation ) we can check the constraint and add zero as the result of that particular function call as it generated an invalid permutation. valid permutation contributes to a 1 in our function.
Our function will look something like this :

def change(list, number, countCoinsList, totCount):
if (number is 0):
    return 1
if (len(list) is 0):
    return 0
if (number < list[0]):
    return 0
if(countCoinsList[i]<8)
     countCoinsList[i]+=1
     tmp1= change(list, (number - list[i]),countCoinsList,totCount+1)

 tmp2= change(list[i+1:], number,countCoinsList,totCount)
return  tmp1+tmp2;


Problems that don't have polykernel when parametrized by vertex cover

Yes, consider the clique problem (W[1]-hard for the parameter solution size). The problem is FPT when parameterized by the vertex cover number: any clique can contain at most one vertex outside the vertex cover, so it is enough to look at only $2^\tau(n-\tau+1)$ possible solutions, where $\tau$ is the vertex cover number.

On the other hand, the clique problem has no kernel of polynomial size (unless $\text{NP} \subseteq \text{coNP/poly}$). See e.g. the arXiv version

Bodlaender, Hans L., Bart MP Jansen, and Stefan Kratsch. "Cross-composition: A new technique for kernelization lower bounds." arXiv preprint arXiv:1011.4224 (2010).

The same is true for weighted feedback vertex set according to the paper.


Why have additional symbols on a Turing machine?

Turing Machines are an abstract model of computation, their purpose is to define in a mathematical way what problems are theoretically computable and which are not.

It is true that a binary alphabet is enough to reach the full expressive power of Turing Machines. However, when playing with them "in practice" to prove theorems and to communicate these proofs, it can be more convenient to use more symbols, instead of encoding everything in binary. We could always go back to binary if it's absolutely needed.

An extreme example of the same sort would be "why are we still using 26 characters to write texts, now that we know that two are enough? It would save time when learning the alphabet!".


Automated geometric theorem-proving using synthetic methods

(Note: I don't know anything about geometric reasoning, so I'm shifting from my limited experience in automated theorem proving in another field. I think the fundamental issue is the same.)

Synthetic reasoning tends to blow up exponentially. Typically, after $n$ steps of reasoning, there are about $a^k$ ways to choose a next step for some $a \gt 1$. There might be some overlap because there are multiple ways to prove the same theorem, but you still end up with a really fast combinatorial explosion in practice.

Reasoning from the goal is typically a lot tamer, because you tend to try to deduce the goal from simpler premises. It's still impractical in all but rather constrained settings (e.g. some arithmetic or geometric theories).

Putting a geometric problem into equations sets a boundary on the problem. You have $p$ equations and $q$ unknowns, now go and solve. Since the problem is bounded, the search for a solution will not go on forever. Furthermore, this form is convenient for many shortcut tricks that allow for faster solving, because solving algebraic equations is a well-known problem.

This choice of method is not less insightful than synthetic reasoning. An algebraic solver can keep track of the reasoning steps that it uses, and produce a proof trace that explains why the purported solution is really a solution. (Not all solvers bother to keep a proof trace.) This proof trace can be expressed in terms of geometric axioms. Thus you can get the same amount of insight no matter how the proof was obtained. (Insight, or lack thereof: in synthetic reasoning, “and then you apply this lemma” doesn't tell you why this lemma rather than any other lemma.)


How to Convert from Decimal to Qm.n format

Convert $0.065$ in binary with 15 digits of precision in the fractional part (rounding to the nearest such number):

$$
(0.065)_{10} \approx ( 0.000100001010010)_2$$

Multiply $(0.000100001010010)_2$ by $(2^{15})_{10}$ (i.e., remove the fractional-part separator) to obtain $(0000100001010010)_2$.

If you want it in hexadecimal, as you have asked in another question, you can convert it:

$$
(0000100001010010)_2 = (0852)_{16}
$$.


How can ships in Battleship be partitioned into B subsets, each with a capacity C?

The idea is to reduce the bin packing problem to battleship, not the other way around.

The variant of bin packing they use in the paper is to decide if it is possible to partition $n$ numbers into $B$ subsets (the bins) so that the numbers into each subset add to a quantity $C$.

Example:

Input:

The set $\{2,3,5\}$ , $B=2$ and $C=5$

Possible solution:

Two subsets $1$ and $2$:

$1 = \{2,3\}$

$2 = \{5\}$

This problem can be reduced to battleships  in the following way:

Create a board of width $B \times 2$ and height $S + n$ , where $n$ is the cardinality of the subset we are going to partition and $S$ is the sum of all the elements of the multiset we want to partition.

Then for each pair of columns that belong to each bin, we set the number that the  first column should ammount to $0$ and the other one to $C$. These numbers are the number of pieces of a ship that there should be in each column.

For the rows:
For each number $a_i$ that belongs to the multiset that we want to partition, we have a separator row with a value of $0$ and $a_i$ rows with a value of $1$. These numbers make reference to the number of boat pieces that there should be in each row.
For each row that belongs to a number, we have only a ship piece because we want each of the $a_i$ numbers to be covered by a single ship of that size.

So in one column of each column pair we will have a separator row and a vertical strip of $a_i$ rows of height for each number of the multiset we have to partition. We can cover that strip with a ship or not, but we have to cover enough strips of a column so that the number of ship pieces of that column adds to exactly $C$.

Because a picture is worth a thousand words i made a picture of a solved example board that we obtain by reducing an instance of bin packing to battleship

The instance of bin packing that i'm going to use as an example is:

The set $\{2,3,5\}$.

$B=2$

$C=5$

The shaded squares are squares that are occupied by a boat.

Thanks for bringing my attention to this problem, i didn't know it.

Hope this is helpful.


Set of Turing machines $S$ such that any $A \in S$ halts on input the description of any $B \in S$

Let us construct a Turing machine $M$ such that $M$ first generates its own description $\langle M \rangle$ by recursion theorem. Then for any input $w$ it first checks if $w=\langle M \rangle$, if yes it halts. If not it starts counting infinitely. Now let $S=\{\langle M \rangle\}$. If you try to add any other Turing machine $T$ to $S$ , it could not be part of $S$ as $M$ won't halt on $\langle T \rangle$. Thus following your definition of a maximal set,  $S=\{\langle M \rangle\}$ is such a set.


Constructing logical sentences that involve negative integers over the nonnegative integers

Any integer $x \in \mathbb{Z}$ can be expressed in the form $x = x_+ - x_-$ where $x_+ \in \mathbb{N}$  and $x_- \in \mathbb{N}$ (i.e., every integer can be expressed as the difference of two natural numbers; and conversely, the difference of any two natural numbers is always an integer).

Try using that to formulate your statement.  You'll need to work out how to define the $\le$ operator, but that's a separate issue.


surprizing reducibility and challenge on it

I am assuming that $A$ is a non-trivial problem. If $A$ is trivial, then the claims cannot be correct in their current form (make sure you understand why).
Consider an  NP-complete problem $B$, and consider some non-trivial problem $A \in \text{P}$. Clearly, $A\leq_p B$. If we assume that claim 2 is correct, then as $A\leq_p B$, we get that $A$ is $\text{NP}$-hard and thus for every problem $L\in \text{NP}$, it holds that $ L\leq_p A$. Hence, as $A\in \text{P}$, we get that $L\in \text{P}$ as well, and so $\text{NP}\subseteq \text{P}$.
Conversely, if we assume that $\text{NP}\subseteq \text{P}$, then as every non-trivial problem is $\text{P}$-hard, we get that every non-trivial problem $A$ is $\text{NP}$-hard. Hence, claim 2 holds trivially.
So we have in total that claim 2 is correct iff $\text{P} = \text{NP}$ which is quite open.


Are there any types of distributed databases which allows untrusted peers, like Blockchain?

Distributed Hash Tables (DHT) are key value stores that work in a P2P manner, which is basically a database. There are implementations that don't rely on trust between peers. Obviously this can only be achieved by strong replication and consensus on the current value to a given key. So you face similar problems as with a blockchain.

The Wikipedia Article https://en.wikipedia.org/wiki/Distributed_hash_table will give you a good overview. Chord and Tapestry are probably the most famous DHT concepts.

If you want to look at applications instead The DHT approach is mostly used in peer-to-peer file hosting and file sharing.

There might also be other distributed databases or database-like concepts out there. This is just one I know.


Linear equation solving with special sparse coefficient matrix

There are iterative methods in which each iteration takes time $O(nnz)$, where $nnz$ is the number of non-zero entries. See for example Chapter 4 of Saad's lecture notes. For the state-of-the-art, consult Section 5 of Lee and Sidford (2013). For special types of matrices, see Lee, Peng and Spielman (2016).


Time complexity of dequeue function (queues)

It's $\Theta(n)$. Observe that if you are limited by $n$ operations, the total number of elements that ever enter the queue is less than or equal to $n$. Furthermore, every element is processed at most twice: once when it enters the queue, and once when it leaves the queue, therefore the total time is at most a constant times $n$.


Showing that Karger's contraction algorithm has exponentially small probability of finding an optimum

Consider a graph $G$ with nodes $s$ and $t$, and $n-2$ other nodes $v_1, ..., v_{n-2}$. There are two parallel edges from $s$ to $v_i$, and one edge from $v_i$ to $t$. The minimum $s-t$ cut is to separate $t$ by itself.

If we run the version of the contraction algorithm described in the problem, it will independently contract each of the length-2 paths from $s$ to $t$ in some order. In order for it to find the minimum $s-t$ cut, it must contract $v_i$ into $s$, not into $t$. There is a $\frac{2}{3}$ chance of this happening for each $i$, so the probability that the minimum $s-t$ cut is found is $(\frac{2}{3})^{n-2}$, an exponentially small quantity.

Though, I don't know whether this one works.


Applying subproblem technique to permutations with grouping

The subproblems can be broken down as follows.

f0 :- Number of available 0s.

f1 :- Number of available 1s.

ld :- The last digit of the string generated till now.

dp[f1][f0+f1][0] = dp[f1][f0+f1-1][0] + dp[f1-1][f0+f1-1][1]

dp[f1][f0+f1][1] = dp[f1-2][f0+f1-2][0] + dp[f1-1][f0+f1-1][1]

which basically boils down to,

Say at any step the string is S0

then S011 and S00 are valid as well.

Similarly,

if the string is S1 then S11 and S10 are valid as well.

The following code solves the given problem recursively.

def rec(f0,f1,stn): # Frequency of 0,Frequency of 1, List to store generated output
  if f0==0 and f1==0:
    print(''.join(stn))
    return -1;
  if len(stn)==0 or stn[-1]=='0':
    if f0>0:
      rec(f0-1,f1,[x for x in stn]+['0'])
    if f1>1:
      rec(f0,f1-2,[x for x in stn]+['1','1'])
  else:
    if f1>0:
      rec(f0,f1-1,[x for x in stn]+['1'])
    if f0>0:
      rec(f0-1,f1,[x for x in stn]+['0'])

rec(4,4,[])

You can easily solve the overlapping subproblems issue by using a dp-table along with the propagation rules listed above.

Output of the code for a string with 4 1s and 4 0s:-

00001111
00011110
00011011
00111100
00110011
00110110
01111000
01100011
01100110
01101100
11110000
11000011
11000110
11001100
11011000


If by deterministic GNF you mean as a deterministic grammar that is also GNF then yes, here is the paper. Normal forms of deterministic grammars

  It is shown that every strict deterministic language may be given a
  strict deterministic grammar which is also in Greibach normal form.

EDIT
Here is a paper outlining the technique to do the conversion Strict deterministic grammars and Greibach normal form


The length of the smallest co-prime chain between any two integers

The conjecture $\ell \leq 2$ seems to be open. It is stated as Conjecture 3 in a paper of Dowe. Dowe does show that the Goldbach conjecture implies that $\ell \leq 3$, and mentions that Alan Woods showed in his PhD thesis that $\ell$ is bounded. Perhaps the recent proof of the odd Goldbach conjecture also implies a definite and small bound.

If $\ell > 1$ then $b-a$ is an Erdős-Woods number. In particular, if $\ell > 2$ then both $b-a$ and $b-a-1$ have to be Erdős-Woods numbers. A059756 lists the first few Erdős-Woods numbers. While all numbers on that list are even, there are also odd Erdős-Woods numbers, some of which are listed in A111042. The smallest values of $a$ corresponding to given differences are listed in A059757. While this list is not increasing, it does seem as if the numbers are growing pretty fast. Any counterexample to $\ell \leq 2$ would to be such that both $b-a$ and $b-a-1$ are Erdős-Woods numbers, and in particular $b-a > 430$ (per A059756). This suggests (but does not prove) that any such counterexample will be huge, and so for all practical purposes we can assume that $\ell \leq 2$.


Time complexity of a precedence constrained selection problem

If you flip the signs on your costs and reverse edge directions, this is the Closure Problem, also known as the Open-Pit Mining Problem, and it's actually solvable in polynomial time using a rather non-obvious transformation into maximum flow.

The algorithm is described in the Wikipedia page linked above.  Briefly, it involves setting the capacity of each edge to infinity, which has the effect that any minimum cut avoids all original graph edges in the forward direction (since any cut that included such an edge would have infinite flow), and adding a new edge to each vertex from one of two new vertices, $s$ (for positive-weight vertices) or $t$ (for negative-weight vertices).  The capacity of any $s$-$t$ cut magically works out to be a constant minus the total weight of vertices on one side of the cut, so minimising this (which can be done by a max-flow algorithm) maximises said total weight!


Logarithmic vs double logarithmic time complexity

Do not forget that $\log n$ still grows exponentially (in $\log(n)$) faster than $\log(\log n)$!

Indeed, if you look at the quotient of $\log(n)$ and $\log(\log(n))$, there is not much impressive to see:

[source]

But still, you get a factor five to six for sizes up to $100000$. Note that larger sizes are not uncommon in practice, and a speedup by that factor is awesome! It may make the difference between having results after lunch or only tomorrow. Be aware that part of the speedup may be eaten away by higher constants of the tree implementation; you would have to plot (or analyse) $c\cdot \log(n)$ and $d\cdot \log(\log(n))$ with $c,d$ the actual runtime constants to get a real picture.

Additionally, what Dave mentions is important: if the operation sped up thusly is executed, say, linearly often, constant speedups become linear speedups, i.e. you may decrease the leading constant of your entire algorithm! As I said above, that is awesome. Just look at what happens if you run the operation $n$ times:

[source]

Now if that's not worth the trouble I don't know what.


Regular language is closed given transposition of rightmost character to leftmost

This answer assumes that the transposed language never contains the empty string.
Let $L$ be a regular language, say accepted by a DFA with states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$.
We construct a new DFA with states $Q' = q'_0 \cup (Q \times \Sigma)$. The initial state of the new DFA is $q'_0$. The transition function is defined as follows: $\delta'(q'_0,\sigma) = (q_0,\sigma)$, and $\delta'((q,\sigma),\tau) = (\delta(q,\tau),\sigma)$. Finally, the set of accepting states $F'$ contains all states $(q,\sigma)$ such that $\delta(q,\sigma) \in F$.
The new DFA reads the first symbol $\sigma$ and remembers it. It then simulates the original DFA, accepting a word if adding $\sigma$ would result in the original DFA accepting it.


What is determinism in computer science?

I'd like to expand on @jmite's mention of non-determinism due to threading.  "Is your program deterministic?" is a question that might well be asked in a parallel programming class, and the answer with many multi-threaded programs is often "no."

In most multi-threaded programs the exact interleaving of instructions from different threads is indeterminate. We can't determine the order in which instructions are interleaved just by using the program and its input.  To actually figure out what order the instructions would interleave would require us to know the exact state of the caches and branch predictors and tlbs on every core, when all the external interrupts occur to the picosecond (mouse movements, external network traffic, timer interrupts) the exact position of the disk drive heads with respect to the spinning platter, the temperatures of every transistor (at least the transistors that drive the asynchronous busses) and the small fluctuations in voltage coming from the wall socket or battery.

Given that every time you run your multithreaded program the exact instruction interleaving is different, we are really interested in:

  can the multi-threaded program's output be exactly determined knowing only the input and the code?

For example, the following multithreaded program is non-deterministic:

thread A                    thread B
acquire mutex m             acquire mutex m
x = 0                       x = 1
release mutex m             release mutex m
print x

This program will sometimes print "0" and sometimes print "1".

The following multithreaded program is determinisitic

thread A
x = 0
fork thread B               thread B
acquire mutex m             acquire mutex m
x = x + 1                   x = x + 2
release mutex m             release mutex m
join with thread B          finished
print x

This program would usually be considered deterministic.  It always prints "3", although we don't know if the sequence of values of x was 0, 1, 3 or 0, 2, 3.

Things get even more interesting when we are talking about data structures like binary trees.  In a binary tree the exact shape of the tree usually depends on the exact order in which nodes were added.  But often you are using the binary tree to represent some abstract data type (like an ordered sequence) in which many different tree shapes represent the same abstract value.

For example, the binary trees

  0          1          2
   \        / \        /
    1      0   2      1
     \               /
      2             0

all represent the same ordered sequence "0, 1, 2".  So most people would still call this ordered-sequence type deterministic although if you have to debug the program (and thus deal with different runs having different actual representations of the data structure) you might also call it annoying.


How can I determine the input size of an algorithm?

for the first code segment, input size is 2n. a has n elements, so does b.
for the second code segment, input size is 2n. a has n elements, so does b.
for the third segment, input size is n+1. a has n elements, and there is another value n.
for the fourth code segment, input size is 2.