Primitive Recursive Function for Division and Hailstone function

For your division example, what would the case be if y was equal to zero?

The function is undefined if y = 0.  Thus, it is not a total function.  Thus, division is not primitively recursive, as all primitively recursive functions are total functions.


So here, it looks as though $u \in U$ is a vertex representing the team and $v \in V$ is an edge between the vertices representing the matches possible.

If we can generate a Bipartite Graph, the edges ${ v_i, ...v_j}$  going across are all non-conflicting matches. Those edges for this matching ( $M_1$) can be held on that day. Next, we remove ${ v_i, ...v_j}$ and check to see if we can get more Bipartite Graphs. The edges going across are similarly the non-conflicting matches.

Not sure if this is what you asked for.


Hamming code distance and error detection

Let's see. With parity, each block is 1001 bits long vs 1010 bit for Hamming code. So if the error rate is 0, then you economize 9 bits.

OTOH, if each second block fails, the in 50% of cases you will have to transmit a second block, in 25% of cases third block and so on. On average you have to send 2 blocks.

Now, let's go deeper. If the error rate is r, this means that each bit fails with the r probability. So, you can compute probability that there are k errors in the block.

You know that if there are 0 errors, you don't need to retransmit block, for a single error you need to retransmit parity-protected block, and for 2n errors you will got unrecoverable error.

Similarly, you can compute it for Hamming code protected block.


The graph is log-space reducible to the same question restricted to a leveled directed graph. We know the problem whether there is a path between s, t can be solved in NL, so the idea is to repeat the question for different distances.  Let G be the leveled directed graph where v(i) denotes vertex v in level i.

i=1
while i<=N where N is the size of the original graph before leveling.
    check if path exists between s(1) and t(i+1) using an NL machine.
    if yes:
        then return Accept if i is odd, else reject
    else: i++

If you have a copy of Sipser checkout page 333 for more about leveled graphs since that is where I got the idea.


The Potential function for Fibonacci heaps

Because it works.

In amortized analysis, you pick the potential function. While it's usually related to some insight about the data structure or algorithm work, is it per se completely arbitrary. The only important thing is that if you write down the telescoping sum -- which is always set up in the same way! -- you can derive a good estimate.


Feature detector that doesn't use corners

If you have prior knowledge of the objects expected size you should ignore interest points of too small scale. I think these objects (thanks to round shape and contrast with the background) it should be an easy task for blob detection algorithms, you'd get one detected blob / item. Note that for SIFT or SURF the major orientation isn't well defined for blobs with rotational symmetry but it might be sufficient to assume fixed orientation (like on U-SURF).


Understanding how convolution of images work in cnn

We apply one filter to 32x32x3 image and output 32x32x1 image.And we stack all these twelve 32X32X1 images,which gives 32x32x12 volume.

check this image.In here we apply 5x5x3 kernal to 32x32x3 image with zero padding and stride 1.which gives you 28x28x1 output.if we use 12 filters like this,we get 28x28x12 volume.


How to extent primitive recursion from natural numbers to finite strings?

You don't really need to do anything. Without loss of generality, let $\Sigma = \{0, \dots, d-1\}$.  A string in $\Sigma^*$ is (almost) just a natural number written in base-$d$. The only problem is that leading zeroes are significant in strings but not natural numbers so we instead associate the string $w_1\dots w_k\in\Sigma^k$ with the base-$d$ natural number that's written $1w_1\dots w_k$. The length function is just a suitably rounded logarithm, which is primitive-recursive anyway.

