Showing Optimal Substructure for Stacking Boxes DP Problem?

When people talk about this notion of an optimal substructure, they're just saying that you can solve a bigger problem by looking at the best solutions to smaller (sub)problems and somehow transforming these solutions to these subproblems back into a solution of the bigger problem.

So let's look at a modified version of this box-stacking problem that is also used in G4G's solution. Let $\text{Stack-Boxes-No-Rotation}(\mathrm{B})$ be the problem of finding a maximum stack of boxes in $B$ such that we are not allowed to rotate any of the boxes. Later on, we'll relax this restriction of not being able to perform rotations.

Now, let's get to the meat and potato of this concept. First, let's break down the phrase. What is a substructure? Well, the prefix "sub" suggests that this is a smaller problem structure than the whole problem. However, it's still a bit hazy what we mean by smaller. Are we talking about the number of boxes in $B$ to stack? Are we talking about volume? The height?

Unfortunately, there's no singular prescription that you can follow to figure this out. You'll have to rely on your intuition, and there are usually multiple valid ways to compare two things. The intuition however always comes back to the idea that if you have the solutions to the smaller problems, then you should be able to easily use them to create a solution to the big problem.

It's pretty hard to get a good feel for this unless we work through an example. Here, I'll start off with a way of defining "smaller" subproblems that is different from the way that G4G is doing, but which may have been one of your first instincts. Let's say a problem is smaller than another problem if its height is smaller than the other.

First thing first, since we're defining comparisons in terms of height, we need to create a parameter for it. So let $\text{Stackable}(B, h)$ determine whether it's possible to stack boxes in $B$ to a height of $h$. We wish to find the largest $h$ such that $\text{Stackable}(B, h)$ is still possible.

