I've reread Herlihy and Wing many times over the past 15 years.  It is a very difficult read.  And that is unfortunate, because while there are some subtleties around the edges the basic idea is actually quite reasonable.

In short: linearizability is like serializability, but with the additional requirement that the serialization respect additional ordering constraints between the transactions.  The goal is to allow you to reason rigorously about an individual atomic data structure rather than having to reason about the entire system all at once.

Linearizability is also easy to achieve: just associate a mutex with the object you want to linearize. Every transaction on that object starts by locking the mutex and finishes by unlocking the mutex.

Here are the definitions I'll use:

  A system is serializabile if given a set of transactions over a set of data, any result of executing the transactions is the same as if the transactions were executed in some sequential order, and the operations within each transaction are contained within their transaction in the order specified by the transaction's code.

Serializability disallows the appearance of interleaving of operations between different transactions, and requires that the chosen ordering of transactions satisfies causality (if transaction A writes the value x, and transaction B reads the value x that A wrote, then transaction A must precede transaction B in the chosen serial order.)  But it says nothing about any other constraints on the ordering of transactions (in particular, it says nothing about processes and the order in which processes perceive events.)

There is another related idea that does add in the constraints about the order in which processes executed operations (but doesn't talk about transactions only individual read/write operations):

  A system is sequentially consistent if the result of any execution is the same as if the operations of all the processes were executed in some sequential order, and the operations of each individual process appear in this sequence in the order specified by its program. (Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE T Comp 28:9(690-691), 1979).

Implicit in the definition of sequential consistency is that we only accept sequential orders where for each memory location (object) the induced sequential order of operations obeys the rule that the value returned by each read operation to location x must be the same value that was written by the immediately preceding write operation to location x in the sequential order.

Linearizability has the good intentions of (a) combining together the notion of transactions (from serialization) with the notion that processes expect the operations they issue to complete in order (from sequential consistency) and (b) narrowing the correctness criteria to talk about each object in isolation, rather than forcing you to reason about the system as a whole.  (I would like to be able to say that my object's implementation is correct even in a system where there are other objects that are not linearizable.)
I believe Herlihy and Wing may have been trying to rigorously define a monitor.

Part (a) is "easy": A sequential consistency-like requirement would be that the transactions on the object issued by each process appear in the resulting sequence in the order specified by the program.  A serialization-like requirement would be that the transactions on the object are all mutually exclusive (can be serialized).

The complexity comes from objective (b) (being able to talk about each object independently of all the others).

In a system with multiple objects it is possible that operations on object B place constraints on the order in which we believe operations were invoked on object A.  If we are looking at the entire system history then we will be constrained to certain sequential orders, and will need to reject others.  But we wanted a correctness criteria that we could use in isolation (reasoning just about what happens to object A without appealing to the global system history).

For example: suppose I am trying to argue about the correctness of object A, which is a queue, suppose object B is a memory location, and suppose I have the following execution histories: Thread 1: A.enqueue(x), A.dequeue() (returns y).  Thread 2: A.enqueue(y), A.dequeue() (returns x).  Is there an interleaving of events that would allow this implementation of the queue to be correct?  Yes:

Thread 1                           Thread 2
A.enqueue(x)                       ...
...                                A.enqueue(y)
...                                A.dequeue() (returns x)
A.dequeue(y) (returns y)           ...

But now what if the history (including object B) is: B starts with value 0. Thread 1: A.enqueue(x), A.dequeue() (returns y), B.write(1).  Thread 2: B.read() (returns 1) A.enqueue(y), A.dequeue() (returns x).

Thread 1                           Thread 2
A.enqueue(x)                       ...
A.dequeue() (returns y)            ...                       (uh oh!)
B.write(1)                         ...
...                                B.read() (returns 1)
...                                A.enqueue(y)
...                                A.dequeue() (returns x)

Now we'd like our definition of "correctness" to say that this history indicates that either our implementation of A is buggy or our implementation of B is buggy, because there is no serialization that "makes sense" (either Thread 2 needs to read a value from B that hasn't been written yet, or Thread 1 needs to dequeue a value from A that hasn't been enqueued yet.)  So while our original serialization of the transactions on A seemed like a reasonable one, if our implementation allows a history like the second one, then it is  clearly incorrect.

So the constraints that linearization adds are quite reasonable (and necessary even for simple data structures like FIFO queues.)  They are things like: "your implementation should disallow dequeue() a value that won't be enqueued() until some time in the future."
Linearizability is quite easy (and natural) to achieve: just associate a mutex with your object, and each transaction starts by locking and ends by unlocking.  Reasoning about linearizability starts to get tricky when you are trying to implement your atomicity with non-blocking or lock-free or wait-free techniques instead of simple mutexes.

If you are interested in some pointers to the literature, I found the following (although I think the discussion about "real-time" is one of the red-herrings that make linearizabilty more difficult than it needs to be.) https://stackoverflow.com/questions/4179587/difference-between-linearizability-and-serializability


Simultaneous regression of multiple curves in the same dataset or image?

There are many possible methods.  In your picture, there aren't too many dots, so the following algorithm might be good enough:

For each pair of points, find the line through them.  Count the number of points that are approximately on that line.
Choose the line that has the most number of points on it.  Output that line.  Delete all points that are approximately on that line from the figure.
Repeat until no points remain.

For fancier methods (e.g., if you have a huge number of points, or some prior model for what kinds of lines you expect to see), you can look at RANSAC and the expectation maximization (EM) algorithm, but given your sample picture, the above simple method might be adequate in your setting.


Having trouble understanding blatantly non-private definition because of Little-o notation

The interpretation of your professor is "intuitively correct" (but still formally wrong).
The notation $o(n)$ denotes the set of functions that grow less than linearly with $n$.
That definition means that, if we look at databases $d$ whose number of entries $n$ grows towards infinity, the candidate database $c$ will agree with $d$ in all but a vanishingly small fraction of the entries.
Notice that if $c$ agrees with $d$ "only" on $99.9\%$ of the $n$  entries, then the number of disagreements still grows linearly with $n$. Indeed: $0.001n \in \Theta(n)$ and hence $0.001n \not\in o(n)$. See the page about asymptotic notation on Wikipedia.


Find the subset of k element between n that maximize the total distance

This problem smells like it might be NP-hard, though I have no proof.  If you are looking for a proof of NP-hardness, my advice would be to go through Garey & Johnson (or some other list of NP-complete problems) and look for all problems that seem plausibly related: e.g., ones that involve the hypercube, bitvectors and the Hamming distance, clustering in general metric spaces, or total/average distance in some general metric space.  Then, edit your question to list all of those known-NP-complete and plausibly-related problems in your question... and try to see if you can find a reduction from any of them to your problem.

If you are less concerned about theoretical results and instead are looking to solve this in practice as efficiently as possible, some of the techniques in Maximize distance between k nodes in a graph can be adapted to your problem.  In particular, I'll suggest two candidate approaches: if you want an exact solution, try using ILP; if you want an approximate solution, try FPF.

You can formulate your problem as an instance of integer linear programming (ILP).  Introduce variables $y_i$, where $y_i$ indicates whether the $i$th point $x_i$ is included in $S_{max}$, and $z_{i,j}$, with the intended meaning that $z_{i,j} = y_i \land y_j$.  Constrain each of these to be zero-or-one integer variables.  Add the constraints $\sum_i y_i \le k$ and $z_{i,j} \le y_i$ and $z_{i,j} \le y_j$ and $z_{i,j}=z_{j,i}$.  Your goal is to maximize the objective function

$$\sum_{i,j} d(x_i,x_j) z_{i,j}.$$

You can optionally add the extra constraints $y_i+y_j-1 \le z_{i,j}$ and/or $z_{i,j}+z_{j,k}-1 \le z_{i,k}$ and/or $\sum z_{i,j} \le k(k-1)$; this will increase the number of constraints, but might help the solver find a solution more quickly.  Now give this ILP instance to an off-the-shelf ILP solver, and hope that it can find a solution efficiently.

If you want a fast heuristic to find an approximate solution, you could try using FPF, as described here.  You could also try a greedy algorithm: at the $i$th iteration, select the vertex $x_j$ that increases the total distance of all the vertices selected so far by as much as possible.  Neither of these is guaranteed to find an optimal solution, and the solution they output probably won't be optimal, but if you're lucky, they might be not-too-much-worse than optimal.


Proof of a greedy algorithm concerning “Buy and Resell Problem”

Summary: It is proposed to label the simple and intriguing algorithm given in the question as Adaptive Greedy. Several characterizations of the best strategy are presented. Also included is a rigorous and nontrivial proof of the algorithm. Some interesting original exercises and topics are attached.

Reformulation in mathematical terms

Let $a..b$ stand for the integers from a to b inclusively.

Let us fix $n\ge 2$ and $p(i)>0$, the price of an item in city $i \in 1..n$ (All items are the same except their prices). Assume all prices are different. This assumption is not necessary in order to establish the arguments, the concepts and conclusions below. However, it does simplify them significantly. For example, the algorithm becomes deterministic, producing the same output given the same input.

A strategy $s$ is a function from $1..n$ to $\{1,0,-1\}$, where $1,0$ and $-1$ mean buying, passing and selling respectively.

Given a strategy $s$,  let $h_s(i)=\sum_{j\in 1..i}s(j)$ be the number of items held right after city $i$ and also let $h_s(0)=0$. A strategy is an admissible strategy if $h_s(i)\ge0$ for all $i$; otherwise it is an inadmissible strategy. We will only consider admissible strategy unless stated otherwise.

The profit made by strategy $s$ is profit$(s)=\sum_{i\in 1..n} -s(i)p(i)$. If strategy $m$ makes the maximal profit, that is, profit$(m)=\max_s($profit$(s))$, then we say $m$ is a best strategy. Since there are finitely many strategies, there must exist at least one best strategy.

The adaptive greedy algorithm that returns the best strategy

Here is the pseudocode in Python style for the adaptive greedy algorithm. It is the same as the pseudocode in the question except that it uses the self-explanatory terms defined above and that it returns the best strategy instead of the maximal profit. We will prove that it returns the unique best strategy shortly.

Input:
  price $p(i)$ for $i\in 1..n$.
Procedure:
  Let s be the all-passing strategy, i.e., s(i)=0 for i in 1..n
  For each city from 1 to n:
    Try finding the previous city where s passes or sells with the \
       lowest prices that is lower than the price at the current city.
    If found, let s sell in the current city and change its action \
       at the city found from pass to buy or from sell to pass.
Output:
    strategy s

The above algorithm, or its equivalent version given in the question, will be referred to as "this algorithm".

Is this algorithm a greedy algorithm and why is it better called adaptive greedy?

At each city, given all admissible pairs of choices of an action in the current city and a change of the action in a previous city, this algorithm selects the pair of choices that can increase the profit the most if it is possible to increase the profit. Otherwise, this algorithm does nothing. That locally optimal selection of admissible choices at each successive city is why we call this algorithm greedy.

Readers might wonder why I explain this algorithm can be classified as greedy, a fact that seems obvious and is assumed by the questioner. That classification is, in fact, not conclusive at all. In fact, the Wikipedia entry on greedy algorithm says the following.

  Greedy choice property
  We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices.

  Optimal substructure
  "A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems."[2]

Note that this algorithm reconsiders all of its choices made so far when it makes every new choices. When this algorithm runs for cities 1, 2, 3, 4, 5 with prices 1, 2, 3, 4, 5 respectively, the unique optimal solution returned by it, buying in city 1 and 2 and selling in city 4 and 5, does not contain any optimal solution to any sub-problem it has considered except for two cities. It is clear this algorithm is not an ordinary greedy algorithm. Nor does it belong to dynamical programming in its usual sense. Readers can also check some answers to does every greedy algorithm have matroid structure.

Considering the definition and explanations in the Wikipedia, I propose to label this algorithm as an adaptive greedy algorithm, a greedy algorithm in the more general sense of "greedy". More precise definitions of adaptive greedy algorithm will be referenced here after they become available elsewhere.

Henceforth, this algorithm will also be referred as "this greedy algorithm" or "this adaptive greedy algorithm".

Why is it not easy to prove this greedy algorithm is correct?

All greedy algorithms other than this algorithm I have seen so far build larger optimal solutions by keeping the smaller optimal solutions intact and adding one more element. Their correctness are often proved by one of the following three strategies, which are not necessarily mutually exclusive.

"Staying Ahead". Show that after each step of $G$, its solution is at least as good as any other algorithm's.
This proof technique applies to Dijkstra's algorithm that finds the shortest path between nodes in a graph and the algorithm that always selects next interval of earliest ending time to find the most compatible interval in activity selction problem (which is also a kind of interval scheduling).
"Unimprovable Solutions". Give any other solution, we can gradually improved it until it becomes unimprovable. Show all unimprovable solutions give the same result or there is only one unimprovable solution. Show that the solution found by greedy algorithm is unimprovable.
This proof technique applies to the usual greedy algorithms for problems such as Interval Scheduling for Minimal Maximum Lateness and others [1] [2] [3] [4] [5].
"Always promising". If $G$ is a weighted matroid or greedoid, its standard greedy algorithm adds one more element to the current result subset in each stage, always promising there is a desired subset with maximal total weight that contains the result subset so far. When the algorithm ends, that promised desired subset will become none other than the result subset. The way to keep the promise is to use exchange of elements.
This proof technique applies to most of problems tagged with "greedy algorithm" including Kruskal’s algorithm or Prim's algorithm for minimal spanning tree.

However, as observed before, the new decision made by this algorithm at each city may, more often than not, modify the decisions for previous cities. In fact, the decision made at the last city may modify the selected action of the first city that has stayed the same for all previous partial solutions. This modification makes it non-trivial to prove the correctness of this simple algorithm. I encourage interested readers to try proving it. Any proof that is easier than the proof below will be a nice surprise.

In fact, there is not a single proof of the correctness of this algorithm as far as I have searched. Many answers, articles or online programming contests may explain clearly the greediness (in its plain sense as in English) of this algorithm or provide vast numerical evidences, which are still, however, far from a rigorous proof of its correctness.

It turns out only the second proof strategy, "unimprovable solutions" can be applied to this adaptive greedy algorithm successfully, as shown in a later section of this answer. There is a new twist, though. The uniqueness of the unimprovable solution can only be established by induction with the help of applying this algorithm. I am stilling searching for ways to show that uniqueness directly without using this algorithm.

The characterization theorem on the best strategy

An increasing integer pair $(i,j)$ is said to be $s$-clearance-separated if $h_s(z)=0$ for some $z\in i..(j-1)$.

A strategy $s$ to be said to improvable at two selected cities if the following conditions hold.

(room to improve) $s$ buy or pass at a lower price in one city but buy or pass at a higher price in the other city. Assume the former city is city $i$ and the other city is city $j$.
(no obstruction to switch) $i>j$ or $i<j$ and $(i,j)$ is not $s$-clearance-separated.

A strategy $s$ is unimprovable if $h_n(s)=0$ and it is not improvable at any two cities.

(The characterization theorem) The following four propositions about a strategy $s$ are equivalent.

(best strategy) $s$ is a best strategy.
(unimprovable strategy) $s$ is unimprovable.
(output of the greedy algorithm) $s$ is the unique strategy produced by this adaptive greedy algorithm.
(anatomy of the best strategy) There are integers $0=i_0\lt i_1\lt i_2\lt\cdots \lt i_t=n$ such that $h_s(i)=0$ if $i=i_j$ for some $j$ and $h_s(i)\gt0$ otherwise. That is, $i_j$'s are all clearance cities where he ends up with no item in his inventory. Call cities $(i_{k-1}+1)..i_k$ of term $k$.

If $s$ buys in a city of some term and sells in a city of the same term or a previous term, the buying price is smaller than the selling price.
If $s$ buys in a city of some term and passes in a city of the same term or a previous term, the buying price is smaller than the passing price.
If $s$ passes in a city of some term and sells in a city of the same term or a previous term, the passing price is smaller than the selling price.
Each passing price happens in a city of a different term.
All passing prices form a decreasing sequence.

Proof of the theorem

"best strategy $\Rightarrow$ unimprovable strategy": Suppose strategy $s$ is not unimprovable.

If $h_s(n)>0$, then we can find city $b$, the last city where $s$ buys. Construct $s'$, the strategy that is the same as  $s$ except $s'$ passes in city $b$. Since $h_{s'}(i)=h_s(i)$ if $i\lt b$ and $h_{s'}(i)=h_s(i)-1\ge h_s(n)-1\ge 0$, $s'$ is an admissible strategy. Since $\text{profit}(s')=\text{profit}(s)+p(b)$, $s'$ makes bigger profit than $s$.

If $h_s(n)=0$, then we can find two integers $i,j\in 1..n$ such that $p(i)<p(j)$ such that one of the following two cases happens.

$s(i)=s(j)=0$ or $s(i)<s(j)$. Furthermore, $i<j$.

Let $s'$ be the strategy that is the same as $s$ except that $s'(i)=s(i)+1$ and $s'(j)=s(j)-1$. Since $h_{s'}(t)\ge h_s(t)$ for all $t$, $s'$ is an admissible strategy. We have,
$$\text{profit}(s')-\text{profit}(s)=-p(i)+p(j)\gt0$$
$s(i)=s(j)=0$ or $s(i)>s(j)$. Furthermore, $i<j$ and $(i,j)$ is not $s$-clearance-separated.

Recall that $h_s(t)\ge0$ for all $t$ and, since $(i,j)$ is not $s$-clearance-separated, $h_s(t)\ge1$ for all $t\in i..(j-1)$. Let $s'$ be the strategy that is the same as $s$ except that $s'(i)=s(i)-1$ and $s'(j)=s(j)+1$. Since $h_{s'}(t)= h_s(t)$ for all $t\not\in i..(j-1)$ and $h_{s'}(t)= h_s(t)-1$ for all $t\in i..(j-1)$, $h_{s'}(t)\ge0$ for all $t$. That is, $s'$ is an admissible strategy. We have,
$$\text{profit}(s')-\text{profit}(s)=p(i)-p(j)\gt0$$

So in all cases, we have found an admissible strategy that makes more profit then $s$.

"unimprovable strategy $\Rightarrow$ output of the greedy algorithm": We will use mathematical induction on $n$.

The base case, $n=2$ is easy. In fact, we can extend the whole exposition to include the case when $n=1$, which becomes the obviously-true base case.

Suppose the implication is true for $n$ cities. Now consider the case of $n+1$ cities. Let $w$ be an unimprovable strategy on $1..(n+1)$ for some price function $q$. Since $w(n+1)=h_w(n+1)-h_w(n)=-h_w(n)\le 0$, there are two cases.

$w(n+1)=0$. That means, $h_w(n)=0$. Let $s$ be the restriction of $w$ to $1..n$. Then $s$ is an unimprovable strategy on $1..n$ for the same prices as $q$. Then $s$ is the uniqued strategy produced by the greedy algorithm running up to city $n$. If we continue to run the greedy algorithm at city $n+1$, it must choose to passes in that last city since $w$ is unimprovable. That is, the greedy algorithm will produce $w$.
$w(n+1)=-1$. That means, $n+1$ is a clearance city where $w$ sells. Treating 0 as an clearance city if necessary, let $c$ be the last clearance city before $n+1$. Let $k$ be the city among $(c+1)..n$ where $w$ passes or buys with the highest price. Let $s$ be the strategy on $1..n$ that is the same as $w$ except that $s(k)=w(k)-1$. Then we can verify that $s$ is an unimprovable strategy on $1..n$ for the same prices as $q$. Then $s$ is the unique strategy produced by the algorithm running up to city $n$. If we continue to run the algorithm at city $n+1$, we can verify that it will select to sell in that city as well as change the action in city $k$ from $s(k)$ to $w(k)$.  That is, the greedy algorithm will produce $w$. (There are quite some details left out in this part of the proof. Interested readers may take a look at Exercise 0.)

So, we have shown the implication is also true for $n+1$.

"output of the greedy algorithm $\Rightarrow$ best strategy" Let $s$ be the unique strategy generated by the greedy algorithm. Let $b$ be a best strategy. Then $b$ must be an unimprovable strategy and, then, must also be the unique strategy generated by the greedy algorithm as we just proved.

"unimprovable strategy $\Leftrightarrow$ anatomy of the best strategy". The latter one is basically a careful refinement of the former one into cases.

Beyond this problem

There are multiple variations and possible generalizations. It should be a nice topic for an undergraduate student or a master student to look further into this phenomenon, since this adaptive greedy algorithm does not fit into the framework of matroid or greedoid.

Please leave a comment if anyone wants to collaborate on this topic. Please leave a comment if anyone encounters some literature that looks like applicable, especially in integer linear programming theory or generalized greedoid or submodular functions.

Some exercises and topics

The answers to all the exercises are known. However, topics are much harder, to which I do not claim to know an answer or verify the answer.

Exercise 0. Fill the missing details in the proof of "unimprovable strategy $\Rightarrow$ output of the greedy algorithm". As a hint, "anatomy of the best strategy" may help you get a better understanding of the cities in the last term. (Thanks to user zbh2047, the questioner, who points out a missing case in a previous more-complex formulation of "unimprovable strategy")

Exercise 1. Suppose the prices in different cities can be the same. Then there might be multiple best strategies. Show that the algorithm, after slight modification, is able to find all best strategies.

Exercise 2. By switching buying and selling, describe a greedy algorithm that starts from city $n$, moving backwards. Prove its correctness.

Exercise 3. Suppose he can only either buy an item or sell one item in each city. That is, he cannot do nothing in any city. Describe a greedy algorithm to find the strategy that makes the most profit or, if no profit can be made, make the least loss. Prove its correctness.

Exercise 4. Describe a greedy algorithm that, in each iteration, tries determining the available city of lowest price to buy an item and the corresponding available city with the highest price that is higher than that lowest price to sell an item, staying away from the inadmissible strategies. If it can find the corresponding city, mark both cities as unavailable; otherwise, mark the first city as unavailable. Prove its correctness.

Exercise 5. Can you find a greedy algorithm and prove its correctness in each of the following situations?
(Part a) Suppose he can short items. That is, the number of items hold by him can be as low as $-n$ but not any lower for some positive integer $n$.
(Part b) Suppose for some positive integer $k$, if the number of items held by him is no more than $k$ in the last city, then the total prices of those items will be added to his profit.
(Part c) Suppose he is required to buy in some specified cities and to sell in some other specified cities.

Exercise 6. Show that the best strategy can be verified in linear time of $n$. The characterization theorem on the best strategy tell us that the best strategy only depends on the relative size of the prices. Show that the minimal number of comparisons needed to determine the best strategy for 2, 3, 4, and n cities are 1, 3, 5 and $\Theta(n\log n)$ respectively.

Topic 1. Suppose he can only buy or pass initially until he holds $k$ items for some positive integer $k$. Then he can buy or sell one item or pass as before. (When) is there a greedy algorithm?

Topic 2. Suppose there is a selling cost $t(i)>0$ associated to sell in city $i$ for each $i\in 1..n$. (When) is there a greedy algorithm?

Topic 3. Let $c(n)$ be the minimal number of comparisons needed to sort any $n$ numbers and $z(n)$ be the minimal number of comparisons needed to find a best strategy for any prices in $n$ cities. We know $z(n) \le c(n)$. Is it true that $c(n)=z(n)$ for all $n$?

All above exercises and topics are created by this author except exercise 4 that comes from an answer at Quora


The $k$th letter equals $a$, for fixed $k$, assuming a two letter alphabet.

This generic answer is made precise in the comment by @AntonTrunov below.


Let's say the final goal is to prove $T(n) = \mathcal{O}(n)$. You start with the induction hypothesis:

$T(i) \leq ci$ for all $i < n$.

And to complete the proof, you have to show that $T(n) \leq cn$ as well.

However, what you're able to deduce is $T(n) \leq (c+1)n$, which is not helpful to complete the proof; you need one constant $c$ for (almost) all $n$. Therefore, we cannot conclude anything and $T(n) = \mathcal{O}(n)$ isn't proved.

Notice that you are confused between the result and the proof process. And one more point, $T(n)$ is actually $\Theta(n \log n)$ in this case so you may consider an appropriate induction hypothesis to be able to prove it.


How to find recurrences where Master formula cannot be applied

For the recurrence,
$$
T(n) = T(\sqrt{n}) + 1
$$
Let $n = 2^{2^{k}}$, therefore we can write the recurrence as:

$$
T(2^{2^{k}}) = T(2^{2^{k-1}}) + 1 \\
T(2^{2^{k-1}}) = T(2^{2^{k-2}}) + 1
\\\ldots\\\\\ldots\\
T(2^{2^{k-k}}) = 1
$$

, i.e. $ k * O(1) $ work or linear in $k$. We can express $k$ in terms of $n$:
$$
\log{n} = 2^{k} \\
\log{\log{n}} = k
$$

Hence, the recurrence solves $T(n) = O(\log{\log{n}}) $


It may be helpful to show the motivation for this kind of parallelism.

Compared to other components (such as memory access), computation, especially adding/subtraction, is cheap on chips. It takes very little space, relatively, to add another adder - and of course that adder could be used for address calculations as well as for actual arithmetic.

So more ALUs are easy to add. The problem is how to keep them busy. For instance, if you are calculating A+B+C then you need to work out A+B first and then add C to it. Nothing useful can be done with C until you have worked out A+B. So two ALUs don’t help and one is idle.

There is a lot that a CPU can do in terms of sorting out what calculation depends on what data. If a compiler emits code for “add A to B, store in X, add C to D, store in Y, add X to Y” then the chip itself can work out that the first two adds are independent of each other so can be executed simultaneously by two ALUs (but that the third add depends on the results of the first two).

But in many instruction streams there isn’t enough scope for such parallelism, because of the problem of having to wait for results. This is particularly annoying when memory access is involved because memory today is hundreds of times slower than it was in the 1980s, so there are long periods when everything may be idle waiting for memory data to arrive.

The hyper-threading solution is to run two unrelated instruction streams on the same core at the same time. Since they are unrelated, the data for one never depend on a result from the other, and while one is waiting for memory there is a good chance that the other will not be. The main cost is a doubling of the number of registers (one set of registers per instruction stream) but that is silicon area, not long-distance wiring, so it is cheap.

The threads in a core still share the same memory access mechanism, including the cache, so how well all this works does depend on what the instruction streams are doing. If they are both memory-intensive then they will get in each other’s way.

The term “multithreading” is incorrect for this kind of setup because multithreading means any way of accomplishing a goal by means of multiple threads, irrespective of the actual bits of hardware that execute the threads.


What does every root is at the same level mean

It basically is a typo, every leaf at same level may be the correct words


Example of unrestricted grammar which produces non-context-sensitive language

For posterity.

Start with undecidable Post Correspondence Problem, or PCP:

  Given two lists of words $(u_1,\dots,u_n)$ and $(v_1,\dots,v_n)$ does
  there exist a sequence of indices such that $u_{i_1}\dots u_{i_k} = v_{i_1}\dots v_{i_k}$?

The language will consist of PCP over $\{a,b\}$ that have a solution, coded as string $(u_1;v_1) \dots (u_n;v_n) $ with $u_i,v_i \in \{a,b\}^*$.

The grammar will generate a PCP instance, and non-deterministically an attempt for a solution. Then equality of the two strings is tested by deleting matching letters.

The equality check is more easily done when one of the strings is stored in reverse, so we will generate $u^R_{i_k} \dots u^R_{i_1} X v_{i_1}\dots v_{i_k}$.

Generate an instance of PCP.

$ I \to (W;W) I \mid (W;W) $ (add a pair of words)
$ W \to a W \mid b W \mid \varepsilon $ (generate a word)

Copy one of the pairs of PCP and move it to the pair of words around $X$ that should be equal.

$ D \tau \to \tau D$ for $\tau = a,b,(,),;$
$ D ( \to ( L $  (pair selected)
$ L ; \to ; R $
$ R ) \to ) $
$ L \sigma \to \sigma L_\sigma L $ for $\sigma = a,b$ (make a copy)
$ R \sigma \to \sigma R_\sigma R $ for $\sigma = a,b$
$ L_\sigma \tau = \tau L_\sigma $ for $\sigma = a,b$ and $\tau = a,b,(,),;$ (move right)
$ R_\sigma \tau = \tau R_\sigma $ for $\sigma = a,b$ and $\tau = a,b,(,),;$
$ L_\sigma X \to \sigma X$  (drop copy to the left of $X$, it will
reverse)
$ R_\sigma X  \to X \sigma$  (drop copy to the right of $X$)

Check equality

$ X \to Z $
$ \sigma Z \sigma \to Z$  for $\sigma = a,b$

Start. The $\#$ marks the end of the string, or rather the end of the solution that is generated. The last rule will delete it and at the same time test whether the solution has been completely removed by the earlier rules checking equality.

$ S \to C I X \#$
$ C \to C D \mid D $  for generating the solution, copy several word pairs

Done

$ ) Z \# \to )$