(The first way you'd try to compute a base-$d$ logarithm would probably be to use a while loop to repeatedly divide by $d$. But you can replace that with a for loop, since we know that $\log_d n\leq n$.)


Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ context free?

Suppose $L$ was context-free. Then $L \cap 0^*$ were also context-free. Since $L \cap 0^*$ is a unary language (a language over a unary alphabet, i.e., an alphabet of size $1$), Parikh's theorem states that it is context-free iff it is regular. As you mention, $L \cap 0^*$ isn't regular, and so $L$ can't be context-free.


Let's start with some background. The context is derandomization:

  Given a randomized algorithm, is there an equivalent deterministic algorithm?

Let's consider a randomized algorithm for some decision problem. The algorithm makes use of some random bits $r_1,\ldots,r_n$. In practice, we run this algorithm by using an "informal" pseudorandom number generator, perhaps injecting some physical randomness. Perhaps we can do the same formally?

The best case scenario is that there exists some really complex sequence of random bits that "looks random" for every efficient algorithm; the complexity of the sequence should grow with the complexity of the algorithm, but we want the algorithm generating the sequence to be efficient (though perhaps less efficient than the algorithm itself). While one sequence is perhaps too much to ask for (how exactly would it work, anyway?), but we can hope that a simpler distribution causes the randomized algorithm to act in roughly the same way:
$$
\Pr[A(x,\mathbf{r})] \approx \Pr[A(x,\mathbf{g})],
$$
where $A$ is the randomized algorithm, $x$ is the input, $\mathbf{r}$ is a vector of random bits generated uniformly at random, and $\mathbf{g}$ is the same generated pseudorandomly. What we aim for is for $\mathbf{g}$ not only to be generated efficiently, but moreover we want the support of the distribution to have polynomial size. By enumerating all possible values of $\mathbf{g}$, we can derandomize $A$.

Now back to your question. A pseudorandom sequence $\mathbf{g}$ (or a collection of such sequences) is said to fool an algorithm $A$ if $\Pr[A(x,\mathbf{r})] \approx \Pr[A(x,\mathbf{g})]$. It fools a complexity class if it fools all algorithms in this class.

Another context in which similar concepts appear is cryptography. For example, in cryptography a pseudorandom number generator is defined (roughly) as an efficient algorithm producing a long random sequence which fools every polynomial time distinguisher (a distinguisher a machine trying to distinguish the YES case (truly random) from the NO case (pseudorandom)).


What is the space complexity of Dijkstra Algorithm?

Dijkstra's algorithm can be implemented in many different ways, leading to resource usage. The page you link gives the resource usage the implementations in the specific library being described.

I can't think of a way of implementing Dijkstra to use $|V|^2$ space, but I would note two things.

$O(\cdot)$ only gives an upper bound. Even if the implementation actually uses space $O(|V|)$, it's not wrong to say that it uses $O(|V|^2)$ or even $O(2^{|V|})$, just as it's not wrong to say that I earn less than a billion dollars a year. However, it would be unusual to say $O(|V|^2)$ if it was easy to prove the stronger bound of $O(|V|)$ (I also earn less than a million dollars a year), and it is easy to prove $O(|V|)$ for most implementations of Dijkstra.
The page quotes the running time as $O(s|E|\log|E|+V)$, where $s$ is the number of sources being considered. It's easy to imagine space usage of $O(s|V|)$ so maybe they wrote $O(|V|^2)$ since $s\leq|V|$.  But that would also be strange, given that the quoted running time shows they're not afraid to use $s$.


Fitting a low-degree polynomial to a function on a finite 1d grid - a combinatorial problem?

The problem can be solved in polynomial time using linear programming.

Write $p(x) = c_k x^k + \dots + c_1 x + c_0$, and think of $c_0,\dots,c_k$ as unknowns.  Also introduce an unknown $d$, which will represent the $L_\infty$ norm.  We will minimize $d$, subject to the following inequality:

$$-d \le f(i) - (c_k i^k + \dots + c_0) \le d.$$

Notice that, since $i$ and $f(i)$ are constants, this is a linear inequality in the unknowns.  We obtain one inequality per value of $i$.  Now the minimum achievable value of $d$ corresponds to the polynomial $p$ that minimize the $L_\infty$ norm, so you can solve this using any algorithm for linear programming.  Since linear programming is in P, your problem is in P, too.

I expect that this algorithm will be efficient in practice, as linear programming over $k+2$ unknowns and $n$ inequalities should be pretty efficient for reasonable values of $k,n$.

I don't know what the numerical stability issues might be.

Another solution in practice might be to find a solution that minimizes the $L_p$ norm.  You could start by minimizing the $L_2$ norm, using any standard method (e.g., least squares).  Then you could start from that solution and find a solution that minimizes the $L_p$ norm, for some larger value of $p$, say using gradient descent.  After increasing $p$ a few times I expect the resulting solution might often turn out to be a reasonable approximation, even if not optimal.


What is the motivation behind restore model of computation?

The restore model is semantically identical to the read-only model. Both models are natural since you expect operations on objects to not alter them. For example, imagine running a query on a database. You don't want the query to modify the database, but you might not mind if the database is temporarily changed while running the query, as long as it is restored to its original state in the end.

(In fact, in this particular you might care, for many reasons: perhaps several processes access the database in parallel; or perhaps you are worried that a failure will stop the process in the model, thus leaving the database in a modified state. These are reasons why you'd sometimes prefer the read-only model.)

The restore model is more powerful than the read-only model, in the sense that it potentially requires less auxiliary memory. In recent times, this model is known as catalytic computation. See for example Koucký's expository article, which provides further motivations for this model.


The running time you quote isn't correct. If $n = m$ then it takes $\Omega(n)$ to verify that $T = P$. The best case running time of any string matching algorithm is $\Omega(m)$, since this is how long it takes to verify a match. Perhaps you are disregarding the time it takes to compute the hashes.

Ignoring all of this, let us suppose that we are considering an algorithm whose running time is $\Theta(n-m+1)$, where $m \leq n$ are two parameters. As your example makes clear, this is not the same as $\Theta(n)$, since if $m$ is close to $n$ then $n-m+1$ is much smaller than $n$. Generally speaking, an asymptotic expression depending on two parameters cannot be reduced to an asymptotic expression depending on only one of them.

In practice, often $m$ is itself a known function of $n$, and this can be used to reduce $\Theta(n-m+1)$ to an asymptotic expression depending on a single parameter. For example, if $m = n/2$ then $\Theta(n-m+1) = \Theta(n)$, whereas if $m = n$, then $\Theta(n-m+1) = \Theta(1)$.


Are the two LTL properties $GF(\psi_1 \land F\psi_2 )$ and $GF(\psi_2 \land F\psi_1 )$ equivalent?

You are right, but you should prove it.  Here's a proof sketch:

Proof setup:

  Suppose that $GF(\psi_1 \land F\psi_2)$ is true and assume towards a contradiction that $\neg GF(F\psi_1 \land \psi_2)$.

Observations:

  Then there exists a state $s_1$ in which $\neg F(F\psi_1 \land \psi_2)$, which means that every state $s_2 > s_1$ has $\neg(F\psi_1 \land \psi_2)$, which means that for every state $s_2$, either $\neg F\psi_1$ or $\neg \psi_2$.

Contradiction:

  But since $GF(\psi_1 \land F\psi_2)$, there exists a state $s_3 > s_2$ such that $s_3 \vDash \psi_1$ and a state $s_3 > s_2'$ such that $s_3' \vDash \psi_2$, which is a contradiction.

The other direction is identical.


Best Approach To Parse Human Readable Text To Machine Readable (CSV)

My approach is to check that my assumptions about the format of the data are correct while reading. Example, I ensure that as expected, I get the series of # characters, that the next line starts with a number and ends with a date as mm/dd/yyyy. Upon any failure, I would throw an exception with a message such as "expected so and so at line xxx but found yyy". In case things go south, I will not be left with some cryptic error message related to regex.


Why do we have to make variables unique when evaluating $\lambda$-calculus?

When performing a $\beta$-reduction, there are cases in which an $\alpha$-conversion is needed first; otherwise, the $\beta$-reduction fails to preserve semantics. This is here the case: you are replacing the free variable $x$ with $e_2$ and $e_2$ contains free variables which are bound within $e_1$.

You can easily see why the semantics are not preserved: $(\lambda y.y)$ and $(\lambda y.x)$ are not equivalent expressions because $(\lambda y.y)z = z$ but $(\lambda y.x)z = x$. In order to preserve the semantics, you first need to perform an $\alpha$-conversion on $(\lambda y.x)$ so as to replace $y$ with something else which is not free in $e_2$ (thus achieving "uniqueness"—though IMO such a term should be frowned upon here).


Pittsburgh approach, how does encoding and fitness function work?

So both the Pittsburgh and Michigan approaches are techniques for applying evolutionary methods to learning (essentially) a set of "if/then" rules for performing some task effectively. The important bit is the "set" there in "set of rules". You need to learn multiple rules that can each fire in different situations in order to cover the entire space of behaviors the algorithm needs to learn. Where the Pittsburgh and Michigan approaches differ is in how you arrive at that set of rules.

They're both GAs under the hood, so there's a population of things. In the Pittsburgh approach, those "things" are complete candidate solutions to the problem. A single individual in a Pittsburgh algorithm might contain many rules. A single individual in a Michigan approach contains only one rule. In order to form a viable actual algorithm for solving the problem, the Michigan approach needs to take the entire population and hope that each of those individuals with their individual rules combine together in a way to cover the problem space well.

Under the hood though, as I said, they're basically just GAs. So you can do recombination and mutation however you like. You can handle floating point genes the same way you'd handle them in any other GA -- perhaps by using variation operators that natively work on floats or by encoding the values as binary yourself. Fitness in Pittsburgh systems can be reasonably straightforward. Every individual is intended as a complete solution, so you just run your simulation and calculate how well that individual's rule set solves the problem. The answer is that individual's fitness. For Michigan approaches, it's harder, because there's a credit assignment problem. One individual encodes one rule, and that rule may be perfect for its niche, but if the rest of the population is terrible, performance will be poor.

Another problem is that the structure inherent in classifier systems like this means that typical genetic operators won't necessarily work that well. You can use them, but tweaks to the ideas can perform quite a bit better. The Learning Classifier Systems community has done quite a bit of work figuring this stuff out. My general advice would be to start by looking at Stewart Wilson's XCS algorithm.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.363.2210&rep=rep1&type=pdf

http://opim.wharton.upenn.edu/~sok/papers/b/XCSAlgDesc01202001.ps


How can GIF compression be lossless if the maximum # of colors is 256?

GIF is only capable of storing images with at most 256 different colours. If you have such an image, the compression used by GIF is lossless. If you have an image with more than 256 different colours, you must first reduce the number of colours, which does indeed lose data but that's a preprocessing stage that isn't part of the compression process. Once you've preprocessed, the compression occurs without further loss.

You should parse the sentence quoted in the question as "If you have an image with at most 256 colours, GIF will compress it losslessly", rather than "If you have an image, GIF will losslessly produce a compressed version with at most 256 colours."


Recall 2-SAT solution which uses strongly connected components: we build a graph with vertices $x_1,\ldots,x_n, \lnot x_1, \ldots, \lnot x_n$, and we replace each clause $x_i \lor x_j$ with edges $\lnot x_i \to x_j$ and $\lnot x_j \to x_i$. An example from here:

To satisfy the formula, it's necessary and sufficient to assign vertices so that there are no contradictions in the graph (no edge $true \to false$). We'll use these graphs for equivalence checking.

We build these graphs $G_1$ and $G_2$ for both formulas $F_1$ and $F_2$.
If there is a cycle $x_i \leadsto \lnot x_i \leadsto x_i$ in a graph, then its formula has no solutions. We check that both formulas are solvable/unsolvable.
If there exists a path of form $x_i \leadsto \lnot x_i$ (similarly for the case $\lnot x_i \leadsto x_i$), we know that to satisfy the formula we must select $x_i$ to be false (otherwise we have a contradiction). We remember this choice. Using the graph, we can assign values to all vertices reachable from $\lnot x_i$ (they must be true). Again, check that both formulas made exactly the same decisions in the end.
Remove all edges to/from all known vertices from the graphs.
Now, $F_1$ and $F_2$ are equivalent $\iff$ the remaining graphs are equivalent in the following sense: for any $v_1,v_2$ path $v_1 \leadsto v_2$ exists in $G_1$ iff it exists in $G_2$. This can be checked in at most $O(|V|\cdot|E|)$ time (just run DFS from each vertex and check that it has visited the same vertices for both graphs). Maybe it can be done faster.

Proof:
$\Leftarrow$: evident, since after transitive closure of graphs we'll have the same implications in both formulas.
$\Rightarrow$: By contradiction. Wlog we assume that there exists a path $v_1 \leadsto v_2$ in $G_1$ which doesn't exist in $G_2$. It means that assignment $v_1 := true$, $v_2 := false$ is feasible in $F_2$ (since there is no path $v_1 \leadsto v_2$) but is infeasible in $F_1$.
Namely, the following assignment satisfies $F_2$:

$true$ for all vertices reachable from $v_1$.
$false$ from all vertices which can reach $v_2$.
Remove all known vertices (mentioned above and their complements) from the graph. All remaining vertices create connected components. We color connected components in $true$, and connected components corresponding to their complements - in $false$ (see note below).

This assignment has no contradiction, since there can be no edge $u \to v$ of form $true \to false$:

If $u$ belongs to a component which was full colored $true$, then such $v$ must also be true.
Otherwise, it means that $u$ is reachable from $v_1$, and therefore $v$ is also reachable from $v_1$ and must be true. $\blacksquare$

Technical note: for each variable $x_i$ there are two vertices: $v_i$ and $\lnot v_i$ - and one may wonder if it'll lead to some problems with assignments. The answer is that after step 4), $v_i$ and $\lnot v_i$ will lie in two different components (moreover, they are symmetric: $u \to v$ in one component means $\lnot u \to \lnot v$ in another one). Therefore, whatever decision we make for $u$ in one component, we can make the opposite decision for $\lnot u$ in another one.


I suppose you are already familiar with the idea behind mathematical induction, but just to recap the general idea, the goal is to use the inductive hypothesis to help us get the desired statement. It is helpful to construct the words in a way that will simplify how you can relate back to the original word.

Suppose it works for all words $v \in \Sigma^*$ such as $\lvert v \rvert = n$ (we can do this because you proved the base case for words of length 0). Now, take $w = vx$ for any $x \in \Sigma$. Note that the length of $w$ is $\lvert v \rvert + 1$ by construction ($\lvert w \rvert = n + 1$).

$$ quer(w) = quer(vx) = quer(v) + x \leq quer(v) + 2 \\
                                    \leq 2\cdot \lvert v \rvert + 2\\
                                    = 2 \cdot (\lvert w \lvert -1) + 2\\
                                    = 2\lvert w \rvert - 2 + 2 \\
                                    = 2 \lvert w \rvert
$$


Would using the mean as pivot speed up quicksort?

Using the mean for your partition does not prevent the $\Omega(n^2)$ worst-case behavior. It occurs when the input list is exponentially increasing. Consider the input:

$1,n^2,n^3,\ldots,n^n$

The mean of this set is (asymptotically) $n^{n-1}$ so you obtain the worst partition possible. This is a bit of a cheat considering that storing the list takes $\Omega(n^2)$ space if the numbers are represented as integers. But if you are sorting floating-point numbers then this scenario is concievable.

However, it is possible to calculate the median of a set (or any other order statistic for that matter) in $O(n)$ time so if you really care about run time guarantees for quick sort you should use that rather than the mean.

However, in all practical scenarios the additional cost of computing the mean/median is so large that picking a random pivot almost always is faster.


Why can't we search lexicographicaly ordered programs to compute Kolmogrov complexity?

The problem with your approach is that some programs never halt, and it's difficult (indeed, uncomputable) to tell whether they do. You can tell if a program outputs $s$ and halts, but you don't know how much to wait before declaring that the program never halts. However, your approach shows that it is possible to write a program that prints upper bounds on the Kolmogorov complexity of a give string, eventually printing the correct upper bound. This doesn't give you the Kolmogorov complexity since you don't know when the program will have printed its final upper bound.


Can we make a problem harder than NP and coNP if they are not equal?

Note: this answer was posted for the original post.

  Given a graph G: is there an algorithm, bounded by a polynomial of order k, that can determine if G is 3-colorable-or-non-3-colorable and provide a certificate?

If you fix the graph then the problem is trivial. There is always an algorithm that answers in constant time. There is no input.

If the graph is the input, then the answer is always YES. Any graph is either 3-colorable or not 3-colorable.

  Note that the answer is not alway yes since NP ≠ Co-NP

I don't see how this is relevant.


Determining the existence of a forced win vs determining the best outcome

They are equivalent under Turing reductions, assuming that the game has finite/polynomial-size branching factor (i.e., only that many moves are possible from each position).  I don't know if they are equivalent under Karp reductions.

Consider a position $P$.  Assume there are $k$ moves that are legal there.  Let $P_1,\dots,P_k$ denote the possible positions after making a single move.

Check whether $P$ is a forced win for player #1.  If yes, you are done.

Check whether any of $P_1,\dots,P_k$ is a forced win for player #2.  If they are all a forced win for player #2, then $P$ is a forced lose for player #1.

Otherwise, $P$ is a forced draw for player #1.


Girth of Undirected Graph with Positive Integer Weights

Use an all-pairs shortest-paths algorithm to find the distance from each vertex to each other vertex, call it $d(u,v)$.  Now find the minimum value of $d(v,v)$ over all vertices $v$.  That is the length of the shortest cycle.

Why does this work?  Suppose the shortest cycle from $v$ to $v$ has length $\ell$.  Obviously we will have $d(v,v) \le \ell$ (since we have a path from $v$ to $v$ of length $\ell$, the shortest such path is at most $\ell$).  Conversely, we know there is a path of length $d(v,v)$ from $v$ to $v$; since it goes from $v$ to $v$, this is a cycle; so the length $\ell$ of the shortest cycle must satisfy $\ell \le d(v,v)$.  We have proven both $d(v,v) \le \ell$ and $\ell \le d(v,v)$, so it follows that $\ell = d(v,v)$.


"If any problem in NP is not polynomial-time solvable, then no NP-complete problem is polynomial-time solvable."

Assume that the following were true:

A problem $X$ in NP is proven to not to be able to be solved in polynomial time.
A NP-complete problem $Y$ is proven to be solved in polynomial time with algorithm $Z$.

However, since $Y$ is a NP-complete problem we can transform an instance $x$ of $X$ into an equivalent instance $y$ of $Y$ in polynomial time, and then solve it with $Z$ in polynomial time. The sum of two polynomial times is polynomial, thus our assumption is violated.


symmetrical subtraction between $L_1 \in \mathsf{P}$ and $L_2 \in \mathsf{NPC}$

The answer is actually yes. Some intuition is that, when considering $\mathsf{NP}$-completeness (or in general, considering any complexity class under polynomial-time reductions), polynomial-time parts of the computation don't matter. Since $L_1$ is polynomial time, and $L_1 \Delta L_2$ and $L_2$ can be computed from each other knowing the answer to $L_1$, they should both be equivalent languages, up to polynomial-time computations.

Formally, to show "equivalence" we use polynomial time reductions. So you could solve this problem by:

Finding a polynomial-time reduction from $L_2$ to $L_1 \Delta L_2$. (How do we compute $L_1 \Delta L_2$ from $L_2$?)
Finding a polynomial-time reduction from $L_1 \Delta L_2$ to $L_2$. Hint: use the fact that
$$(L_1 \Delta L_2) \Delta L_1 = L_2$$

Once you have done this, you have shown that $L_2$ and $L_1 \Delta L_2$ are equivalent; if you are familiar with the notation,
$$
L_2 \le_p L_1 \Delta L_2 \le_p L_2
$$
which  means if one of them is $\mathsf{NP}$-complete, then both of them are.


Back invalidation to maintain inclusion in inclusive cache

There are a broad range of design choices about how back invalidation is handled. Whether the L2 knows if a cache block is in L1 (and which L1, instruction or data) is one implementation choice with three basic options: no knowledge, approximate but conservative knowledge, and perfect knowledge.

With the no knowledge, the L2 cache will always probe both L1 caches (assuming a coherent L1 instruction cache as in x86 generally and some other processors, e.g., recent POWER processors). With approximate knowledge back invalidation commands would be filtered so they are sent to the appropriate L1 only if the block is likely to be present. With perfect knowledge only necessary back invalidations are sent to L1.

Obviously the no knowledge option provides the most straightforward implementation since there is no choice but to send the invalidation request. This can waste request bandwidth between L2 and L1 and may interfere with the availability of L1 tags for memory accesses from the core. Replication of tags or adding a read port would solve this issue, banking of the tags would reduce the frequency of conflict, adding a filter on the L1 side would also reduce access to the complete tags.

Approximate knowledge can substantially reduce the number of probes needed and reduces the amount of information that must be stored with the L2 cache and makes communication about L1 evictions less critical. The latter factor can be exploited to schedule communication of the information to minimize overhead, including interference with required communication. Since back invalidation probes are filtered, their interference with normal operation of the core is reduced giving less reason to increase the number of tag reads supported.

An approximate filter could use per L2 block information (where techniques similar to those used to compression coherence directory entries could be used) or could use a separate filter (like a Bloom filter).

Perfect knowledge (or a very close approximation) avoids unnecessary invalidation requests to L1, but effectively requires the equivalent of a directory coherence entry for each L2 cache block and every eviction from L1 must be quickly communicated to L2. A simple implementation might use one bit per L1 cache to track the presence of the block in that cache (e.g., tracking the presence in a single core's L1 instruction and data caches would use two bits per L2 block).

Another, not entirely implausible option for an L2 much larger than the L1 caches would be replicating the entire L1 cache tags, possibly in a compressed format that used the L2 set and way (excluding the bits used for indexing the L1 cache) for the replicated L1 tags.

The information can be kept current by communicating to L2 the address (or in the case of the replicated L1 tags located with L2 just the set and way could be communicated) of every L1 eviction. To include this information in the message requesting the data replacing the evicted block, the victim would have to be selected quickly. While this is not a substantial problem, it treats an L1 victim as if it was immediately replaced (i.e., an access to the victim block before the L2 cache has supplied the new block would be treated as a miss even though the data is still present).

This miss could be made merely conceptual by changing the victim choice in the rare case that the victim is accessed during this small window between victim selection and the response from L2 filling the L1 entry, but in that case an additional message must be sent to the inform L2 of the change in victim.

When the back invalidated block is dirty in L1, this block typically would be written back to memory (or sent to the requesting cache for a coherence invalidation caused by another cache attempting a write to that address; in that case whether it is also sent to memory is another implementation choice). However, when the eviction is not coherence-related, it would be quite possible to change the victim choice. In this case, the L2 might retain the dirty block, possibly requiring another back invalidation if the new victim is (or might be) in L1. Obviously, this same strategy could be used if the L1 informed the L2 cache that the block is a poor replacement choice (e.g., being more recently used than most other blocks in its L1 set).

Note that it is also possible to communicate information about L1 accesses back to the L2 cache so that an LRU-oriented L2 replacement policy would less often choose a block that is still in L1. While doing this for every L1 access or even every L1 access that influences replacement (with LRU replacement an access of the most recently used block will not change the state), would be excessively expensive, partial information could be sent when convenient. E.g., extra information could be included with a miss handling request or extra messages could be sent to L2 when the interface is otherwise idle (using a separate queue of replacement policy update information from which entries can be dropped if the interface is busy when more information is added to a full queue).

Since back-invalidations are relatively rare, the cost of unnecessary invalidation requests (i.e., when the block is not actually in a particular L1 cache) might be lower than the cost of reducing or completely avoiding them. On the other hand, with L2 cache potentially shared among several L1 caches (e.g., an L2 cache shared by two cores might include four L1 caches), avoiding the need to broadcast the invalidation to all the included L1 caches would have some attraction.

These implementation details do not appear to be documented in general, so the above is derived from reasoning about the tradeoffs.


Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?

I have done some more research, and I think I've found a solution for the 1st and 2nd questions, as for the 3rd one, I found an existing solution on StackOverflow for it, the proof attempts are written below:

We start by writing the three rules of the definition of an LL(1) grammar:

For every production A -> α | β with α ≠ β:

FIRST(α) ∩ FIRST(β) = Ø.
If β =>* ε then FIRST(α) ∩ FOLLOW(A) = Ø (also, if α =>* ε then FIRST(β) ∩ FOLLOW(A) = Ø).
Including ε in rule (1) implies that at most one of α and β can derive ε.

Proposition 1: A non-factored grammar is not LL(1).

Proof:

If a grammar G is non-factored then there exists a production in G of the form:

A -> ωα1 | ωα2 | ... | ωαn

(where αi is the i-th α, not the symbols α and i), with α1 ≠ α2 ≠ ... ≠ αn. We can then easily show that:

∩(i=1,..,n) FIRST(ωαi) ≠ Ø

which contradicts rule (1) of the definition, thus, a non-factored grammar is not LL(1). ∎

Proposition 2: A left-recursive grammar is not LL(1).

Proof:

If a grammar is left-recursive then there exists a production in G of the form:

S -> Sα | β

Three cases arise here:

If FIRST(β) ≠ {ε} then:

    FIRST(β) ⊆ FIRST(S)

=>  FIRST(β) ∩ FIRST(Sα) ≠ Ø

which contradicts rule (1) of the definition.
If FIRST(β) = {ε} then:

2.1. If ε ∈ FIRST(α) then:

ε ∈ FIRST(Sα)

which contradicts rule (3) of the definition.

2.2. If ε ∉ FIRST(α) then:

    FIRST(α) ⊆ FIRST(S) (because β =>* ε)

=>  FIRST(α) ⊆ FIRST(Sα) ........ (I)

we also know that:

FIRST(α) ⊆ FOLLOW(S) ........ (II)

by (I) and (II), we have:

FIRST(Sα) ∩ FOLLOW(S) ≠ Ø

and since β =>* ε, this contradicts rule (2) of the definition.

In every case we arrive at a contradiction, hence, a left-recursive grammar is not LL(1). ∎

Proposition 3: An ambiguous grammar is not LL(1).

Proof:

While the above proofs are mine, this one is not, it's by Kevin A. Naudé which I got from his answer that is linked below:

https://stackoverflow.com/a/18969767/6275103


Why isn't every vertex connected to every other vertex in TextRank?

After getting in touch with the authors of the paper, the reason why every vertex isn't connected to every other vertex in the graph is because only edges with a non-zero weight are added to the graph.


Regular expressions with backreferences over unary alphabet

Evidence against the effective decidability of the problem is provided by the construction in the proof of Theorem 9 in my paper On Practical Regular Expressions: You could determine if there are finitely many Fermat primes.


Does a greedy task selection algorithm find a c-approximate solution?

The shortest-task-first heuristic is a 1/2-approximation algorithm.

For a tight example, image that a compatible set $\{T_i\mid 1\leq i\leq m\}$ sorted by their finish time and the other shorter tasks $Y_i$, $1\leq i\leq m/2$, such that $Y_i$ overlaps with $T_{2i-1}$ and $T_{2i}$ for each $i$. The shortest-first heuristic finds $m/2$ tasks while the optimal solution contains $m$ tasks.

To show the approximation ratio:
For any compatible set $T$ sorted by their finish time, a task in the approximation solution overlaps with at most two tasks in $T$ since it cannot contain any task as a sub-interval of it. In fact, you can always obtain a 2-approximation if you select no tasks ``covering''  another task.


When does an algorithm run in $O(1)$ time?

If you follow the definition of $\mathcal O$, a function $f(x)\in\mathcal O(1)$ when there's an $x_0$ and $M$ such that for all $x>x_0$, $f(x) \leq M$.

For both algorithms you mention, there clearly is an upper bound on the number of steps a machine has to take to compute the result. Therefore, the time complexity for either problem will be some function $T(n)$, where $n$ is the length of the input, such that $T(n)\leq M$ for some $M$ for all $n$. Therefore $T(n)\in \mathcal O(1)$.

Note that the $\mathcal O$ notation has to do with asymptotic behavior of functions, i.e. their behavior as their input grows beyond all bounds. It doesn't care about tiny inputs, whether their length is $1$, $2^7$, or $10^{100}$.


What you are looking for is just a higher dimensional array.

Let's say you want a 5x5 array where each element is a 2x2 array with random number. You can easily represent that as a 5x5x2x2 array.

If you are happy about using numpy

A = numpy.random.rand(5,5,2,2)

Will create a 5x5x2x2 array.

You can use the first two indexes to access your 2D random arrays.

print A[1,1]

Results in:

[[ 0.68527006  0.37304491]
 [ 0.23281899  0.46951261]]


How do I construct reductions between problems to prove a problem is NP-complete?

There is no magic bullet; NP-hardness proofs are hard.  However, there is a general framework for all such proofs.  Many students who struggle with NP-hardness proofs are confused about what they're supposed to be doing, which obviously makes it impossible to figure out how to do it.  So here is what to do to prove a problem NP-hard.

First, unless you're just doing homework, you have to decide which NP-hard problem to reduce to your problem.  This is largely a question of "smell".  If the number 3 appears anywhere in the problem statement, try reducing from $\mathsf{3SAT}$ or $\mathsf{3Color}$ or $\mathsf{3Partition}$.  (Yes, I'm serious.)  If your problem involves finding an optimal subsequence or permutation or path, try reducing from $\mathsf{HamiltonianCycle}$ or $\mathsf{HamiltonianPath}$.  If your problem asks for the smallest subset with a certain property, try $\mathsf{Clique}$; if it asks for the largest subset with a certain property, try $\mathsf{IndependentSet}$.  If your problem involves doing something in the plane, try $\mathsf{PlanarCircuitSAT}$ or $\mathsf{PlanarTSP}$.  And so on.  If your problem doesn't "smell" like anything, $\mathsf{3SAT}$ or $\mathsf{CircuitSAT}$ is probably your best bet.

Obviously, you need to already know precisely how all these problems are defined, and the simpler the problem you reduce from, the better.  So as cool as the result might look in the end, I don't recommend reducing from $\mathsf{Minesweeper}$ or $\mathsf{Tetris}$ or $\mathsf{OneCheckersMove}$ or $\mathsf{SuperMarioBros}$.

Second, the actual reduction.  To reduce problem X (the one you know is NP-hard) to problem Y (the one you're trying to prove is NP-hard, you need to describe an algorithm that transforms an arbitrary instance of X into a legal instance of Y.  The reduction algorithm needs to do something specific with each "feature" of the X-instance; the portion of the output for each "feature" is usually called a gadget.

But what's a feature?  That depends on problem X.  For example:

To transform an instance of $\mathsf{3SAT}$, you'll need a gadget for each variable and for each clause in the input formula.  Each variable gadget should have two "states" that correspond to "true" and "false".  Each clause gadget should also have multiple "states", each of which somehow forces at least one of the literals in that clause to be true.  (The states are not part of the output of the reduction algorithm.)
To transform an instance of $\mathsf{3Color}$, you'll need a gadget for each vertex and each edge of the input graph, and another gadget to define the three colors.
To transform an instance of $\mathsf{PlanarCircuitSat}$, you'll need a gadget for each input, for each wire, and for each gate in the input circuit.

The actual form of the gadget depends on problem Y, the one you're reducing to.  For example, if you're reducing to a problem about graphs, your gadgets will be small subgraphs; see the Wikipedia article.  If you're reducing to a problem about scheduling, each gadget will be a set of jobs to be scheduled.  If you're reducing to a problem about Mario, each gadget will be a set of blocks and bricks and Koopas.

This can get confusing if both problems involve the same kind of object.  For example, if both X and Y are problems about graphs, your algorithm is going to transform one graph (an instance of X) into a different graph (an instance of Y).  Choose your notation wisely, so that you don't confuse these two graphs.  I also strongly recommend using multiple colors of ink.

Finally, your reduction algorithm must satisfy three properties:

It runs in polynomial time.  (This is usually easy.)
If your reduction algorithm is given a positive instance of X as input, it produces a positive instance of Y as output.
If your reduction algorithm produces a positive instance of Y as output, it must have been given a positive instance of X as input.

There's an important subtlety here.  Your reduction algorithm only works in one direction, from instances of X to instances of Y, but proving the algorithm correct requires reasoning about the transformation in both directions.  You must also remember that your reduction algorithm cannot tell whether a given instance of X is positive or negative—that would require solving an NP-hard problem in polynomial time!

That's the what.  The how just comes with practice.


Do self-loops in DFA cause infinite languages?

the answer is False:

consider a DFA that has no accepting states at all: any loop is not relevant, the language will always be the empty set.

Another option - a loop on a dead state, etc.

However, if it contains a loop on an "accepting path", then indeed the language must be infinite. (this is actually the key idea behind the pumping lemma..)


Here is why you would expect these properties to hold. Suppose that $a_1,\ldots,a_n$ are chosen independently from the uniform distribution on $[0,1]$. The event $a_i = a_j$ has probability zero, and so with probability $1$ all numbers are distinct. Moreover, given that, all sequence orderings are equally likely, and since there are $n!$ of them, the probability that the sequence is ordered is exactly $1/n!$.

To prove that these claims hold in the limit even when the $a_i$ are sampled from a finite set requires some calculation, which I leave to you.


For simplicity write all the numbers in base $4$. Fix an arbitrary ordering of the edges of the graph $G$ and let $e_i$ be the $i$-th edge ($i= 1, \dots, |E(G)|$).

For each vertex $v \in V(G)$ define an integer $n_v$ of $|E(G)| + 1$ digits as follows:

the $i$-th least significant digit of $n_v$ is $1$ if $e_i$ is incident to $v$ and $0$ otherwise;
the most significant digit of $n_v$ is $1$.

For each edge $e_i \in E(G)$ let $m_{e_i} = 4^{i-1}$ (i.e., the $i$-th least significant digit of $m_e$ is $1$ and all the other digits are $0$).

The instance of subset sum is obtained by choosing $S = \{ n_v : v \in V(G) \} \cup \{m_e : e \in E(G) \}$ and $t = k 4^{|E(G)|} + 2\sum_{i=0}^{|E(G)|-1} 4^i$.
In other words, the most significant digits of $t$ encode the number $k$ in base $4$, while the $|E(G)|$ least significant digits of $t$ are all equal to $2$.

If there is a vertex cover $V' \subseteq V(G)$ of $G$ of size $k$,
let $E'$ be the set of edges $(u,v) \in E(G)$ such that exactly one of $u$ and $v$ is in $V'$.
Then, $A = \{ n_v : v \in V' \} \cup \{ m_e : e \in E' \}$ is a subset of $S$ that sums to $t$. Indeed:
$$
\sum_{x \in A} x = \sum_{v \in V'} n_v + \sum_{e \in E'} m_v
= k 4^{|E(G)|} + 2 \sum_{e_i \in E \setminus E'} 4^{i-1} +
2 \sum_{e_i \in E'} 4^{i-1}
= k 4^{|E(G)|} + 2 \sum_{e_i \in E} 4^{i-1} = t.
$$

If there is a subset $A$ of $S$ that sums to $t$, then $A$ contains exactly $k$ numbers from $\{ n_v : v \in V(G) \}$ (as otherwise the most significant digits of $\sum_{x \in A} x$ would not match those of $t$). Moreover, $V' = \{v_i : n_i \in A \}$ is a vertex cover for $G$.

To see this, pick any $e_i = (u,v) \in E(G)$ and notice the $i$-th least significant digit of $t$ is $2$.
Since, for $j=1,\dots, |E(G)|$, there are exactly $3$ numbers in $S$ whose $j$-th least significant digit is non-zero (namely $n_{u'}$, $n_{v'}$, and $m_{e_j}$, where $e_j = (u', v')$),
we have that in the summation $\sum_{x \in A} x$ no carry occurs among the $|E(G)|$ least significant digits. We conclude that $A$ contains exactly two numbers from $\{n_u, n_v, m_e\}$, implying that $u \in V'$ or $v \in V'$ (possibly both).

In your example graph, for $k=3$ you get the following (bold rows denote the elements of $A$ when $V'=\{v_1, v_3, v_4\}$):
$$
\begin{array}{|c|c|c|c|c|}
\hline
& & e_1 & e_2 & e_3 & e_4 \\ \hline
\pmb{n_{v_1}} & \pmb{1} & \pmb{1}& \pmb{0}& \pmb{0}& \pmb{1}\\ \hline
n_{v_2} & 1 & 1& 1& 0& 0\\ \hline
\pmb{n_{v_3}} & \pmb{1} & \pmb{0} & \pmb{1} & \pmb{1} & \pmb{0}\\ \hline
\pmb{n_{v_4}} & \pmb{1} & \pmb{0} & \pmb{0} & \pmb{1} & \pmb{1}\\ \hline
\end{array}
$$
$$
\begin{array}{|c|c|c|c|c|}
\hline
& & e_1 & e_2 & e_3 & e_4 \\ \hline
\pmb{m_{e_1}} & \pmb{0} & \pmb{1} & \pmb{0} & \pmb{0} & \pmb{0} \\ \hline
\pmb{m_{e_2}} & \pmb{0} & \pmb{0}& \pmb{1}& \pmb{0}& \pmb{0}\\ \hline
m_{e_3} & 0 & 0& 0& 1& 0\\ \hline
m_{e_4} & 0 & 0& 0& 0& 1\\ \hline
\end{array}
$$

$$
\begin{array}{|c|c|c|c|c|}
\hline
\phantom{m_{e_4}}& & e_1 & e_2 & e_3 & e_4 \\ \hline
t & 3 & 2& 2& 2& 2\\ \hline
\end{array}
$$


Using B-method, and formal methods in general, to model and verify a reverse linked list

There are many approaches for verifying linked structures---arguably, more suitable than the B method---that you might want to use, depending on the language and properties you want to verify. Most of the approaches rely on separation logic (which was in big part motivated for verification of linked structures).

Some tools include:

Full Functional Verification of Linked Data Structures -- where you write Java code with specifications in classical higher-order logic, while the verifier uses integrated reasoning of multiple different provers
Linked list, imperative separation logic in Isabelle -- uses separation logic in Isabelle theorem prover (other similar data structure examples might be found in the archive of formal proofs)
Dafny: A Language and Program Verifier for Functional Correctness -- which allows specifying and verifying wide range of data structures in C# (many examples for linked lists exist, e.g. this one)

To quote this answer (which answers a very similar question), even though you did not give details about what are you trying to verify, it seems that properties you might want to prove about the "reverse linked list" might be formulated as properties for a regular linked list. (If the reverse list requires some additional (non-standard) implementations, not already declared for the linked list, you might be able to model those in addition.)

I am not sure what was the purpose of your example, but your code seems similar to an example of modelling a linked list with B (which includes other standard operations) method in Program Development by Refinement Case Studies Using the B Method.


Is it possible to copy data in a linear type system?

I don't know why you bring up registers at all, but the answer to your first question is "sure".  You (potentially) are able to copy data, you just aren't able to do it freely.  For example, an operation $\mathtt{dup}_A : A \multimap A\otimes A$ may be provided, but only for certain types $A$.  Most commonly there are "exponentials", written $!A$ for which $\mathtt{dup}_{!A}$ is definable or given.  The opposite operation is often called $\mathtt{kill}_A : A \multimap 1$ or $\mathtt{discard}_A$. You may start to see how this leads to a kind of functional manual memory management.

For programming languages, the exponential modality is usually the opposite of what we want as it allows the defining an operation of type $!A \multimap A$ via a rule called "dereliction".  If we think of $!A$ as a type that may have multiple references, then a linear type $A$ means that references to $A$ will not be duplicated, not that it hasn't already been duplicated.  A different modality leading to uniqueness logic gives the more commonly desired sense of a variable of type $A$ has not been multiply referenced (and thus we are free to mutate it, for example).

The main "serious", general purpose languages I'm aware of using substructural types are: Rust, Clean, and Pony. Rust and Pony allow freely "copying" primitive types but put restrictions on reference types.


Error bound for minimum-degree spanning tree

It is $\sf NP$-complete to decide if a given a graph has a minimum-degree spanning tree of maximum degree 2. Because the problem is hard, we would like to compute an approximate solution (to the optimization problem).

What they do is that they show how to find a tree $T$ with $\Delta(T)$ being at most $2\text{OPT} + \log_2 n$. The intuition is that the local search tries to make local improvements to a candidate tree, and when it can't make any improvements, it has found a locally optimal tree. It can then be shown that for any locally optimal tree, the maximum degree is at most $2\text{OPT}+\log_2n$, where $n$ is the number of vertices. The explanation for the logarithmic term is given in Theorem 2.19; it results from a tight analysis.

The best we can hope to do assuming $\sf P \neq NP$ is to find a tree $T$ with $\Delta(T)$ being at most $\text{OPT}+1$. This in fact possible to do, and is shown in a later section of the book.


In the FLP Impossibility paper, why did the authors claim that e is applicable to every E in proof of lemma 3?

The crucial understanding here is the notion applicability of an event in some configuration versus the effect of applying the event to that configuration.
If an event e applies to configuration C, it follows that e applies to all C, where C is the set of all configurations reachable from C (all admissible extensions of C). This is a simple consequence of the model assumptions. If I can theoretically receive e now, and e can be delayed indefinitely, then I can apply e at any point in the future, perhaps having applied e', e'', and so on.
There is a myriad of conceivable scenarios where, in practice, either e will not be applied by the program (because the program counter has advanced beyond the point where this is possible, as per your example) or where the message in e will be rejected by the program because of some other condition (i.e. internal state that forbids the processing of e). An example of the latter is the receipt of phase 1a and 2a messages in Paxos: they may be silently discarded by an acceptor that has already promised a higher ballot number.
Now we come to the notion of effect, which was omitted from FLP. (One of the reasons that FLP is obscure.) Applying e in some configuration does not imply a measurable transition. A process p could conceivably pop a message from its receive queue and discard it immediately. FLP does not forbid this, provided p behaves deterministically at all times and does not rely on the notion of time. Perhaps, p has received some other message m', which has 'locked out' m, so to speak; ergo, the late delivery of m has no measurable effect on p. This is entirely possible.
The reasoning behind FLP is to only induce a contradiction. If applying e to any configuration in C results in a configuration in D, and if we can prove that D does not solely comprise univalent configurations, then we have shown that there is an ever-admissible schedule that spans bivalent states. Lemma 3 does not state that C and D are disjoint: some configurations in C may conceivably be in D. In the case where applying e to some state C' in C has no effect, then C' is in D by the assumption of the lemma.
In summary, applies simply means that an event may be delivered. It does not mean that it is acted upon in a transition-inducing way.


Formal Languages: if $L_1^* = L_2^*$, then $L_1 = L_2$

Certainly not. Consider $L_1=\{a\}$ and $L_2=\{\epsilon, a\}$.


Distribute numbers 1,N on a grid as evenly as possible

Simulated Annealing might work well for this problem.

The idea is to introduce a "temperature" component to your heuristic function to avoid getting stuck at local optima. Temperature corresponds to how willing the heuristic function is to accept an inferior arrangement. With simulated annealing, temperature starts off high and decreases until an optimal solution is found.

Here is solution to the Travelling Salesman Problem using simulated annealing

You can tinker with the starting temperature and its rate of change to try and find an optimal arrangement.


As the stack pointer may change while a function is executed, access to the stack is less confusing with a static frame pointer, that is set upon the entry to the function, so relative addressing becomes simpler.

On reason for using the stack to store parameters is that there is usually more memory available than registers. What would you do with a function g(a,b,c,d,e,f) where you have enough registers free to store a–e, but non for f? You would put f on the stack. As the size of the stack is only limited by the available memory using the stack still works for functions with even more parameters.

Modern compilers typically have a flag that controls whether the use of registers for parameter passing is allowed or not.


Official Name for the “First” Programming Language Developed by Turing?

Turing machines are not programmable. Each Turing machine computes only one function. Hence they do not use any
programming language. What you see as a language is the description of
the machine itself, not of a program in some programming language. Thus the name "Turing machine" is the only appropriate terminology.

Now it turns out that there are devices that can emulate Turing
machines, such as a computer programmed to do such an emulation.  They
can use the description of a Turing machine to simulate its
computation. This is very similar to a hardware emulator that can
mimic the hardware of a computer from a formal description of the
circuits.

The abstract theoretical model of such an emulation, as then performed
by a Turing machine is called a Universal Turing machine. But
universal Turing machines are in no way specialized for that kind of
description. It is a much more general concept. The most general name for the input to a universal Turing machine could possibly be "Natural numbers".

However, in his 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem, Turing uses the kind of encoding you have in mind as input to be properly encoded for his universal computing machine.
He calls it "standard description", abbreviated as "S.D.".

But it is not the first Turing complete language, even ignoring earlier theoretical work such as done by people like Church and Gödel.

You view of history is missing an earlier invention, which is Charles Babbage's Analytical Engine. Lady Augusta Ada King, Countess of Lovelace, is considered the first programmer in history, though her computer, Babbage's engine, never worked in her lifetime. I do not know that the "assembly language" for the engine received a name. According to Wikipedia it would have been Turing complete.


A Shortest Path Strange Formulation, or new modeling?

Solution I) is recursive definition where $k$ is number of links. This formulation comes from same as Bellman-Ford-Moore algorithm.

Solution II) is recursive definition where $k$ is an intermediate node. $d[i,j,k]$ is length of shortest path from $i$ to $j$ involving only $1..k$ as intermediate nodes. This formulation comes from Floyd Warshall algorithm.

Solution III) is recursive definition where $k$ is again number of links. I) and III) will give same value for $d[i,j,k]$. (See Shortest Paths)

Final solution will be $d[i,j,n]$ for every case.


Solution for a combinatorial minimization problem

G. Bach noticed that the best choice for $b$ is $\lfloor a/2 \rfloor$, and furthermore this choice gives the maximal binomial coefficient. The easiest way to see this is to consider the ratio of two adjacent binomial coefficients:
$$ \frac{\binom{a}{b}}{\binom{a}{b+1}} = \frac{b+1}{a-b}.$$
Therefore $\binom{a}{b} \leq \binom{a}{b+1}$ iff $b+1 \leq a-b$ iff $2b+1 \leq a$, and we get the desired result.

The binomial theorem states that
$$ \sum_{b=0}^a \binom{a}{b} = 2^a, $$
hence
$$ \frac{2^a}{a+1} \leq \binom{a}{\lfloor a/2 \rfloor} \leq 2^a. $$
(The correct order of magnitude, $\Theta(2^a/\sqrt{a})$, can be found using Stirling's approximation.) Therefore the optimal $a$ satisfies the following inequalities:
$$ \frac{2^{a-1}}{a} < p \leq 2^a. $$
Therefore $a \geq \log_2 p$. On the other hand, when $p \geq 4$, $a \geq 2$, and so $a - \log_2 a \geq a/2$ (since $a-\log_2 a$ is monotone and $2 - \log_2 2 = 2/2$). Therefore for $p \geq 4$,
$$ 2p\log_2 (2p) > 2\frac{2^{a-1}}{a} (a - \log_2 a) > 2^{a-1}.$$
We conclude that
$$ \log_2 p \leq a < \log_2 p + 1 + \log_2 \log_2 (2p). $$
Therefore the binary search that G. Bach mentions takes only $O(\log\log\log p)$ steps.

If all we want is an asymptotic expression, then since $\binom{a}{\lfloor a/2 \rfloor} = \Theta(2^a/\sqrt{a})$, approximately we have $2^a/\sqrt{a} = Cp$, and so $a = \log_2 p + \Theta(\log_2\log_2 p)$. More terms can be obtained by taking more terms in Stirling's approximation. For example, we can find a constant $A$ such that $a = \log_2 p + A\log_2\log_2 p + o(\log_2\log_2 p)$.


If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable?

First of all, notice that not all c.e. sets have a c.e. complement, i.e. there are c.e. sets like $Q$ such that $Q^c=\mathbb{N}-Q$ is not c.e. In fact the  Halting Problem $H$ is such a c.e. set.

To see why $H^c$ is not c.e., notice that if both a set and its complement are semi-decidable, then both are also decidable. And since $H$ is not decidable, then $H^c$ should not be semi-decidable either.

Now for the counter example to your question, let $Q_1 = \mathbb{N}$ and $Q_2 = H$. Then $\mathbb{N} - H = H^c$, is not c.e.

Edit: Explained $H^c$ and added a simpler and more straightforward counter example.


Prove $\{xy \mid |x|=|y|, x \neq y\}$ is not a linear language

Consider this string: $w=a^kb^ka^{2k+2k!}b^ka^k$. We will show that we can't write this string in form of $uvxyz$ in a way that the conditions of pumping lemma for linear languages statisfy.
Because $|uvyz|\leq k$ we have :  $|uv|\leq k$ and $|yz|\leq k$
So we can write: $uv=a^{f_1}$ ,  $yz=a^{f_2}$ ,   $y=a^{g_1}$ , $v=a^{g_2}$ where $g_1+g_2>0$ (because  $yv$  is cannot be empty string) and $g_1+g_2\leq k$.
Now we pump $v$ and $y$  $n$-times and we have: $w'=a^{k+ng_1}b^ka^{2k+2k!}b^ka^{k+ng_2}$
We want to conclude this string is not in language for some $n$. So if we rewrite $w'$ as $w'=a^{k+ng_1}b^ka^xa^{2k+2k!-x}b^ka^{k+ng_2}$,
we should have:
$k+ng_1=2k+2k!-x$  and  $x=k+ng_2$
so $k+ng_1=2k+2k!-k-ng_2 \to n(g_1+g_2)=2k! \to n=\frac{2k!}{g_1+g_2}$.
Notice that $g_1\leq k , g_2 \leq k \to g_1+g_2 \leq 2k$  $\to$  $g_1+g_2| 2k!$
So we only need to set $n=\frac{2k!}{g_1+g_2}$ to have $w'=w''w''$ and this is a contradiction. So $L$ is not linear.


Do all NP complete problem have polynomial verifier?

A problem is in NP if and only if it has a polynomial verifier – that's the definition of NP. All NP-complete problems are in NP – that's part of the definition – and so have a polynomial verifier.

Factoring is not a decision problem, so it neither belongs to NP nor doesn't belong to NP. You can turn Factoring into a decision problem in many ways, for example asking if the $i$th bit of the $j$th factor of $n$ is equal to $b$. In that case a witness will be the list of factors of $n$. We can check that the factors multiply to $n$, and that they are all prime (since primality testing is in polynomial time).

(We are using here the unique factorization theorem, stating that a positive integer can be factored as a product of primes in a unique way. The same property doesn't hold in some more general situations.)

It is suspected that the decision problem corresponding to Factoring is not NP-complete, though it is certainly in NP, as the preceding paragraph shows.


This is a bipartite matching problem, which has several known algorithms. As a bonus, you get a combinatorial criterion for when it is even possible (namely, Hall's theorem).

Construct a bipartite graph with $n$ vertices on each side $x_i,y_j$. Connect $x_i$ to $y_j$ if $A_{ij} \neq 0$. A maximum matching in this graph, if it involves all the vertices, gives you a permutation $\pi$ such that $A_{i\pi(i)} \neq 0$ for all $i$.


Computing the hit and miss ratio of a cache organized as either direct mapped or two-way associative

Consider a cache of 4 lines of 16 bytes each. Main memory is divided
  into blocks of 16 bytes each. That is, block 0 has bytes with
  addresses 0 through 15, and so on.

Number of cache lines = 4

Each cache line = 16 bytes

Main memory block size = 16 bytes

Block 0 holds address 0 to 15,Block 1 holds address 16 to 31,Block 2 holds address 32 to 47, etc as below

╔══════════════════════════╗
║       Main Memory        ║
╠════════════════╤═════════╣
║ Memory address │         ║
╟────────────────┼─────────╢
║       0        │ Block 0 ║
╟────────────────┤         ║
║       1        │         ║
╟────────────────┤         ║
║       2        │         ║
╟────────────────┤         ║
║       3        │         ║
╟────────────────┤         ║
║       4        │         ║
╟────────────────┤         ║
║       5        │         ║
╟────────────────┤         ║
║       6        │         ║
╟────────────────┤         ║
║       7        │         ║
╟────────────────┤         ║
║       8        │         ║
╟────────────────┤         ║
║       9        │         ║
╟────────────────┤         ║
║       10       │         ║
╟────────────────┤         ║
║       11       │         ║
╟────────────────┤         ║
║       12       │         ║
╟────────────────┤         ║
║       13       │         ║
╟────────────────┤         ║
║       14       │         ║
╟────────────────┤         ║
║       15       │         ║
╟────────────────┼─────────╢
║       16       │ Block 1 ║
╟────────────────┤         ║
║       17       │         ║
╟────────────────┤         ║
║       18       │         ║
╟────────────────┤         ║
║   and so on    │         ║
╚════════════════╧═════════╝

  Now consider a program that accesses memory in the following sequence
  of addresses:

  Once: 63-70

  Loop 10 times: 15-32; 80-95

Here its not correctly specified that-

Case 1 : looped 15-32 ten times and then looped 80-95 ten times

Case 2 : 15-32 and 80-95 are looped one after another ten times

anyway we'll solve both cases.

  a. Suppose the cache is organized as direct mapped. Memory blocks 0,
  4, and so on are assigned to line 1; blocks 1, 5, and so on to line 2;
  and so on. Compute the hit ratio.

Direct mapped Cache :

╔═════════════╤═══════════════════╤═════════════════════════╗
║ Cache lines │ Main memory block │ Addresses in each block ║
╠═════════════╪═══════════════════╪═════════════════════════╣
║      0      │      Block 0      │          0-15           ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      1      │      Block 1      │          16-31          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      2      │      Block 2      │          32-47          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      3      │      Block 3      │          48-63          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      0      │      Block 4      │          64-79          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      1      │      Block 5      │          80-95          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      2      │      Block 6      │         96-111          ║
╚═════════════╧═══════════════════╧═════════════════════════╝

Accessing memory:

(1) once: 63-70

63 falls in Block 3 - Miss on 63 (Block 3 is bought to cache)

64 falls in Block 4 - Miss on 64 (Block 4 is bought to cache)

╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║      0      │      Block 4      │  64-79  ║
╟─────────────┼───────────────────┼─────────╢
║      1      │         -         │    -    ║
╟─────────────┼───────────────────┼─────────╢
║      2      │         -         │    -    ║
╟─────────────┼───────────────────┼─────────╢
║      3      │      Block 3      │  48-63  ║
╚═════════════╧═══════════════════╧═════════╝

therefore, 2 miss and 6 hit.

(2) loop: 15-32,80-95

Case 1:

15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache, replacing Block 4)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache)

╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║      0      │      Block 0      │  0-15   ║
╟─────────────┼───────────────────┼─────────╢
║      1      │      Block 1      │  16-31  ║
╟─────────────┼───────────────────┼─────────╢
║      2      │      Block 2      │  32-47  ║
╟─────────────┼───────────────────┼─────────╢
║      3      │      Block 3      │  48-63  ║
╚═════════════╧═══════════════════╧═════════╝

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1)

╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║      0      │      Block 0      │  0-15   ║
╟─────────────┼───────────────────┼─────────╢
║      1      │      Block 5      │  80-95  ║
╟─────────────┼───────────────────┼─────────╢
║      2      │      Block 2      │  32-47  ║
╟─────────────┼───────────────────┼─────────╢
║      3      │      Block 3      │  48-63  ║
╚═════════════╧═══════════════════╧═════════╝

therefore, 4 miss and 29 hit.

Case 2 : loop: 15-32,80-95

{{ 15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache, replacing Block 4)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache)

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1) }} x 1 times