Now, we've talked about using the height to determine which problem is smaller. We say that $\text{Stackable}(B', h') \preceq \text{Stackable}(B, h)$ if $h' \le h$ and $B' \subseteq h'$. Now, we haven't shown that $\text{Stackable}(B, h)$ has the optimal-substructure property with respect to the order $\prec$ yet. Before we do so, let's review what optimal-substructure claims if it applies to this problem.

  If we know $\text{Stackable}(B', h')$ for every subset of boxes $B' \subset B$ or every height $h' < h$ (that is, $(B', h') \prec (B, h)$, then we would be able to use that information to find out whether $\text{Stackable}(B, h)$ is possible.

Okay, so how do we do that?

Well, a good approach is usually to think backwards. If it's possible for a set of boxes in $B$ to stack to height $h$, then let's consider the last move that we could have made. It could be any of the boxes in $B$. Suppose that we've picked a box $b$ to use as the top of the stack, then what? Well, it better be the case that the stack under it uses only boxes from $B - \{b\}$ and has height $h - h(b)$. In addition, it better be the case that the box immediately under $b$ must have an area large enough to accommodate $b$.

If you think about it for a moment, figuring out whether the stack under $b$ has height $h - h(b)$ can be accomplished by knowing $\text{Stackable}(B - \{b\}, h - h(b))$ (which literally tells me if it's possible to stack boxes from $B - \{b\}$ to a height of $h - h(b)$). However, there's no way to ensure that the box immediately under $b$ has to have a large enough area! Therefore, just knowing the solutions to the subproblems is not enough (in this formulation of the problem) to piece together a solution for the bigger problem.

But what went wrong here? It turns out that to stack a box on top of another box, we also need to know the area of the box on the bottom. Now, you have a few choices that you can make here. The problem at hand is that we're not tracking enough information, so one solution is to track more information. The other is to formulate an altogether different problem-structure.

Let's go with the former. How do we amend our process to keep track of the area of the box on top of a stack? Well, we could just add them as parameters of $\text{Stackable}$. Now, we interpret $\text{Stackable}(B, h, w, l)$ as whether it is possible to stack boxes from $B$ to a height of $h$ such that the box on the top of this stack has area $w \times l$. How's that for a mouthful. In addition, we need to also consider whether we should amend our denotation $\preceq$ of whether one subproblem is smaller than the other. While it's tempting to say that $(B', h', w', l') \preceq (B, h, w, l) \iff B' \subseteq B, h' \le h, w' \ge w, l' \ge l$, as you'll see, it's also okay if we just keep the original $\preceq$.

Now, let's see what optimal substructure claims here: If I have the answer to whether it is possible to stack boxes to a height of $h'$ using subsets of boxes that I am given, such that the final box of that stack is some $w' \times l'$, then I should be able to use that information to figure out whether it is possible to stack boxes to my desired height $h$ such that the final box has size $w \times l$.

Fortunately for us, it is now possible to do this. Once again, let's think backwards and consider the final box that we wish to stack: $b$. Now, we know that $b$ has an area of $w \times l$, so in order to stack it, we need to make sure that the preceding stack of boxes in $B - \{b\}$ has height $h - h(b)$ and whose final area is at least $w' \times l'$ where $w' > w$ and $l' > l$. Well, fortunately for us, this is literally what $\text{Stackable}(B - \{b\}, h - h(b), w', l')$ (for each $w', l' > w, l$) answers. Therefore, we know that our subproblem candidate space is
$$
\text{candidates}(B, h, w, l) = \bigcup_{b = (h(b), w, l) \in B, \\ w' > w, l' > l} \text{Stackable}(B - \{b\}, h - h(b), w', l').
$$
Now, given these candidates, how do we find $\text{Stackable}(B, h, w, l)$? Well, it's simple; if any of the candidate subproblems are possible, then so is the bigger problem. Therefore, we just have
$$
\text{Stackable}(B, h, w, l) = \bigvee_{b = (h(b), w, l) \in B, \\ w' > w, l' > l} \text{Stackable}(B - \{b\}, h - h(b), w', l').
$$

Now, there are $2^{|B|} \times H \times W \times L$ possible ways to fill the parameters $(B, h, w, l)$, so that's definitely a horrible solution, since you might have to find the value of each of these possible arguments in order to find the best result. Don't worry; this actually happens quite a lot in practice. Not everyone finds an acceptable solution on their first try.

After one iteration of a possible Dynamic Programming formulation that you find lacking, you can think about alternative formulations of your problem structure. In my example, I used the formulation $\text{Stackable}(B, h, w, l)$ to structure the solution space. There, I interpreted the result of $\text{Stackable}(B, h, w, l)$ as whether it is possible to stack boxes in $B$ to a height of $h$ such that the final box has area $w \times l$. Now, is there a better formulation that I can make?

Well, in the spirit of gradually refining your process, it's quite obvious that in the formulation $\text{Stackable}(B, h, w, l)$, the final box must have an area of $w \times l$. However, it's probably the case that not that many boxes share the same area. Therefore, we can probably gain back some time if we just outright say what the last box is: $\text{Stackable}(B, h, b \in B)$. Now, our dynamic programming formula becomes
$$
\text{Stackable}(B, h, b \in B) = \bigvee_{b' \in B-\{b\}\\w(b') \ge w(b) \\ l(b') \ge l(b)} \text{Stackable}(B, h - h(b'), b')
$$
Still, we're potentially looking at $|B| 2^{|B|} H$ arguments here.

Unfortunately, this is the extent of what the stackability formulation can do for us. However, we can try other substructure formulations.

And this is where the idea of the G4G solution comes into place. Let's number each of the boxes in $B$, so that $B = b_1 \le b_2 \le \dots \le b_n$ (with respect to their area). Now, instead of looking at this problem in terms of whether it is possible to stack some boxes to some height, let's look at what the maximum height of the set of boxes $b_1, \dots, b_k$ can reach.

This then gives another sub-structure ordering. We say that a problem on $(b_1, \dots, b_k)$ is smaller ($\prec$) than another problem on $(b_1, \dots, b_{k'})$ if $k < k'$. Now, let's consider the formulation $\text{Tallest}(b_1, \dots, b_k)$, which gives you the tallest stack you can build using just the boxes in $\{b_1, \dots, b_k\}$. Can we show that it has an optimal substructure?

Unfortunately, it's not all rainbows and sunshine: we run into the same problem that we've had before. Suppose we're considering the last box on a stack, we have no way to ensure that the box preceding it can fit the final box, just that its total area is larger. Therefore, let's try our parameterization trick from before; let $\text{Tallest}(n, b_k)$ denote the tallest tower that we can build using just boxes in $(b_1, \dots, b_n)$, such that the final box is $b_k$.

Third time's a charm, right? To see that this formulation has an optimal substructure property, let's try to build the tallest stack using the first $n$ widest boxes that ends at some $b_k$. Well, if we have $\text{Tallest}(n-1, b_{k'})$ where $b_{k'}$ is both wider and lengthier than $b_k$, then we could build an even taller stack. The tallest stack we can build is then the maximum of these candidates:
$$
\text{Tallest}(n, b_k) = \max_{b_{k'} \sqsubset b_k} \left(\text{Tallest}(n - 1, b_{k'})\right)
$$
where $b_{k'} \sqsubset b_k$ if $k' < k$ and $w(b_{k'}) \ge w(b_k), l(b_{k'}) \ge l(b_k)$. Now, shrinking $n$ is valid, but the astute reader will also notice that
$$
\text{Tallest}(n, b_k) = \max_{b_{k'} \sqsubset b_k} \left(\text{Tallest}(n, b_{k'})\right)
$$
will work just as well. In fact, we no longer need to keep track of the range of boxes to consider, and we can simplify this formulation down to just
$$
\text{Tallest}(b_k) = \max_{b_{k'} \sqsubset b_k} ~ \text{Tallest}(b_{k'})
$$
which can be interpreted as the tallest stack that you can build if the final block is $b_k$. This then concludes the formulation that G4G constructed.

I want to sign off with a few pieces of advice. Dynamic Programming is a very intuition-driven technique for problem solving. It might seem daunting at first, but with enough experience, you'll eventually view it as an extremely powerful tool. Personally, I find that the approaches that works best for me are:

Don't worry about the implementation of the actual dynamic program, and instead focus on its interpretation. When you see $\text{Tallest}(b_k)$, don't worry too much about what its code should look like; rather, stick to the high level interpretation and just read it out as "the tallest stack ending at the box $b_k$". This way, it makes reasoning about the correctness of the approach much easier.
Try to work backwards if possible. Dynamic programming is essentially just structural induction. It might seem daunting to have to build up the recursion tree in your head, so don't. Instead, the "inversion" trick of looking at the final operation of your program and working backwards is much less mentally taxing. On top of that, working this way will quickly tell you if your "induction hypothesis", or your "optimal substructure" hypothesis, actually holds or not.
Dynamic Programming is about decisions. Whenever you formulate a dynamic programming problem, always ask yourself: what is it that I need to choose and decide at every point? In the case of $\text{Tallest}(b_k)$, for each $b_{k'} \sqsubset b_k$, you have to decide whether you will include that box in your stack or not. You can explore all of these possibilities simultaneously, but at the end of the day, you have to commit to a concrete event. Therefore, it's important to figure out what your options/candidate subproblems are and how you can either combine them or choose the best outcome.


The substitution lemma only holds if what you're substituting is well-formed: $S$ can only contain type variables listed in $E$. In the application of T-TApp, $Y$ is a fresh variable, not present in $E,X,\Delta$. In particular, $Y \ne X$, $Y \notin S$ and $Y \notin A$.

There several ways to model variable names and renaming.

Shadowing allows a binder inside another binder to use the same name (e.g. $\lambda x. \lambda x. M$), and then the outer name is hidden (shadowed) in the inner construct (any occurence of $x$ in $M$ refers to the inner $x$). If you want to refer to the outer variable (which can happen to perform a beta reduction, for example), you need to first perform an explicit alpha conversion to rename one of the variables.
Implicit renaming always uses distinct names for any two binders present anywhere in an expression (so you never write $\color{red}{\lambda x. \lambda x. M}$ or even $\color{red}{(\lambda x. M) (\lambda x. M)}$, but $\lambda y. \lambda x. M$ and $(\lambda x.M) (\lambda y.[x \mapsto y]M)$), and there is an implicit alpha conversion after any reduction that duplicates a term. This is called the Barendregt convention.
Most literature claims to use the Barendregt convention, but in fact uses an intermediate convention where there nested binders never use the same name, but binders that don't overlap each other can use the same name, and there is an implicit alpha conversion step immediately after shadowing occurs. So for example $(\lambda x.M) (\lambda x.M)$ is allowed in writing, but the meta-notation $x$ in the two subterms are supposed to represent two different variables. As far as I remember, TAPL uses this convention.

An environment is a collection of binders, so without shadowing, it cannot define the same variable name more than once (no $\Gamma_1,X,\Gamma_2,X,\Gamma_3$).

Now, let's look at the application of T-TApp. The premise is $\Gamma' \vdash t' : \forall Y. T'$ where $\Gamma' = (E, [X \mapsto S] \Delta)$, $t' = [X \mapsto S] t$ and $T' = [X \mapsto S] T$. From this premise, you can conclude
$$\Gamma' \vdash \lambda t'[A'] : [Y \mapsto A'] T'$$
for any well-formed $A'$. You want to prove $\Gamma' \vdash [X \mapsto S] (t[A]) : [X \mapsto S] [Y \mapsto A] T$. So take $A' = [X \mapsto S] A$. The conclusion is
$$\Gamma' \vdash ([X \mapsto S] t)[[X \mapsto S] A] : [Y \mapsto [X \mapsto S] A] [X \mapsto S] T$$
and this is indeed
$$\Gamma' \vdash [X \mapsto S] (t[A]) : [X \mapsto S] [Y \mapsto A] T$$
since $Y \ne X$ and $Y \notin S$.


Is it possible to mapping reduce either of these languages to the other?

I'll assume that by $L(M)$ you mean the set of strings on which $M$ halts.

Hints:

INFINITE to AALL: Given a Turing machine $M$, construct a Turing machine $M'$ that on input $x$ halts if and only if $M$ halts on some $y \geq x$. (Arrange the inputs in some arbitrary way of your choice.)
AALL to INFINITE: Given a Turing machine $M$, construct a Turing machine $M'$ that on input $x$ halts if and only if $M$ halts on all $y \leq x$.

Both directions require use of dovetailing.


Find the minimum path to every vertex using Bellman-Ford

The algorithm is very similar to Bellman-Ford algorithm except that for each vertex $v$, you maintain $\delta^*(v)$, while in Bellman-Ford algorithm you maintain the length of shortest path from a certain source to $v$.

The correctness of the proof is also similar to that of Bellman-Ford algorithm. More specifically, you prove the following lemma by mathematical induction.

  Lemma. After $i$ repetitions of for loop:

  If $\mathrm{Distance}(u)$ is not infinity, it is equal to the length of some path from to $u$;
  If there is a path to $u$ with at most $i$ edges, then $\mathrm{Distance}(u)$ is at most the length of the shortest path to $u$ with at most $i$ edges.


How to pack polygons inside another polygon?

This belongs to an optimization class of problems called Packing problems. In your case, instead of a regular polygon as container, you've got an irregular one, but the idea remains the same.
These optimization problems are usually NP-hard, so I don't think there is an easy way to get the exact solution and trying all the combinations would be too too expensive.
There are some people interested in this kind of problems; I've found this link of some solved specific packing problems: https://erich-friedman.github.io/packing/
The easiest way I see, is to define an approximate center of the leather sheet, to move the set of polygons to there and, by scaling up and down and checking if the set of polygons is or not inside the target polygon, to get a closer and closer scale factor 'f' for your desired set of polygons.
But, unless you are going to use this factor for a large scale juggling balls production, probably doing it by hand would be fairly enough.


Best operating system for a computing degree?

I'm in the final year of a 4-year engineering degree program in Electronics and Communication Engineering. I have installed and use Kubuntu for the past 3 years and I love it!

It is lightweight and crashes very rarely (with 8 GB RAM, but 4 GB RAM is also useable with fewer applications runnning concurrently).
Most updates can be done without restarting your computer and you are not forced to update.
Beautiful and intuitive GUI (KDE)
Free KDE development tools like KDevelop and Kate are awesome!
Easily install and update software using Discover application.
Different modes and a fully customisable desktop
Tons of free software that can be installed.
The PDF reader, Okular is really good!
Learning Unix and Linux administration is a very valuable skill in the computing industry.


Show that the following language is not recursive:

We say a language $L$ is good if "$0x\in L$ if and only if $1x\in L$". Let $\mathcal{L}$ be the set of all good languages. Then you are trying to determine whether the language recognized by a given TM belongs to $\mathcal{L}$. Since $\mathcal{L}$ is non-trivial, according to Rice's theorem, this is undecidable.

If you want a proof without Rice's theorem, you can take a look at the proof of Rice's theorem and try to write a proof for this specific problem. This is not hard.


How do I prove a certain upper bound on the runtime of a probabilistic 2-SAT solver?

Denote the probability for increasing from $i$ to $i+1$ by $P(i \to i+1)$ and denote the probability for decreasing from $i$ to $i-1$ by $P(i \to i-1)$.

Consider an assignment $a$. Either one or both literals in the chosen clause $C$ are assigned incorrectly.

Case 1) Only one literal in $C$ is assigned incorrectly: In this case, the algorithm choose a literal $l$ from $C$ randomly. The chances for increasing or decreasing are equal.

Case 2) Both literals in $C$ are assigned incorrectly: Decreasing must happen. (Recall that $i$ denotes the number of the differences.)

Therefore, $P(i \to i-1) > P(i \to i+1)$, and $P(i \to i-1) > 0.5, P(i \to i+1) < 0.5$.

Because $t(i-1) \le t(i) \le t(i+1)$, so we have the upper bound by a little relaxation:

Correction according to "Ref" below: Consider a stochastic process (denoted $X$) $X_0, X_1, X_2, \ldots$ (not necessarily a Markov Chain) over state space $\{0, 1, \cdots, n \}$. The state $i$ here corresponds to the difference $i$.

The randomized algorithm aims to head to the state $0$ (possibly not monotonically). Although the algorithm could terminate before $X$ reaches $0$ if it finds another satisfying assignment than $h$, but we consider the worst case in which the algorithm only stops when $X_i = 0$. Also notice that $h$ here is arbitrary (meaning that the analysis is applicable to any satisfying assignment argument $h$; hence the worst case.)

Now we have

$$P(X_{i+1} = 1 \mid X_i = 0) = 1;$$
$$P(X_{i+1} = j+1 \mid X_i = j) < 0.5, \quad P(X_{i+1} = j-1 \mid X_i = j) > 0.5 \quad (1 \le j \le n-1).$$

Consider the following Markov Chain (denoted $Y$) $Y_0, Y_1, Y_2, \ldots$:
$$Y_0 = X_0;$$
$$P(Y_{i+1} = 1 \mid Y_i = 0) = 1;$$
$$P(Y_{i+1} = j+1 \mid Y_i = j) = 0.5, \quad P(Y_{i+1} = j-1 \mid Y_i = j) = 0.5 \quad (1 \le j \le n-1).$$

The process $Y$ can be regarded as a pessimistic version of $X$ because $X_i$ which decreases at the next step with probability $> 0.5$ in $X$ now decreases with probability exactly 0.5 in $Y$.
We are only interested in the case of $X$ reaching $X_0$ by decreasing.

  Therefore, the expected time to reach $X_0$ starting from any state is larger for $Y$ than for $X$.

NOTE: This is quite intuitive; however, the formal proof of this statement will involve some advanced techniques on Markov Chains. I have posted a follow-up problem at math.se).

Taking the place of $X$ by $Y$, we get the upper bound
$$t(i) \le 1 + \frac{1}{2} t(i−1) + \frac{1}{2} t(i+1)$$

Ref: Section 7.1.1 of the book "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" by Eli Upfal et al. (2005)


Local Cache miss using MESI Coherence Protocol

In cache coherence protocols there needs to be a single location where the global state can be figured out.  There are two ways to implement this location.  The first is to use a directory.  The second way is to broadcast all information on a shared bus.

If you are using a directory, then the cache that misses sends a message to the directory node that "knows" the global state for that cache line.  The directory records the list of caches that have a copy of the cache line and what the state is at each of those caches.  (This is easier than it sounds at first, the line is either invalid everywhere, modified in exactly one cache, exclusive in exactly one cache, or shared in more than one cache.)

In a directory-based coherence protocol, when a cache misses it sends a message to the directory for that line.  If the directory sees that the line is invalid everywhere it forwards the request to the main memory, which responds to the cache, and the directory updates its state so that it knows the cache has an exclusive copy.

If the directory sees that the line is modified or exclusive in another cache, it forwards the request to that cache, changes the global state to shared, and (in most versions of the algorithm) saves the identifiers of the two caches that are now sharing the line.

If the directory sees that the line is in state shared, it forwards the request to one of the other caches sharing the line, and adds the requester to the list of sharers.

Directory based cache coherence is elegant, and scalable, but requires more than the necessary number of message hops for small systems, so for small systems a hack is used to replace the directory.  Instead of a directory, all requests from caches or responses to requests (from other caches or from memory) are placed on a shared bus.  Every message is broadcast to all the other nodes on the bus.  So in the case of a read miss: the cache that missed broadcasts a request for the data in state "shared".  All the other caches and the main memory are listening to the bus (this is called snooping).  If one of the other caches has the line in state modified or exclusive, it changes its state to shared and sends the data back on the bus to the requester.  If several of the other caches have the line in state shared then they will all try to send the data back on the bus to the requester (and the bus arbiter will ignore all but one of the replies).  Finally if none of the other caches have a copy of the line then the main memory will respond with the data.  The cache that made the request sees that the responder was main memory rather than another cache, so puts the newly received line in state exclusive.


The two players construct a sequence $V_0 \supset V_1 \supset \cdots \supset V_m$ of sets of vertices such that:

$V_0$ consists of all vertices in the graph.
$|V_{i+1}| \leq (|V_i|+1)/2$.
$V_i \supseteq C \cap I$.

The players stop once $|V_m| \leq 1$. At this point they can answer the question using $O(1)$ communication.

At round $i$, the players know $V_{i-1}$, and wish to construct $V_i$. They act as follows:

If $C \cap V_{i-1}$ contains a vertex $v$ with fewer than $|V_{i-1}|/2$ neighbors in $V_{i-1}$, then Alice sends Bob one such vertex $v$, and both players set $V_i$ to be this set of neighbors, together with $v$ (this is valid since $C \cap I \subseteq C \subseteq V_i$). Otherwise, she sends $\bot$.
If Alice sent $\bot$ and $I \cap V_{i-1}$ contains a vertex $v$ with fewer than $|V_{i-1}|/2$ non-neighbors in $V_{i-1}$, then Bob sends Alice one such vertex $v$, and both players set $V_i$ to be this set of non-neighbors, together with $v$ (this is valid since $C \cap I \subseteq I \subseteq V_i$). Otherwise, he sends Alice $\bot$.
If both players sent $\bot$, then $C \cap I = \emptyset$. Indeed, if $v \in C \cap I$, then $v$ has at least $|V_{i-1}|/2$ neighbors and at least $|V_{i-1}|/2$ non-neighbors inside $|V_{i-1}|$, whereas the number of potential neighbors and non-neighbors is just $|V_{i-1}|-1$. Therefore the players can abort and conclude that $C \cap I = \emptyset$.

Each round takes $O(\log n)$ bits of communication, and there are $O(\log n)$ rounds, for a total of $O(\log^2 n)$ bits of communication.


Fastest algorithm for transforming points into graph

As you can imagine, evaluating every pair of points is very expansive ($O(N^2)$ for $N$ points).

If your set of point is sufficiently dense with respect to $M$, a simple solution is to use a grid. Build a grid of $M \times M$ cells, then for each cell, compute the list of points inside (doing one loop on points $O(N)$). Finally you just have to compare every point with every other point in the same cell or in one of the 8 surrounding it.

If you set of points is very dense you even can use a second grid of $\frac{M}{\sqrt{2}} \times \frac{M}{\sqrt{2}}$ cells so the points in the same cells have necessarly pair-wise distance lower than $M$. This may save some computation.

Note that in the case you have lot of empty cells (small density), it may generate memory issue. Imagine for instance 2 pairs of points very distant to each other (with respect to $M$). It may require a tremendeous grid, just to process 4 points... In this case, the basic "all-pair" comparison would be largely more efficient. k-d tree may be a solution to this problem. Or you can either identify the empty zones to process the points subset by subset.


Virtual Address and Physical Address Space

When we are using Virtual Memory, we are translating from a Virtual Address Space to a Physical Address Space.

To understand why it requires $2^{35}$ entries, consider the page size. In order to byte address $8$KB, we require $2^{13}$ entries. If we consider the Virtual Address given to us of $48$ bits, this gives us $48-13=35$ bits. These are the bits that are used for indexing into the page table for determining the address of the page or 'frame' in main memory.

The reason for having more virtual memory is because programs were getting so large that they couldn't be fit in main memory. So in order to allow a greater degree of multiprogramming, virtual memory was introduced. A program could have a 'large' memory to itself. However only the required parts would be loaded into memory as and when required a concept refered to as Demand Paging.


How can I find the Myhill-Nerode classes for the language A?

Two strings $x$ and $y$ are in the same Myhill–Nerode class if they can't be distinguished by adding the same string onto the end of them. That is, they're in the same class if, for all strings $z$, either $xz$ and $yz$ are both in the language or neither of them is.

So, for example, the strings $00$ and $01$ are in different classes because we can distinguish then by adding $1$: $001$ is in the language and $011$ is not.  In fact, they're already distinguished by the empty string $\epsilon$, since $01$ is in the language but $00$ is not.

In your case, you can shortcut this because the notion of indistinguishability corresponds exactly to minimal automata: the classes are exactly the sets of strings that take you to each state of the automaton.


Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$

An alternative solution still using domain transformation/change of variables.

$$T(n) = T(\sqrt{n}) + \log \log n$$

1. Let $m = \log n$

We can then define a new function $S$ based on how $m$ changes in $T$ and expand it:

$$\begin{align}
S(m) &= S\left(\frac{m}{2}\right) + \log m\\
&=S\left(\frac{m}{4}\right) + \log m -1 + \log m\\
& \vdots\\
& = \log^2 m - \sum_{i = 1}^{\log m} i \\
& = \Theta(\log^2 m) \implies T(n) = \Theta((\log \log n)^2)
\end{align}$$

2. Let $k = \log \log n$

We can then define a new function $R$ based on how $k$ changes in $T$ and expand it:

$$\begin{align}
R(k) &= R(k - 1) + k\\
& = R(k - 2) + k - 1 + k\\
& \vdots\\
& = \Theta(k^2) \implies T(n) = \Theta((\log \log n)^2)
\end{align}$$


How to show all possible implied parenthesis?

I'm assuming the input expression does not contain parentheses.

The idea is that for each binary operator we pick it as the principle operator (which is at the root of the parse tree) and split the expression into two subexpressions.
Then we solve the subproblems recursively.
After that we combine those solutions prepending and appending parens and inserting the principle operator in the middle. Notice that there could be multiple solutions for both subproblems.

Also you need to figure out the base case for recursion.


Sequence of N operations Amortized Analysis

How about this. Assume we maintain a binary counter $C$ that counts the operations executed so far. Let $D_i$ be the data structure after the $i$-th operation. We then define as potential $\Phi(D_i)$ number of $\tt 1$-digits in $C$. As usual $c_i$ denotes the actual costs, and $\hat c_i$ the amortized costs.

If $i$ is not a power of two, then we have
$$ \hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) \le 2 .$$
This is true since the addition of a $\tt 1$ on $C$ will turn one digit from $\tt 0$ to $\tt 1$ while possibly turning some digits from $\tt 1$ to $0$.

If $i$ is a power of two then clearly
$$ \hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1})= i + 1 - (i-1) =2 .$$