PS. Most constructions for a non-context-sensitive language use diagonalization on context-sensitive grammars to get a language that is still recursive. This one is not recursive, but recursively enumerable.

Indeed many rules are context-sensitive (or rather monotonic/non-contracting). But especially note the rules like $aZa\to Z$: they shorten the string. These are definitely type-0 and not monotonic, and they are essential. After the computation they delete the proposed solution of PCP. Like a scratch tape used by a Turing machine.

PS2. Although the intuitive meaning of each of the productions is explained above, it is not very simple to formally prove the grammar is correct. This is mostly due to the parallellism. There are many nonterminals moving around in the grammar at the same time independently (for instance, when a copy of a PCP pair $(u_i,v_i)$ is made all these letters move in a row to the right; also we can start looking for the next pair to copy even before the last one was finished). This makes it hard to formulate invariants. It takes some time to check that all nonterminals keep in a proper order, for instance. Fortunately none of the moving nonterminals can overtake one another.

For this reason analysing Turing Machines sometimes is less complicated. Only the reading/writing head is moving around.

Example (added by Andremoniy)

Consider simplest case: $(a;a)$. For this string derivation sequence will be:

$S\Rightarrow CIX\Rightarrow D(W;W)X\Rightarrow C(a;a)X\Rightarrow D(a;a)X\Rightarrow (La;a)X\Rightarrow (aL_aL;a)X\Rightarrow (aL_a;Ra)X\Rightarrow (a;L_aRa)X\Rightarrow (a;L_a aR_aR)X\Rightarrow (a;aL_aR_aR)X\Rightarrow (a;aL_aR_a)X\Rightarrow (a;aL_a)R_aX\Rightarrow (a;a)L_aR_aX\Rightarrow (a;a)L_aXa\Rightarrow (a;a)aXa\Rightarrow (a;a)aZa\Rightarrow (a;a)Z\Rightarrow (a;a)$