{{ 16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache, replacing Block 5)

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1) }} x 9 times

therefore, 22 miss and 11 hit.

  b. Suppose the cache is organized as two-way set associative, with two
  sets of two lines each. Even-numbered blocks are assigned to set 0 and
  odd-numbered blocks are assigned to set 1. Compute the hit ratio using
  the least recently used replacement scheme.

Two-way set associative mapping:

╔═════════════════════════════╗
║            Cache            ║
╠═════════════╤═══════╤═══════╣
║ Cache lines │ Set 1 │ Set 2 ║
╟─────────────┼───────┼───────╢
║      0      │   -   │   -   ║
╟─────────────┼───────┼───────╢
║      1      │   -   │   -   ║
╚═════════════╧═══════╧═══════╝

Block allocation to cache lines:

╔═════════════╤═══════════════════╗
║ Cache lines │ Main memory Block ║
╠═════════════╪═══════════════════╣
║      0      │  Block 0,2,4,..   ║
╟─────────────┼───────────────────╢
║      1      │  Block 1,3,5,..   ║
╚═════════════╧═══════════════════╝

Accessing memory:

(1) once: 63-70

63 falls in Block 3 - Miss on 63 (Block 3 is bought to cache)

64 falls in Block 4 - Miss on 64 (Block 4 is bought to cache)