As a final comment, the amortized costs do always depend on the potential function. So another potential function yields different amortized costs.


$O(nop)$ is indeed exactly the best upper bound one can conclude for this program without additional information. The bound $O(n^3)$ cannot be shown unless you know $o$ and $p$ are themselves $O(n)$. On the other hand, if you knew $o$ and $p$ were actually constants, then you could prove a bound of $O(n)$ for the entire program.


How to reduce C′A′B + CAB′ to C′B + CB′?

What Boolean law / identity I can use to reduce $C'A'B+CAB'$ to $C'B+CB'$?

None.  You can't reduce $C'A'B+CAB'$ to $C'B+CB'$.  Those two Boolean expressions are not equivalent.  For example, when $A=\text{True}$, $B=\text{True}$, and $C=\text{False}$, $C'A'B+CAB'$ becomes $\text{False}$, but $C'B+CB'$ becomes $\text{True}$.


How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?

The grammar

$$\begin{array}{l}
S \rightarrow T_0 \\
T_n \rightarrow a \; T_{n+1} \\
T_n \rightarrow b \; T_{n+1} \\
T_n \rightarrow b \; T_{n+1} \; t_n \\
T_N \rightarrow t_N
\end{array}
$$

has the LR(0) state
$$T_N \rightarrow t_N \dot \\$$
expanded to $2^N$ variants in the LR(1) automata as all the partitions of $\{t_0 \dots t_{N-1}\}$ are possible look-head which appear in different contexts.  The number of states in the LR(0) automaton on the other hand is linear in term of $N$.  Thus an expansion factor of the order of $2^N/N$ is possible.

Edit: I'll have to check later when I've more time, I think adding $T_N \rightarrow T_0$ would give the exponential factor on nearly all the LR(0) states. That result in a shift-reduce conflict.


Finding infinitely many Myhill–Nerode equivalence classes

Let's consider your second example (the first example is easier). We will be interested in
$$
F(m) = \{ n : 0^m 1^n \in L \} = \{ n : \gcd(m,n) = 1 \}.
$$
If $F(m_1) \neq F(m_2)$, then $m_1$ and $m_2$ belong to two different equivalence classes.
From $F(m)$ you can recover the set of primes dividing $m$: $p \in F(m)$ iff $p \not\mid m$. In particular, this shows that if $p_1 \neq p_2$ are two different primes, then $F(p_1) \neq F(p_2)$. Since there are infinitely many primes, we conclude that there are infinitely many different equivalence classes.
The first example can be analyzed in a similar way (considering only odd $m$).


Adversarial Monte Carlo Tree Search Asymmetry

The most explored path will be the Nash Equilibrium, because at each step we choose the best move for each player.
The asymmetry happens at each level towards the best move for the current player, thus overall the tree will not grow asymmetrically.


Does this classify as Information retrieval?

You could consider that a form of information retrieval, if you want.  It sounds like keyword matching, so not one of the more sophisticated forms of information retrieval, but sometimes the simplest solutions are the best.

I wouldn't worry too much about the name.  There's no strict, hard-and-fast definition of exactly what counts and what doesn't.  The term serves as an aid for communication, and to my way of thinking, it sounds fine to consider what you are doing as a form of information retrieval.


Really confused about latency with pipelining

It is possible that you did not understand the mentioned references. Let say that $T_s$ is the time that is needed for completion of each stage, and $k$ is the number of stages. $T_s$ may or may not include the cost of pipelining. The latency of the first instruction is equal to the sum of times needed for completion of each stage, i.e.,
$kT_s$. Once the pipeline is full, the latency of each subsequent instruction is $T_s$. Therefore, the total time needed for execution of $n$ instructions is: $kT_s$ (first instruction) $+ (n - 1) T_s$ (each subsequent instruction).

Therefore, when pipeline is full, latency of each instruction is $T_s$. Still, the time needed for completion of each instruction is $kT_s$. Please note the difference between the latency and the time needed for completion of instruction. Pipelining only reduces the latency.


You are asking two questions. The answer to your first question is very simple – the authors used a figure of speech when they wrote over $10^{250,000,000,000}$. What they meant was roughly $10^{250,000,000,000}$. In any case, the exact number isn't important – it is just supposed to be an impressively large number rather than an exact estimate. For this reason I didn't bother to check your calculation. It is possible that your calculation is right, and the authors either got it wrong or preferred writing a round number rather than a more pedantic one; but it doesn't really matter.

As to your second question, probably the authors meant what they wrote – even when the table is small, it's not clear what its contents should be! For example, consider a speech recognition program. It is possible to convert the high dimensional raw input into a low dimensional representation using a vocoder. However, it is still difficult to parse what the person is saying, for many reasons. (This is just a guess as to what they meant; you aren't supplying enough context.)

If you want to understand the authors' comments mentioned in your second question better, I suggest you keep reading the book. The authors probably offer solutions to these problems, and these solutions will highlight the problems themselves.


Is there an algorithm that can solve chess within the span of a human lifetime?

You can't prove that chess can't be solved with less than 100 years time because you don't know what computers will be developed during that time. The only limits on computational speed we know are pretty ridiculous compared to what we can do today.

You might be able to prove that solving chess needs at least X many operations, but I don't know of any such results.


What is the most recent comparison of signature files and inverted indices?

Don't know any fresh references.

Off the top of my head:

Signature files require candidate verification via forward files. This requires lots of random accesses, basically one per potential match. One random memory access is 100+ CPU cycles. You can do a lot of work in 100 CPU cycles (e.g., you can decompress more than 100 IDs single core http://boytsov.info/pubs/simdcompressionarxiv.pdf).

Random access speed is even worse in the case of HDD or even SSD. There is in fact a growing gap between random and sequential access speed.

Before making this random access you cannot do pruning, early-termination, etc... BTW, for the most fancy recent data structure, you should probably check partitioned Elias-Fano indices:
http://pages.di.unipi.it/rossano/wp-content/uploads/sites/7/2015/11/sigir14.pdf


Find number of candidate keys given non-trivial functional dependency X->Y, where X is some set of attributes and Y is some prime attribute

X -> Y non-trivial means that X does not include Y. Since Y is a prime attribute, we know that there is at least a candidate key that include it. Let's call this key K1.
Now we have two cases: either X is a superkey, or not.
If X is a superkey, then it contains at least a candidate key K. We can easily convince that K ≠ K1, since it differ from K1 by at least one attribute.
So in this case in the relation there are at least two different candidate keys, K and K1.
Now suppose that X is not a superkey, and consider X ∪ (K1 - {Y}). This is surely a superkey, since it determines K1, which determines all the attributes. This superkey does not contains Y, but contains at least a candidate key K', so again we have at least two different candidate keys, K' and K1.
Edit
Let's see in a more formal way why X ∪ (K1 - {Y}) is a superkey.
A superkey is a set of attributes that determines all the attributes of the relation, and we can check this property by computing its closure and see if it contains all the attributes of the relation (let's call them T).
Since K1 is a candidate key, we know that:
(1) K1 -> T

we also know:
(2) X -> Y
(3) Y ∈ K1

So we can calculate the closure of X ∪ (K1 - {Y}) in this way:
(4) (X ∪ (K1 - {Y}))+ = X ∪ (K1 - {Y})
(5) (X ∪ (K1 - {Y}))+ = X ∪ (K1 - {Y}) ∪ Y = X ∪ K1  by (4) and (2)
(6) (X ∪ (K1 - {Y}))+ = X ∪ K1 ∪ T = T by (5) and (1)

so we can conclude that (X ∪ (K1 - {Y}))+ contains T, and, consequently, that (X ∪ (K1 - {Y})) is a superkey.


Sorting in computing longest increasing subsequence

Here is a sketch of the proof of Theorem 3.5:

If there is a comparison-based algorithm for LIS using $m$ comparisons in the worst case, then we can convert it to an algorithm which answers the question "is $L \geq k$" (for some fixed $k$) using $m$ comparisons.
Given an algorithm which answers the question "is $L \geq k$" using $m$ comparisons, we can convert it into an algorithm using $m + n \log k + O(n)$ comparisons which sorts the input whenever $L < k$.
Any comparison-based algorithm which sorts the input whenever $L < k$ must perform at least $\log S(n,k)$ comparisons (since it has at $S(n,k)$ possible outputs).
Consequently, every comparison-based algorithm for LIS must use at least $\log S(n,k) - n \log k - O(n)$ comparisons.
The theorem follows by choosing $k = \lfloor 3\sqrt{n} \rfloor$ and using the asymptotics of $S(n,k)$.

We sort the input in order to use a lower bound on sorting.


Understanding a binary classifier problem

This kind of analysis could be confusing if you are new to it. I think you need some intuition about what's going on. I will assume you understood until this point

$$
Pr[|p - \frac{1}{n} \sum_{i = 1}^{n} X_i| > \epsilon] \leq 2 e^{-2n\epsilon^2}
$$

(If not, hold tight and ask in the comments, I will elaborate).

So this inequality tells you this. You should be expecting the average value to be around the expected value of the average (that's why they call it expected value), and larger and larger deviations should be less and less likely. So if you ask what is the probability the average is at least $0.01$ away from the expected value, you plug-in $\epsilon = 0.01$ in the right hand side and get an upper bound on the probability that this happens.

Notice that as $\epsilon$ gets larger the probability gets smaller and smaller. Also notice that as $n$ gets larger, the probability gets smaller. These reason behind these two statements should be clear to you. (If not, pause and think about it).

Now you ask the inverse question. If I want to be 95% sure that the average is within $\epsilon$ from the expected, how big must epsilon be. Notice that the answer to this question must necessarily be a lower bound on $\epsilon$. Since if you are 95% sure that the average is within $\epsilon$ from the expected value, then with even bigger probability you are sure that it is within a bigger range from expected.

So what you want to do is assert that $Pr[\dots > \epsilon] \leq 0.05$, that is the probability that the average is farther away than $\epsilon$ be at most 5%. You cannot calculate the probability exactly, but you do have an upper bound on how big it can be (given by your inequality above). So if you want to be certain the probability is less than 5%, you can assert that the upperbound on the probability is less than 5%. That is, you want to solve:

$$
2 e^{-2n\epsilon^2} \leq \alpha = 0.05
$$

Note, that solving this will give you something like $\epsilon \geq \dots$ That means as long as you choose $\epsilon$ to be at least this, you are sure that the probability of deviating from the expected value by at least $\epsilon$ is at most 0.05.

Of course you can do the entire analysis for a variable $\alpha$ instead of 0.05.


Proving that CFLs are closed under even-ness using grammars

Actually you can shoot all three qestions with a single stone.

Since you can easily define a regular language $Even=\Sigma^{2n}$ for all
even strings :

you prove the result by applying closure of CF languages under
intersection with regular sets.
You use the standard construction of such an intersection based on
CF grammar to get the grammar version of the proof.
You use the standard construction of such an intersection based on
PDAs to get the PDA version of the proof.

You have to know at least one of the two constructions, since it is
usually how the closure under regular set intersection is proved.

The purpose of the question is to check that you know the theorem, and at least one way to prove it.


Ant Colony optimisation for finding subsets with ~0 sum

Your problem is no harder and no easier than the approximate subset-sum problem.  There is a natural approach for your problem:

Find any subset that sums to something close to zero, and output it.  Remove those numbers from the set $A$.
Go back to step 1 and repeat, until the set $A$ is empty.

This requires a way to find a subset that sums to approximately zero, i.e., an approximation algorithm for the subset-sum problem.  That problem is well-studied and can be solved in polynomial time using an approach based on rounding and dynamic programming.

I don't see any reason to expect ant colony programming to be better than the standard approaches; and I wouldn't be surprised if it is worse.


Turing Machine that both halts and loops in NP

It's not only NP-hard, it's undecidable!

For the easy proof, use Rice's Theorem. This is a non-trivial semantic property, so it's undecidable (and thus NP-hard). Done.

For a more interesting proof:

For any Turing machine $T$, let's define a new machine $Z_T$ like this:

  $Z_T$ looks at the first symbol on the tape. If it's a 1, it moves to the right and runs $T$ on the remainder of the tape. If it's anything else, it loops forever.

Now, suppose there exists a machine $U$ that can decide UNIQUE. I'm going to use this machine to decide the "Any-Input Halting Problem" ("is there any input that will make this machine halt?"), which is known to be undecidable (and NP-hard).

For any Turing machine $T$ that you give me, I can create a $Z_T$. Then I run $U$ on $Z_T$. I know that, for the input 0, $Z_T$ will loop forever. I also know that $Z_T$ halts on input 1XYZ only if $T$ halts on input XYZ. Therefore, $U$ will accept $Z_T$ if and only if $T$ halts on some input.

Since we know the Any-Input Halting Problem can't be decided, this hypothetical $U$ can't exist. Therefore UNIQUE is also undecidable, and anything undecidable is also NP-hard.


How do solve assignment of one interval to another?

This is an instance of bipartite matching (i.e., the assignment problem with no costs).  It can be solved by standard methods, such as network flow algorithms (e.g., Ford-Fulkerson), the Hopcroft-Karp algorithm, or using linear programming.  See also https://cs.stackexchange.com/a/61264/755.

In particular, you can build a bipartite graph, with one "left vertex" per peg, and one "right vertex" per hole, and an edge from peg $p$ to hole $h$ if the interval $p$ is contained in the interval $h$.  Compute the maximum cardinality matching for this bipartite graph.  If this matching covers every hole, then  the answer to your problem is "yes", otherwise the answer is "no".


What are flops and how are they benchmarked?

As far as I know, they give peak performance values. Given clock speed $f$ (in Hz) and number of cycles per (shortest) floating point operation $c$, the peak performance is essentially $f \cdot c$.

Of course, modern machines execute multiple floating point operations in parallel, have multiple cores etc. A more accurate formula can be found on Wikipedia.

This measure ignores all of the pain any real program encounters, e.g. cache misses and pipeline stalls. That is, any (reasonable) benchmark will not reach this number. But as an (unattainable) ultimate figure it can be useful to compare machines and even programs (how close to peak performance do they get?) -- take such statements with a grain of salt, always.


Given n strings, is one of them a substring of another?

You can build a suffix tree in linear time and check if there's an inner node that corresponds to a full string (constant time per node).

In more detail, assume we are given strings $s_1, \dots, s_n \in \Sigma^*$.

Build a (generalised) suffix tree of $s_1\$_1, s_2\$_2, \dots, s_n\$_n$ with $n$ pairwise distinct terminal markers $\$_1,\dots,\$_n \notin \Sigma$.

Using Ukkonen's algorithm, this can be done in linear time; linear in the sum of all string lengths.
Assuming that you label leaves with $(i,j)$ if they represent suffix $s_i[j..|s_i|]$ of $s_i$, traverse the tree and find those $n$ leaves labelled $(i,0)$, i.e. the leaves that correspond to the full strings.

This takes time linear in the tree size, which itself is linear in the input size.
The descendant leaves of the parent of $(i,0)$ (which is reached by an edge labelled $\$_i$) represent all matches from the set; this follows from the basic invariant of suffix trees. Find any one match by descending to any leaf (but $(i,0)$).

This again takes linear time.

The distinct terminal markers are not really necessary; a single one used to terminate all strings is quite sufficient as long as you allow multiple labels per leaf.


What would happen in the variant of the Josephus problem in which people in odd-numbered positions are killed in each round?

Position $2^{\lfloor \log_2 N \rfloor}$ is always safe since it is the position that maximizes the number of trailing zeros in its binary representation.
Claim: The person originally sitting in position $n$ is killed in the $i$-th round iff the binary representation of $n$ has exactly $i-1$ trailing zeroes.
Proof: By strong induction on $i$. If $i=1$ the claim is trivially true since $n$ has $0$ trailing zeroes iff $n$ is odd.
If $i > 1$, by induction hypothesis we have that all remaining people were originally sitting in positions whose binary representation has $i$ or more trailing zeros, i.e, those positions are exactly the integers in $S = \{1, \dots, N\}$ that are multiples of $2^i$.
If $n=2^i k$ then there are exactly $k$ positions in $S$ smaller than or equal to $n$, i.e., $n$ is killed iff $k$ is odd.


NP-completeness of Induced disjoint paths

Your problem is NP-hard (and so NP-complete), by reduction from 3SAT.

Consider a 3SAT instances with variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$.

For each variable $x_i$, there are four vertices $a_i,T_i,F_i,b_i$, connected as follows: $a_i-T_i-b_i$ and $a_i-F_i-b_i$.

For each clause $C_j = \ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3}$ (where $\ell_{j,1},\ell_{j,2},\ell_{j,3}$ are literals), there are five vertices $c_j,L_{j,1},L_{j,2},L_{j,3},d_j$, connected as follows: $c_j-L_{j,k}-d_j$ (for $k=1,2,3$).
Additionally, if $\ell_{j,k} = x_i$ then we connect $L_{j,k}$ with $F_i$, and if $\ell_{j,k} = \bar{x}_i$ then we connect $L_{j,k}$ with $T_i$.

The source-sink pairs are $(a_i,b_i)$ (for $i=1,\ldots,n$) and $(c_j,d_j)$ (for $j=1,\ldots,m$).

Each $a_i-b_i$ path corresponds to a truth assignment of $x_i$, and each $c_j-d_j$ path corresponds to a choice of a satisfied literal in $C_j$.


Reducing Exact Cover to Subset Sum in practise!

The short answer is no :-)

Why? ... Because SUBSET SUM is weakly NP-complete; you cannot avoid the exponential blowup of the numerical value of the arguments with respect to the input size of the original problem
(in other words the length of the binary representation of the $a_j$  is kept polynomial by the reduction but the values obviously are exponential)

If this was not the case you could use Dynamic Programming to solve an NP-complete problem in polynomial time.


Checking Feasibility of Linear Program in Polynomial Time

Restating the problem.  As far as I can tell, your system is equivalent to the following:

$$c_1 x_1 + \dots + c_n x_n = N$$

subject to the constraints

$$0 \le x_1, \dots, x_n \le 1.$$

Solving this problem. This is a linear program, so certainly we can tell in polynomial time whether it has any feasible solution, as a result of the fact that there are polynomial-time algorithms for linear programming.

However, there's a better solution.  We can directly solve this problem by inspection, without needing a linear programming solver.

Suppose without loss of generality that $c_1,\dots,c_j$ are positive and $c_{j+1},\dots,c_n$ are zero or negative.  (You can re-order the variables to put things into this standard form.)

Then it follows that $c_1 x_1 + \dots + c_n x_n \le c_1 + \dots + c_j$.  So, if $c_1 + \dots + c_j < N$, then this problem has no feasible solution.  On the other hand, if $N \le c_1 + \dots + c_j$, then it is easy to demonstrate that this problem does have a solution: simply let $x_1 = \cdots = x_j = N/(c_1 + \dots + c_j)$ and let $x_{j+1} = \cdots = x_n = 0$.  These $x_i$'s will all fall in the desired range.

Thus, feasibility can be checked in $O(n)$ time (in the RAM model, where basic operations take $O(1)$ time).

Details.  Why is it fair game to reduce the problem to the form given above?  How did I get the simpler form above?

Well, first off, I removed the variables $a,b$ from the linear program.  No matter what values you assign to the $x$'s, you'll always be able to assign a value to $a,b$ derived from the $x$'s that satisfies the equations that mention $a,b$.

Similarly, I removed the equation $k=\dots$ and the variable, since no matter what value we assign to the other variables, we can simply set $k=x_1+\dots+x_n$ and get a value that will satisfy this equation; it will also satisfy $k\ge 0$, since all the $x_i$'s are required to be $\ge 0$.  That leaves me with the problem shown at the top of my answer.


Performing Transitive Reduction via neighbourhood and strongly connected components

The standard definition of the transitive reduction of a graph $G$ says that we delete as many edges as possible, to retain the same reachability relationships.  However, the vertex set is unchanged: no vertices may be deleted.

The procedure you describe appears to involve deleting vertices.  Therefore, it does not appear to match the standard definition of transitive reduction.  (Perhaps your book has a non-standard definition of transitive reduction; if so, you might need to edit your question to ask about it.)

That said, a related construction does appear to correctly provide the transitive reduction.  In the related construction, instead of collapsing all vertices in a SCC into a single vertex, we replace the SCC with a directed cycle; then we apply transitive reduction to the dag of SCCs.  It is possible that your textbook actually uses the following procedure: (1) shrink each SCC to a single vertex, (2) apply transitive reduction to the resulting graph (which is the dag of SCCs), (3) now take each shrunken vertex and restore all of the original vertices and turn it into a directed cycle.  That should provide a correct algorithm for transitive reduction.  If that is what the book had in mind, your mistake was that you failed to perform step (3): you performed steps (1) and (2) and stopped there.  Of course, you have to perform the full procedure to get the full transitive reduction.

You might also be interested in the notion of a minimum equivalent graph, which involves deleting both edges and vertices; however, finding it in general is NP-hard.


about the complexity of recursive sequence

I calculated the first few values of your sequence:
$$
4,2,2,2,2,2,2,2,2,\ldots
$$
Indeed, $a_2 = 4^2-2 \bmod{2^2-1} = 14 \bmod{3} = 2$, and henceforward we have $a_{n-1}^2-2 = 2^2-2 = 2$ and so $a_n = 2$.


Is it necessary to learn how to prove Mathematical theorems as a CS Student?

There are several different ways to answer your question.

First, in the particular course you are taking now, part of the material is mathematical proofs. In order to succeed in this course, you need to be able to prove mathematical theorems. There are several reasons for this requirement:

Some more advanced classes also involve proving theorems.
The concept of proof and mathematical validity is important even if you don't expect to actively prove theorems. You need to understand the difference between a heuristic algorithm and an algorithm which is guaranteed to always work efficiently.
Programming is an abstract pursue, and requires a certain way of thought. Mathematics is one way to develop this way of thought, since it forces you to think in abstract terms.

Second, while more advance proofs do involve a lot of problem solving, in this particular problem you are handed out the solution, and your task is to convert the hint into a formal proof (in the sense of your class). At this stage of your class, you are not required to be able to create completely new proofs. Rather, the emphasis is on you understanding what is a mathematical proof and how it is written. Later on you might be given more creative tasks.

Third, the course you're taking will also teach you basic mathematical concepts that might be useful for you in the future. For example, one of the topics you are taught is propositional logic. You could encounter propositional logic in database theory, verification, and elsewhere. The only way to understand such an abstract concept is to play with it, and the way we play with concepts in mathematics is by proving simple statements.

Fourth, you mention that proving theorems is hard for you at the moment. This is why you're taking this class. One goal of the course is to teach you how to prove theorems. You might find it hard, but if the course goes slowly enough, you will eventually find it easy, and will have gained an invaluable skill. In a similar vein, you might have encountered the jump in difficulty level from high school to undergraduate studies. It requires some adjustment, but eventually you will gain the relevant studying skills.


Calculation of effective average instruction execution time in a 2-level paging system

I think the question wants you to assume that only about 30% of instructions involve a data memory access (which is somewhat low even for a RISC, Hennessey & Patterson give 47% for MIPS for 5 SPECint2000 benchmarks).  100ns + (1.3 * 420ns) = 646.

(Unless the average number of memory accesses per instruction was provided elsewhere, this question is technically unanswerable; but guessing that the number is less than two per instruction [e.g., a load-store ISA and not a memory-memory ISA] might be reasonable.)


I feel like there is a kind of circularity in the last part of your argument (and I think the conclusion is wrong, there are undecidable problems which we cannot prove to be undecidable).
You are basically making a case distinction:

if $\alpha$ can be proved or $\neg \alpha$ can be proved: Then $P(\alpha)$ can be proved and thus $P(P(\alpha))$ is true. (I agree here)
if neither $\alpha$ nor $\neg \alpha$ can be proved: Then $\neg P(\alpha)$ can be proved and thus $P(P(\alpha))$ is true. I disagree here. The correct assumption to make this conclusion would be: "if we can prove that neither $\alpha$ nor $\neg \alpha$ can be proved".

Note that you cannot in general prove that you are in the second case. You say you can because otherwise you could prove that you are in the first case. But what you need is to be able to prove that you cannot find a proof that you are in the first case, which is a different thing.


"Given $f(x)$, what is $\min(f(x))$?" becomes "Given $f(x)$, and $k$, decide if there is an $x$ such that $f(x)< k$?"


Does forcing TMs to change all symbols they read change their power?

If you give me a standard Turing Machine, I can build a must-write-different Turing Machine that does the same thing.

I'll take the original alphabet and double it -- so for symbol $a$, I create two symbols $a_1$ and $a_2$, and for symbol $b$, I create $b_1$ and $b_2$.

Now I treat both $a_1$ and $a_2$ in the exact same way as the old TM treated $a$, except when I'm supposed to write an $a$ back onto an $a$, I check if the current symbol is $a_1$ or $a_2$ and write the other one.

We could verify that this construction will indeed mimic the behavior of the original TM (no matter what it was), so must-write-different TMs are equally powerful.

(If this is not clear, please let me know so I can explain further!)


Complete examples of program correctness proofs

You will find a collection of proof techniques illustrated with poofs of small programs in the following paper:

Inductive Methods for Proving Properties of Programs, Manna, Ness, Vuillemin, CACM 16-8, August 1973.

It is made available on the web by one of the authors. It is also the first paper I ever read on the subject, and I remember enjoying it.

But I would expect the literature, on and off the web, refereed papers, textbooks and other sources. to include a considerable number of such proofs, considering that today people are working on the proofs of real program (such as compilers), with the help of mechanized proof systems.

OF course, you are aware that there is no such thing as correctness in an absolute sense. Correctness is defined only with respect to some specification, i.e. to some predicate in a logic that can also express the meaning of programs
(or whatever part of it is relevant).

Of course, there are different ways of defining the semantics of a program. So one might expect to have proof techniques that vary accordingly.


Finding connected components without building the graph first

I have an idea for the algorithm that's slightly better than a simple dfs based on the fact that the relationship is transitive.
From transitivity follows that $a \sim b \land b \sim c \Rightarrow a \sim c$. For our undirected graph this implies that every node in a connected component is connected to every other node. This yields following simple algorithm:
component = 1
mark = array of size n; initialized with 0
for i = 1 to n:
  if mark[i] == 0:
    mark[i] = component
    for j = i+1 to n:
      if i != j and mark[j] == 0 and c(X[i],X[j]):
        mark[j] = component
    component += 1

$mark$ now assigns every node a component.
The runtime of the algo is $O(cn)$ where $c$ is the number of components.
This would usually considerably faster than a dfs.
Notice in the worst case every node is its own component leading to $O(n^2)$.
But if this even occurs depends on the properties of your $c(x,y)$ function.
EDIT: The algorithm doesn't work since c(x,y) isn't transitive. My bad.


Is "lazy evaluation" part of the compilation process or a run-time feature?

I am not familiar with Clean; this answer addresses Lazy Evaluation in general.

Lazy evaluation happens at runtime.

The most fundamental form of lazy evaluation is leftmost reduction in lambda calculus. I will not burden this answer with a full introduction to lambda calculus. The intuition is that terms in lambda calculus consist of function definitions and function applications (and little to nothing else). Runtime of a program (which is a term) means evaluating the term. For an application term (which you can think of as $f(a)$), both $f$ and $a$ are also terms. Evaluating $f(a)$ may entail evaluating $f$ and/or $a$. The principle of leftmost reduction (lazy evaluation) means that $f$ is evaluated before $a$. Let us say $f$ is the function defined by $f(x)=x+x$ and $a$ is the term $1+2$. Then, lazy evaluation proceeds with the following steps:

$f(a)$
$a+a$
$(1+2)+a$
$(1+2)+(1+2)$

(At least if $+$ does not have a definition of its own. If it has, then after 2. the definition of $+$ will be expanded.)

If, on the other hand, $f$ is defined by $f(x)=0$, the evaluation is

$f(a)$
$0$

You notice that $a$ is not evaluated (because it is not needed), hence the connection to lazy evaluation. One final comment on this part: Lambda terms are in prefix notation, so "leftmost" actually means "outermost" when you think in terms of nested function applications.

In the second example above, lazy evaluation led to a speedup, because the term $a$ was not evaluated. In the first example, it led to a slowdown, because $a$ was evaluated twice. Actual lazily evaluated functional programming languages usually (again, I am not familiar with Clean) make the following optimization: Terms are not stored as syntax trees but as syntax dags. That is, in the first example, the two $a$ in term 2 would be the same node, also shared among all other positions of all other terms into which $a$ might have been copied. As soon as lazy evaluation dictates that $a$ is evaluated, the result is stored in place of the node $a$, becoming immediately available at all other occurences of $a$. The effect is a bit like memoization.


Solving a complicated recurrence relation

Following Timot's suggestion, let $S(m) = T(2^m)$, so that $S$ satisfies the recurrence
$$ S(m) = \begin{cases} 2S(m/2) + \tfrac{m}{\log m} & \text{ if } m > 2 \\ 1 & \text{ otherwise.} \end{cases} $$
In fact, we'll analyze the recurrence with a base case of $m = 1$ instead, and assume the logarithm is base $2$. We have
$$
\begin{align*}
S(2^k) &= \frac{2^k}{k} + 2 \frac{2^{k-1}}{k-1} + 4 \frac{2^{k-2}}{k-2} + \cdots + 2^{k-1} \frac{2^1}{1} + 2^k \\ &=
2^k \left[ \frac{1}{k} + \frac{1}{k-1} + \cdots + \frac{1}{1} + 1 \right] = \Theta(2^k\log k).
\end{align*}
$$
Therefore $S(m) = \Theta(m\log\log m)$ and $T(n) = \Theta(\log n\log\log\log n)$.


Example of worst case input for Build-Max-Heap

Think of a heap as a tree, not its array implementation.

Building a heap work bottom-up. Working from the lowest levels up to the root we add the keys one by one. Worst case is when each key moves as much as possible, so all the way to the level of leaves.

This should start getting the picture.


Entropy and Information Gain for multi attributes

You can group attributes together, but (assuming you're building some kind of decision tree) your decision tree will no longer be a binary tree, and you probably won't be any better off than just splitting by one attribute. Say for example you group $x_1$ and $x_2$ together, then there are 4 possible values for this new meta-attribute. You can use the same entropy calculation for this meta-attribute, and split on these four values.

But ask yourself this: why would you want to split on multiple attributes at once? Sure, it's true that $y=1$ whenever $x_1$, $x_2$, and $x_3$ are 1, but once you split on this you can't split on any subset of these three (for example, observe that $y=0$ whenever $x_2$ and $x_3$ are zero. If we split on all three variables we'd need two identical subtrees, one for $x_1=1, x_2=0, x_3=0$ and one for when they're all zero.)


There are two reasons to use this kind of definition:

It is a formal way to define the run of the machine.
It generalizes to the nondeterministic setting.

In the deterministic setting, an equivalent definition would be:

Define a (possibly finite) sequence $C_1,C_2,\ldots$ as follows:

$C_1$ is the start configuration of $M$ on input $w$,
For $i \geq 1$, $C_{i+1}$ is the unique configuration yielded by $C_i$, if such a configuration exists.

The machine $M$ accepts the input $w$ if the sequence is finite, and the last configuration is accepting.

This is not dramatically better than the quoted definition, and it doesn't generalize to the nondeterministic setting. It is a matter of taste which of the two to prefer.


How is quantum function $f(x) = a^x \mod N$ constructed in Shor's algorithm?

This paper by Pavlidis and Gizopoulos walks through one possible construction of the circuit you're looking for and also provides references to other literature on the subject:

"Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm". Archimedes Pavlidis, Dimitris Gizopoulos.  http://arxiv.org/abs/1207.0511


Yes.  If you can decide all languages in NP on a DTM in polynomial time, then P = NP = co-NP, i.e., you can also decide all languages in co-NP on a DTM in polynomial time, basically by negating the output of the DTM.  Taking the converse... if there exists a language $L$ in co-NP that can't be solved in polynomial time on a DTM, then there exists a language $L'$ in NP that can't be solved in polynomial time on a DTM (for instance, you can take $L'$ to be the complement of $L$).


Could the execution of a Haskell program be considered as a proof using equational reasoning

"Equational logic" has a fairly specific meaning, while you seem to be vaguely referring to the notion of "equational reasoning" which makes your question not meaningful. If we tried to take your question at face value, we immediately run into issues. Before we can talk about whether computation corresponds to proof in the logic, we'd first need to be able represent Haskell programs as terms in the logic! That can't be done, at least, not in a naive way. To handle binding forms and beta reduction, would require something like nominal/higher-order equational logic or utilizing explicit substitutions. This is just the beginning. Another question is: what do you want to constitute a Haskell program? Haskell is a Church-style language, meaning you need the type information to execute the code, i.e. a Haskell program has no meaning without type information. So does "Haskell program" mean some representation with all type information included, or do you intend to model type inference equationally somehow? Once you figure all that out, you then need some equations for your equational logic, at which point you run into another problem: Haskell has no formal semantics.

Let's step way back. For just plain arithmetic, how do we show that $2+2=1+3$? One answer is that we have an equational logic with equations like $2 = 1+1$, $3=1+(1+1)$, $(x+y)+z=x+(y+z)$, $x+y = y+x$, $0+x = x$. We might prove the equality then by using $2=1+1$ twice to get $(1+1)+(1+1) = 1+3$ then use associativity to get $1+(1+(1+1))$, and then $3 = 1+(1+1)$ to get $1+3 = 1+3$ which is then true by reflexivity. There are many other proofs besides this one that could be formulated. Just given a list of equations gives you no guidance on the proof approach, i.e. which equations to apply when and in which direction. Furthermore, if you fail to find a proof, you don't know if that's just because you weren't clever enough, or if there actually is no proof (i.e. the expressions are not equal). Both of these problems are solved by formulating a notion of "normal form" and a rewrite system that takes any term to its normal form. This is what Knuth-Bendix completion and its successors do1. In this case, each rewrite rule is derived from an equational proof, and the sequence of steps can be interpreted as stitching together these proofs with transitivity.

But this is not what people are thinking when they compute by hand, it's not what your calculator/computer is doing, and it's not even what automated theorem provers/proof assistants are typically doing2. Typically this is turned around: we have an algorithm for addition, and two expressions are considered equal when the algorithm produces the same result for both of them (where "the same" here means syntactically identical). In other words, computation comes first and "equality" is a derived concept.

For arithmetic, one might argue about which perspective is more "fundamental", but for a programming language it's clear computation is the fundamental notion. This computational approach frees us to use any representation of "terms" we want and any algorithmic approach we want as long as it's (ultimately) deterministic. Of course, this presumes that normal forms exist and are computable. For a general programming language, neither statement is true. Computing a normal form is then usually semidecidable, and the "equality" gets weakened to a partial equivalence relation. Most proof assistants avoid this issue by restricting to strongly normalizing languages. Computational Type Theory/NuPRL takes a very different approach. It exposes the operational semantics of its built-in notion of computation and gives the user some control over that computation process, e.g. "perform one beta reduction". We can then define "equality" as $x = y$ iff $x \leadsto^* x'$ and $y\leadsto^* y'$ and $x' =_\alpha y'$ where $\leadsto^*$ is the reflexive, transitive closure of the one-step reduction relation. This captures the previous notion when $x$ and $y$ have normal forms, but it allows equating expressions that lack normal forms as well, as long as they reduce to a common expression. This casts us back into the world where there's no obvious strategy, and we can't in general be sure whether two expression are unequal or we have simply failed to find a proof. That's unavoidable, since this notion of equality is not decidable.

Unsurprisingly, the steps of your "equational proofs" don't directly have to do with equality, but are, instead, sketches of proofs that e.g. $1+(2+1)\leadsto^* 4$ with respect to a hypothetical operational semantics for Haskell.

1 For just checking whether two ground terms are equal, a simpler algorithm called congruence closure can be used.

2 It (or congruence closure) is what most automated theorem provers are doing if you do literally present a series of equations and then ask if two expressions are equal, but not if numbers are built-in nor, more for proof assistants, if you define addition algorithmically. More generally, many proof assistants have built-in notion of computation, and many automated theorem provers heavily rely on decision procedures.


Algorithm to convert many instances of unidirectional lists to a graph?

You can find the smallest graph that is consistent with those walks from the graph as follows: start with an empty graph; for each pair of vertices that are adjacent in a list, e.g., $A \to B$, add the corresponding edge $A \to B$ to the graph.  The resulting graph is one that could have led to those walks, and is the smallest such.
You can't guarantee to uniquely and correctly reconstruct the original graph.  If you are unlucky, there could be some vertex in the graph that was just never visited by any walk, and then it won't appear in the reconstruction.  If walks are chosen randomly and you have enough of them, the probability of this happening might be low enough that you are willing to accept this risk.


Is there difference between a function in mathematics to a function in computer science?

A function in mathematics is just a special case for a binary relation, where for every x there is exactly one y such that xRy is in the binary relation.
Computer science uses that term with the same meaning, as it uses lots of mathematical terms. It also uses the term "function" (or "subroutine", "procedure", "method") with a totally different meaning of one component of a program in the area of computer programming.
Just like the word "function" would be used with a completely different meaning in patent law (functional vs. decorative components) architecture (a functional design), medicine or psychology (like a "functional alcoholic").


You should think of this language as all words of the form
$$
xa^nya^n,
$$
where $x=ab$ and $y \in b^*$. You can now modify a grammar for $a^nb^n$ to generate your language.


Comparison Based Sorting Run-time with respect to Total Number of Bits of Input

Assume, as is often the case, that all elements in the list have width $\Theta(\log n)$. This means that $w = \Theta(\log n)$ and so $x = nw = \Theta(n\log n)$. You can check that $n = \Theta(x/\log x)$, and this allows you to convert running times stated as a function of $n$ to running times stated as a function of $x$. For example, if the running time of some algorithm is $\Theta(n^2)$ as a function of $n$, then its running time as a function of $x$ is $\Theta(x^2/\log^2 x)$.


Understanding the Bitcoin White Paper's Notion of "Signing" and "Verifying"

Yes. It means "sign" and "verify" exactly as in a public key system such as RSA. Bitcoin doesn't introduce new cryptographic primitives or notions; it simply combines existing ones in a novel way. So you would simply use a public key system such as RSA to implement those operations in Bitcoin. The actual algorithm used is ECDSA, but this predates Bitcoin by quite a while. Arguably the "break-through" in Bitcoin is a clever mix of existing cryptographic techniques and aligning incentives.

Another clever aspect is that Bitcoin solves a different problem than what cryptographers traditionally viewed as "digital cash". That is, Bitcoin doesn't meet all the desiderata that one would hope "digital cash" would have, but clearly it's a pretty effective solution to the colloquial meaning of "digital cash".


How to iterate over vectors in order of probability

You can solve this with a priority queue.

Let $L(x)$ be the log-probability of the vector $x$, i.e.,

$$L(x) = \log \prod_i p_i^{x_i} (1-p_i)^{1-x_i} = \sum_i \ell_i(x_i)$$

where

$$\ell_i(b) = \log (p_i^b (1-p_i)^{1-b}).$$

Since the log is monotone, your problem is equivalent to looking for a way to enumerate the vectors $x \in \{0,1\}^n$ in order of decreasing $L(\cdot)$ value.

Of course, it is easy to identify the vector which has highest probability, i.e., highest $L(\cdot)$-value.  We simply put a $1$ in the $i$-th position if $p_i\ge 1/2$ and a $0$ otherwise; call the result $x_{\text{best}}$.  So create a priority queue that will hold a set of $n$-vectors.  Initialize it to a single element, $x_{\text{best}}$.  Assign it the priority $L(x_{\text{best}})$.  In general, if $x$ is in the priority queue, its priority will be $L(x)$.  Also, create a set $S$ of nodes that have been previously output; initially we will have $S = \emptyset$.

Now repeat the following loop:

Find the value of maximum priority and remove it from the priority queue.  Call it $x$.
Output $x$.  Add $x$ to $S$.
For each $i=1,2,\dots,n$: Let $y$ denote the vector obtained by flipping the $i$th bit of $x$; if $y \notin S$, add $y$ to the priority queue, with priority $L(y)$.

This loop will output the elements of $\{0,1\}^n$ in order of decreasing $L(\cdot)$-value.

Why does this work?  Basically, if $x$ has the highest $L(\cdot)$-value, then the next-highest must be obtained by flipping a single bit; flipping two bits will give you something strictly worse.  The same kind of justification can be applied inductively.  Or, to think about it another way, this is basically Dijkstra's algorithm applied to the $n$-dimensional cube (vertices are $\{0,1\}^n$), and Dijkstra's algorithm is an efficient way to enumerate the nodes of a graph in order of decreasing distance.  Since $L(\cdot)$ is additive, it can be understood as a distance from $x_{\text{best}}$.


How can I prove that the language of a read-only Turing machines is regular?

According to wikipedia, a read-only Turing (rTM) machine is a two-way finite automaton (2FSA). Two-way finite automata accept regular languages, and we are done.

Unfortunately, it is not that simple.

A Turing machine is allowed to wander into the area of the tape that consists of blank cells. This a 2FSA cannot do, usually it has end-of-tape markers. (Turing machines in general do not have these markers, otherwise they would be equivalent to linear-bounded automata.) Now a simulation of a rTM machine by a 2FSA is straightforward for the written part of the tape. For the blank parts we need transitions to code that the machine leaves to the right in state $q$, making a computation on blanks, returning in the rightmost cell in state $q'$. These are fixed by the machine, and do not depend on the actual input. Similarly for the left part (is the tape is two-sided infinite). Then there are accepting transitions that recognize that the rTM walks off the tape, does not return, but halts (and accepts). Non-halting non-returning excursions in the blank part can be ignored, they do not add to the accepted language.


Traveling Salesman's Tour Approx Algorithm: is this really a Hamiltonian Path?

You're wrong and the question is also unclearly worded. First, TSP is usually defined in terms of Hamiltonian cycles, not paths. That is, the salesman is in each city exactly once, except for the start point, which he is in twice. Second, as @avakar explains in his first comment, the algorithm given doesn't repeat vertices.

Also, the question seems to be making an unstated assumption. To flesh out @avakar's second comment, suppose you are given cities $1, \dots, n$ where:

$d(i,n)=k$ for $i< n-2$
$d(n-2,n)=d(n-1,n)=2$
$d(n-2,i)=d(n-1,i)=0$ for $i<n$
$d(i,j)=1$ for all other pairs $i$,$j$.

The optimal tours have cost $n$: e.g., $1, 2, \dots, n-2, n, n-1, 1$. However, the given algorithm will produce a tour like $1, n-1, n-2, 2, 3, \dots, n-3, n, 1$ when started at any vertex except $n$.  This has cost $n-5+2k$, which is more than twice the optimum whenever $k>\tfrac12(n+5)$.


What all can a valid approximation algorithm access?

Depends. Typically, with "approximation algorithms" people understand algorithms that run in polynomial time and return a possibly non-optimal solution (with a formal guarantee on the solution quality). In this definition, no, you can't spend exponential time solving an NP-hard problem.

On the other hand, nothing is forcing you to consider polynomial time algorithms that return non-optimal solutions. In fact, it is interesting to consider algorithms that take exponential time, and still return non-optimal solutions. See for instance [1, 2].

[1] Cygan, Marek, Lukasz Kowalik, Marcin Pilipczuk, and Mateusz Wykurz. "Exponential-time approximation of hard problems." arXiv preprint arXiv:0810.4934 (2008).

[2] Cygan, Marek, Łukasz Kowalik, and Mateusz Wykurz. "Exponential-time approximation of weighted set cover." Information Processing Letters 109, no. 16 (2009): 957-961.


Having trouble understanding a proof of Mahaney’s theorem

Let me recap the proof. We are given a sparse NP-hard language $A$: for each length $n$, there are at most $n^c$ strings of length $n$ in $A$.

For a satisfiable CNF $\varphi$, let $a(\varphi)$ be the lexicographically first satisfying assignment for $\varphi$. We consider the NP language $B$, which consists of all pairs $(\varphi,w)$ such that $\varphi$ is satisfiable and $a(\varphi) \leq w$ (in lexicographic order).

Since $B$ is in NP, there is a polytime reduction $f$ such that $(\varphi,w) \in B$ iff $f(\varphi,w) \in A$. Since $f$ runs in polytime, $|f(\varphi,w)|$ is polynomially bounded, say $|f(\varphi,w)| \leq N$ (where $N$ depends on $n = |(\varphi,w)|$). Since $A$ is sparse, we can bound
$$
 |\{f(\varphi,w) : w \text{ is an assignment for $\varphi$}\} \cap A| \leq \sum_{k \leq N} k^c =: m,
$$
where $m$ is also polynomial in $n$.

We will show how to use $f$ to decide SAT in polynomial time. Given a CNF $\varphi$, we will assume that $\varphi$ is satisfiable, and will attempt to verify it. That is, under the assumption that $\varphi$ is satisfiable, we will run an algorithm that is guaranteed to find a satisfying assignment for $\varphi$. If it succeeds, we can conclude that $\varphi$ is indeed satisfiable (since we have found a satisfying assignment). If it fails, then $\varphi$ couldn't have been satisfiable.

We will use $f$ to determine $a(\varphi)$ using some sort of binary search.
The idea is to pick $m+1$ many assignments $w_1,\ldots,w_{m+1}$, equally spaced in assignment space, and to calculate $f(\varphi,w_1), \ldots, f(\varphi,w_{m+1})$. We now consider two cases:

$f(\varphi,w_i) = f(\varphi,w_j)$ for some $i < j$. If $f(\varphi,w_i) \notin A$ then this means that $a(\varphi) > w_i,w_j$. If $f(\varphi,w_i) \in A$ then this means that $a(\varphi) \leq w_i,w_j$. In both cases, it is clear that $a(\varphi) \notin \{w_i+1,\ldots,w_j\}$ (where $w_i+1$ is the successor assignment in lexicographic order).
All $f(\varphi,w_i)$ are distinct. By construction, at least one of them is outside of $A$, say $f(\varphi,w_i)$. Then $a(\varphi) > w_i \geq w_1$. In particular, $a(\varphi) \notin \{0,\ldots,w_1\}$, where $0$ is the first assignment in lexicographic order.

Since we chose the $w_i$ to be evenly spaced, in both cases we eliminate a (roughly) $1/m$ fraction of the search space. After $O(nm)$ such iterations, we will be left with only $\operatorname{poly}(n)$ potential values of $a(\varphi)$, and can check them one by one (in order), thereby finding $a(\varphi)$ (if it is there to be found). (I am sketching this part since your question is about the preceding part.)


Solving an ordered knapsack problem exactly with a non linear (blackbox) evaluation function

If your function (or your surrogate function) has no structure, then there's nothing to say: you can't do any better than exhaustive search.  In particular, you must examine every possible combination of the items that has the right weight.  If your function has no structure, then you must evaluate it on each possible combination of items whose total weight matches the desired value: you can't rule out any of the possible combinations.  There are exponentially such combinations, so your problem requires evaluating the function (or surrogate function) on exponentially many possible inputs.

Also, if your function has no structure, there are no heuristics or approximation algorithms that will do better than brute force (try some randomly chosen set of combinations and see which does best).

No, this case probably hasn't been studied, because it isn't interesting: there's nothing interesting or useful you can say about it, beyond what I've listed above.


If worst-case one-way permutation exists (which exists iff. $P\neq UP\cap coUP$, proven here), then there exists inefficient reduction proof for some $NP$-complete problem.

We denote $\pi$ the one-way permutation above.

Specifically, for each proven $NP$-complete $L$, we can define:

$PERMUTED-WITNESS(L)=\{\pi(x)\mid x\in L\}$

with the certificate for $y\in PERMUTED-WITNESS(L)$ as: $(x,c)$ where $\pi(x)=y$ and $\pi(c)$ is a certificate for $x\in L$ (the "original" certificate). In other words, $c$ is the pre-image of the "original" certificate.

So, given a certificate $c'$ for $x\in L$, we cannot efficiently find $c$ (the pre-image of $c'$) for $\pi(x)\in PERMUTED-WITNESS(L)$