I know this is old but the previous answer has a huge misconception.

The following function is in System F.

$f = \lambda X. X \rightarrow X \rightarrow X$

All we know of this function is it selects one of its arguments and can be instantieded with any type; $\ f$ [Bool] : Bool $\rightarrow$ Bool $\rightarrow$ Bool.

In System $F_{<:}$ is possible to have the following function.

$f' = \lambda X<:$Number$.\ X \rightarrow X \rightarrow X$

This function can be the addition, multiplication, division, subtraction, etc, and can be instantiated with subtypes of Number.

$f'$ [Int], $\ f'$ [Double], $\ f'$ [Real] are valid instantiations, but $\ f'$ [Bool] not, because Bool is not a subtype of Nat.

Dependent types are a different thing. It has nothing to do here and is out of the scope of the question, but it is a very interesting topic. See Lambda Cube


Detemine if two DFA's are non-disjoint in polynomial time?

You want to know if there is any string accepted by both automata. There are standard techniques for producing an automaton that accepts exactly these strings, and there are standard techniques for seeing if the resulting automaton accepts any strings.


You're almost there.

$((a+b+c)(a+b+c))^∗$ gives you strings of even length.

$((a+b+c)(a+b+c))^∗a$ gives you strings of even length plus an $a$.  That is, odd-length strings that contain at least one $a$ and end with an $a$.

Now, we're told that there are no $b$s after the last $a$. And there are certainly no $a$s after the last $a$, because that's what "last" means! So there can only be $c$s after the last $a$.

So, the answer is going to have to look something like $((a+b+c)(a+b+c))^∗ac^*$. That's not quite right, because it doesn't force the whole string to be even-length and it does force the last $a$ to be in an odd-numbered position in the string (whereas, hint, it should be able to be even or odd).

I'm going to stop there because you showed enough in the question that I think you can finish this yourself, now.


Is there an efficient algorithm for WEAK-PARTITION?

Your problem is NP-complete, as proved by Adi Shamir in his paper On the cryptocomplexity of knapsack systems.


HandyAR finger tip detection and tracking

What does 'successful configuration over time' mean?...  why are there false positives.
I am not able to understand properly how does it handle large movements

they are repeatedly scanning a similar form, the "hand blob", so any outliers from the usual successful input will hopefully be ignored. (maybe if someone nearby passes you something and it thinks their hand is yours for a few frames)

the paper says they register the "hand blob" or centroid of skin color as an easier tracking target for large movements. the "one time calibration" is probably about where your hand is, and it's predominant shade, in relation to the device. then it makes sure the fingers are there and orientates using the thumb. there is no difference to the formula for large movements except where Ci+1 actually is compared to Ci.

I really am looking forward to real time interaction with augmented reality.
are there many more papers you know of like this? id love to read them too.

Edit: hello again raphael.  this is someone of my lvl of understanding and the attempt has been made to fill all of the exceedingly strict criteria for a simple question. this guy is interested, like many are, but has been told off and deleted by you lot before. i can tell.


Based on the book "Algorithm Design" by Kleinberg and Tardos, Kevin Wayne has a set of slides (second part here) where the following applications of max flow and matching are presented in some detail:

survey design
airline scheduling
image segmentation
project selection
baseball elimination
assignment problem
input-queued switching

For even more examples, have a look into the exercises of Chapter 7 of Kleinberg and Tardos' book, or into the exercises of the book "Network Flows: Theory, Algorithms, and Applications" by Ahuja, Magnanti and Orlin.