╔═══════════════════════════════╗
║             Cache             ║
╠═════════════╤═════════╤═══════╣
║ Cache lines │  Set 1  │ Set 2 ║
╟─────────────┼─────────┼───────╢
║      0      │ Block 4 │   -   ║
╟─────────────┼─────────┼───────╢
║      1      │ Block 3 │   -   ║
╚═════════════╧═════════╧═══════╝

therefore, 2 miss and 6 hit.

(2) loop: 15-32,80-95

Case 1:

15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache, replacing Block 4)

╔═════════════════════════════════╗
║              Cache              ║
╠═════════════╤═════════╤═════════╣
║ Cache lines │  Set 1  │  Set 2  ║
╟─────────────┼─────────┼─────────╢
║      0      │ Block 2 │ Block 0 ║
╟─────────────┼─────────┼─────────╢
║      1      │ Block 3 │ Block 1 ║
╚═════════════╧═════════╧═════════╝

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 3)

╔═════════════════════════════════╗
║              Cache              ║
╠═════════════╤═════════╤═════════╣
║ Cache lines │  Set 1  │  Set 2  ║
╟─────────────┼─────────┼─────────╢
║      0      │ Block 2 │ Block 0 ║
╟─────────────┼─────────┼─────────╢
║      1      │ Block 5 │ Block 1 ║
╚═════════════╧═════════╧═════════╝