One approach would be to bring out the big hammer and try using a SAT solver.  You introduce boolean variables $x_{\ell,p,o}$, which is true if piece $p$ is placed in orientation $o$ in location $\ell$ on the grid.  Then, you write down boolean clauses to encode the conditions for a grid to be valid.  Finally, you do binary search: given $k$, you try to find a placement that has score at least $k$ (by writing boolean clauses to force the score to be at least $k$ and then using a SAT solver to test whether there exists an assignment to the variables that satisfies all of the clauses), and then do binary search on $k$.  This might be effective, or it might be slow; it's hard to predict, so the only way to find out is to try it.

The trickiest part of encoding into SAT will probably be calculating the score.  I suspect it will be useful to introduce extra boolean variables $y_{\ell}$, which is true if the piece at location $\ell$ is connected to the spool.  Then, write constraints that capture the relationship between the $x$'s and $y$'s.


PDA of the language where the number of a's are NOT equal to the number of b's

Your PDA can act as follows. For each $a$ being read, it pushes $A$ into the stack. Then, for every $b$ being read, it attempts to pop $A$ off the stack. If there are no more $A$s, it moves to an accepting state, checking that the rest of the input consists of $b$s; this handles the case in which there are more $b$s than $a$s. Alternatively, it could decide at some point to move, via an $\epsilon$ transition that pops an $A$, to a different accepting state at which no more symbols can be read; this handles the case in which there are more $a$s than $b$s.