Maximum Chromatic number of Cayley Graphs with large degree

Erdős and Gallai showed in their paper Solution of a problem of Dirac then the chromatic number of a non-complete regular graph is at most $\frac{3}{5}n$.
Caccetta and Pullman constructed in their paper Regular graphs with prescribed chromatic number connected $k$-chromatic regular graphs on $n$ vertices for all $k > 1$ and $n \geq \frac{5}{3}k$. You can check their construction to see whether it can be adapted to give Cayley graphs.


I am skipping the first question, question A, as it is not clear to me
how it can make sense formally, since I am not familiar with the
formalizations the OP mentions in a comment: Are there established complexity classes with real numbers?

I am only adressing the relation between question A and question B,
proving that question B can be reduced to question A, which the OP considers of interest in itself. And since we are supposed to deal with only one question at a time, this follows the local rules. :)

Question B reduces to question A : B ≤ A

First I will rephrase both questions, so as to add a missing
hypothesis (bijectivity of the function, though existence of an
inverse implies it), and also to use notations that will make the proof
easier to state.

Question A: Let $F$ be a bijective, monotonically increasing real
function from $[0,1]$ onto $[0,1]$. Given an oracle to compute $F$ on
any input and a number $y\in[0,1]$, is there a way to calculate the
inverse function $F^{-1}(y)$ in a finite number of calls to the $F$
oracle?

Question B: Let $H, K$ be two functions like $F$ above, and let $G$ be
their average: $G(x)=[H(x)+K(x)]/2$. Given an oracle to compute
$H^{-1}$ and an oracle to compute $K^{-1}$ and a number $y\in[0,1]$,
is there a way to calculate $G^{-1}(y)$ in a finite number of calls to
the $H$ and $K$ oracles.?

Note: all functions considered are bijective monotonic, but for
readability we leave implicit the related arguments, though they do matter in some of the inferences below.

The idea of the proof is that, if $x=G^{-1}(y)$ is a solution to
problem B, then there are two numbers $h,k\in[0,1]$ such that

$y=(h+k)/2$, and
$h=H(x)$, and $k=K(x)$ for some $x\in [0,1]$

We try to resolve the problem by defining a variable $u\in[0,1]$, so
that $h$ and $k$ are computed from $u$ to take all possible values
while $u$ varies from $0$ to $1$.

From $y=(h+k)/2$ we get $h+k=2y$. So we define: $h_u=2yu$ and
$k_u=2y(1-u)$.
This ensures that $y=(h_u+k_u)/2$, but will let $h_u$ or $k_u$ become greater than $1$ when $y$ is greater than $1/2$.

So, we must actually consider two somewhat similar cases, depending on the value of $y$, after noting that $h_u$ and $k_u$ are both monotonically increasing functions of $u$.

case 1: $y\leq 1/2$

What we want is to find $h$ and $k$ such that $h=H(x)$ and $k=K(x)$
for some value $x$.

We define the function
$D(u)=H^{-1}(h_u)-K^{-1}(k_u)=H^{-1}(2yu)-K^{-1}(2y(1-u))$
Note that $H^{-1}(0)=K^{-1}(0)=0$.
Hence $D(0)=H^{-1}(0)-K^{-1}(2y)=-K^{-1}(2y)$,
and $D(1)=H^{-1}(2y)-K^{-1}(0)=H^{-1}(2y)$.

So the function $D(u)$ is increasing onto $[-K^{-1}(2y),H^{-1}(2y)]$,
and the solution to finding the value of $u$ that corresponds to the
right values of $h$ and $k$ is given by the equation $D(u)=0$.

However, we intend to resolve it using an algorithm to solve
question A, so we must normalize the interval to make it $[0,1]$.

For that we define
$F(u)=\frac{D(u)+K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}$
The function $F$ satisfies the conditions of question A,
and we remark that $D(u)=0$ iff
$F(u)=\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}$.
So we have to compute
$u_0=F^{-1}(\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)})$, which can be
done using the algorithm answering question A.
Then $G^{-1}(y)=H^{-1}(2yu_0)$, or to summarize in one formula:

$$G^{-1}(y)=H^{-1}(2yF^{-1}(\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}))$$

Each computation of $F(u)$ uses only a finite (small) number of calls to the
oracles for $H^{-1}$ and $K^{-1}$. Thus a solution to question B can
be computed with a finite number of oracle calls if that is the case
for problem A.

case 2: $y>1/2$

This case is a bit more complicated, as different bounds must be found
for varying $u$ so that $h$ and $k$ do not get greater than $1$, since
the functions $H$ and $K$ are defined only onto $[0,1]$.

Since $y=(h_u+k_u)/2$, we have $h_u=2y-k_u$. Thus, $k_u\leq 1$ implies
$h_u\geq 2y-1$.

The same reasonning holds, exchanging $h$ and $k$, so that we have
$h_u,k_u\in [2y-1, 1]$. Since $u=h_u/(2y)$, we have $u\in[u_0,u_1]$
with $u_0=1-1/(2y)$ and $u_1=1/(2y)$.

In order to have a variable $v$ varying in $[0,1]$, we normalize by
defining $v=(u-u_0)/(u_1-u_0)$. But
$u_1-u_0=1/(2y)-(1-1/(2y))=(1-y)/y$
which gives $v=(u-u_0)y/(1-y)$.
Hence, with $u=v(1-y)/y+u_0$, $u$ is
a function of $v$ monotonically increasing onto $[u_0,u_1]$ when
$v\in[0,1]$.

Thus, considering $h$ and $k$ as functions of $v$ we have
$h_v=2y(v(1-y)/y+u_0)$ and $k_v=2y(1-(v(1-y)/y+u_0))$, with $u_0=1-1/(2y)$

Simplifying we get $h_v=2y-1+2v(1-y)$ and $k_v=1-2v(1-y)$, for $v\in[0,1]$

From here on the reasonning is the same as for the first case, since monotonically increasing functions are closed under composition, the variable being $v$ rather than $u$, considering the function:
$D(v)=H^{-1}(h_v)-K^{-1}(k_v)=H^{-1}(2y-1+2v(1-y))-K^{-1}(1-2v(1-y))$

I hope that there is no error in symbol manipulations, but the line of reasonning should not be affected if that were the case.

The proof can be simplified by using a lemma that generalizes the question A, which is here a hypothesis, to any strictly increasing function from any closed interval to any other closed interval.


For sufficiently large $M$, the size distribution of hash slots with good uniform hash functions follows a Poisson distribution.

Let $\lambda = \frac{N}{M}$ be the load factor. Then the expected proportion of buckets with exactly $k$ items in it is:

$$P(\hbox{# of items in the bucket is } k) = \frac{e^{-\lambda} \lambda^k}{k!}$$


How do NFA's make program design any better when converted DFA form can't remember original states?

[i]f the above DFA is implemented it surely finds a winning state on a "m"(move),but how does it decide whether it was right or left move?

In the example you gave, it can't. The nondeterministic transition from the start state occurs when a "move" is made. That's all you can possibly know; the machine can't determine whether the winning move was left or right, because those aren't allowed possibilities.


Whenever you are interested in a (well-known) graph invariant, it's a good idea to check out ISGCI first. Have a look at graphs that have bounded chromatic number, or graphs for which computing the number is doable in polynomial time.

To shortly summarize the above, one could highlight perfect graphs (a superclass of chordal graphs), and graphs of bounded treewidth.


Effect of increasing the capacity of an edge in a flow network with known max flow

I am assuming that you are given the flow on each edge which corresponds to the maximum flow for the graph $G$. So $f_e$ is the flow on edge $e$.

I am also assuming that all the capacities and flows values are integral.

Now given this information, capacity of an edge $e$ is increased by 1. Therefore, the mincut value can increase by at most 1 implying that the maxflow can increase by at most 1.

Thus, find the residual graph and check if there is an augmenting path $P$ from $s$ to $t$. If such a $P$ exists, then increase your maxflow by augmenting this path, otherwise the current flow is still the maximum.


How is average precision related to the precision-recall curve?

Let $p(r)$ be the best precision which can be achieved at recall $r$. The average precision is
$$ p_{avg} = \int_0^1 p(r) \, dr. $$
Let $r(p)$ be the best recall which can be achieved at precision $p$. The average recall is
$$ r_{avg} = \int_0^1 r(p) \, dp. $$
Notice that the functions $p(r)$ and $r(p)$ are inverses of one another.

We can express these quantities using the function $\chi(p,r)$, which is 1 if precision $p$ and recall $r$ are achievable at the same time, and 0 otherwise.
We have $p(r) = \int_0^1 \chi(p,r) \, dp$, and so
$$ p_{avg} = \int_0^1 \int_0^1 \chi(p,r) \, dp dr. $$
Similarly, $r(p) = \int_0^1 \chi(p,r) \, dr$, and so
$$ r_{avg} = \int_0^1 \int_0^1 \chi(p,r) \, dr dp. $$
As a consequence, $p_{avg} = r_{avg}$.

Yet another interpretation of this common quantity is the area below the precision–recall curve. It is also the area below the ROC curve.


Why not implement Union-Find structure using root as the direct parent?

Because then a Union operation would be very slow: when you Union two trees, you would have to reparent all of the nodes in one of the trees.


Hint: Associate each edge $e$ with a prime $p_e$, and each vertex $v$ with a number $n_v \in S$. Choose $n_v$ so that the GCD of $\{n_v : v \in A\}$ encodes the set of edges covered by the vertices in $A$.

If you get stuck, try first showing that SubsetLCM is NP-complete. (LCM is Least Common Multiple.)


Geometric median of two disjoint sets of points lies on line between their respective medians

If $A$ and $B$ are two set of points, the geometric median of $A \cup B$ does not necessarily lie on the line passing between the geometric mean of A and the geometric mean of $B$.

In the following example the points of $A$ are red and the one in $B$ is blue. The geometric median of $A$ is the red square. The green line connects the geometric means of $A$ and $B$. The black square is the geometric mean of $A \cup B$, i.e., the Fermat point of the triangle whose vertices are in $A \cup B$.


How to count stores in cache analysis of matrix multiplication

It appears that the analysis assumes that integer variables are stored in registers, whereas array elements have to be loaded from and stored to memory. The point you've missed is that the statemnt X += Y requires reading X and then writing the new value of X.

sum += a[i][k] * b[k][j];

This loads a[i][k], loads b[k][j], multiplies them, reads sum, adds sum and the product and writes the result to sum. Two loads, no stores.

c[i][j] += r * b[k][j];

This loads b[k][j], reads r, multiplies them, loads c[i][j], adds the product to it and stores the new value of c[i][j]. Two loads, one store.

c[i][j] += a[i][k] * r;

This is essentially the same as the previous case.


what is a shearlet/shearlet transform and how can i use it?

Shearlets are a family of basis functions. Cartesian coordinate systems have already made you familiar with orthonormal basis functions: scaling up a rightward- and an upward-pointing unit vector lets you express any (x, y) point in the plane.
Suppose you are Seurat, the pointillist, and you have a budget of 100 brushstrokes with which to express a monochromatic landscape. In addition to (x, y) information we can also give each stroke a radius r, for big blobs or fine dots. This is not too far away from a wavelet representation of the landscape.
Linear features like grass or tree limbs will be a poor fit for such a scheme, requiring many dots. Imagine replacing circles with ellipses of defined aspect ratio and orientation, a and theta, or in your case replacing them with parabolic shapes of defined narrowness and orientation. This is not too far away from a shearlet representation. It uses a shearing transform, rather than an angular rotation transform, as the math works out more conveniently that way. The rubber sheet deformation of shearing expresses the direction of each landscape feature, and resembles rotation. In fact, a sequence of three shears can rotate an image exactly.
For an implementation you should refer to https://github.com/stefanloock/pyshearlab or http://shearlab.org. Quoting the latter:

... shearlet systems are particularly well adapted to represent anisotropic features (such as curves) that are often crucial in multidimensional data. The resulting representation has proven well-suited for image processing tasks such as inpainting, denoising or image separation. ...
Similiar to wavelet systems, shearlet systems are constructed by modifying generator functions. For wavelet systems, these functions are isotropically scaled and translated. While this is enough to provide an optimally sparse representation for an interesting class of 1D functions it fails to do so in higher dimensions. To compensate this shortcoming, the direction of the generator functions has to be varied. In shearlet theory, this is accomplished by shearing and anisotropic scaling.


CLRS: Asked to prove a result and then told to give a counter example

You aren't asked to give a counterexample to the proof, as that would be impossible.

Instead, they're asking for an example where equality does not hold, that is, the left hand side is strictly smaller than the right hand side. That's not a counterexample since the theorem states less or equal.


Why selection sort will require $O(N)$ time

It is simpler and more correct to say: selection sort requires $O(n)$ exchanges (and this is optimal in the worst case).

That doesn't imply $O(n)$ time, unless the other operations take negligible time.
But from a theoretical standpoint, $O(n^2)$ is never negligible compared to $O(n)$.

In practice if a comparisons and related overhead takes $s$ seconds and an exchange and related overhead takes $e$ seconds, the total time will be

$$\frac{sn^2}2+cn=\left(\frac{sn}2+c\right)n.$$

This can be considered a linear behavior as long as $sn\ll c$. That could be true if the records are stored on a slow disk while the keys are cached in RAM.

This course plays a dangerous game with the Big-$O$ notation.


Calculate the average length of the linked lists in a hash table

since the hash is constructed such that the input element has an equal chance to be in any of the bins of the hash table, then the average number will be (number of imputed elements) / (size of the hash table)


How to find a function in Lambda Calculus?

In your attempt,

$$map=(\lambda a \lambda b (\lambda s \lambda d((b(st))d)))$$

$a$ plays the role of $l$, $b$ the role of $t$, $s$ the role of $k$, and $d$ the role of $x$.

So, $b(st)d$ should actually play the role of $l(kt)x$, but here we see some mismatch: $b$ does not represent $l$, $a$ does that. Also, we can not use $t$, but must use $b$ instead.

Hence, the correct answer seems to be $a(sb)d$. We get (using the standard notational shortcuts)

$$map=(\lambda a b s d.\, a(sb)d)$$

Try to check whether $map\, l\, t$ does $\beta$ convert to the intended term.

Your original idea, namely using $kt$ instead of $k$, seems to be the right intuition, as far as I can see.


It just means that you can create levels or puzzles within these games that encode NP-Hard problems. You can take a graph coloring problem, create an associated Super Mario Bros. level, and that level is beatable if and only if the graph is 3-colorable.

If you want to see the specific way the NP-Complete problems are translated into the games, I recommend the paper "Classic Nintendo Games are (Computationally) Hard". It's well written and easy to follow.

An important caveat to keep in mind is that the NP-hardness requires generalizing the games in "obvious" ways. For example, Tetris normally has a fixed size board but the hardness proof requires the game to allow arbitrarily large boards. Another example is off-screen enemies in Super Mario Bros: the proof is for a variant of the game where off-screen enemies continue moving as if they were onscreen, instead of ceasing to exist and being reset to their starting position when Mario comes back.


Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?

I recommend you to check Scott Aaronson's blog post on a proof of the Incompleteness Theorem via Turing machines and Rosser's Theorem. His proof of the incompleteness theorem is extremely simple and easy to follow.


CFG and PDA for the set of strings in $\{a, b, c\}^∗$ such that the number of b’s is equal to the sum of number of a’s and c’s

For the PDA, I think you use the stack to track the number of A plus the number of C minus the number of B seen so far, using both positive and negative tokens:

If the stack is empty and you see an A or a C, you push a "+1" token.
If the stack is empty and you see a B, you push a "-1" token.
If the stack is not empty and you see the kind of token that's already on there (e.g. you have a +1 token and you see an A or a C), then you push another of the same token.
If the stack is not empty and you see the wrong kind of token (e.g. there's a "-1" token on the stack and you see an A or a C), you pop one token.

Depending on your formalisation of PDA you may want to start off by pushing a "zero" token in order to check whether the stack is "logically empty" or not.
The stack keeps the invariant that there can never be both a "+1" and a "-1" token on it at the same time.
The word is in the language if and only if the stack is (logically) empty at the end of the string.


In case someone else needs this in the future

I ended up using indicator constraints

$desiredOverlap_{ik} = 1 \rightarrow desiredEnd_{ik} - desiredStart_{ik} \geq 0$
$desiredOverlap_{ik} = 1 \rightarrow desiredDuration_{ik} = desiredEnd_{ik} - desiredStart_{ik}$
$desiredOverlap_{ik} = 0 \rightarrow desiredEnd_{ik} - desiredStart_{ik} \leq 0$
$desiredOverlap_{ik} = 0 \rightarrow desiredDuration_{ik} = 0$


How can we prove that in binary search, low – high ≤ 1

Let's denote the indices by $l,h,m$. If $l \leq h$ and $h-l$ is even then $m = \frac{l+h}{2}$ and so in the following iteration, the new values $l',h'$ will either be $\frac{l+h}{2}+1,h$ or $l,\frac{l+h}{2}-1$. In the first case
$$
l'-h' = \frac{l-h}{2}+1 \leq 1,
$$
and in the second case
$$
l'-h' = \frac{l-h}{2}+1 \leq 1.
$$
If $l \leq h$ and $h-l$ is odd then $m=\frac{l+h-1}{2}$ and so either $l',h' = \frac{l+h+1}{2},h$ or $l',h' = l,\frac{l+h-3}{2}$. In the first case
$$
l' - h' = \frac{l-h+1}{2} \leq \frac{1}{2}
$$
and so $l'-h' \leq 0$, since $l'-h'$ is an integer. In the second case
$$
l' - h' = \frac{l-h+3}{2} \leq \frac{3}{2},
$$
and so $l'-h' \leq 1$, since $l'-h'$ is an integer.
Put together, we have shown:

If $l \leq h$ then $l'-h' \leq 1$.

Now let's use it to show that $l-h \leq 1$ always holds.
We first prove by induction on $t$ that if the loop executes at least $t$ times, then after $t$ iterations of the loop, $l-h \leq 1$. The base case $t = 0$ is by assumption. Now suppose that after $t$ iterations, we have $l-h \leq 1$. If $l > h$ then the loop terminates, and so there is nothing to prove. Otherwise, $l \leq h$, and so $l-h \leq 1$ at the end of the iteration, as shown above.
This shows that when the loop terminates (if it terminates — which has to be shown separately), $l-h \leq 1$ necessarily holds. In fact, we can say more: since the loop terminated, we must have $l > h$, and so $l-h = 1$.


1. FCFS

Turnaround Time T T = 5.866 is correct.

2. Non-PreEmptive SJF

T T = 5.2 is correct.

3. Future-Knowledge (Non-PreEmptive SJF with Idle time)

T T = 6.2, I'm not sure about this.

We never get a future knowledge of how big the next process will be.

4. PreEmptive SJF (SRTF)

Here, your scheduling is wrong.

$P_2$ arrives at time 1.4, how can you schedule it at time 0.4?

Refer below scheduling:

\begin{array} {|r|r|}
\hline
P_1 &P_2 &P_3 &P_2 &P_1 \\
\hline
0-1.4 &1.4-3 &3-4 &4-5.4 &5.4-9 \\
\hline
\end{array}

T T ($P_1$) = 9 - 0=9
T T ($P_1$) = 5.4 - 1.4=4
T T ($P_1$) = 4 - 3 =1
Avg T T = 4.6

Dont you see the improved TT of one over other.

FCFS = 5.8 > NON-PRE SJF = 5.2 > PRE SJF =4.6


Closure of regular languages are closed under certain cut operations

Take a DFA $\langle Q,q_0,F,\delta \rangle$ for $L$. For every state $q \in Q$, it is known that
$$
N_q = \{ n : \delta(q,x) \in F \text{ for some $|x|=n$} \}
$$
is an eventually periodic set. In these terms, we have
$$
f(L) = \bigcup_{q \in Q} \{ w : \delta(q_0,w) = q \text{ and } |w|+f(|w|) \in N_q\}.
$$
A few simple arguments show that $f$ is admissible (the set of regular languages is closed under $f$) if for every modulus $m$, there is a DFA $\langle Q',q'_0,\delta' \rangle$ over the alphabet $\{0\}$ which "computes" $|w|+f(|w|) \bmod m$, in the sense that on input $0^n$, you can recover $n+f(n) \bmod{m}$ from $\delta'(q'_0,0^n)$. This, in turn, happens if for every modulus $m$, the function mapping $n$ to $n+f(n) \bmod{m}$ is eventually periodic. Since $n \bmod{m}$ itself is periodic, we conclude that:

  A function $f$ is admissible iff for all $m$, the function $\psi_{f,m}(n) = f(n) \bmod{m}$ is eventually periodic.

The Chinese Remainder Theorem shows that it suffices to consider values of $m$ which are prime powers.

All polynomials are clearly admissible: if $f$ is a polynomial, then $\psi_{f,m}$ has period $m$. Exponential functions $a^n$ are also admissible: if $m=p^k$, then either $p \mid a$, in which case $\psi_{f,m}$ is eventually zero, or $(p,a)=1$, in which case Euler's formula shows that $\psi_{f,m}$ has period $\varphi(m)$.

I'm not sure if the set of admissible functions can be characterized any further – this is an interesting research direction.


Particular techniques for NP-complete problems

For such a broad technique as dynamic programming, the answer is almost certainly no. Suppose somebody proves that P = NP (and we don't know that they can't) by giving a polynomial-time algorithm for 3SAT. Surely, that algorithm could be rewritten as some kind of trivial dynamic programming, since pretty much any for loop can be written as dynamic programming.  For example,

total=0
for i=1 to n do
    total = total + data[i]
print total

can be rewritten as

total[n] = data[n]
for i=n-1 downto 1 do
    total[i] = total[i+1] + data[i]
print total[1]

However, one result that is in the spirit of a "yes" answer to the question is in Mihalis Yannakakis's paper "Expressing combinatorial optimization problems by Linear Programs" (Journal of Computer and System Sciences, 43(3):441-466, 1991; DOI, free PDF). This shows that any symmetric linear program for TSP must have exponential size – a linear program is symmetric if, whenever you permute the main variables, you can permute the auxiliary variables to get back the original program. Yannakakis's paper was, as I understand it, written because Ted Swart had been trying to use linear programming to solve Hamiltonian cycle in P and couldn't quite get the very large ($n^8$ to $n^{10}$ variables) linear programs to work.


How does the CPU receive, process and output information?

From what I know, and I might be slightly wrong here,
each device (Mouse, keyboard, screen etc') has a device driver.

The device driver is the one handling the communications with the CPU.
Where usually, each device has its own Data register, Status register and Command register (Where the register are basically mapped areas in memory for the device itself).

What happens is when any action is made (i.e pressing a key on the keyboard) the device "updates its status" to ready to send and stores the data it needs to send in some area of memory specifically saved for it, and then interrupts the CPU to perform the action needed.

The CPU sends "Ack" as acknowledgement and accepts the interrupt, executes it, and goes back to what it did before. (Only if the status is ready, otherwise does nothing).

(There are other methods such as busy wait that the device can notify and interact with the CPU).


From your question I assume you understand how symmetries are computed. As an exercise, make sure to understand the example given in Figure 4 which refers to the easiest of all symmetries, the Mirror (also known as Diagonal) denoted as $D$. In the following I will refer to this symmetry only unless otherwise noted.

Next, hope you also understand that symmetries create isomorphic puzzles so that the number of moves necessary to optimally solve the reflected state is precisely the same number of moves (but different) necessary to optimally solve the original state ---see Figure 3 in the paper for a good example of a path reflection which results from applying $D$.

Hence, when computing the heuristic estimate of any state $p$, compute its symmetrical state $p'$ (in time linear in the size of the puzzle), and look up the Pattern Database for both states $p$ and $p'$. Since Pattern Databases are indeed homomorphisms let $\rho$ denote such mapping ---i.e., what tiles are mapped to themselves and what tiles are replaced by the don't care symbol. Thus, you can safely take the maximum of both values returned from the PDB:

$h(p)=\max\{V(\rho(p)), V(\rho(p'))\}$

where $V(n)$ denotes the value stored in the PDB for the abstracted state $n$ which consists of tiles and don't care symbols. The two values within brackets are indeed those mentioned at the beginning of Section 4.3.

Note the importance of the blank tile: The other symmetries H, V and D' do not preserve its location and therefore Section 4.2 proposes to use some corrections (3, 3, and 6 respectively) to both the lower and upper bounds.

Of all these symmetries, the most widely used are $D$ and $D'$. Other works (among many others) exploiting them are given below:

Richard E. Korf, Ariel Felner. Disjoint Pattern Database Heuristics. Artificial Intelligence, 134, pp. 9--22, 2002

Ariel Felner, Richard Korf, S. Hannan. Additive Pattern Database Heuristics. Journal of Artificial Intelligence Research, 22, pp. 279--318, 2004.

Uzi Zahavi, Ariel Felner, Robert C. Holte, Jonathan Schaeffer, Duality in Permutation State Spaces and the Dual Search Algorithm, Artificial Intelligence, 172 (4--5), pp. 514--540, 2008

To finish, let me reproduce here a paragraph from the last paper:

  Because all valid, alternative PDB lookups provide lower bounds on the
  distance from state $S$ to $G$, their maximum can be taken as the
  value for $h(S)$. Of course, there is a tradeoff for doing this
  ---each PDB lookup increases the time it takes to compute $h(S)$. Because additional lookups provide diminishing returns in terms of the
  reduction in the number of nodes generated, it is not always best to
  use all possible PDB lookups.

Hope this helps,


Average Time Complexity of Searching An Array

It sounds like you're talking about a linear search.  If we assume that the key is equally likely to be in any of the $n$ locations in the array, then the expected location is $\frac{n+1}{2}$.  A linear search for this element would then require $O(\frac{n+1}{2}) = O(n)$ time.


Here are two ideas. It's hard to say whether they're any good - you'll have to implement them.

Use (randomized or deterministic) QuickSelect in order to find the median, and then find the bottom half with a single scan.
Use some hard-coded sorting network, e.g. Batcher, bitonic or pairwise. If there is some hardware support for the basic operation of sorting two memory cells, then this can be pretty fast (even though you're not using parallelism). You can also try to come up with your own sorting network that only sorts in your sense - perhaps trimming one of the ones I listed would do.


What is the origin of using Q to denote a set of states in an automaton?

The symbol $q$ to denote the state of a finite automaton appears (for the first time??) in Moore's 1956 paper Gedanken-Experiments on Sequential Machines and since the paper became very popular, I suppose that Moore's notation has been adopted since then. Apparently, Moore didn't use any special notation for the set of states, but it you adopt $q$ for a state, $Q$ seems to be an obvious choice for the set of states.

I don't think there is any special meaning for the letter $q$ (or $Q$).

[1] E.F. Moore, Gedanken experiments on sequential machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, 129–156. Princeton University Press, 1956.


Prove regular languages are closed under f(n) = 2^n and f(n) = n^2

For $f(n)=2^n$:

Let $M=(Q,\Sigma,\delta,q_0,F)$ be the DFA recognizing $R$. Denote by $\mathcal{G}$ the set of functions from $Q$ to $\mathcal{P}(Q)$ (where $\mathcal{P}(Q)$ means the power set of $Q$), and for any $g,h\in\mathcal{G}$, denote by $gh$ the function defined as $$gh(\cdot)=\bigcup_{q\in h(\cdot)}g(q).$$

Construct a new DFA $M'$ of whose states each is labeled a pair $(q,g)\in Q\times\mathcal{G}$. The transition function $\delta'$ of $M'$ is defined as

$$\delta'((q,g),a)=\left(\delta(q,a),gg\right),$$

for all $q\in Q, g\in\mathcal{G}, a\in\Sigma$. The start state of $M'$ is $(q_0,g_0)$ where $g_0$ is defined as $g_0(\cdot)=\{\delta(\cdot,a)\mid a\in \Sigma\}$. The set of accept states of $M'$ is $\{(q,g)\in Q\times\mathcal{G}\mid g(q)\cap F \neq \emptyset\}$.

Now we claim that

  After reading a word $w$, if $M$ reaches state $q$, then $M'$ reaches the state $(q,g)$, where $g(\cdot)$ represents the set of states $M$ can potentially reach when starting at state $\cdot$ then reading a word of length $f(|w|)$.

This cliam can be proven by mathematical induction on $|w|$. With this claim, we can see $M'$ indeed recognizes $f(R)$.

For $f(n)=n^2$, the proof is similar. In this case, each state of $M'$ is labeled a tuple $(q,g_1,g_2)\in Q\times \mathcal{G}^2$, the transition function becomes

$$\delta'((q,g_1,g_2),a)=\left(\delta(q,a),g_1g_0,((g_2g_1)g_1)g_0\right),$$

where $g_0(\cdot)=\{\delta(\cdot,a)\mid a\in \Sigma\}$ as above, the start stae becomes $(q_0,I,I)$ where $I(\cdot)=\{\cdot\}$, and the set of accept states becomes $\{(q,g_1,g_2)\in Q\times\mathcal{G}\mid g_2(q)\cap F \neq \emptyset\}$.

Also, our claim becomes

  After reading a word $w$, if $M$ reaches state $q$, then $M'$ reaches the state $(q,g_1,g_2)$, where $g_1(\cdot),g_2(\cdot)$ respectively represent the set of states $M$ can potentially reach when starting at state $\cdot$ then reading a word of length $|w|,|w|^2$.


Paint the balls: what patterns can be painted?

Every pattern with a run of length $\ell$ is feasible. Indeed, consider first that the last run has length at least $\ell$. We go over the string from left to right, and for each $i$, we paint balls $i,i+1,\ldots,i+\ell-1$ with the required color for position $i$. After going over all possible indices (i.e., all but the last $\ell-1$), we have painted the pattern.

Now suppose that there is such a run in the middle, say $r,\ldots,s$. We run the algorithm above up to position $r-1$, and the we run a similar algorithm going from left to right, until ball $r$ is painted. We have painted the pattern.

As for the optimal number of moves, one natural algorithm to consider is the algorithm described above, with a simple optimization: when attempting to paint the $i$th ball, if it is already of the correct color, then don't bother. I conjecture that this algorithm, or some simple variant of it, is indeed optimal.


The T-diagrams (which you had omitted from the original version of your question) are crucial for understanding this sort of question. Let's look at the last T-diagram.

The first T describes a compiler from L to N written in S.

The second T describes a compiler from S to M written in M (or running on M). This will be your compiler compiler.

Applying the second T to the first T compiles the first T so that it runs on machine M. The result is thus a compiler from L to N running on machine M.

The fact that the second T also runs on machine M is captures that you are running the compiler compiler on the machine which you will run the compiler, rather than having to use a cross compiler (which would be the case if the bottom M were different).


Why do compute time complexity for algorithms?

The problem you are describing is indeed a shortcoming of asymptotic notation. Asymptotic notation has several advantages:

It doesn't depend as much on the underlying computation model. For example, the microprocessor executing the compiled code shouldn't affect the running time by more than a constant.
It avoids cumbersome exact results, for example instead of $n^2 + 3.5n\log n + 700\log n\lfloor \log\log n \rfloor$ we can write simply $O(n^2)$ (or even $\Theta(n^2)$).
In many cases it is hard to analyze exactly the running time (even ignoring the first issue), but easy to come up with asymptotics. Standard examples are recursive algorithms. In those case, however, it is often possible to come up with first-order estimates, that is, perhaps we can say that the running time satisfies $T(n) \sim 2n^2$, which is more accurate than $T(n) = \Theta(n^2)$.
Practically speaking, in many cases the constants hidden by the big O notation are "small" or at least "reasonable", and therefore for $n$ which is not too small, a $\Theta(n)$ algorithm will usually be faster than a $\Theta(n^2)$ algorithm.
Big O estimates function as ball park heuristics, which allow us to guess which algorithm is better or which part of an algorithm needs optimization the most. If in doubt, however, it is better to use profiling.

On the other hand, in some cases the problem you're indicating is serious. A classical case is fast matrix multiplication, where the trivial $O(n^3)$ algorithm often beats Strassen's $O(n^{\log_2 7})$, and always beats all other algorithms (which have better asymptotic running time).

Summarizing, there is no easy answer. Asymptotic notation is a good model of reality in many cases, but not always. Still, it is useful since it is concise and allows quick comparison between different algorithms.


Let $k=2009$ and $L = \{w : |u_a| \ge k\cdot |u_b|$}. I think it is easier to prove using Myhill-Neorde's Theorem.
Consider the strings $a^k, a^{2k}, a^{3k} \ldots$, we claim that all of these have a $L$-distinguishable suffix. Consider $a^{lk}$ and $a^{mk}$ with $l < m$. Let $x = b^m$. We have $a^{lk}b^m \notin L$ but  $a^{mk}b^m \in L$ (Why?). Therefore, there are infinitely many $L$-equivalence classes, which proves that, by Myhill-Nerode's theorem, that $L$ is non-regular.

Your argument is almost correct:
Assume, for the sake of contradiction, that $L$ is regular. Therefore, by closure property of regular languages, $L' = L(a^*b^*) \cap L$ will also be regular. Notice that all the words in $L'$ will be of the form $a^{n_1}b^{n_2}$ s.t. $n_1 \ge kn_2$.
Now, consider a word $w = a^{kn}b^{n}$ in $L'$. Using pumping lemma, for a sufficiently large $n$, there should exist a partition of this string $w = xvy$ such that $v \ne \epsilon$. Now, three case arises:

If $v$ lies in the part $a^{kn}$: pumping down will lead to a contradiction
If $v$ overlaps both the $a$'s and $b$'s parts: $v$ should be of the form $a^{m_1}b^{m_2}$. Pumping up will result in a string of the form $a^{kn}b^{m_2}a^{m_2}b^{m_2 + n}$, which doesn't belong to $L'$ (why?)
If $v$ lies in the part $b^n$: pumping up will lead to a contradiction


Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'?

Here the explanation for the numbers we found in the comments, which unfortunately do not match yours. If you have additional explanations I can delete this answer, or perhaps improve.

Goal: given $a$ students, make $b$ groups, each consisting of $c$ persons, $bc \le a$. What is the number of possibilities?

My assumptions, the groups are unordered, so $(1,2,3)$ is the same group as $(3,1,2)$. Also the solution $(1,2)(3,4)$ is equal to $(3,4)(1,2)$

Put your students in a row: $a!$ possibilities. The first $b$ students form the first group, the next $b$ students the second group, etc. The order in the line-up between each group of students does not matter, so we have to divide by th1s number of possibilities which is $(c!)^b$. Again we divide by $(a-bc)!$ the number of permutations of the not chosen ones. Also, the order of the groups themselves does not matter, we additionally divide by $b!$.

Answer: $a!\;/\;{(c!)^b (a-bc)! \;b!}$

Another way of obtaining the same number. Choose a group of $c$ students from total $a$, then a group of $c$ students from the remaining $c-b$, etc. This can be done in ${a \choose c}{a-c\choose c}\dots{a-c(b-1)\choose c}$. Again I divide by the possible orderings of the groups which is $b!$.
Thus $\frac{a!}{c!(a-c)!}\frac{(a-c)!}{c!(a-2c)!}\dots \frac{(a-(b-1)c)!}{c!(a-bc)!} / b!$

Your first example $a=12$, $b=4$, $c=3$. You have 880, this number is 15400.

Second example  $a=12$, $b=3$, $c=2$. 13680, we agree.


If $$\limsup_{n \rightarrow \infty} \frac{g(n)}{f(n)} < \infty,$$ then we have that $g(n)$ is $O(f(n))$.

That is actually (almost) the definition of the big-O notation (modulo the $| \cdot |$ function that I left out for readability). You would prove that using your math knowledge. Note that if you can show that $$\lim_{n \rightarrow \infty} \frac{g(n)}{f(n)} < \infty,$$ for strictly increasing positive functions $g$ and $f$, this implies the satisfaction of the first equation. Analyzing the latter function should be part of most computer science curricula.


Preprocess an array for counting an element in a slice (reduction to RMQ?)

Since $k$ is constant, we can store the count of each element in the range $0..m$  for $0\leq m \lt n$ in $0..n$ in $O(nk) = O(n)$ time and space. The primary observation is that you can make a two-dimensional array count[pos][elem] = occurences of 'elem' in the indices 0..pos in $O(nk)$ time, then query ranges by finding the difference in $i,j$ indices in constant time.

Preprocessing

initialise count[pos][elem] to 0 for all elem, pos
for pos=0 to n
  for num=0 to k
      count[pos][num] = (0 if pos==0 else count[pos-1][num])
  count[pos][arr[pos]] ++

Query

(assumes i,j are both inclusive bounds)

if i == 0
  return count[j][m]
else
  return count[j][m] - count[i-1][m]

If the array is also getting updated throughout the query process, you can use $k$ Fenwick (binary index) trees in place of the count array. This lets you update in $O(\log n)$ and query in $O(\log n)$.

Apologies for any issues with this answer, it's my first.


Your problem is in polynomial time, as the following claim implies.

Claim Let $A$ be an $m\times n$ matrix with rational entries. There exists an integer $x > 0$ such that $Ax \geq 0$ if and only if there exists a real $x > 0$ such that $Ax \geq 0$.

Proof The forward implication is trivial. For the backward implication, suppose that there exists a real $x > 0$ such that $Ax \geq 0$. In particular, the polytope $P = \{ x \geq 0 : Ax \geq 0 \text{ and } \sum x = 1 \}$ is non-empty. Pick some vertex $x$ of $P$. Since all entries of $A$ are rational, all coordinates of $x$ are also rational. Therefore for some integer $N>0$, all entries of $Nx$ are integral. Furthermore $Nx > 0$ and $A(Nx) = N(Ax) \geq 0$. $\square$

Given a matrix $A$, in order to determine whether there exists a real $x > 0$ such that $Ax \geq 0$, check whether the polytope $P = \{ x \geq 0 : Ax \geq 0 \text{ and } \sum x = 1 \}$ is non-empty using linear programming. This can be done in polynomial time.


We can understand it as set $\{2^{f(n)}: f \in O(n)\}$.
For example any $n^k,k>0$, will be in $2^{O(n)}$: $n^k=2^{k\log_2 n}$ and  we have $\log_2 n \in O(n)$.
Note: I especially not write $k \cdot \log_2 n \in O(n)$, because multiplication on positive constant has no influence.


Find disjoint contiguous sub-arrays in better than $\mathcal O(n^2)$

This is a complete re-edit of my previous solution, which erroneously focused on partitions, not on arbitrary sub-arrays.

This problem seems to be an interesting variation on the Maximum subarray problem, which consists of finding the subsequence of values with the largest sum in an array.

Given an array a of integers, finding the maximum subarray can be done as follows:

int best_left = 0, best_right = -1, best_sum = INT_MIN;
int i, curr_left = 0, curr_sum = 0;
for ( i = 0 ; i < N ; i++ ) {
    curr_sum += a[i];
    if ( curr_sum < a[curr_left] ) {
        curr_sum = 0;
        curr_left = i+1;
        }
    else if ( curr_sum > best_sum ) {
        best_left = curr_left;
        best_right = i;
        best_sum = curr_sum;
        }
    }

The above code is untested. The largest summing interval should then be [best_left,best_right].

To solve your problem, you could sweep from left to right and store the values best_left and best_sum for each position i in the array, effectively giving you the largest sub-array from 0 to i for each i.

At the same time, you could flip the signs in the above code and also store the minimum subarray from 0 to i for each i.

Now imagine doing the same thing again, yet this time traversing the array backwards, from right to left, also storing the minimum and maximum subarrays as you go along.

Once you've constructed both sets of indices, you can traverse them and find the point which partitions the array such that the difference between the minimum/maximum subarray on either side is largest.


Misunderstanding the Church-Rosser property

If $x$ and $y$ are such that $x \leftrightarrow^* y$, then $x \rightarrow^* y$

This is not true in general. It is not even true if $\rightarrow$ is confluent!

For example, consider the lambda calculus with for $\beta$ reduction. $(\lambda x. x) y \rightarrow y$, therefore $(\lambda x. x) y \leftrightarrow^* y$, but it is not the case that $y \rightarrow^* (\lambda x. x) y$ ($y$ does not reduce to any term).

The statement $x \leftrightarrow^* y$ means that there exists a chain of reductions $x \leftarrow \rightarrow \leftarrow \leftarrow \leftarrow \rightarrow \ldots \rightarrow \leftarrow \leftarrow y$, indiscriminately mixing “reduces to” and “reduced from”. This is a lot coarser than the statement that $x$ and $y$ converge, which is usually written $x \rightarrow^* \leftarrow^* y$. A relation is Church-Rosser if for all $x$ and $y$ such that $x \leftrightarrow^* y$, it is the case that $x \rightarrow^* \leftarrow^*$. Church-Rosser means that whenever there is a chain of reductions in arbitrary directions, then there exists another chain of reductions where all the $\rightarrow$ arrows are to the left of all the  $\leftarrow$ arrows.

  it just seems to me that the reflexive transitive closure of any relation trivially has the C-R property

No. Taking the reflexive transitive closure doesn't help Church-Rosser along. Church-Rosser is in fact a property of the reflexive closure of a relation (if two relations have the same reflexive closure, then one is CR iff the other is) — you can see in the definition that arrows in the same direction are always taken in a group.

For example, a partial order is not in general confluent. Confluence, for a partial order, is the existence of a least upper bound.


Why doesn't parallelism necessarily imply non-determinism?

The book is using the term non-deterministic in two different ways.  In concurrent computations and parallel computations the order in which the computations occur is non-deterministic.  The final result however may (or may not) be deterministic.

Consider the following example:

thread A        thread B
--------        --------
x = 0           y = 1

The x assignment might happen before the y assignment, or the y assignment might happen before the x assignment, so the order is non-deterministic, but the end result after both threads finish is that x contains the value 0 and y contains the value 1.  So the result is deterministic.

The two major ways in which we achieve deterministic results from non-deterministic ordering is (a) by performing completely independent computations in different threads and (b) by taking advantage of operations that are commutative and/or associative.  An example of case (b) is if you have an atomic addition operator:

thread A               thread B
--------               --------
atomic_increment(x)    atomic_increment(x)

At the end of the computation x will have a value 2 larger than it had before the computation, no matter whether thread A's increment happened before thread B's increment, or the other way around.


Sorting "almost sorted" array in $O(n\log\log n)$

Suppose that $A$ is an array with $m$ indices satisfying $A[i] > A[i+1]$. You can find these indices in $O(n)$. These $m$ indices split $A$ into $m+1$ nondecreasing arrays $B_1,\ldots,B_{m+1}$ of total length $n$. We now merge them according to the following strategy: at each step, take the two shortest arrays, and merge them. You can implement the choice mechanism in $O(m\log m) = O(n\log m)$ using a heap.

When merging two arrays of length $a,b$, the running time is $O(a+b)$. Hence we would like to understand the total sum $S$ of $a+b$, where $(a,b)$ goes over all $m$ pairs of arrays being merged. To this end, we consider a merge tree, which is formed in the following way. We start with $m+1$ vertices corresponding to $B_1,\ldots,B_{m+1}$. When two arrays corresponding to vertices $x,y$ are merged, we create a new vertex with $x,y$ its only children. You can check that
$$
S = \sum_{i=1}^{m+1} |B_i| \mathrm{depth}(B_i).
$$
Consider now a probability distribution $X$ on $[m+1]$ with $\Pr[X=i] = |B_i|/n$. Then $S/n$ is the average codeword length of an optimal prefix code for $X$ (this is because we're essentially running Huffman's algorithm). Therefore $S/n < \log m + 1$, showing that the merging steps take $O(n\log m)$ time in total.

Summarizing, the algorithm runs in time $O(n\log m)$.

(Strictly speaking, to handle the cases $m=1$ and $m=0$, we should replace $m$ with $m+2$.)


Are all pseudo-random number generators ultimately periodic?

All pseudorandom generators that don't rely on outside randomness and use a bounded amount of memory are necessarily ultimately periodic since they have finite state. You can think of them as huge deterministic finite automata which have special "output" states in which they give their output. All finite automata are eventually periodic, and so all pseudorandom generators produce eventually periodic output.

However, the period length can be enormous. For example, a PRNG with a cryptographic state of 128 bits might only cycle once every $2^{128}$ bits of output, and so even if outputting one bit every nanosecond, the solar system will be dead ere the PRNG repeats.

If the PRNG is allowed to use an unbounded amount of memory (which isn't realistic) then it can, for example, output the binary expansion of $\sqrt{2}$, which we know isn't eventually periodic (since $\sqrt{2}$ is irrational).


Maximum variance and useful information of dataset

I'll answer this, even thought the question is not well defined and would possibly be better suited for cross validated. But since it has some connection to information it's not totally off topic here.

Short version: Now, we can't apply that to any data set. Variance alone is not a good measure of information. PCA chooses the components with the highest eigenvalue, because they explain the input variance (i.e. euclidean distance from the origin). That's why you should normalize your input, if you don't want to emphasize a certain input component.

Long version:

Let's say you have two random variables $X$ and $Y:=10X$ where $E(X)=E(Y)=0$, $\mathrm{Var}(X)=1$ and thus $\mathrm{Var}(Y) = 100$. Now assume a third variable $K$ uniformly distributed among $\{1,\dots,k\}$ (this models drawing a random individual form your sample).

The variance before the PCA is not a sufficient measure for information, e.g. if we use $X$ and $Y$ to distinguish the individuals:
$$P(K=k|X=x) = P(K=k|Y=10x)$$

The covariance matrix looks like this:
$$\left(\matrix{1&10\\10 & 100}\right)$$

Using R's "eigen" we get:

$values
[1] 101   0

$vectors
           [,1]        [,2]
[1,] 0.09950372 -0.99503719
[2,] 0.99503719  0.09950372

If we now transform $X$ and $Y$ to $X'=M_{11}\cdot X + M_{21}\cdot Y$ and $Y'=M_{12}\cdot X + M_{22}\cdot Y$ (where $M$ is "vectors" from $R$), $X'$ contains "all the information":
$$\forall y\;:P(K=k|X'=x) \neq P(K=k|Y'=y)=P(K=k)$$

But, of course, again $X''=10^{-100}\cdot X'$ contains "the same information".


Regular Language $a^n b^m c^k$ to Context free grammar

Let us get things straight...the language $L$ is not regular (you can check using Pumping lemma) Although the language is Context Free as it is the union of two CFLs.

The grammar does not correspond to the language since the non-terminal $B$ can not be terminated. So  only way to termiante it and get a word of the language is $S=A^*$. But $A=aAb=aAcb=aabcb\notin L$

Correct grammar should be

$$S\to A|B$$
$$A\to Ac|aAb|\lambda$$
$$B\to aB|bBc|Bc|\lambda$$

Two non terminals $A$ and $B$ for the two CFLs whose union is $L$.


I think I see where your confusion arises. Hopefully ;).

Suppose you have a problem $\Pi \in NP$, and two algorithms $\mathcal{A}$ and $\mathcal{B}$ that both solve $\Pi$.

Assume that $\mathcal{A}$ uses algorithm $\mathcal{A'}$ as a sub-algorithm, where $\mathcal{A'}$ is acutally an algorithm for a $PSPACE$-complete problem.

Also assume that $\mathcal{B}$ is the same as $\mathcal{A}$, but instead of using $\mathcal{A'}$ as a sub-algorithm, it uses $\mathcal{B'}$, which is sufficient to solve $\Pi$, but not to solve the $PSPACE$-complete problem.

I think this is the situation you want to describe?

Now I think your confusion comes from assume that because a problem has two different algorithms, that the algorithms must have the same complexity - at least this is what I get from the analogy with the functions.

This isn't true, you can quite happily have an algorithm which solves a problem, but is actually far more powerful (i.e. it can solve a much bigger super-problem) and another algorithm that can only solve the smaller problem. These two algorithms don't really say anything about one another (at least without a lot more information).

To stretch the function analogy to its breaking point, the situation is more like $g(x) \leq f(x)+h(x)$ and $g(x) \leq f(x)+ q(x)$. Sort of. But not really.


Counting arrays with Euclidean distance at most 2 from a given binary array

Don't search for a formula – you'll probably never find something so specific. Instead, try to break up the task into smaller units.

Since your arrays are binary,
$$(A_i-B_i)^2 = \begin{cases}0 &\text{if }A_i=B_i\\ 1&\text{if }A_i\neq B_i\,.\end{cases}$$

So $\sqrt{\sum(A_i-B_i)^2}\leq 2$ if, and only if there are at most four values of $i$ such that $A_i\neq B_i$.  So you just need to compute the number of ways that $B$ could have zero, one, two, three or four different entries from $A$ (or, more simply, the number of ways that it could have five or six different entries, and subtract that from the total possible values of $B$). This calculation is high-school combinatorics. Note that, because the arrays are binary, there's only one value of $B_i$ that's the same as $A_i$ and only one that's different.


Why is the size of the search space 2057 in the 8-queen puzzle?

According to Peter Norvig in 2007, it comes from "... writing a program and counting the states."

For the $n$-queens problem, it is not too hard to show that $(n!)^{(1/3)}$ is a lower bound on the size of state space. This can be calculated by considering the maximum number of squares in each column that might be threatened by queens from previous columns. For $n=8$, this evaluates to $34.29$.


Regular Expression for {W | W contains an even number of As and an odd number of Bs, but doesn't contains AB}

Here's one possible solution:

(In fact, the words $b,bb,ba,baa,bab$ show that at least five states are needed, so this is the unique minimal DFA.)


How to print all pairs of ID numbers such that the corresponding people don't belong to the same socieities

Firstly $\Pi_{i_1, i_2}(\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1, s)}People\times \rho_{c_2(i_2, s)}People)})$ gives all possible permutations of ID pairs in the form $(a, b)$ with $a\leq b$.

By $\Pi_{i_1, i_2}(\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1, s)}People\bowtie \rho_{c_2(i_2, s)}People)}$, we can gain all pairs of people who attend a same society.

So the answer is

$$\Pi_{i_1, i_2}\Big(\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1,s)}People\times\rho_{c_2(i_2, s)}People)}-\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1, s)}People\bowtie \rho_{c_2(i_2, s)}People)}\Big)$$