therefore, 4 miss and 29 hit.

Case 2 : loop: 15-32,80-95

15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache,, replacing Block 2)

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 5)

therefore, 4 miss and 29 hit.

Answer:

a.

Case 1: hit ratio = (6+29)/(8+18+15) * 100 = 85.3%

Case 2: hit ratio = (6+11)/(8+18+15) * 100 = 41.1%

b.

Case 1: hit ratio = (6+29)/(8+18+15) * 100 = 85.3%

Case 2: hit ratio = (6+29)/(8+18+15) * 100 = 85.3%


Sequence to explore the complexity of the NP problem

So you have found out $X \in \mathbf{NP}$. Unfortunately, as Juho hints at in their answer, there is no "list" you can systematically go over to try and investigate $X$ further. This is mainly because separation results in complexity theory are (yet) few and far between, so most of the things you may try will not explicitly fail; you'll only be unsuccessful. For example, if you try to show $X \in \mathbf{P}$ you might succeed, but if it turns out to be incorrect it is very unlikely you will be able to prove it (since then $\mathbf{P} \neq \mathbf{NP}$).

This lack of "feedback" means you should tackle $X$ from different perspectives, and it is only experience (and a good deal of luck!) which will give you a "hunch" as to where the most promising one is. The following are a few options you might consider, as well as their implications if you manage to prove or disprove them (if any). Note I am only considering structural complexity theory here (which seems to be what you are interested in), but by all means this is what the entirety of complexity theory is about. Depending on the structure of $X$, it is also possible to consider $X$ from a parameterized complexity point of view, or try to find subexponential algorithms for it (see also number 4 below), and so forth and so on.