Try to find an explicit formula for $T(n)$: Start by writing a few examples, such as $T(2)$, $T(4)$, etc.
Then, after you got some intuition on how $T(n)$ behaves, formulate it as a summation, and find a closed form for it. I will give the example of how to do it for the "best case" scenario:
Examples
$T(2) = T(1) + c_1 \cdot 2$
$T(4) = T(2) + c_1 \cdot 4 = T(1) + c_1 \cdot 4 + c_1 \cdot 2 = T(1) + c_1 \cdot (4 + 2)$
$T(8) = T(4) + c_1 \cdot 8 = T(1) + c_1 \cdot 8 + c_1 \cdot 4 + c_1 \cdot 2 = T(1) + c_1 \cdot (8+4+2)$
Opening recursion
And now (try for yourself) you can prove using induction that:
$T(n) = T(1) + c_1 \sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{n}{2^k}$
Finding closed form
Notice that $\sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{1}{2^k} = \frac{\left(\frac{1}{2}\right)^{\lfloor \log(n) \rfloor} - 1}{\frac{1}{2}-1} = \frac{1 - \frac{1}{n}}{\frac{1}{2}} \le 2$ Since it is the sum of a geometric progression.
Therefore, $T(n) = T(1) + c_1 \cdot n \cdot \sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{1}{2^k} \le T(1) + c_1 \cdot 2 \cdot n = O(n)$