How to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages

We typically think of instances to problems as being in some format. There are several ways to think of this. Consider for example $A_{TM}$, in which the input is a pair $\langle M,w \rangle$. The three most obvious are:

Every input string can be decoded into an input pair $\langle M,w \rangle$.
Inputs not of the form $\langle M,w \rangle$ don't belong to the language.
We think of $A_{TM}$ as a promise problem: inputs $\langle M,w \rangle$ where $M$ accepts $w$ are Yes instances, inputs $\langle M,w \rangle$ where $M$ doesn't accept $w$ are No instances, and we don't care about other inputs.

If you take complementation, here is what you get under each interpretation:

$\overline{A_{TM}}$ consists of all inputs strings which, when decoded to $\langle M,w \rangle$, are such that $M$ doesn't accept $w$.
$\overline{A_{TM}}$ consists of inputs not of the form $\langle M,w \rangle$, and of those of the form $\langle M,w \rangle$ such that $M$ doesn't accept $w$.
$\overline{A_{TM}}$ is the promise problem corresponding to option 1.

While these different interpretations look different, in practice the difference is very slight, given that it is easy to recognize that the input is of the correct format. For example, given interpretation 2, consider the following two languages: $\overline{A_{TM}}$, and $\widetilde{A_{TM}}$, the language of all pairs $\langle M,w \rangle$ such that $M$ doesn't accept $w$. These two languages differ in malformed inputs, that is, outputs not of the form $\langle M,w \rangle$. Since such inputs are easy to detect, we have an algorithm for $\overline{A_{TM}}$ iff we have one for $\widetilde{A_{TM}}$, and furthermore, the complexity of both algorithms is very similar.