$X$ is $\mathbf{NP}$-complete

Prove: This is basically the end of the line for investigating $X$. It is also not a very surprising result since the list of $\mathbf{NP}$-complete problems is huge (and it already was when Richard Karp started to compile this list).

Disprove: Congratulations! You have proved $\mathbf{P} \neq \mathbf{NP}$.
$X \in \mathbf{P}$

Prove: This is the second most likely outcome and even more unsurprising than the former.

Disprove: Congratulations! You have proved $\mathbf{P} \neq \mathbf{NP}$.
$X \in \mathbf{coNP}$

Prove: Then $X$ is in $\mathbf{NP} \cap \mathbf{coNP}$ (which, for instance, includes factoring). Reconsider $X \in \mathbf{P}$.

Disprove: Congratulations! You have proved $\mathbf{NP} \neq \mathbf{coNP}$.
$X \in \mathbf{GI}$ (the graph isomorphism class)

Prove: Then $X$ admits a quasipolynomial-time algorithm (and is unlikely to be $\mathbf{NP}$-complete). Reconsider $X \in \mathbf{P}$.

Disprove: Congratulations! You have proved $\mathbf{P} \subseteq \mathbf{GI} \neq \mathbf{NP}$
$X \in \mathbf{BPP}$

Prove: Since it is widely suspected that $\mathbf{BPP} = \mathbf{P}$, this is only interesting if $X \in \mathbf{P}$ is not obvious. Consider also $X \in \mathbf{RP}$ or even $X \in \mathbf{ZPP}$.

Disprove: Congratulations! You have proved $\mathbf{NP} \neq \mathbf{BPP}$ (and quite likely also $\mathbf{P} \neq \mathbf{NP}$).

And the list goes on and on. As you can see, disproving any of these options leads to separation results, all of which would be major breakthroughs and, thus, unlikely to be proven simply by considering a random problem $X \in \mathbf{NP}$. This means you cannot expect to go through this list from head to tail making ticks and crosses as you go; you have to "guess" which of the options (if any!) is more likely and (with some luck) you'll be able to prove it.


Can we find the largest intersecting subfamily of convex polygons in quadratic time?

As Discrete lizard pointed out in a comment, I misinterpreted the statement of "sharing a common point", which I read as "pairwise sharing a common point".
You can thus ignore the below answer.  I will delete it later.

I'm not an expert in this area but I do actually believe that the problem you are talking about is surprisingly enough NP-complete.
The problem, known as Maximum Clique in convex planar sets (graph class: Conv)  was proved NP-hard by Kratochvíl and Kuběna [1] who write the following:

We show that complements of planar graphs have intersection representations by convex sets in the plane, i.e., for every planar graph, one can assign convex sets in the plane to its vertices in such a way that two of the sets are disjoint if and only if the correspondning vertices are adjacent. This fact has a complexity consequence — it follows that the problem of determining the clique number of an intersection graph of convex sets in the plane is NP-hard. We note that the complexity of this problem for intersection graphs of straight line segments in the plane is unknown.