If $V$ was recognizable then the language of Halting problem could be reduced to $V$ as following.

Let $M_V$ be a TM recognizing $V$, i.e, $M_V$ accepts $x$ if $x \in V$. Let $u$ be some string (description of a TM). Then we run $M_V$ on $0u$ and $1u$ by dovetailing. $M_V$ will eventually halt on one of these inputs since $u$ is either in $HALT$ or not in $HALT$. So, when it halts we simply check: if $M$ has halted on $0u$ then $u \in HALT$, else if $M$ has halted on 1u then $u \notin HALT$. Thus this implies that $HALT$ is decidable which is impossible.

Similarly for $\overline{V}$. Let $u$ be some string (description of a TM). If $M_{\overline{V}}$ accepts $0u$ then $u \notin HALT$. If $M_{\overline{V}}$ accepts $1u$ then $u \in HALT$.


Shortest path in a known room for a Roomba

the classic A* algorithm was invented in 1968 and is used for the purpose of shortest path-finding by robots, and it is provably optimum in a limited sense (eg given an unchanging layout and other constraints). there are many other pathfinding algorithm variants, basically "smart graph traversal" algorithms, eg focused on the online problem with changing constraints, see eg "how do state of the art pathfinding algorithms differ", cstheory.

here is some information on the roomba algorithm which is somewhat proprietary based on an interview with one of the designers (the interview seems no longer available). it is somewhat random and apparently uses a locally optimizing algorithm aka "greedy".