For this reason, we typically ignore such issues, and implicitly work under the "promise problem" interpretation: the input is assumed to be of the form $\langle M,w \rangle$. Purists can think of the first interpretation instead, which from this point of view behaves identically.

More generally, whatever interpretation you choose, you still formally have to describe what encoding is used for $\langle M,w \rangle$. We typically don't bother, since all reasonable interpretations are inter-reducible, and so don't change the computability or complexity of the problem. That said, the difference between weak NP-hardness and strong NP-hardness lies exactly in which input representation is being used.


There are no "rules", you make the rules yourself. The rule used in class has the property that the numbers appear in the same order in both expressions. The rule is also pretty natural:

$$ T(\alpha \circ \beta) = T(\alpha) T(\beta) \circ $$

Here $\alpha$ is an infix expression, $T(\alpha)$ is the translation of $\alpha$, and $\circ$ is a binary operation. The corresponding rule for unary expressions is $T(\circ \alpha) = T(\alpha) \circ$, and there is also a deparenthesizing rule, $T((\alpha)) = T(\alpha)$. If you apply these rules to the expression $4 + (5 * 6)$ you will get $4 \; 5 \; 6 * + $.

Keeping the order is important for operations which are not commutative, such as subtraction and division; that's assuming on the convention that $3 \; 2 \; - = 1$ and so on, rather than the other way around.