[1] Kratochvíl, Jan, and Aleš Kuběna. "On intersection representations of co-planar graphs." Discrete Mathematics 178.1-3 (1998): 251-255


Making 5-tuples out of their respective 4-tuples

Go over all $\binom{36}{5}$ possible five-number combinations. For each one, calculate the five four-number combinations, and check whether all of them are unused.

In order to check whether a given four-number combination is unused, you can use a table. This will allow each such test to proceed very quickly. You can either use an array of size $36^4$ using the trivial encoding, or a slightly more sophisticated one of size $\binom{36}{4}$.


Asymptotic bounds on number of 3SAT formulas with unique solutions

It is dense, just as one would expect.

The number of uniquely satisfiable 3SAT formulas with $n$ variables and $n$ clauses is at least $2^n$, since for every possible assignment to the $n$ variables there is at least one 3SAT formula $\phi$ for which that is the satisfying assignment, and there are $2^n$ such assignments.  A 3SAT instance with $n$ variables and $n$ clauses can be represented as a string of length $\ell = 3n \lg n$.  Therefore, the number of such formulas is exponential in $\ell$.


An almost surely finite time game of coin toss where you win with probability $p$

Let $x_1,x_2,x_3,\ldots$ be the coin tosses, and let $p=0.y_1y_2y_3\ldots$ be the binary expansion of $p$. Halt once either of the following events happens:

$x_1=y_1,\ldots,x_{n-1}=y_{n-1}$ but $x_n < y_n$. In that case, declare a win.
$x_1=y_1,\ldots,x_{n-1}=y_{n-1}$ but $x_n > y_n$. In that case, declare a loss.

The game halts with probability $1$, since at any step it has a probability of $1/2$ to end. Let us now compute the probability of winning at the $n$'th step. If $y_n = 0$ then this event has probability $0$, and if $y_n = 1$ then it has probability $2^{-n}$. In total, the probability to win at the $n$'th step is $y_n 2^{-n}$. Since these events are disjoint, we deduce that the winning probability is
$$
\sum_{n=1}^\infty y_n 2^{-n} = p.
$$
What is happening here? We can imagine the coin being tossed infinitely many times, generating a value $q \in [0,1]$ whose binary expansion is $0.x_1x_2x_3\ldots \in [0,1]$. Clearly, $q$ is uniformly distributed in $[0,1]$. The game is a win if $q < p$ and a loss if $q > p$ (the probability that $q = p$ is zero). We can halt the game without generating all digits of $q$ if a prefix of its binary expansion suffices to determine that $q < p$ or that $q > p$.


Is it possible to prove Turing irreducibility

Let $A_{TM}$ be the language of the Halting problem. Then $\overline{A_{TM}} \nleq_T A_{TM}$, otherwise $A_{TM }$ would be recursive.

Another well-known theorem by Friedberg–Muchnik proves (using the finite injury priority argument) that there are recursively enumerable languages $A$ and $B$ such that $A \nleq_T B$ and $B \nleq_T A$ (pairwise incomparable).

R. Soare's book, for example, has more on this subject.


deterministic finite automaton for "does contain substring $w$" is of linear size

Consider the following NFA: the states are $q_0,\ldots,q_{|w|}$, there are transitions $q_{i-1} \to q_i$ on $w_i$, there are self-loops on $q_0,q_{|w|}$ (for all alphabet symbols), the initial state is $q_0$, and the unique final state is $q_{|w|}$.

Assuming $w \neq \epsilon$, the determinization generates $2|w|$ states:

For each location $0 \leq i < |w|$, a state consisting of $q_0$, $q_i$, and $q_j$ for $j < i$ such that $w_1\ldots w_j$ is a suffix of $w_1\ldots w_i$.
Same as before, with $q_{|w|}$ added.

When $w = \epsilon$, the NFA is already deterministic, and contains only one state.


How Babbage's Analytic engine made calculations of unlimited extent?

tl;dr-  The bit about "unlimited extent" is referring to being able to perform general-purpose computation rather than infinite computation.  They probably thought that it was trippy for a finite device to be able to pursue any sort of computation.

It seems that Brian Randell was referring to how the Analytical Engine was meant to be a general-computing device that could, in principle, perform any sort of computation.

The fuller quote discusses the notions of Turing completeness and "unlimited extent" as two different perspectives on this topic:

  Turing thus was the first to arrive at an understanding of the universal nature of a (conceptual) digital computer which matches and indeed surpasses the philosophic understanding that I believe Babbage had attained, a century earlier, of the universality of his planned (mechanical) Analytical Engine. Babbage’s phrasing was “that the whole of the conditions which enable a finite machine to make calculations of unlimited extent are fulfilled in the Analytical Engine” [2, p.28], where the term “extent” encompassed both the amount and accuracy of the data to be processed, and the length and logical complexity of the algorithm to be performed. Central to the Universal Turing Machine is the idea of having data, and input data in particular, represent a program (called a “table”
  in Turing’s paper). A hitherto little known manuscript by Babbage [1] which has recently been published for the first time makes it clear that Babbage had reached an almost similar level of understanding. In the manuscript he points out that a fully detailed sequence of “formula cards” might be prepared by the Analytical Engine from a more abstract sequence. However, this is not to say that Turing’s work was in any way derived from Babbage’s – indeed there is no evidence that Turing even knew of Babbage at this time, but this topic will be returned to later.

  -"The COLOSSUS", Brian Randell, page 4

This seems to be referring to the property of the Analytical Engine to perform general-purpose computation, which the above quote refers to as "universal nature" and "universality".


Let $S(n) = T(n)/(n+1)$. Notice that $S(0) = 0$ and $S(n) = S(n-1) + 1/n(n-1)$. Thus
$$
S(n) = \frac{1}{n(n+1)} + S(n-1) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + S(n-2) = \cdots
$$
Continuing in this way, for any $i \geq 0$ we get
$$
S(n) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + \cdots + \frac{1}{(i+1)(i+2)} + S(i).
$$
In particular, for $i = 0$ we get
$$
S(n) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + \cdots + \frac{1}{(1)(2)}.
$$

Alternatively, you can prove by induction that $S(n) = n/(n+1)$. This clearly holds for $n = 0$. Assuming it holds for $n-1$, we prove it for $n$:
$$
S(n) = \frac{1}{n(n+1)} + S(n-1) = \frac{1}{n(n+1)} + \frac{n-1}{n} = \frac{1+(n-1)(n+1)}{n(n+1)} = \frac{n^2}{n(n+1)} = \frac{n}{n+1}.
$$

Alternatively, we can prove directly that $T(n) = n$ by induction. This clearly holds for $n = 0$. Assuming it holds for $n-1$, we prove it for $n$:
$$
T(n) = \frac{n+1}{n} T(n-1) + \frac{n+1}{n(n+1)} = \frac{n+1}{n} \cdot (n-1) + \frac{1}{n} = \frac{(n+1)(n-1)+1}{n} = \frac{n^2}{n} = n.
$$


Are there any problems that are easy to compute but hard to verify?

If you are fine with artificial problems, you can make plenty of them.  Here are a few:

Given a positive integer n in unary, answer a satisfiable 3CNF formula in n Boolean variables.
Giving one satisfiable 3CNF formula is easy, but deciding whether a given 3CNF formula is satisfiable or not is 3SAT, a well-known NP-complete problem.
There is no input.  Just answer a Turing machine which halts (when run with an empty input tape).
Giving one such Turing machine is easy, but whether a given Turing machine halts or not is undecidable.

Added: By the way, I do not think that what you wrote in the last paragraph holds:

  I think such a problem would imply exponentially many "correct" answers for any given input, because otherwise verification could be carried out by simply computing all of the correct answers.

If the problem has one solution, then indeed checking an answer is no harder than computing the correct solution.  However, if the problem has one easy solution and one difficult solution, then you cannot compute all the solutions efficiently.  Here is one such problem (which is very artificial):

Given a Turing machine M, answer one of the following statements that is true: “M halts on empty input tape,” “M does not halt on empty input tape,” and “M is a Turing machine.”
Giving one solution is easy: you can always choose “M is a Turing machine.”  However, whether a given answer is correct or not is undecidable.  Note that in this problem, there are only two solutions for each instance.


Can you create a deterministic PDA for non-palindomes?

The language of palindromes isn't DCFL, see for example this question, which proves this for the closely related language of even length palindromes. Since DCFL are closed under complementation, it follows that your language is not DCFL.


Difficulty understanding the use of arbitrary function for the worst case running time of an algorithm

I think that the point that the authors are trying to make is the following:

The exact running time depends on the input.

When we say that the running time of insertion sort is $O(n^2)$, what we really mean is:

The worst-case running time of insertion sort is $O(n^2)$.

Actually, we could be even more verbose, and mention that by worst-case we mean worst case with respect to the length of the array:

The worst-case running time of insertion sort, in terms of the length $n$ of the input, is some function $f(n)$ which belongs to the class $O(n^2)$.

This is equivalent to the following claim:

There exists $C$ such that insertion sort takes time at most $Cn^2$ when running on an input of length $n$.

Note that there is no need to specify a lower bound on $n$ – if the running time is bounded by $C_1n^2$ for all $n \geq N$, then it is bounded by $C_2n^2$ for all $n \geq 1$. You can take $C_2$ to be the maximum between $C_1$ and the worst-case running times on inputs of length at most $N$.


What is the purpose of k in the transitive closure method?

One way you can think about the transitive closure method of converting DFAs to regular expressions (suggested by Michael Sipser in "Introduction to the Theory of Computation") is to think about converting a DFA to a regular expression by progressively ripping out states from the DFA and replacing transitions into and out of that state with new transitions labeled with regular expressions that have the same effect as entering and leaving the state.  Once you have ripped out a sufficiently large number of states, you can directly read off the regular expression from the resulting automaton.

$k$ in this algorithm is used to indicate what states you have eliminated so far.  You number all of the states $1, 2, 3, ..., n$, then use $k$ to indicate the numbers of all states you have eliminated at a particular point.  First you eliminate state 1; then states 1 and 2; then states 1, 2, and 3; etc.  Once you have $k = n$, you've eliminated all states and can just read off the answer.

If you'd like a graphical presentation of how this works, I have a set of lecture slides I used when teaching this construction.  It doesn't formally specify the algorithm or prove correctness, but should give you a visual representation of what the algorithm is doing.

Hope this helps!


There's no need to bubble-up the element all the way to the root. You can replace the item to be removed with the last element in the heap. If that new element is less than its parent, then bubble it up. If it's greater than its children, bubble it down.

I implemented this in my DevSource article, A Priority Queue Implementation in C#. Full source is available at http://www.mischel.com/pubs/priqueue.zip.

See my Stack Overflow answer about this at https://stackoverflow.com/a/8706363/56778


Regular Expression and NFA: each block of five consecutive symbols contains at least two 0's