What is the difference between a fraction and a float?

Computers usually deal with floating-point numbers rather than with fractions. The main difference is that floating-point numbers have limited accuracy, but are much faster to perform arithmetic with (and are the only type of non-integer numbers supported natively in hardware).
Floating-point numbers are stored in "scientific notation" with a fixed accuracy, which depends on the datatype. Roughly speaking, they are stored in the form $\alpha \cdot 2^\beta$, where $1 \leq \alpha < 2$, $\beta$ is an integer, and both are stored in a fixed number of bits. This limits the accuracy of $\alpha$ and the range of $\beta$: if $\alpha$ is stored using $a$ bits (as $1.x_1\ldots x_a$) then it always expresses a fraction whose denominator is $2^a$, and if $\beta$ is stored using $b$ bits then it is always in the range $-2^{b-1},\ldots,2^{b-1}-1$.
Due to the limited accuracy of floating-point numbers, arithmetic on these numbers is only approximate, leading to numerical inaccuracies. When developing algorithms, you have to keep that in mind. There is actually an entire area in computer science, numerical analysis, devoted to such issues.


Unrestricted grammar to generate $a^{n^2}$

Set aside $n$ of the $n^2$ characters, and use that $(n+1)^2 = n^2 + 2n +1$.

So at any moment we have (say) $n^2-n$ symbols $A$ and $n$ symbols $B$.
We also need endmarkers. $L,R$ count as A$.

$S\to LBBR$

In one linear phase we visit all symbols, and each symbol $B$ will generate two extra $A$'s. Finally we add a $B$.

$L \to LX$; $XA\to AX$; $XB\to AABX$; $XR\to BR$

Nondeterministically end, transforming all symbols into $a$.


Is there an O(n log n) algorithm for 4D line simplification?

The algorithm that works with 4D case is described in the article Near-Linear Time Approximation Algorithms for Curve Simplification by four authors: Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, and Yusu Wang.

  Given a polygonal curve $P$ in $\mathcal R^d$
  and a parameter $\epsilon \ge 0$, an $\epsilon$-simplification of
  $P$ with size at most $\mathcal \kappa_F(\epsilon/2, P)$
  can be constructed in $\mathcal O(n\log n)$ time and $\mathcal O(n) $ space.

The algorithm does not depend on monotonicity properties. It covers the original line with disks and seeks the line traversal on the ordered set.

Sidenote:
There is a modification of Douglas-Peucker algorithm with the worst-case in $\mathcal O(n\log n)$ described in the paper An O(n log n) Implementation of the Douglas-Peucker Algorithm for Line Simplification. by John Hershberger and Jack Snoeyink: improved DP line simplification. Indeed it uses path hull.


I think that learning about computer science certainly can be an advantage. Here are a number of (related) skills computer science has to offer.

Programming – knowing how to program is a useful skill for any discipline. Statisticians and sociologists, geographers and engineers, and so on, often find themselves needing to program. Following a CS degree should teach you to program properly.
Modelling – one of the key things computer scientists do is modelling the world. True, physicists, biologies and sociologists do too, but the kinds of models they are different. Knowing about the kinds of models computer scientists build can often help modelling in other disciplines. Even better, computer science models are generally executable (see point 1).
Abstraction – computer science is all about abstraction, ignoring irrelevant details to bring out the core of a problem. When modelling a programming language, not every single detail is modelled. One can abstract away from almost all details and study the concurrency model in isolation or just the classes in an object-oriented language. This kind of abstraction is less common in other sciences (I claim), but they are crucial for understanding phenomena computer scientists are interested in. I'm sure that other fields could benefit from some abstraction.

This is probably best summed up in an article about Computational thinking by Jeannette Wing.


Here is the simulation by hand.

call by need using static scope

The function receives as x parameter the thunk [n+m] bound to the
globals. Then local n gets 10. The print statement requires evaluation
of the thunk, which becomes 100+5, i.e. 105. It prints 105+10,
i.e. 115. Local n and global m are changed, but this cannot affect x for two
reasons: the thunk does not depend on the local variable n (because
statically bound to the global variables n and m), and it is already evaluated to 105
anyway, which is printed by the second  print.

Note that, if the first print statement were removed, then x would be evaluated after changing the global variable m, which would then be 20 instead of 5, and the answer for the remaining print statement (formerly the second one) would be 120.

result: 115 105
call by name using dynamic scope

The function receives as x parameter the unbound expression [n+m]. Then
local n gets 10. Then x gets evaluated, with local n=10  and global m=5,
i.e. 15, and added 10 to print 25. Then local n=200 and global m=20. The
parameter x is reevaluated as 200+20, i.e. 220, which gets printed.

result: 25 220

How to test it? One would have to check various implementations of
programming languages. I do not remember off hand.

Call by need is usually found in functional languages, which normally
do not have assignment. But some still allow it. So I would look for
that regarding the first case. I think CAML may provide it.

Call by name is fairly rare, and rather weird in a dynamic scope
context. I do not know of any language that will offer that
combination. The best is to use a dynamic binding langage and simulate
the example by explicitly replacing the call by name argument by a
parameterless function that has the parameter as body.

In the example, you would call in main(): fun(lambda().n+m), and
in the body of the function fun you would replace x by the call x().


On a single-processor system, it is impossible for two threads to access the same location simultaneously. Rather, if the threads access the same data outside of a critical section, it's possible for their execution to become interleaved, in which case the access order is undefined. Execution is concurrent and you might call the result "random", in that nothing obvious affects the choice of one thread's code over another's. Of course, the scheduler is making the choice somehow, but it's fairly opaque in terms of ordering for access to thread-shared memory.

In multiprocessor/multicore/distributed applications, the notion of ordering is a little hazier. We can define the happens-before partial relation based on causation of signals and use this to define time stamps that can be used for coordinating events across sites. Unrelated events are called concurrent, and any processes which care about the order of concurrent events need to agree amongst themselves.  Consistency is a well-studied problem in shared-memory distributed systems. If sites request access to shared memory over some medium (bus, interconnect, etc.) then the medium access protocol will, in an opaque fashion, determine which thread gets access first. Like scheduling, the result here may appear "random", since different decisions can be made on different executions.


Why can't linear bounded automata accept an empty string?

Linear-bounded automata are able to accept the empty string. The equivalence between linear-bounded automata and context-sensitive grammars needs to be cognizant of this discrepancy between the two models. Usually a context-sensitive grammar is allowed one extra product to optionally produce the empty string. Alternatively, there is an equivalence between LBAs not accepting the empty string and CSGs.


Yes, this can be solved much more efficiently.  You can solve this problem in $O(b 2^b)$ time using a FFT, if each number is a $b$-bit number.  In the comments, you said $b=16$, so this should be an efficient solution: something like $2^{21}$ steps of computation.

Consider the sequence $b_{-1},b_0,b_1,\dots,b_n$ defined by $b_{-1}=0$ and $b_i = a_0 \oplus a_1 \oplus \dots \oplus a_i$.  Now your problem is equivalent to asking for the value that appears most frequently, out of all of the values $b_i \oplus b_j$ with $i<j$.

Let $x \in \mathbb{N}^{2^b}$ be the characteristic vector of $b_{-1},b_0,\dots,b_n$.  In other words, $x_v$ is equal to the number of times that $v$ appears in the values $b_{-1},b_0,\dots,b_n$; or, equivalently, $x_v = \#\{i : -1 \le i \le n, b_i = v\}$.

Let $y \in \mathbb{N}^{2^b}$ be the characteristic vector of $\{b_i \oplus b_j : i<j\}$.  In other words, $y_v$ is equal to the number of times that $v$ appears in the values $b_i \oplus b_j$; or, equivalently, $y_v = \#\{(i,j) : -1 \le i < j \le n, b_i \oplus b_j = v\}$.

We see that $y = x * x$, i.e., $y$ is the convolution of $x$ with itself:

$$y_v = \sum_u x_u x_{u \oplus v}.$$

This convolution can be computed using a discrete Fourier transform on the group $(\mathbb{Z}/2\mathbb{Z})^b$.  We find

$$y = \mathcal{F}^{-1}(\mathcal{F}(x)^2),$$

where here $\mathcal{F}$ is the Fourier transform and $\mathcal{F}^{-1}$ is the inverse Fourier transform.

Moreover, there is a fast Fourier transform  (FFT) for this group.  The FFT can be computed in $O(N \lg N)$ time, on sequences of length $N$.  Here $N=2^b$, since the characteristic vector has length $2^b$, so the running time to compute $\mathcal{F}$ and $\mathcal{F}^{-1}$ is $O(b 2^b)$.

Once you have the characteristic vector $y$, you just look for the index $i$ such that $y_i$ is maximized.  This is the desired output value.

All in all, this gives an algorithm with $O(b 2^b)$ running time.  This is probably much better than your $O(n^2)$ algorithm, for your particular parameters, but implementing it takes considerably more sophistication (you have to know how to implement a non-standard FFT, for a particular finite group).


Why are diploid (dominant/recessive) genes not used widely in genetic algorithms?

I don't know the actual reason, but it feels intuitive: let's think about what the diploid nature of genes does in RL. In essence it allows the recessive gene to remain in the gene pool  even if it's currently at disadvantage to exist, and occasionally resurface, giving two things - first, it doesn't go extinct and can re-multiply if it becomes advantageous; and second, it ensures some population variety as you'll continuously have both phenotypes - a part of population that exhibits the gene and part that doesn't.

Both of these things can be achieved in simpler ways by the mutating/crossover engine - you can directly 'fetch' random good-performing items from 100000 generations ago (which nature usually can't); and you can keep multiple varied subpopulations while protecting the non-primary ones from extinction, which nature usualy doesn't do.