Two addresses point to the same data - is the data then stored 2 times in the cache?

To answer the question: The read addresses are always rounded down to the next cache line address, then it will be looked up, whether an cache entry already matches this address.

In case yes: Then the address will just be ignored. Nothing further happens.

In case no: Then the data corresponding to the address will be load into the cache.


Sum of unique integers to cnf constraint

Here's a strategy for solving Kakuro with a SAT solver.

Make a nine variables for each cell, each variable indicating whether that cell contains $1$, $2$, etc.
Add a exactly-one-out-nine constraint for the variables of each cell. You can do this naively in 37 clauses by adding a clause that at least one of the nine must be true ($x_1 \vee x_2 \vee \dots \vee x_9$) and 36 clauses that no pair of them may be true at the same time ($(\neg x_1 \vee \neg x_2) \wedge (\neg x_1 \vee \neg x_3) \wedge \dots \wedge (\neg x_8 \vee \neg x_9)$).
For each row/column in the puzzle add an at-most-one-out-of-k constraint in the manner above for all the variables encoding ones, twos, threes, etc in that row or column to ensure each row/column uses unique numbers.
For each row/column make a new set of variables $q_1, q_2, \dots $ that encode "contains $1$, contains $2$, etc". As an example, if a row contains cells $a, b, c, d$ then "contains $2$" would be $(\neg q_2 \vee a_2 \vee b_2 \vee c_2 \vee d_2)$ and $(q_2 \vee \neg a_2) \wedge \dots \wedge (q_2 \vee \neg d_2)$.
Now for each row/column, take the target sum and find all partitions using unique parts smaller than or equal to nine of it, excluding order, using exactly the right amount of parts that fit in the row/column. This may sound like a lot, but this is at worst 11 unique partitions for digits 1-9. Then for each partition introduce a new variable $p$. Suppose our target is $14$ and our partition is $14 = 8 + 3 +2 +1$. Then we add clauses $p \vee q_9 \vee \neg q_8 \vee q_7 \vee q_6 \vee q_5 \vee q_4 \vee \neg q_3 \vee \neg q_2 \vee \neg q_1$ and $(\neg p \vee \neg q_9) \wedge (\neg p \vee q_8) \wedge (\neg p \vee \neg q_7) \wedge (\neg p \vee \neg q_6) \wedge (\neg p \vee \neg q_5) \wedge\\(\neg p \vee \neg q_4) \wedge (\neg p \vee q_3) \wedge (\neg p \vee q_2) \wedge (\neg p \vee q_1)$

You get the idea. The variable $p$ is now an indicator variable for the combination $q_8, q_3, q_2, q_1$  being true. It may not be necessary to also include the negated terms for $q_9, q_7, q_6, q_5, q_4$, but it may speed up (or slow down) the SAT solver. Experiment with it.
Finally for all partitions variables $p_k$ of a row/column add a single clause $p_1 \vee p_2 \vee \dots \vee p_k$ indicating at least one of the partitions must hold.


Your question makes a category error. Your problem is an enumeration problem ("List all the things with property X") but NP is a class of decision problems ("Does the input have property X?").

In any case, there is an obvious deterministic polynomial time algorithm for your problem. Just check each character of each string against $L$. If $L$ is fixed, this runs in linear time; if it's a part of the input, it runs in quadratic time.


If f(n) = Ω(n) and g(n) = O(f(n)), what do we know about g?

Knowing that $f(n)=\Omega(n)$ and $g(n)=O(f(n))$ doesn't tell you anything about $g(n)$. For all we know, $f(n)$ could be $2^{(2^{(2^n)})}$ and then $g(n)$ could be almost any function. All we know is it is upper bounded by some function, which might grow arbitrarily fast. It's akin to saying "up to 50% off or more".