The states of your DFA are pairs of integers $(i,j)$ with $1 \le i \le j \le 5$, plus a $\mathrm{REJECT}$ state.
Intuitively state $(i,j)$ means that the two most recent $0$s have been encountered when $i$-th to last and $j$-th to last character were read.
The transition function $\delta$ satisfies $\delta(\mathrm{REJECT}, x)=\mathrm{REJECT}$ for $x \in \{0,1\}$ while, for any other state $(i,j)$, $\delta$ is defined as follows:
$$
\delta( (i,j), x) =
\begin{cases}
(1, i+1) & \mbox{if } x=0 \mbox{ and } i<5\\
\mathrm{REJECT} & \mbox{if } x=0 \mbox{ and } i=5\\
(i+1, j+1) & \mbox{if } x=1 \mbox{ and } j<5\\
\mathrm{REJECT} & \mbox{if } x=1 \mbox{ and }j=5.
\end{cases}
$$
The initial state is $(1,1)$. All states, except for $\mathrm{REJECT}$,  are accepting states.


iterating over subsets by switching one element at a time

Here is how to convert a number from $\binom{n}{k}$ to a subset of $\binom{[n]}{k}$, and vice versa. This is known as inductive counting. I'll use your formula
$$ \binom{[n]}{k} = \binom{[n-1]}{k} + \binom{[n-1]}{k-1} \times \{n\}. $$

Given a code $x \in [0,\binom{n}{k})$, the idea is that the first $\binom{n-1}{k}$ codes will be used to code the $\binom{[n-1]}{k}$ part, and the rest will be used to code a subset in $\binom{[n-1]}{k-1}$ which will be completed to the required subset by adding the element $n$. Here is the relevant quasi-python code:

decode(n, k, code):
  if k == 0:
    return []
  elif code < binom(n-1, k):
    return decode(n-1, k, code)
  elif:
    return decode(n-1, k-1, code - binom(n-1, k)) + [n-1]

Encoding is the reverse process, and mirrors it exactly:

  encode(n, k, S):
    if k == 0:
      return 0
    elif n-1 not in S:
      return encode(n-1, k, S)
    else:
      return encode(n-1, k-1, S[:-1]) + binom(n-1, k)

Using these subroutines, you can compute the successor and predecessor of a given subset. You could also do it directly, for example by "unrolling" the resulting code, but this is a programming question which you should be able to solve for yourself in a couple hours.

The preceding doesn't produce a Gray code at all. You can obtain a Gray code by reversing the second half in your fundamental formula (this is the meaning of the overline). The corresponding decoding function is

decode2(n, k, code):
  if k == 0:
    return []
  elif code < binom(n-1, k):
    return decode2(n-1, k, code)
  elif:
    return decode2(n-1, k-1, binom(n, k) - 1 - code) + [n-1]

I'll leave the encoding function as an exercise. The proof that this forms a Gray code is by induction. You prove a more general claim, stating what are the first and last sets in the ordering for any given $n,k$, and given that you prove by induction that the result is a Gray code. Details left to you.


Algorithm for cost function maximization

If don't know anything about the function, then your problam is practically unsolvable: The function in the box could be 0 evereywhere, except for a single set of inputs, where it is 1. No strategy can guarantee that you find this set of inputs in finite time.

The situation might look better, if you can assume some sort of smoothness and/or monotony conditions.


How to do asynchronous programming with only global variables?

Every program that uses local variables can be converted to one that uses only global variables.  So, the answer is trivially yes.  However, it might not be pleasant for the software developer.


Search vs planning in artificial intelligence

Short answer is "Yes".

Long answer is "No":

As far as I am concerned the difference is limited to a specific author/lecture:
(to the best of my understanding of the slides)
The author of the linked slides does not want to refer to "search" as a technique like planning, but rather as a general procedure.

Planning is the process of finding a set of (valid) actions that transform an initial state (set of properties) to a goal state. Such a problem can be represented by a state space graph, where each node defines a complete world state (i.e. a set of properties). Two nodes are connected if there exists a valid action transforming one state into another.

"Search" is the general procedure of finding a solution by searching the problem space. In this case it is the process of iterating a state space graph starting at the initial node, trying to find a path to the goal node, i.e., using DFS. The search problem is given an (perhaps implicit) representation of the graph and is not concerned about internal properties of nodes.
A non-search "Planning" algorithm on the other side may make use of the logical properties of the states to iterate the state space graph.

However, I would like to note that most "Planning" algorithms do use some kind of search procedure on the state space graph, significantly improving the search using planning-heuristics:
Consider the graph given on slide 4 (of the referenced link). The complete graph represents the planning problem. The search "only sees" nodes and edges. A DFS would simply iterate all possible paths until a solution is found. A heuristic (planning algorithm) may use additional relations between properties (i.e. getting milk implies going to the supermarket first).

Informal definition of plan: the solution to a planning problem. A sequence of actions that translate the initial (world) state into the goal state.

In terms of the (graph) search this would be a list of edges to traverse. If there exists a valid plan, then there exists a path in the graph.

(this may be a little out of scope)
Since planning is in general PSPACE-complete naive search algorithms perform exceptionally bad on many instances. Common heuristics/techniques used in planning are based on the relaxation of the state space graph, i.e., by relaxing preconditions or effects (resulting in easier problems; in P, or NP) which can be solved "easily". If you are interested in planning that is somewhat separated from "search" you might wan to take a look at hierarchical task networks (HTN) which is basically planning with additional domain knowledge.


No. of subsets whose element multiply to give a square number

Factor each element $x_i$ to produce a vector $v_i$ of the powers of all primes which are at most 70. The product $\prod_{i \in S} x_i$ is a perfect square if every prime appears in an even power, that is, if $\sum_{i \in S} v_i = \mathbf0 \pmod{2}$. This suggests considering $v_i$ as a vector over $\mathbb{Z}_2$ (the integers mod 2). You are now given a matrix, and wish to know how many subsets of rows sum to the zero vector. This is a problem in linear algebra, and the answer depends on the rank of the matrix: if the matrix has $n$ rows, $m$ columns, and rank $r$, then the answer is $2^{n-r}$.

Here is a worked out example for $1,2,4,5,8$. In this case there are two relevant primes: $2,5$. The full matrix (before reducing modulo 2) is
$$
\begin{bmatrix}
0 & 0 \\ 1 & 0 \\ 2 & 0 \\ 0 & 1 \\ 3 & 0
\end{bmatrix}
$$
After reducing modulo 2, the matrix becomes
$$
\begin{bmatrix}
0 & 0 \\ 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ 1 & 0
\end{bmatrix}
$$
This matrix has full rank (rank 2), and so the answer is $2^{5-2} = 8$.

Here are the 8 subsets:
$$
\emptyset \\
\{1\} \\
\{4\} \\
\{1,4\} \\
\{2,8\} \\
\{1,2,8\} \\
\{2,4,8\} \\
\{1,2,4,8\}
$$

As noted in the comments, you might want to disallow the empty set (which multiplies to 1). In this case, the formula becomes $2^{n-r}-1$.


Big-Endian/Little-Endian argument - paper by Danny Cohen

The first statement says that there is a system that consistently uses the big-endian convention for various things (instructions, registers, etc.) The second statement says that the little-endian convention is more elegant ("consistent with itself").

How are these contradictory?


How to explain a language with modulo conditions is regular?

The easiest way is by giving a regular expression for $L$:
$$
L = (a+b+c)^2((a+b+c)^3)^*a.
$$
Here $(a+b+c)^2$ is a shorthand for $(a+b+c)(a+b+c)$, and $(a+b+c)^3$ is a shorthand for $(a+b+c)(a+b+c)(a+b+c)$.

Other ways described in the comments:

Give a DFA (6 states) or an NFA (4 states) for $L$.
Decompose $L = L' a$ and give a DFA (3 states) or an NFA (3 states) for $L'$.


If the union and intersection of two NP languages are both in P, prove that the langauges are in co-NP

Hint: You only need to distinguish between two non-trivial cases: $x\in (L_1\setminus L_2)$ and $x\in L_2\setminus L_1$. In these cases, membership-certificates for $L_1$ would be nonmembership-certificates for $L_2$ and vice versa. Hence, you always have nonmembership-certificates for every input string $x$. And conclude that both $L_1$ and $L_2$ are in $\mathrm{co}$-$\mathrm{NP}$.


How CompCert "proves" different things in its codebase

I am not very sure what you are asking, and I am also not sure that you have the background to understand CompCert. It seems that you are still confused by some basic concepts in Coq.

I would suggest you start with Software Foundations. Most of your questions would be answered there.

But, basically:

Definition and Fixpoint are like OCaml's let and let rec, respectively. They are used to define values and functions (and, of course, propositions).
Inductive is like  type in OCaml, or datatype in SML. They are used to define algebraic data types (or "inference rules").
Prop is the sort of propositions, so Definition and Inductive that return Props are defining propositions (i.e., "proof rules"). The Definition and Inductives are not themselves proofs.
Lemma, Theorem, Corollary, etc...are used for proofs.
Coq is based on the Curry-Howard correspondence: a proof of the proposition $A \rightarrow B$ is a function that takes something of type $A$ and produces something of type $B$, a proof by induction corresponds to a recursive function, etc. A proof of $A = B$ is obtained by transforming both sides and applying the only constructor of the type $=$, which is Refl of x * x (not Coq syntax, but you should get it). So, all proofs by tactic actually expand into programs!
In other words, Coq tactics are just another style of programming. You can use Definition and/or Fixpoint to write proofs, or use Proof to write programs. Of course, you should not do so; but you can.
CompCert is indeed proved against a formal specification. Which one? The official C programming language specification! Of course, you can't really prove anything against the text of the specification, so they encoded the specification in Coq using Definitions and Inductives.

In Software Foundations, there are examples of verifying a few toy interpreters and some toy programs, as well as more serious examples of verifying algorithms like red-black tree insertions and graph coloring. It does a pretty good job of explaining what and how to prove when you are writing programs in Coq. I would suggest that you start from there.


Sorting a sorted array after increasing several elements

You can update the array using the merge procedure of mergesort. Decompose your array into two smaller arrays: unchanged elements and updated elements. Since multiplying elements by $2$ preserves their relative order, you can do this decomposition in $O(n)$ while producing two sorted smaller arrays. You can then merge them in $O(n)$.


Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

Asympotically, you'll need $\Theta(n^2 \log n)$ comparisons.

Suppose $x_{(1)},\dots,x_{(n)}$ denotes the elements in sorted order.  Then if you don't see a comparison between $x_{(1)}$ and $x_{(2)}$, you will have no way to tell which order they should appear in.  The same is true of every pair of adjacent element.  So, there are $n-1$ coupons (one per adjacent pair of elements), and you need to collect them all.  Based on the coupon collector problem, we know you'll need $\Theta(n \log n)$ randomly chosen coupons before we've collected them all.  Each observation has a $2/n$ chance of being a coupon, so in total we'll need $\Theta(n^2 \log n)$ observations before we've collected all the coupons.  If we collect all the coupons, we can sort the $x$'s; if we're missing any coupon, we can't sort them.

The subsequent questions boil down to facts about the coupon collector problem, and you can use the tail bounds on Wikipedia to bound the information about the distribution.

If comparisons are chosen without replacement, then you need $\Theta(n^2)$ observations.

A reasonable way to check whether the list is sortable is to do a topological sort, then check that you've observed a comparison between every pair of adjacent items in the topologically sorted order.